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 Überarbeitung | ||
pruefungen:bachelor:algoks:loesungss15 [19.07.2016 23:53] – Yannik | pruefungen:bachelor:algoks:loesungss15 [01.08.2017 13:48] (aktuell) – Marcel[Inf] | ||
---|---|---|---|
Zeile 49: | Zeile 49: | ||
| 1 -1 -1 1 | | 0 0 0 1 | | | 1 -1 -1 1 | | 0 0 0 1 | | ||
| | ||
- | ==== Aufgabe 3 (Singulaerwertzerlegung) ==== | + | ==== Aufgabe 3 (Singulärwertzerlegung) ==== |
**a)** | **a)** | ||
* V^T: Drehung von x | * V^T: Drehung von x | ||
* Sigma: Streckung / Stauchung von y | * Sigma: Streckung / Stauchung von y | ||
* U: Drehung von z | * U: Drehung von z | ||
- | **b)**\\ \\ | + | |
+ | **b)** | ||
+ | Die Singulärwerte sind die Quadratwurzeln der Eigenwerte von A^T*A bzw. A*A^T. | ||
+ | |||
+ | Sei A^T A = E_1 D_1 E_1^T und A A^T = E_2 D_2 E_2^T. Dann gilt: U = E_2, V = E_1. | ||
**c)** | **c)** | ||
/A/_2 * /A^-1/_2 = 8 * 1 = 8 \\ | /A/_2 * /A^-1/_2 = 8 * 1 = 8 \\ | ||
Zeile 60: | Zeile 65: | ||
**d)** | **d)** | ||
* im(A) = 1/5 * [(3, 0, 4, 0)^T, (0, -3, 0, -4)^T, (-4, 0, -3, 0)^T, (0, -4, 0, -3)^T] | * im(A) = 1/5 * [(3, 0, 4, 0)^T, (0, -3, 0, -4)^T, (-4, 0, -3, 0)^T, (0, -4, 0, -3)^T] | ||
- | * ker(A) = (-2, -4, -2, 1)^T | + | * ker(A) = {0} (der triviale Nullraum) |
**e)** | **e)** | ||
- | | 12 -6 -3 -6 | | + | | 3 | |
- | | + | | 0 | |
- | 8 * 1/5 * (3, 0, 4, 0)^T * 1/5 *(4, -2, -1, -2) = 8/25 * | 16 -8 -4 -8 | | + | 8 * 1/5 * | 4 | * 1/5 * (4, -2, -1, -2) = 8/25 * | 16 -8 -4 -8 | |
- | | + | | 0 | |
==== Aufgabe 4 (Programmierung: | ==== Aufgabe 4 (Programmierung: | ||
Zeile 74: | Zeile 79: | ||
m_pointcloud = pc; | m_pointcloud = pc; | ||
} | } | ||
- | **b)** | ||
- | // in C++ NULL == 0 | ||
- | min = NULL; | ||
- | min = NULL; | ||
- | for(auto a : pc){ | + | **b)** |
- | | + | void MedianCut:: |
- | | + | min = new Point2d(pc[0]); |
- | | + | max = new Point2d(pc[0]); |
- | | + | |
- | + | | |
- | if(a.x < min.x) | + | |
- | | + | |
- | if(a.y < min.y) | + | if(a.y < min.y) |
- | min.y = a.y; | + | min.y = a.y; |
- | if(a.x > max.x) | + | if(a.x > max.x) |
- | max.x = a.x; | + | max.x = a.x; |
- | if(a.y > max.y) | + | if(a.y > max.y) |
- | max.y = a.y; | + | max.y = a.y; |
+ | } | ||
} | } | ||
+ | |||
**c)** | **c)** | ||
+ | Point2d MedianCut:: | ||
+ | Points2d result; | ||
+ | for(auto &a : pointcloud){ | ||
+ | result += a; | ||
+ | } | ||
+ | | ||
+ | result /= pointcloud.size(); | ||
+ | return result; | ||
+ | } | ||
+ | |||
**d)** | **d)** | ||
+ | std:: | ||
+ | std:: | ||
+ | MedianCutRecursion(m_cloudpoint, | ||
+ | return result; | ||
+ | } | ||
+ | |||
**e)** | **e)** | ||
+ | void MedianCut:: | ||
+ | if (subpointcloud.empty()) return; | ||
+ | std:: | ||
+ | | ||
+ | if(sc.size() == 1 || cCuts >= nCuts) { | ||
+ | result.push_back(GetRepresentative(sc)); | ||
+ | return; | ||
+ | } | ||
+ | | ||
+ | Point2d min, max; | ||
+ | ComputeBoundingBox(sc, | ||
+ | | ||
+ | if(max.x - min.x >= max.y - min.y) | ||
+ | SortPointCloudAlongXAxis(sc); | ||
+ | else | ||
+ | SortPointCloudAlongYAxis(sc); | ||
+ | | ||
+ | std::size_t const half = sc.size() / 2; | ||
+ | std:: | ||
+ | std:: | ||
+ | | ||
+ | MedianCutRecursion(left, | ||
+ | MedianCutRecursion(right, | ||
+ | } | ||
==== Aufgabe 5 (Iterative Loesungsverfahren) ==== | ==== Aufgabe 5 (Iterative Loesungsverfahren) ==== | ||
Zeile 127: | Zeile 170: | ||
| | ||
| | ||
- | * Gauss-Seidel | + | * SOR benoetigt Wurzel-n-mal so viele Iterationen wie Jacobi |
13 | 18 | 23 | 13 | 18 | 23 | ||
Zeile 147: | Zeile 190: | ||
grad(3, 1) = (0, -1)^T | grad(3, 1) = (0, -1)^T | ||
- | x_1 = x_0 - t*grad(3, 1) = (3, 5/4)^T | + | x_1 = x_0 + t*(-grad(3, 1)) = (3, 5/ |
**c)** Newton-Verfahren: | **c)** Newton-Verfahren: | ||
Zeile 168: | Zeile 211: | ||
**b)**\\ | **b)**\\ | ||
- | | + | |
- | x = | -4 | | + | x = | -2 | |
- | | -4 | | + | | -2 | |
==== Aufgabe 8 (Programmierung: | ==== Aufgabe 8 (Programmierung: | ||
Zeile 222: | Zeile 265: | ||
**c)**\\ | **c)**\\ | ||
- | M(1/4) = (2, 1, 27/8)^T (z. B. mithilfe De-Casteljau) | + | M(1/4) = (2, 1, 27/8)^T (z. B. <del>mithilfe De-Casteljau</ |
**d)**\\ | **d)**\\ | ||
- | d_0 = S(0, 0) = C_W(0) = b_0\\ | + | d_0 = S(0, 0) = C_W(0) = (0, 0, 4)\\ |
- | d_3 = d_2 | + | d_3 = S(1, 1) = C_O(1) = (4, 4, 4) |
==== Aufgabe 10 (Multivariate Interpolation) ==== | ==== Aufgabe 10 (Multivariate Interpolation) ==== | ||
**10.1 a)**\\ | **10.1 a)**\\ | ||
- | | + | Reihenfolge: |
- | * (rho = 0 and sigma > 1 and tau > 1) or (rho > 1 and sigma = 0 and tau > 1) or (rho > 1 and sigma > 1 and tau = 0) | + | |
+ | * [(rho = 0 and 0 ≤ | ||
* rho = sigma | * rho = sigma | ||
* not (rho > 0 and sigma > 0 and tau > 0) | * not (rho > 0 and sigma > 0 and tau > 0) | ||
+ | |||
+ | Beim zweiten hätte man auch jeweils eine der ≤ 1 Bedingungen weglassen können, denn diese folgen sowieso durch die Bedingung (rho + sigma + tau = 1). | ||
**10.1 b)**\\ | **10.1 b)**\\ |