===== Forendiskussionen =====
* [[https://fsi.informatik.uni-erlangen.de/forum/thread/9408-Klausur-Februar-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 - Speicherung dünn besetzter Matrizen ====
**a)**
val = 3, 1, 5, 6, -2, -1 \\
col_idx = 1, 3, 1, 3, 1, 2 \\
row_ptr = 0, 0, 2, 2, 4, 6
**b)**
m entspricht der Anzahl der Einträge im row_ptr - 1 \\
n entspricht mindestens des größten Werts im col_ind + 1
**c)**
|0 0 0 0 0|
|0 4 0 -2 0|
|0 0 3 8 0|
|0 0 7 0 4|
==== Aufgabe 3 - Numerische Integration ====
**a)**
12 \\
1. Trapez: (1,0), (1,5), (3,0), (3,1) \\
2. Trapez: (3,0), (3,1), (5,0), (5,5)
**b)**
10 \\
1. Trapez: (1,0), (1,5), (2,0), (2,2) \\
2. Trapez: (2,0), (2,2), (3,0), (3,1) \\
3. Trapez: (3,0), (3,1), (4,0), (4,2) \\
4. Trapez: (4,0), (4,2), (5,0), (5,5) \\
**c)**
28/3
**d)**
28/3
==== Aufgabe 4 - Least-Square Approximation ====
**a)**
Für Q: \\
w_00 = 1/2 \\
w_10 = 1/6 \\
w_11 = 1/12 \\
w_01 = 1/4 \\
Für M: \\
w_00 = 1/4 \\
w_10 = 1/4 \\
w_11 = 1/4 \\
w_01 = 1/4 \\
**b)**
w_N = 1/2 \\
w_S = 1/2 \\
w_W = 1/2 \\
w_O = 1/2 \\
w_NO = -1/4 \\
w_NW = -1/4 \\
w_SO = -1/4 \\
w_SW = -1/4 \\
==== Aufgabe 5 - Singulärwertzerlegung ====
**a)**
Singulärwerte: 1, 1/2, 1/3 \\
Rang: r = 3 \\
Bild: span{(0, -1, 0)^T, (-1, 0, 0)^T, (0, 0, 1)^T} \\
Kern: span{(-1/2, 1/2, -1/2, 1/2)^T} \\
Konditionszahl: 1/(1/3) = 3
**b)**
U^T * (1, 0, -2)^T = (0, -1, -2)^T \\
S^~1 * (0, -1, -2)^T = (0, -2, -6, 0)^T \\
V * (0, -2, -6, 0)^T = (2, -4, -4, 2)^T
**c)**
| 0 0 0 0|
|-1/2 -1/2 1/2 1/2|
| 0 0 0 0|
==== Aufgabe 6 - Programmierung: LU-Zerlegung ====
**a)**
void Solver::decomposeLU(const Matrix& m, Matrix& l, Matrix& u) {
int d = m.getWidth();
u = m;
l.setIdentity();
for(int c = 0; c < d; c++) {
for(int r = c + 1; r < d; r++) {
float factor = u(r,c) / u(c,c);
for(int c2 = c; c < d; c++) {
u(r, c2) = u(r, c2) - u(c, c2) * factor;
}
l(r,c) = factor;
}
}
}
**b)**
void Solver::solveSystem(const Matrix& m, const Matrix& b, Matrix& x) {
int d = m.getHeight();
Matrix u(d, d);
Matrix l(d, d);
Matrix y(d, 1);
decomposeLU(m, l, u);
forwardSubstitution(l, b, y);
backwardSubstitution(u, y, x);
}
**c)**
float Solver::calcDeterminant(const Matrix& m) {
int d = m.getHeight();
Matrix u(d, d);
Matrix l(d, d);
decomposeLU(m, l, u);
float res = 1.0f;
for(int i = 0; i < d; i++) {
res *= u(i,i);
}
return res;
}
==== Aufgabe 7 - Programmierung: Bildbearbeitung ====
**a)**
void computeDerivativeXX(const Image& image, Image& result) {
int d = image.getDimension();
for(int r = 0; r < d; r++) {
for(int c = 0; c < d; c++) {
if(c < 2 || c >= d - 2)
result(r,c) = 0.0f;
else
result = -2 * image(r,c) + image(r,c-2) + image(r, c+2);
}
}
}
**b)**
void computeLaplacian(const Image& image, Image& result) {
int d = image.getDimensions();
Image dX(d);
Image dY(d);
computeDerivativeXX(image, dX);
computeDerivativeYY(image, dY);
for(int r = 0; r < d; r++) {
for(int c = 0; c < d; c++) {
result(r, c) = dX(r,c) + dY(r, c);
}
}
}
**c)**
...
==== Aufgabe 8 - Nichtlineare Optimierung ====
**a)**
s_0 = (0, -2)^T \\
t_0 = 1/2 \\
x_1 = (1, 0)^T
s_1 = (-2, 0)^T \\
t_1 = 1/4 \\
x_2 = (1/2, 0)^T
**b)**
s_x = 0, s_y beliebig \\
z.B.: (0, 1)^T
**c)**
Konvergenzordung: \\
Die Konvergenzordnung beschreibt, um welchen Grad die Genauigkeit einer Approximation pro Iterationsschirtt zunimmt.
Lineare Kovergenz: \\
Für alle c < 1 gilt:
|x_i+1 - x*| <= c * |x_i - x*|
Quadratische Kovergenz: \\
Potenzordnung p mit der der Fehler kleiner wird:
Für alle c < 1 gilt:
|x_i+1 - x*| <= c * |x_i - x*|²
==== Aufgabe 9 - Interpolation ====
**a)**
{ -x + 1 für 1 <= x < 3
L(x) = { 2x - 8 für 3 <= x < 5
{ -2x + 12 für 5 <= x < 7
**b)**
Interpolation: Graph verläuft exakt durch die Werte der Stützpunkte. \\
Approximation: Graph nähert sich den Werten der Stützpunkte an, verläuft aber nicht zwingend durch sie.
**c)**
Grad des Polynoms: 5 \\
Damit: 6 Datenpunkte nötig
**d)**
c_0 = 0 \\
c_1 = 2/π \\
c_2 = -8/3π² \\
c_3 = 16/6π³ \\
p(x) = 2/π * x - 8/3π² * x (x - π/2) + 16/6π³ * x (x - π/2)(x - 3π/2)
==== Aufgabe 10 - Bézier-Kurven ====
**a)**
(55/2, 44)^T
**b)**
...
**c)**
...
**d)**
* Bézier-Kurven liegt in der konvexen Hülle
* Variationsreduzierend
* In den Endpunkten tangential an das Kontroll-Polygon
* Geht durch die Endpunkte des Kontroll-Polygons