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:loesungss15 [20.07.2016 00:32] – Yannik | pruefungen:bachelor:algoks:loesungss15 [28.07.2017 14:49] – 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) = {} |
**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)** | **b)** | ||
- | | + | |
- | min = NULL; | + | min = new Point2d(pc[0]); |
- | min = NULL; | + | max = new Point2d(pc[0]); |
- | + | ||
- | for(auto a : pc){ | + | |
- | | + | |
- | | + | |
- | | + | if(a.y < min.y) |
- | | + | min.y = a.y; |
- | | + | if(a.x > max.x) |
- | + | max.x = a.x; | |
- | if(a.x < min.x) | + | if(a.y > max.y) |
- | | + | max.y = a.y; |
- | if(a.y < min.y) | + | } |
- | min.y = a.y; | + | |
- | if(a.x > max.x) | + | |
- | max.x = a.x; | + | |
- | if(a.y > max.y) | + | |
- | max.y = a.y; | + | |
- | + | ||
} | } | ||
+ | |||
**c)** | **c)** | ||
- | | + | Point2d |
- | result = new Point2d(0,0); | + | Points2d result; |
- | for(auto a : pc){ | + | for(auto |
- | result.x += a.x; | + | result += a; |
- | result.y += a.y; | + | } |
+ | | ||
+ | result | ||
+ | return result; | ||
} | } | ||
- | + | ||
- | result.x /= pc.size(); | + | |
- | result.y /= pc.size(); | + | |
- | return result; | + | |
- | | + | |
**d)** | **d)** | ||
- | MedianCutRecursion(m_cloudpoint, | + | |
+ | std:: | ||
+ | | ||
+ | return result; | ||
+ | } | ||
**e)** | **e)** | ||
- | std:: | + | |
- | if(sc.size()==1){ | + | if (subpointcloud.empty()) return; |
- | result.push_back(sc[0]); | + | |
- | return; | + | |
- | }elseif{ | + | |
- | | + | result.push_back(GetRepresentative(sc)); |
- | | + | return; |
- | } | + | } |
+ | | ||
+ | Point2d min, max; | ||
+ | ComputeBoundingBox(sc, min, max); | ||
+ | | ||
+ | if(max.x - min.x >= max.y - min.y) | ||
+ | SortPointCloudAlongXAxis(sc); | ||
+ | | ||
+ | SortPointCloudAlongYAxis(sc); | ||
| | ||
- | Point2d min; | + | std::size_t const half = sc.size() / 2; |
- | | + | |
- | | + | |
| | ||
- | if(std:: | + | MedianCutRecursion(left, cCuts+1, nCuts, result); |
- | SortPointCloudAlongXAxis(& | + | |
- | else | + | |
- | | + | |
- | + | ||
- | // | + | |
- | sdt:: | + | |
- | sdt:: | + | |
- | for(int i = 0; i< | + | |
- | if(i< | + | |
- | scn1.push_back(sc[i]); | + | |
- | else | + | |
- | scn2.push_back(sc[i]); | + | |
} | } | ||
- | | ||
- | MedianCutRecursion(scn1, | ||
- | MedianCutRecursion(scn2, | ||
- | return; | ||
==== Aufgabe 5 (Iterative Loesungsverfahren) ==== | ==== Aufgabe 5 (Iterative Loesungsverfahren) ==== | ||
Zeile 172: | Zeile 170: | ||
| | ||
| | ||
- | * Gauss-Seidel | + | * SOR benoetigt Wurzel-n-mal so viele Iterationen wie Jacobi |
13 | 18 | 23 | 13 | 18 | 23 | ||
Zeile 192: | 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 213: | Zeile 211: | ||
**b)**\\ | **b)**\\ | ||
- | | + | |
- | x = | -4 | | + | x = | -2 | |
- | | -4 | | + | | -2 | |
==== Aufgabe 8 (Programmierung: | ==== Aufgabe 8 (Programmierung: | ||
Zeile 276: | Zeile 274: | ||
**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)**\\ |