Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » 1. Komplexität   (Übersicht)

Dies ist eine alte Version des Dokuments!


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, …)
  • Sobel-Filter: (… 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

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)

:pruefungen:bachelor:algoks:algoks_loesung_ss2009_7ab.jpg

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 P_00 = D0(0);     //Alternativ C0(0);
     vec3 P_10 = C1(0);     //Alternativ D0(1)
     vec3 P_01 = D1(0);     //Alternativ C0(1);
     vec3 P_11 = C1(1);     //Alternativ D1(1)

     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)*P_00 + (1-s)*t*P_01 + s*(1-t)*P_10 + s*t*P_11;

     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