Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Forendiskussionen (Übersicht)
Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
Forendiskussionen
Lösungsversuch
Aufgabe 1 - Komplexität
a) O(n²)
b) O(n³)
c) O(n³)
d) O(n²)
e) O(n²)
f) O(n²)
g) O(n²)
h) O(n)
Aufgabe 2 - Baryzentrische Koordinaten
a)
P1: ρ = 0, σ = 0, τ = 1
P2: ρ = 1/2, σ = 0, τ = 1/2
P3: ρ = 1/4, σ = 1/2, τ = 1/4
P4: ρ = 1, σ = 1, τ = -1
b)
Fläche 1:
Fläche oberhalb von der Strecke TS, jedoch ohne die beiden außeren Spitzen bei T und S.
Fläche 2:
Die äußere Spitze von R nach unten.
c)
f_P = 12
d)
f_P = 11
Aufgabe 3 - Falten und Filtern
a)
F1: Nicht separierbar
F2: (1, 2, 1)^T und (-1, 0, 1)
F3: Nicht separierbar
F4: (1, 1, 1)^T und 1/12 (1, 1, 1, 1)
b)
(N-2)² * 5²
c)
(N-2)² * 5 * 2
d)
|0 1 0| |1 -4 1| |0 1 0|
e)
Tiefpass: Glättung
Sobel: Kantendetektion
Aufgabe 4 - QR-Zerlegung
a)
x = (-1, 2, -1, 2)^T
b)
det(A) | = | det(R) |
c)
Q = | -0.6 0.8| | 0.8 0.6| R = | -5 -0.2| | 0 -1.4|
Aufgabe 5 - Nichtlineare Optimierung
a)
s_x = s_y
z.B.: s = (1, 1)^T
b)
t_0 = 1
x_1 = (1, 0)^T
s_1 = (1, 1)^T
t_1 = -3
x_2 = (-2, -3)^T
c)
s_0 = (-4, -2)^T
t_0 = 1/2
x_1 = (-1, 0)^T
d)
|x_i+1 - x*| <= c * |x_i - x*|
Pro Iterationsschritt nimmt der Fehler um einen konstanten Faktor ab.
Aufgabe 6 - Bézier-Kurven
a)
C(1/3) = (6, 5/3)^T
b)
…
c)
…
Aufgabe 7 - Singulärwertzerlegung und PCA
a)
Singulärwerte: 6/4, 3/4, 2/4
Rang: 3
Bildraum: span{1/3(-1, -2, -2)^T, 1/3(-2, 2, -1), 1/3(-2, -1, 2)}
Kern: span{1/2(1, -1, -1, 1)^T}
Konditionszahl: 3
b)
v_1 = (1, 0)^T wobei x_1 beliebig
v_2 = (0, 1)^T wobei x_2 beliebig
Aufgabe 8 - Polynominterpolation
a)
{-1 -1 <= x < 0 k(x) = {2 für 0 <= x < 1.5 {4 1.5 <= x <= 2
b)
l(x) = {3/2x + 1/2 für -1 <= x < 1 {2x 1 <= x <= 2
c)
l_0: 1/6 * (x-1)(x-2)
l_1: -1/2 * (x+1)(x-2)
l_2: 1/3 * (x+1)(x-1)
L(x) = y_0 * l_0(x) + y_1 * l_1(x) + y_2 * l_2(x)
d)
n_0(x) = 1
n_1(x) = x + 1
n_2(x) = (x + 1) * (x - 1)
a_0 = -1
a_1 = 3/2
a_2 = 1/6
Aufgabe 9 - Programmierung: Coons Patches
a)
float CoonsPatch::evaluateAt(float s, float t) { float f_t = (1-s) * m_t0.f(t) + s * m_t1.f(t); float f_s = (1-t) * m_s0.f(s) + t * m_s1.f(s); float f_st = (1-t) * (1-s) * m_t0.f(0) + (1-s) * t * m_s1.f(0) + (1-t) * s * m_t1.f(0) + t * s * m_t1.f(1); return f_s + f_t - f_st; }
b)
float CoonsPatch::evaluateDerivativeS(float s, float t) { float f_t = (-1) * m_t0.f(t) + m_t1.f(t); float f_s = (1-t) * m_s0.d(s) + t * m_s1.d(s); float f_st = (1-t) * (-1) * m_t0.f(0) + (-1) * t * m_s1.f(0) + (1-t) * m_s1.f(0) + t * m_t1.f(1); return f_s + f_t - f_st; }
Aufgabe 10 - Dünnbesetzte Matrizen
a)
CCSMatrix::CCSMatrix(unsigned int height, unsigned int width) { _height = height; _width = width; _nonZeroElements = 0; _values = new float[0]; _rowIndices = new int[0]; _colPtr = new int[width + 1]; }
b)
float CCSMatrix::getEntry(unsigned int i, unsigned int j) { for(int rowP = _colPtr[j]; rowP < _colPtr[j+1]; rowP++) { if(_rowIndices[rowP] == i) return _values[rowP]; } return 0; }
b)
CCSMatrix::CCSMatrix(Matrix& other) { _height = other._height; _width = other._width; _nonZeroElements = other._nonZeroElements; _values = new float[_nonZeroElements]; _rowIndices = new int[_nonZeroElements]; _colPtr = new int[width + 1]; int t = 0; _colPtr[0] = 0; for(int c = 0; c < _width; c++) { for(int r = 0; r < _height; r++) { float elem = other.getEntry(r, c); if(el != 0) { _values[t] = elem; _rowIndives[t] = r; t++; } } _colPtr[c] = t; } }
b)
Matrix Matrix::operator*(CCSMatrix& other) { Matrix result(_height, other._width); for(int r = 0; r < _height; r++) { for(int c = 0; c < other._width; c++) { float sum = 0.0f; for(int rowP = other._colPtr[c]; rowP < other._colPtr[c+1]; rowP++) { float v = other._values[rowP]; sum += v * getEntry(r, other._rowIndices[rowP]); } result.setEntry(r, c, sum); if(sum != 0) { result._nonZeroElements++; } } }