Inhaltsverzeichnis
Quelle: https://fsi.informatik.uni-erlangen.de/forum/thread/7523-LOeSUNGSVERSUCH-Klausur-Juli-2009
1. Komplexität
- O(n²)
- O(n)
- O(n*log(n))
- O(n)
- O(n²)
- O(n^1,5)
- O(n)
- O(m²n²)
2. Multiple Choice (0 = nein, 1 = ja)
- a) 001001
- b) 00110
- c) 10110
- d) 01111
3. Filtern
a)
- Tiefpassfilter: (… 0, 0, 0, 0, 0, 0, 0, 0, 0 …)
- Sobel-Filter: (… 1, -2, 1, 1, -2, 1, 1, -2, 1, …)
b)
- Sobel: Kantendetektion
- Tiefpass: Glättung
c)
- F1 : 1/3(1, 1, 1)^T und 1/3 (1, 1 ,1)
- F2 : nicht separierbar
- F3 : 1/3 (1, 2, 1)^T und 1/2(1 2 2 1)
4. QR-Zerlegung
a)
wähle +:
/ 47 -36 -20 -8 \ 1 | -36 -18 -45 -18 | -- * | -20 -45 38 -10 | 63 \ -8 -18 -10 59 /
alternativ -:
/ 38 40 -40 -16 \ 1 | 40 20 50 20 | -- * | -40 50 20 -20 | 70 \ -16 20 -20 62 /
b)
Mit Householder:
u_2 = (0, 2, -1)^T
/ 1 0 0 \
H_2 = | 0 -0,6 0,8 | = Q^T = (symmetrie) = Q
\ 0 0,8 0,6 /
/ 1 0 3 \
R = | 0 -1,25 0,2 |
\ 0 0 -3,6 /
Mit Givens-Rotationen:
/ 1 0 0 \
J_32 = | 0 0,6 -0,8 | = Q^T
\ 0 0,8 0,6 /
=>
/ 1 0 0 \
Q = | 0 0,6 0,8 |
\ 0 -0,8 0,6 /
/ 1 0 3 \
R = | 0 1,25 -0,2 |
\ 0 0 -3,6 /
5. Singulärwertzerlegung
a)
- Singulärwerte: 3, 2, 1
- Rang = 3
- Bild = span { 1/5 (3, 0, -4)^T, 1/5 (0, 5, 0)^T, 1/5 (-4, 0, -3)^T }
- Kern = {} (leere Menge)
- Konditionszahl zur Euklidischen Norm von A: 3 * 1 = 3
b)
x= (4 3 0)^T
c)
1 / 36 27 0 \ -- * | 0 0 0 | 25 \ -48 -36 0 /
6. Interpolation
a)
n(x) =
-3 für 0 <= x < 0,5
0 für 0,5 <= x < 1,5
5 für 1,5 <= x < 2,5
0 für 2,5 <= x < 3
Klarstellung: „y = -3 von x=0 bis x=0.5, y=0 ab x=0.5 bis x=1.5 usw…“
b)
l(x) =
3x-3 für 0 <= x < 1
5x-5 für 1 <= x < 2
-5x+15 für 2 <= x < 3
c)
- c0 = -3
- c1 = 3
- c2 = 1
- c3 = -2
⇒ a(x) = -3 + 3*x + 1*x*(x-1) -2*x(x-1)(x-2)
d)
Mit zentral symmetrischer Differenz (da Schritweite gleichverteilt)
- m1 = 4
- m2 = 0
e)
Es muss ersichtlich sein, dass die beiden Steigungen aus d) stimmen und die Kurve glatt ist (da C1 stetig)
7. Interpolation
a, b)
c)
- C(t) = (3 9)^T
d)
f(1) = (1 1)^T = g(0) = g_0 f'(1) = (2 0)^T = g'(0) g'(0) = 2*(g_1- (1 1)^T) (2 0)^T = 2*(g_1- (1 1)^T) => g_1 = (2 1)^T
8. Coons-Patch
vec3 evalCoonsPatch(double s, double t)
{
vec3 F_s = (1-t)*C0(s) + t*C1(s);
vec3 F_t = (1-s)*D0(t) + s*D1(t);
vec3 F_st = (1-s)*(1-t)*C0(0) + (1-s)*t*C1(0) + s*(1-t)*C0(1) + s*t*C1(1);
return F_s + F_t - F_st
}
9. Numerische Integration
…
10. Nichtlineare Optimierung
Vorsicht: Die Angabe verwendet eine alte Formel für die Berechnung von tau, die annimmt, dass die Suchrichtung s der positive Gradient ist. Seit einiger Zeit wird als Suchrichtung der negative Gradient gelehrt, daher muss man das Vorzeichen von tau umkehren.
a)
( 4 1 ) A = ( 1 1 ) b = (0 -1)^T s0 = - grad(Q)(0, 0) = (0, 2) tau0 = -1/2 x1 = ( 0 1 )^T s1 = -( 2 0)T = ( -2 0 )^T tau1 = -1/8 x2 = ( -1/4 1)T
b)
g0 = b + A*x0 = (0 -1)^T s0 = -g0 = (0 1)^T alpha0 = 1 x1 = (0 1)^T g1 = (1 0)^T beta0 = 1 s1 = (-1 1)^T alpha1= 1/3 x2 = (-1/3 4/3)^T