Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Forendiskussionen (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:algoks:loesungws11 [07.07.2012 11:38] – o.O | pruefungen:bachelor:algoks:loesungws11 [10.07.2016 01:02] (aktuell) – m0kab0 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | Aufgabe 2 Speicherung dünn Besetzer Matrizen (10 Punkte) \\ | + | ===== Forendiskussionen ===== |
- | a) CRS - Format !! \\ | + | * [[https:// |
- | Werte: | + | ===== Lösungsversuch ===== |
- | Spaltenindex: | + | |
- | Zeilenindex: | + | |
- | b) \\ | + | ==== Aufgabe 1 - Komplexität ==== |
+ | **a)** O(n) | ||
+ | |||
+ | **b)** O(n²) | ||
+ | |||
+ | **c)** O(n³) | ||
+ | |||
+ | **d)** O(n²) | ||
+ | |||
+ | **e)** O(n) | ||
+ | |||
+ | **f)** O(n) | ||
+ | |||
+ | **g)** O(n²) | ||
+ | |||
+ | **h)** O(n) | ||
+ | |||
+ | ==== Aufgabe 2 - Speicherung dünn besetzter Matrizen ==== | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | val = 3, 1, 5, 6, -2, -1 \\ | ||
+ | col_idx = 1, 3, 1, 3, 1, 2 \\ | ||
+ | row_ptr = 0, 0, 2, 2, 4, 6 | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | m entspricht der Anzahl der Einträge im row_ptr - 1 \\ | ||
+ | n entspricht mindestens des größten Werts im col_ind + 1 | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | < | ||
+ | |0 0 0 0 0| | ||
+ | |0 4 0 -2 0| | ||
+ | |0 0 3 8 0| | ||
+ | |0 0 7 0 4| | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 3 - Numerische Integration ==== | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | 12 \\ | ||
+ | 1. Trapez: (1,0), (1,5), (3,0), (3,1) \\ | ||
+ | 2. Trapez: (3,0), (3,1), (5,0), (5,5) | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | 10 \\ | ||
+ | 1. Trapez: (1,0), (1,5), (2,0), (2,2) \\ | ||
+ | 2. Trapez: (2,0), (2,2), (3,0), (3,1) \\ | ||
+ | 3. Trapez: (3,0), (3,1), (4,0), (4,2) \\ | ||
+ | 4. Trapez: (4,0), (4,2), (5,0), (5,5) \\ | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | 28/3 | ||
+ | |||
+ | **d)** | ||
+ | |||
+ | 28/3 | ||
+ | |||
+ | ==== Aufgabe 4 - Least-Square Approximation ==== | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | Für Q: \\ | ||
+ | w_00 = 1/2 \\ | ||
+ | w_10 = 1/6 \\ | ||
+ | w_11 = 1/12 \\ | ||
+ | w_01 = 1/4 \\ | ||
+ | |||
+ | Für M: \\ | ||
+ | w_00 = 1/4 \\ | ||
+ | w_10 = 1/4 \\ | ||
+ | w_11 = 1/4 \\ | ||
+ | w_01 = 1/4 \\ | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | w_N = 1/2 \\ | ||
+ | w_S = 1/2 \\ | ||
+ | w_W = 1/2 \\ | ||
+ | w_O = 1/2 \\ | ||
+ | w_NO = -1/4 \\ | ||
+ | w_NW = -1/4 \\ | ||
+ | w_SO = -1/4 \\ | ||
+ | w_SW = -1/4 \\ | ||
+ | |||
+ | ==== Aufgabe 5 - Singulärwertzerlegung ==== | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | Singulärwerte: | ||
+ | Rang: r = 3 \\ | ||
+ | Bild: span{(0, -1, 0)^T, (-1, 0, 0)^T, (0, 0, 1)^T} \\ | ||
+ | Kern: span{(-1/2, 1/2, -1/2, 1/2)^T} \\ | ||
+ | Konditionszahl: | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | U^T * (1, 0, -2)^T = (0, -1, -2)^T \\ | ||
+ | S^~1 * (0, -1, -2)^T = (0, -2, -6, 0)^T \\ | ||
+ | V * (0, -2, -6, 0)^T = (2, -4, -4, 2)^T | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | < | ||
+ | | | ||
+ | |-1/2 -1/2 1/2 1/2| | ||
+ | | | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 6 - Programmierung: | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | <code cpp> | ||
+ | void Solver:: | ||
+ | int d = m.getWidth(); | ||
+ | u = m; | ||
+ | l.setIdentity(); | ||
+ | |||
+ | for(int c = 0; c < d; c++) { | ||
+ | for(int r = c + 1; r < d; r++) { | ||
+ | float factor = u(r,c) / u(c,c); | ||
+ | |||
+ | for(int c2 = c; c < d; c++) { | ||
+ | u(r, c2) = u(r, c2) - u(c, c2) * factor; | ||
+ | } | ||
+ | |||
+ | l(r,c) = factor; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | <code cpp> | ||
+ | void Solver:: | ||
+ | int d = m.getHeight(); | ||
+ | Matrix u(d, d); | ||
+ | Matrix l(d, d); | ||
+ | Matrix y(d, 1); | ||
+ | decomposeLU(m, | ||
+ | forwardSubstitution(l, | ||
+ | backwardSubstitution(u, | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | <code cpp> | ||
+ | float Solver:: | ||
+ | int d = m.getHeight(); | ||
+ | Matrix u(d, d); | ||
+ | Matrix l(d, d); | ||
+ | decomposeLU(m, | ||
+ | |||
+ | float res = 1.0f; | ||
+ | for(int i = 0; i < d; i++) { | ||
+ | res *= u(i,i); | ||
+ | } | ||
+ | |||
+ | return res; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | |||
+ | ==== Aufgabe 7 - Programmierung: | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | <code cpp> | ||
+ | void computeDerivativeXX(const Image& image, Image& result) { | ||
+ | int d = image.getDimension(); | ||
+ | |||
+ | for(int r = 0; r < d; r++) { | ||
+ | for(int c = 0; c < d; c++) { | ||
+ | if(c < 2 || c >= d - 2) | ||
+ | result(r, | ||
+ | else | ||
+ | result = -2 * image(r,c) + image(r, | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | <code cpp> | ||
+ | void computeLaplacian(const Image& image, Image& result) { | ||
+ | int d = image.getDimensions(); | ||
+ | |||
+ | Image dX(d); | ||
+ | Image dY(d); | ||
+ | |||
+ | computeDerivativeXX(image, | ||
+ | computeDerivativeYY(image, | ||
+ | |||
+ | for(int r = 0; r < d; r++) { | ||
+ | for(int c = 0; c < d; c++) { | ||
+ | result(r, | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | ... | ||
+ | |||
+ | ==== Aufgabe 8 - Nichtlineare Optimierung ==== | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | s_0 = (0, -2)^T \\ | ||
+ | t_0 = 1/2 \\ | ||
+ | x_1 = (1, 0)^T | ||
+ | |||
+ | s_1 = (-2, 0)^T \\ | ||
+ | t_1 = 1/4 \\ | ||
+ | x_2 = (1/2, 0)^T | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | s_x = 0, s_y beliebig \\ | ||
+ | z.B.: (0, 1)^T | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | Konvergenzordung: | ||
+ | Die Konvergenzordnung beschreibt, um welchen Grad die Genauigkeit einer Approximation pro Iterationsschirtt zunimmt. | ||
+ | |||
+ | Lineare Kovergenz: \\ | ||
+ | < | ||
+ | Für alle c < 1 gilt: | ||
+ | |x_i+1 - x*| <= c * |x_i - x*| | ||
+ | </ | ||
+ | |||
+ | Quadratische Kovergenz: \\ | ||
+ | Potenzordnung p mit der der Fehler kleiner wird: | ||
+ | < | ||
+ | Für alle c < 1 gilt: | ||
+ | |x_i+1 - x*| <= c * |x_i - x*|² | ||
+ | </ | ||
+ | |||
+ | ==== Aufgabe 9 - Interpolation ==== | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | < | ||
+ | { -x + 1 für 1 <= x < 3 | ||
+ | L(x) = { 2x - 8 für 3 <= x < 5 | ||
+ | { -2x + 12 für 5 <= x < 7 | ||
+ | </ | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | Interpolation: | ||
+ | Approximation: | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | Grad des Polynoms: 5 \\ | ||
+ | Damit: 6 Datenpunkte nötig | ||
+ | |||
+ | **d)** | ||
+ | |||
+ | c_0 = 0 \\ | ||
+ | c_1 = 2/π \\ | ||
+ | c_2 = -8/3π² \\ | ||
+ | c_3 = 16/6π³ \\ | ||
+ | |||
+ | p(x) = 2/π * x - 8/3π² * x (x - π/2) + 16/6π³ * x (x - π/2)(x - 3π/2) | ||
+ | |||
+ | ==== Aufgabe 10 - Bézier-Kurven ==== | ||
+ | |||
+ | **a)** | ||
+ | |||
+ | (55/2, 44)^T | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | ... | ||
+ | |||
+ | **c)** | ||
+ | |||
+ | ... | ||
+ | |||
+ | **d)** | ||
+ | |||
+ | * Bézier-Kurven liegt in der konvexen Hülle | ||
+ | * Variationsreduzierend | ||
+ | * In den Endpunkten tangential an das Kontroll-Polygon | ||
+ | * Geht durch die Endpunkte des Kontroll-Polygons | ||
- | m = Zeilen = (Anzahl der Elemente in Zeilenindex) - 1 \\ | ||
- | n = ? |