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
pruefungen:bachelor:algoks:loesungss15 [19.07.2016 23:54] – Yannikpruefungen: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 |                                  | 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) ====
Zeile 74: Zeile 79:
     m_pointcloud = pc;     m_pointcloud = pc;
   }   }
 +
 **b)** **b)**
-  // in C++ NULL == 0  +  void MedianCut::ComputeBoundingBox(const std::vector<Point2d>& pc, Point2d& min, Point2d& max) { 
-  min = NULL; +    min = new Point2d(pc[0]); 
-  min = NULL; +    max = new Point2d(pc[0]); 
-   +     
-  for(auto a : pc){ +    for(auto &a : pc){ 
-   +      if(a.x < min.x) 
-    if(min == NULL) +       min.x = a.x; 
-      min = new Point2d(a.x,a.y); +      if(a.y < min.y) 
-    if(max == NULL) +        min.y = a.y; 
-      max = new Point2d(a.x,a.y); +      if(a.x > max.x) 
-   +        max.x = a.x; 
-    if(a.x < min.x) +      if(a.y > max.y) 
-     min.x = a.x; +        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 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 129: 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 149: 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 170: Zeile 211:
  
 **b)**\\ **b)**\\
-       |  6 | +       |  4 | 
-  x = | -4 | +  x = | -2 | 
-       | -4 |+       | -2 |
                
 ==== Aufgabe 8 (Programmierung: Polynominterpolation) ==== ==== Aufgabe 8 (Programmierung: Polynominterpolation) ====
Zeile 224: 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</del> viel einfacher: in a) hat man bereits C_W(1/4) und C_O(1/4) berechnet. Zu jedem t interpoliert S linear zwischen den Kurven! D. h. für s=1/2: S(1/2, 1/4) = 1/2 C_W(1/4) + 1/2 C_O(1/4))
  
 **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)**\\
-  * rho > 0 and sigma > 0 and 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)**\\