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:loesungss12 [06.02.2014 12:14] – Dawodo | pruefungen:bachelor:algoks:loesungss12 [20.07.2016 12:38] (aktuell) – Erich | ||
---|---|---|---|
Zeile 8: | Zeile 8: | ||
**a)** O(n²) | **a)** O(n²) | ||
- | **b)** O(n) | + | **b)** O(k²n) |
**c)** O(n) | **c)** O(n) | ||
Zeile 38: | Zeile 38: | ||
**b)** | **b)** | ||
+ | Rx = Q_t*b\\ | ||
x = (-11/3, -1, 0, 0)^T \\ | x = (-11/3, -1, 0, 0)^T \\ | ||
- | wobei x_4 beliebig wählbar | + | wobei x_3 und x_4 beliebig wählbar |
==== Aufgabe 3 - SVD ==== | ==== Aufgabe 3 - SVD ==== | ||
Zeile 47: | Zeile 48: | ||
< | < | ||
| 1/3 -2/3 2/3 | | | 1/3 -2/3 2/3 | | ||
- | U = | -1/3 | + | U = | -2/3 |
- | | | + | | |
| 2 0 | | 2 0 | ||
Zeile 95: | Zeile 96: | ||
α = 0, 0 <= β <= 1, 0 <= γ <= 1 | α = 0, 0 <= β <= 1, 0 <= γ <= 1 | ||
- | **d)** | + | **e)** |
f_M = 1 | f_M = 1 | ||
- | **d)** | + | **f)** |
- | ... | + | Einfach die 4 Eckpunkte miteinander verbinden, dass oben ein verzerrtes Viereck entsteht. |
==== Aufgabe 5 - Bézier-Kurven ==== | ==== Aufgabe 5 - Bézier-Kurven ==== | ||
Zeile 133: | Zeile 134: | ||
<code cpp> | <code cpp> | ||
+ | float CoonsPatch:: | ||
+ | float f_t = (1-s) * m_t0.f(t) + s * m_t1.f(t); | ||
+ | float f_s = (1-t) * m_s0.f(s) + t * m_s1.f(s); | ||
+ | float f_st = (1-t) * (1-s) * m_t0.f(0) + (1-s) * t * m_t0.f(1) | ||
+ | + (1-t) * s * m_t1.f(0) + t * s * m_t1.f(1); | ||
+ | |||
+ | return f_s + f_t - f_st; | ||
+ | } | ||
</ | </ | ||
Zeile 138: | Zeile 147: | ||
<code cpp> | <code cpp> | ||
+ | float CoonsPatch:: | ||
+ | float f_t = (-1) * m_t0.f(t) + 1* m_t1.f(t); | ||
+ | float f_s = (1-t) * m_s0.d(s) + t * m_s1.d(s); | ||
+ | float f_st = (1-t) * (-1) * m_t0.f(0) + (-1) * t * m_t0.f(1) + | ||
+ | (1-t) * m_t1.f(0) + t * m_t1.f(1); | ||
+ | |||
+ | return f_s + f_t - f_st; | ||
+ | } | ||
</ | </ | ||
- | |||
- | **c)** | ||
- | |||
- | <code cpp> | ||
- | </ | ||
- | |||
==== Aufgabe 7 - Programmierung: | ==== Aufgabe 7 - Programmierung: | ||
Zeile 151: | Zeile 162: | ||
<code cpp> | <code cpp> | ||
+ | double optimizer:: | ||
+ | double x = x0; | ||
+ | double y = y0; | ||
+ | |||
+ | for(int k = 0; k < maxIter; k++) { | ||
+ | double sx, sy; | ||
+ | |||
+ | searchDirection(x, | ||
+ | |||
+ | double t = lineSearch(x, | ||
+ | |||
+ | x = x + t * sx; | ||
+ | y = y + t * sy; | ||
+ | |||
+ | if(Math.sqrt(sx * sx + sy * sy) < m_gradientEpsilon) | ||
+ | break; | ||
+ | } | ||
+ | |||
+ | return m_targetFunction.f(x, | ||
+ | } | ||
</ | </ | ||
Zeile 156: | Zeile 187: | ||
<code cpp> | <code cpp> | ||
+ | double optimize:: | ||
+ | double line, fct; | ||
+ | double t = m_tMax; | ||
+ | |||
+ | do { | ||
+ | double gx, gy; | ||
+ | m_targetFunction.gradf(x, | ||
+ | |||
+ | double tmp = dx * gx + dy * gy; | ||
+ | line = m_targetFunction.f(x, | ||
+ | |||
+ | fct = m_targetFunction.f(x + t * dx, y + t * dy); | ||
+ | |||
+ | t = t * m_reductionFactor; | ||
+ | } while(line > fct); | ||
+ | |||
+ | return t; | ||
+ | } | ||
</ | </ | ||
Zeile 161: | Zeile 210: | ||
<code cpp> | <code cpp> | ||
+ | void gradient_ascent_optimizer:: | ||
+ | m_targetFunction.gradf(x, | ||
+ | |||
+ | dx = -dx; | ||
+ | dy = -dy; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **d)** | ||
+ | |||
+ | <code cpp> | ||
+ | void newton_optimizer:: | ||
+ | double h11, h12, h21, h22, gx, gy; | ||
+ | m_targetFunction.inverseHessian(x, | ||
+ | m_targetFunction.gradf(x, | ||
+ | |||
+ | dx = h11 * gx + h12 * gy; | ||
+ | dy = h21 * gx + h22 * gy; | ||
+ | |||
+ | if(dx < 0 || dy < 0) { | ||
+ | dx *= -1; | ||
+ | dy *= -1; | ||
+ | } | ||
+ | } | ||
</ | </ | ||
Zeile 167: | Zeile 240: | ||
**a)** | **a)** | ||
- | ... | + | {{: |
**b)** | **b)** | ||
Zeile 211: | Zeile 284: | ||
**c)** | **c)** | ||
- | x_1+1 = (-3/16, -1/4)^T | + | x_1+1 = (3/16, 1/4)^T |
**d)** | **d)** |