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.

Link zu der Vergleichsansicht

Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:algoks:loesungws11 [07.07.2012 11:37] – angelegt 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://fsi.informatik.uni-erlangen.de/forum/thread/9408-Klausur-Februar-2012]] Gesamte Klausur 
 + 
 +===== Lösungsversuch ===== 
 + 
 +==== 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)** 
 + 
 +<code> 
 +|0  0  0  0  0| 
 +|0  4  0 -2  0| 
 +|0  0  3  8  0| 
 +|0  0  7  0  4| 
 +</code> 
 + 
 +==== 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: 1, 1/2, 1/3 \\ 
 +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: 1/(1/3) = 3 
 + 
 +**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)** 
 + 
 +<code> 
 +|   0     0    0    0| 
 +|-1/2  -1/2  1/2  1/2| 
 +|   0     0    0    0| 
 +</code> 
 + 
 +==== Aufgabe 6 - Programmierung: LU-Zerlegung ==== 
 + 
 +**a)** 
 + 
 +<code cpp> 
 +void Solver::decomposeLU(const Matrix& m, Matrix& l, Matrix& u) {  
 + 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; 
 + } 
 + } 
 +} 
 +</code> 
 + 
 +**b)** 
 + 
 +<code cpp> 
 +void Solver::solveSystem(const Matrix& m, const Matrix& b, Matrix& x) { 
 + int d = m.getHeight(); 
 + Matrix u(d, d); 
 + Matrix l(d, d); 
 + Matrix y(d, 1); 
 + decomposeLU(m, l, u); 
 + forwardSubstitution(l, b, y); 
 + backwardSubstitution(u, y, x); 
 +} 
 +</code> 
 + 
 +**c)** 
 + 
 +<code cpp> 
 +float Solver::calcDeterminant(const Matrix& m) { 
 + int d = m.getHeight(); 
 + Matrix u(d, d); 
 + Matrix l(d, d); 
 + decomposeLU(m, l, u); 
 +  
 + float res = 1.0f; 
 + for(int i = 0; i < d; i++) { 
 + res *= u(i,i); 
 + } 
 + 
 + return res;  
 +} 
 +</code> 
 + 
 + 
 +==== Aufgabe 7 - Programmierung: Bildbearbeitung ==== 
 + 
 +**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,c) = 0.0f; 
 + else 
 + result = -2 * image(r,c) + image(r,c-2) + image(r, c+2); 
 + } 
 + } 
 +} 
 +</code> 
 + 
 +**b)** 
 + 
 +<code cpp> 
 +void computeLaplacian(const Image& image, Image& result) { 
 + int d = image.getDimensions(); 
 +  
 + Image dX(d); 
 + Image dY(d); 
 +  
 + computeDerivativeXX(image, dX); 
 + computeDerivativeYY(image, dY); 
 +  
 + for(int r = 0; r < d; r++) { 
 + for(int c = 0; c < d; c++) { 
 + result(r, c) = dX(r,c) + dY(r, c); 
 + } 
 + } 
 +} 
 +</code> 
 + 
 +**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: \\ 
 +<code> 
 +Für alle c < 1 gilt: 
 +|x_i+1 - x*| <= c * |x_i - x*| 
 +</code> 
 + 
 +Quadratische Kovergenz: \\ 
 +Potenzordnung p mit der der Fehler kleiner wird: 
 +<code> 
 +Für alle c < 1 gilt: 
 +|x_i+1 - x*| <= c * |x_i - x*|² 
 +</code> 
 + 
 +==== Aufgabe 9 - Interpolation ==== 
 + 
 +**a)** 
 + 
 +<code> 
 +       { -x + 1    für  1 <= x < 3 
 +L(x) = { 2x - 8    für  3 <= x < 5 
 +       { -2x + 12  für  5 <= x < 7 
 +</code> 
 + 
 +**b)** 
 + 
 +Interpolation: Graph verläuft exakt durch die Werte der Stützpunkte. \\ 
 +Approximation: Graph nähert sich den Werten der Stützpunkte an, verläuft aber nicht zwingend durch sie. 
 + 
 +**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
  
-Werte:          [3, 1, 5, 6, -2, -1]; \\ 
-Spaltenindex: [1, 3, 1, 3,  1,  2]; \\ 
-Zeilenindex:   [0, 0, 2, 2,  4,  6]; \\