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 **+**:
<code>       /  47     -36   -20  -8  \
  1   |   -36    -18   -45  -18  |
 -- * |   -20    -45   38   -10  |
 63    \  -8     -18   -10  59 / </code>


alternativ **-**:
<code>     /  38   40  -40  -16 \
 1   |  40   20   50   20 |
-- * | -40   50   20  -20 |
70   \ -16   20  -20   62 /</code>

=== b) ===
Mit Householder:
<code>
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 /
        
 </code>

Mit Givens-Rotationen:
<code>

       /  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 /        
 </code>




==== 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) ===
 <code>
1    /  36   27   0 \
-- * |   0    0   0 |
25   \ -48   -36  0 /</code>




==== 6. Interpolation ====

=== a) ===

<code>
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
</code>
Klarstellung: "y = -3 von x=0 bis x=0.5, y=0 ab x=0.5 bis x=1.5 usw..."

=== b) ===
<code>
l(x) =
    3x-3  für 0 <= x < 1
    5x-5  für 1 <= x < 2
    -5x+15  für 2 <= x < 3
</code>

=== 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) ===
{{:pruefungen:bachelor:algoks:algoks_loesung_ss2009_7ab.jpg|:pruefungen:bachelor:algoks:algoks_loesung_ss2009_7ab.jpg}}

=== c) ===

  * C(t) = (3 9)^T

=== d) ===
<code>
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
</code>


==== 8. Coons-Patch ====
<code>
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
}
</code>


==== 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) ===
<code>
    ( 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
</code>

=== b) ===
<code>
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

</code>