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

--- pruefungen:bachelor:algoks:loesungws11 [07.07.2012 11:39] – o.O
+++ pruefungen:bachelor:algoks:loesungws11 [02.02.2014 12:23] – angelegt Dawodo
@@ Zeile 1: / Zeile 1: @@
-==== 2. Speicherung dünn besetzter Matrizen (10 Punkte) ====
+===== Forendiskussionen =====
+  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9408-Klausur-Februar-2012]] Gesamte Klausur
-a) CRS - Format !! \\
+===== Lösungsversuch =====
-Werte:          [3, 1, 5, 6, -2, -1]; \\
+==== Aufgabe 1 - Komplexität ====
-Spaltenindex: [1, 3, 1, 3,  1,  2]; \\
+**a)** O(n)
-Zeilenindex:   [0, 0, 2, 2,  4,  6]; \\
-b) \\
+**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)**
+\\
+. Trapez: (1,0), (1,5), (3,0), (3,1) \\
+. Trapez: (3,0), (3,1), (5,0), (5,5)
+**b)**
+\\
+. Trapez: (1,0), (1,5), (2,0), (2,2) \\
+. Trapez: (2,0), (2,2), (3,0), (3,1) \\
+. Trapez: (3,0), (3,1), (4,0), (4,2) \\
+. Trapez: (4,0), (4,2), (5,0), (5,5) \\
+**c)**
+/3
+**d)**
+/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
-m = Zeilen = (Anzahl der Elemente in Zeilenindex) - 1 \\
-n = ?