===== Forendiskussionen =====
* [[https://fsi.informatik.uni-erlangen.de/forum/thread/10559,2-Klausur-23-Juli-2012]] Gesamte Klausur
===== 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)| = 54
**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*| , wobei 0
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_t0.f(1) +
(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_t0.f(1) +
(1-t) * m_t1.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 colP = _colPtr[j]; colP < _colPtr[j+1]; colP++) {
if(_rowIndices[colP] == i)
return _values[colP];
}
return 0;
}
**c)**
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;
_rowIndices[t] = r;
t++;
}
}
_colPtr[c+1] = t;
}
}
**d)**
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 colP = other._colPtr[c]; colP < other._colPtr[c+1]; colP++) {
float v = other._values[colP];
sum += v * getEntry(r, other._rowIndices[colP]);
}
result.setEntry(r, c, sum);
}
}
}