Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Lösungsvorschlag
Inhaltsverzeichnis
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)
Sehr ungenau, aber man sieht das Konzept: https://i.imgur.com/IPK64lC.png
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)