Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Lösungsvorschlag (Übersicht)
Dies ist eine alte Version des Dokuments!
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)
d)
p(x) = -l_0 + 2*l_1 + 4*l_2 = -1/6 * (x^2 -3x +2) -(x^2 -x -2) + 4/3 * (x^2 - 1)
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)
b_0 = (18, 8)^T
b_1 = (10, 0)^T
b_2 = (2, 8)^T
b_3 = (58, 32)^T
c)
d)
- liegt nicht in der konvexen Huelle der Kontrollpunkte
- nicht tangential in den Endpunkten
- nicht variationsreduzierend
e)
Aufgabe 7 (Programmierung: Bilineare Interpolation)
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 > 1, sigma < 0, tau < 0
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)
Wegen d_a(x) = d(x-a) gilt Integral( f(x) * d_a(x-a) dx) = f(a)
d)
Der erste Uebergang leicht nach unten gebogen, dann linear:
(-1/2, 0) → (3/2, 1) → (3/2 + x, 1 + x)
Aufgabe 10 (Hauptkomponentenanalyse)
Aufgabe 11 (Numerische Integration)
a)
2 + 18 = 20
b)
1/8 * ( 0+1 + 1+8 + 8+27 + 27+64) = 136/8 = 17