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

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:algoks:loesungss12 [06.02.2014 12:14] – Dawodopruefungen: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 ist+wobei x_3 und x_4 beliebig wählbar sind
  
 ==== Aufgabe 3 - SVD ==== ==== Aufgabe 3 - SVD ====
Zeile 47: Zeile 48:
 <code> <code>
     |  1/3  -2/3  2/3 |     |  1/3  -2/3  2/3 |
-U = | -1/3   1/3  2/3 | +U = | -2/3   1/3  2/3 | 
-    |  1/3   2/3  1/3 |+    |  2/3   2/3  1/3 |
   
     | 2  0   0  |     | 2  0   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::evaluateAt(float s, float t) {
 + 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;
 +}
 </code> </code>
  
Zeile 138: Zeile 147:
  
 <code cpp> <code cpp>
 +float CoonsPatch::evaluateDerivativeS(float s, float t) {
 + 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;
 +}
 </code> </code>
- 
-**c)** 
- 
-<code cpp> 
-</code> 
- 
  
 ==== Aufgabe 7 - Programmierung: Nichtlineare Optimierung ==== ==== Aufgabe 7 - Programmierung: Nichtlineare Optimierung ====
Zeile 151: Zeile 162:
  
 <code cpp> <code cpp>
 +double optimizer::optimize(double x0, double y0, const unsigned int maxIter) const {
 + double x = x0;
 + double y = y0;
 +
 + for(int k = 0; k < maxIter; k++) {
 + double sx, sy;
 +
 + searchDirection(x, y, sx, sy);
 +
 + double t = lineSearch(x, y, sx, sy);
 +
 + x = x + t * sx;
 + y = y + t * sy;
 +
 + if(Math.sqrt(sx * sx + sy * sy) < m_gradientEpsilon)
 + break;
 + }
 +
 + return m_targetFunction.f(x, y);
 +}
 </code> </code>
  
Zeile 156: Zeile 187:
  
 <code cpp> <code cpp>
 +double optimize::lineSearch(const double x, const double y, const double dx, const double dy) const {
 + double line, fct;
 + double t = m_tMax;
 +
 + do {
 + double gx, gy;
 + m_targetFunction.gradf(x, y, gx, gy);
 +
 + double tmp = dx * gx + dy * gy;
 + line = m_targetFunction.f(x, y) + t * m_c1 * tmp;
 +
 + fct = m_targetFunction.f(x + t * dx, y + t * dy);
 +
 + t = t * m_reductionFactor;
 + } while(line > fct);
 +
 + return t;
 +}
 </code> </code>
  
Zeile 161: Zeile 210:
  
 <code cpp> <code cpp>
 +void gradient_ascent_optimizer::searchDirection(double x, const double y, double& dx, double& dy) const {
 + m_targetFunction.gradf(x, y, dx, dy);
 +
 + dx = -dx;
 + dy = -dy;
 +}
 +</code>
 +
 +**d)**
 +
 +<code cpp>
 +void newton_optimizer::searchDirection(const double x, const double y, double& dx, double& dy) const {
 + double h11, h12, h21, h22, gx, gy;
 + m_targetFunction.inverseHessian(x, y, h11, h12, h21, h22);
 + m_targetFunction.gradf(x, y, gx, gy);
 +
 + dx = h11 * gx + h12 * gy;
 + dy = h21 * gx + h22 * gy;
 +
 + if(dx < 0 || dy < 0) {
 + dx *= -1;
 + dy *= -1;
 + }
 +}
 </code> </code>
  
Zeile 167: Zeile 240:
 **a)** **a)**
  
-...+{{:pruefungen:bachelor:algoks:algoks_12sose_a8a.png|}}
  
 **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)**