Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Lösungsvorschlag   (Übersicht)

Lösungsvorschlag

Aufgabe 1 (Theoriefragen)

a)

  • O(n^2)
  • O(n^3)
  • O(n)
  • p=1
  • O(h^2)
  • n+1
  • 1
  • 3

b)

| 1 | 1.25 | 1.5 | 1.75 | 2 | 2.5 | 3 | 3.5 | 4 | 5 | 6 | 7 | 8 |

Aufgabe 2 (Lineare Gleichungssysteme)

2.1 a)

    |  1  0  0 0 |         | 2 -1 1  0 |
    | -2  1  0 0 |         | 0  2 0  2 |
L = |  2 -1  1 0 |     R = | 0  0 1 -2 |
    |  0  0 -2 1 |         | 0  0 0  2 |
    

2.1 b)

    |  2 |   | sqrt(36) |   | -4 |
    | -4 |   |    0     |   | -4 |
L = |  4 | - |    0     | = |  4 |
    |  0 |   |    0     |   |  0 |
    

2.2 c)

  • Doppelte Gitterweite ⇒ 4-fache Anzahl Iterationen
  • Doppelte Fehlertoleranz ⇒ linear mehr Iterationen
 154 |  207 |  260
 620 |  830 | 1040
2480 | 3320 | 4160

2.2 d)

  • Gauss-Seidel benoetigt halb so viele Iterationen wie Jacobi
  77 |  103 |  130
 310 |  415 |  520
1240 | 1660 | 2080

2.2 e)

  • Gauss-Seidel benoetigt Wurzel-n-mal so viele Iterationen wie Jacobi
13 | 18 | 23
25 | 35 | 45
50 | 70 | 90
     

Aufgabe 3 (Programmierung: LR-Zerlegung)

Aufgabe 4 (Speicherung duennbesetzter Matrizen)

a)

val = [5, 1, 3, -6, -2, -1]
col_ind = [2, 4, 2, 4, 1, 3]
row_ptr = [1, 1, 3, 3, 5, 7]

b)
Im CRS-Format sind gegeben: val, col_ind, row_ptr Von Null verschiedene

  • Zeilen: Anzahl versch. Elemente in row_ptr - 1. Alternativ: for i in range(0, len(row_ptr)-1): if (row_ptr[i] != row_ptr[i+1]) row_count++;
  • Spalten: Anzahl versch. Elemente in col_ind
  • Elemente: letztes Element row_ptr - 1. Alternativ: len(val) = len(col_ind)

c)

bB_1 = 0 (kein Wert in 1. Spalte)
bB_2 = 4*b_2 = 4
bB_3 = 3*b_3 + 7*b_4 = 7
bB_4 = (-2)*b_2 + 8*b_3 = -2

=> bB = (0, 4, 7, -2)

Aufgabe 5 (Polynominterpolation)

a)

        | -1   fuer x in [-1, 0)
 l(x) = {  2   fuer x in [0, 1.5)
        |  4   fuer x in [1.5, 2]
        

b)

        | 3x/2 + 1/2   fuer x in [-1, 1)
 l(x) = { 2x           fuer x in [1, 2]

c)
l_0 = [(x-1)(x-2)/(-1-1)(-1-2)] = 1/6 * (x^2 -3x +2)
l_1 = [(x+1)(x-2)/(1+1)(1-2)] = -1/2 * (x^2 -x -2)
l_2 = [(x+1)(x-1)/(2+1)(2-1)] = 1/3 * (x^2 - 1)

Ich glaube nicht, dass das Ausmultiplizieren gefordert war. Dies wird in neueren Klausuren auch explizit angemerkt.

d)
-1, 2 und 4 (das sind genau die y_i)

e)
n_0 = 1
n_1 = (x+1)
n_2 = (x+1)(x-1)

f)
z. B. Aitken-Neville:

|x_i  y_i
|
|-1   -1   
|          \  3/2
| 1    2   /         \ 1/6
|          \   2     /
| 2    4   /

⇒ p(x) = -1 + 3/2*(x+1) + 1/6*(x+1)(x-1)

Aufgabe 6 (Bezier-Kurven)

a)

| 8|
|16| \ | 6|
| 0| / |14| \ | 5| 
| 8| \ | 2| / |12| \ | 5|
| 8| / | 6| \ | 5| / |11|
| 0| \ |14| / | 8|
|32| / |14|
|56|

b)
Affine Transformation \Phi(x, y) = (y, x)^T + (-2, 0)^T.

b_0 = (14, 8)^T b_1 = (6, 0)^T b_2 = (-2, 8)^T b_3 = (54, 32)^T

c)

d)

  • liegt nicht in der konvexen Huelle der Kontrollpunkte
  • nicht tangential in den Endpunkten
  • nicht variationsreduzierend

e)

Man skizziere sich drei Punkte und führe den De-Casteljau-Algorithmus aus. Zuerst interpoliert man d_0 und d_1: 1/2 (d_0 + d_1)
Dann d_1 und d_2: 1/2 (d_1 + d_2)
Nun interpoliert man diese beiden Punkte und gelangt zu:
1/2 (1/2 (d_0 + d_1)) + 1/2 (1/2 (d_1 + d_2)) = 1/4 d_0 + 1/2 d_1 + 1/4 d_2

Aufgabe 7 (Programmierung: Bilineare Interpolation)

def getInterpolatedPixel(img, u, v): # img ist np array
  xf = v * (img.shape[1] - 1)
  yf = u * 8img.shape[0] - 1)
  p00 = (floor(xf), floor(yf))
  p01 = (ceil(xf), floor(yf))
  p10 = (floor(xf), ceil(yf))
  p11 = (ceil(xf), ceil(yf))
  w0 = xf - p00[0]
  w1 = yf - p11[1]
  return w1 * ((1-w0) * img[p00] + w0 * img[p01]) + (1-w1) * ((1-w0) * img[p10] + w0 * img[p11]))

Aufgabe 8 (Baryzentrische Koordinaten)

a)

  • P_0: [0, 1, 0]
  • P_1: [1/2, 0, 1/2]
  • P_2: [2/3, 1/3, 0]
  • P_3: [2/5, 1/5, 2/5]

b)

  • alpha = 5/8
  • beta = 2/8
  • gamma = 1/8

c)
U = 0.5

d)

  • rho < 0, sigma > 0, tau > 0, rho + sigma + tau = 1
  • rho > 1, sigma < 0, tau < 0, rho + sigma + tau = 1. (rho > 1 ist redundant, da dies aus rho = 1 - sigma - tau > 1 folgt.)

Aufgabe 9 (Faltung)

a)
[…, 0, 1, 2, 7/3, 2, 1, 2/3, 1, 2, 7/3, 2, 1, 2/3, 1, …]

b)
1. nein, Reihenfolge egal 2. h = h_1 * h_2

c)
(f * d_a)(x) = \int f(y) d_a(x-y) dy = f(x-a), denn x - y = a ⇔ y = x - a, und an dieser Stelle wird f 'evaluiert'. Steht auch so in den Folien.

d)
Der erste Uebergang leicht nach unten gebogen (quadratisch), dann linear: (-1/2, 0) → (3/2, 1) → (3/2 + x, 1 + x)

Quadratisch kommt daher, dass man in das erste Dreieck hineinläuft. Die 'Slices' des Dreiecks, die man immer hinzufügt, werden größer und größer, sozusagen 1 + 2 + 3 + 4, was bekanntermaßen O(n^2) ist.
Es tritt dann bei x=0,5 vollkommene Überlappung auf. Nun haben wir ein Trapez, das mit größer werdendem x immer weiter nach rechts geschoben wird und oben durch f begrenzt wird. Formel für den Flächeninhalt eines Trapezes ist h * (a + c)/2. Die Höhe, oder hier die Breite des Trapezes, ändern wir nicht, sie bleibt konstant 1. Lediglich a und c ändern wir, diese sind aber gerade die Bilder unter f. Da diese immer 'gleichzeitig' nach rechts geschoben werden, ändert sich a + c auch nur linear. Der Flächeninhalt ist also linear in x. Nun braucht man nur zwei Punkte sich im Kopf kurz zu errechnen und zeichnet sich seine Gerade durch.

e)
Unterscheide nach x < -2, -2 ⇐ x ⇐ 2, 2 < x < \infty.
(f*g_2)(x) =
0 falls x < -2, 1/8 (x+2)^2 falls 2 ⇐ x ⇐ 2,
x falls 2 < x < \infty (also sonst)

Aufgabe 10 (Hauptkomponentenanalyse)

a)

Schwerpunkt S = (1, 1)^T
A := (p_0 - S | p_1 - S | … | p_4 - S)

Dann ist C = 1/(5 - 1) * AA^T = 1/2 {{9, 0}, {0, 4}}.

b)

det(B-\lambda Id) = (1-\lambda)(7-\lambda) // bitte a^2-b^2 = (a-b)(a+b) nutzen :)

Eig(1) = span{(1, 1)^T}\\
Eig(7) = span{(-1, 1)^T}

Aufgabe 11 (Numerische Integration)

a)
2 + 18 = 20

b)
1/8 * ( 0+1 + 1+8 + 8+27 + 27+64) = 136/8 = 17

c)

T_f(1/2) = 20    \
                  v
T_f(1/4) = 17  ---> T_f^1 (1/4) = (4T_f(1/4) - T_f(1/2))/3 = 16 (was übrigens der exakte Wert des Integrals ist)

d)

(1 - 0) * (1/6 * f(0) + 4/6 * f((0 + 1)/2) + 1/6 * f(1)) = 16

Hier muss der exakte Wert rauskommen, denn die Simpson-Regel angwandt auf ein kubisches Polynom ist immer exakt (folgt aus der einen Fehlerabschätzung, welche max{|f^(4)(x)|} erwähnt, was ja 0 bei kubischen Polynomen ist!).

e)
O(h^2)

f)
O(h^4)