Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Lösungsvorschlag   (Ü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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:algoks:loesungss15 [18.07.2016 22:36] – Yannikpruefungen:bachelor:algoks:loesungss15 [28.07.2017 14:55] – 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 |                                  | 12 -6 -3 -6 | 
-                                             |  0  0  0  0 | +            | 0 |                                  |  0  0  0  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  0  0  0 |+            | 0 |                                  |  0  0  0  0 |
                                                                                            
 ==== Aufgabe 4 (Programmierung: Median Cut) ==== ==== Aufgabe 4 (Programmierung: Median Cut) ====
 **a)** **a)**
 +  MedianCut::MedianCut(std::vector<Point2d>& pc):m_pointcloud(pc)
 +Oder:
 +  MedianCut::MedianCut(std::vector<Point2d>& pc){
 +    m_pointcloud = pc;
 +  }
 +
 **b)** **b)**
 +  void MedianCut::ComputeBoundingBox(const std::vector<Point2d>& pc, Point2d& min, Point2d& max) {
 +    min = new Point2d(pc[0]);
 +    max = new Point2d(pc[0]);
 +    
 +    for(auto &a : pc){
 +      if(a.x < min.x)
 +       min.x = a.x;
 +      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 MedianCut::GetRepresentative(const std::vector<Point2d>& pointcloud) {
 +    Points2d result;
 +    for(auto &a : pointcloud){
 +      result += a;
 +    }
 +    
 +    result /= pointcloud.size();
 +    return result;
 +  }
 +
 **d)** **d)**
 +  std::vector<Point2d> MedianCut::ComputeMedianCut(int nCuts) {
 +    std::vector<Point2d> result;
 +    MedianCutRecursion(m_cloudpoint, 0, nCuts, result);
 +    return result;
 +  }
 +
 **e)** **e)**
 +  void MedianCut::MedianCutRecursion(std::vector<Point2d> subpointcloud, int cCuts, int nCuts, std::vector<Point2d>& result) {
 +    if (subpointcloud.empty()) return;
 +    std::vector<Point2d> sc = subpointcloud;
 +    
 +    if(sc.size() == 1 || cCuts >= nCuts) {
 +      result.push_back(GetRepresentative(sc));
 +      return;
 +    }
 +    
 +    Point2d min, max;
 +    ComputeBoundingBox(sc, min, max);
 +    
 +    if(max.x - min.x >= max.y - min.y)
 +      SortPointCloudAlongXAxis(sc);
 +    else
 +      SortPointCloudAlongYAxis(sc);
 +  
 +    std::size_t const half = sc.size() / 2;
 +    std::vector<Color> left(sc.begin(), sc.begin() + half);
 +    std::vector<Color> right(sc.begin() + half, sc.end());
 +  
 +    MedianCutRecursion(left, cCuts+1, nCuts, result);
 +    MedianCutRecursion(right, cCuts+1, nCuts, result);
 +  }
  
 ==== Aufgabe 5 (Iterative Loesungsverfahren) ==== ==== Aufgabe 5 (Iterative Loesungsverfahren) ====
Zeile 103: Zeile 170:
      
  **e)**\\  **e)**\\
-  * Gauss-Seidel benoetigt Wurzel-n-mal so viele Iterationen wie Jacobi+  * SOR benoetigt Wurzel-n-mal so viele Iterationen wie Jacobi
  
   13 | 18 | 23   13 | 18 | 23
Zeile 123: 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/4)^T (wobei x_0 hier (x0,y0))
  
 **c)** Newton-Verfahren:\\ **c)** Newton-Verfahren:\\
Zeile 144: Zeile 211:
  
 **b)**\\ **b)**\\
-       |  6 | +       |  4 | 
-  x = | -4 | +  x = | -2 | 
-       | -4 |+       | -2 |
                
 ==== Aufgabe 8 (Programmierung: Polynominterpolation) ==== ==== Aufgabe 8 (Programmierung: Polynominterpolation) ====
Zeile 207: Zeile 274:
  
 **10.1 a)**\\ **10.1 a)**\\
-  * rho > 0, sigma > 0, tau > 0 +Reihenfolge: links oben, rechts oben, links unten, rechts unten. 
-  * (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 sigma > 0 and tau > 0) and (rho + sigma + tau = 1) 
 +  * [(rho = 0 and 0 ≤  sigma, tau ≤  1) or (sigma = 0 and 0 ≤  rho, tau ≤  1) or (tau = 0 and 0 ≤  rho, sigma ≤  1)] and (rho + sigma + tau = 1)
   * 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)**\\