Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Lösungsvorschlag
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:algoks:loesungws15 [13.02.2017 13:44] – Danyel | pruefungen:bachelor:algoks:loesungws15 [02.08.2017 10:04] – Marcel[Inf] | ||
---|---|---|---|
Zeile 55: | Zeile 55: | ||
**a)**\\ | **a)**\\ | ||
val = [5, 1, 3, -6, -2, -1] | val = [5, 1, 3, -6, -2, -1] | ||
- | | + | |
row_ptr = [1, 1, 3, 3, 5, 7] | row_ptr = [1, 1, 3, 3, 5, 7] | ||
**b)**\\ | **b)**\\ | ||
+ | Im CRS-Format sind gegeben: val, col_ind, row_ptr | ||
Von Null verschiedene | Von Null verschiedene | ||
- | * Zeilen: Anzahl versch. Elemente in col_ptr | + | * Zeilen: Anzahl versch. Elemente in row_ptr |
- | * Spalten: Anzahl versch. Elemente in col_idx | + | * Spalten: Anzahl versch. Elemente in col_ind |
- | * Elemente: letztes Element row_ptr - 1 | + | * Elemente: letztes Element row_ptr - 1. Alternativ: len(val) = len(col_ind) |
**c)**\\ | **c)**\\ | ||
Zeile 86: | Zeile 87: | ||
l_1 = [(x+1)(x-2)/ | l_1 = [(x+1)(x-2)/ | ||
l_2 = [(x+1)(x-1)/ | l_2 = [(x+1)(x-1)/ | ||
+ | |||
+ | Ich glaube nicht, dass das Ausmultiplizieren gefordert war. Dies wird in neueren Klausuren auch explizit angemerkt. | ||
**d)**\\ | **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) | + | -1, 2 und 4 (das sind genau die y_i) |
**e)**\\ | **e)**\\ | ||
Zeile 119: | Zeile 122: | ||
| | ||
| | ||
- | b_0 = (18, 8)^T | + | Affine Transformation \Phi(x, y) = (y, x)^T + (-2, 0)^T. |
- | b_1 = (10, 0)^T | + | |
- | b_2 = (2, 8)^T | + | b_0 = (14, 8)^T |
- | b_3 = (58, 32)^T | + | b_1 = (6, 0)^T |
+ | b_2 = (-2, 8)^T | ||
+ | b_3 = (54, 32)^T | ||
**c)**\\ | **c)**\\ | ||
Zeile 133: | Zeile 138: | ||
**e)**\\ | **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: | ==== Aufgabe 7 (Programmierung: | ||
Zeile 152: | Zeile 162: | ||
**d)**\\ | **d)**\\ | ||
- | * rho < 0, sigma > 0, tau > 0 | + | * rho < 0, sigma > 0, tau > 0, rho + sigma + tau = 1 |
- | * rho > 1, sigma < 0, tau < 0 | + | * 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) ==== | ==== Aufgabe 9 (Faltung) ==== | ||
Zeile 164: | Zeile 174: | ||
**c)**\\ | **c)**\\ | ||
- | Wegen d_a(x) = d(x-a) gilt Integral( | + | (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 ' |
**d)**\\ | **d)**\\ | ||
- | Der erste Uebergang leicht nach unten gebogen, dann linear: | + | Der erste Uebergang leicht nach unten gebogen |
(-1/2, 0) -> (3/2, 1) -> (3/2 + x, 1 + x) | (-1/2, 0) -> (3/2, 1) -> (3/2 + x, 1 + x) | ||
+ | |||
+ | Quadratisch kommt daher, dass man in das erste Dreieck hineinläuft. Die ' | ||
+ | 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 ' | ||
+ | |||
+ | **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) ==== | ==== Aufgabe 10 (Hauptkomponentenanalyse) ==== | ||
+ | |||
+ | 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}} | ||
==== Aufgabe 11 (Numerische Integration) ==== | ==== Aufgabe 11 (Numerische Integration) ==== | ||
Zeile 179: | Zeile 204: | ||
**b)**\\ | **b)**\\ | ||
1/8 * ( 0+1 + 1+8 + 8+27 + 27+64) = 136/8 = 17 | 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)**\\ | ||
+ | < | ||
+ | |||
+ | Hier muss der exakte Wert rauskommen, denn die Simpson-Regel angwandt auf ein kubisches Polynom ist immer exakt (folgt aus der einen Fehlerabschätzung, | ||
+ | |||
+ | **e)**\\ | ||
+ | O(h^2) | ||
+ | |||
+ | **f)**\\ | ||
+ | O(h^4) |