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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:algoks:loesungss15 [18.07.2016 21:43] – Yannikpruefungen:bachelor:algoks:loesungss15 [27.07.2017 15:25] – 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 
 **c)** **c)**
 /A/_2 * /A^-1/_2 = 8 * 1 = 8 \\ /A/_2 * /A^-1/_2 = 8 * 1 = 8 \\
Zeile 60: Zeile 63:
 **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 |                                  | 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 168:
      
  **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 188:
 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 209:
  
 **b)**\\ **b)**\\
-       |  6 | +       |  4 | 
-  x = | -4 | +  x = | -2 | 
-       | -4 |+       | -2 |
                
 ==== Aufgabe 8 (Programmierung: Polynominterpolation) ==== ==== Aufgabe 8 (Programmierung: Polynominterpolation) ====
 **a)** \\ **a)** \\
 +  // Wir bauen eine Vandermondematrix.
 +  
 +  uint32 c = controlPoints.size();
 +  Matrix m = new Matrix(c,c);
 +  for(int i = 0; i<c; i++){
 +    uint32 x = controlPoints[i].x;
 +    for(int k = 0; k<c; i++){
 +      m(i,k) = mul;
 +      mul*=mul;
 +    }
 +  }
 +  return m;
 **b)** \\ **b)** \\
 +  // pensi, preisi ist doch alles das selbe...
  
-**c)** +  uint32 c = controlPoints.size(); 
 +  Matrix b = new Matrix(c,1); 
 +  for(int i = 0; i<c; i++){ 
 +    b(i,0) = controlPoints[i].y; 
 +  } 
 +  return b; 
 +**c)** \\ 
 +  uint32 c = controlPoints.size(); 
 +  std::vector<float> n; 
 +   
 +  // 4 -> Stammfunktion 4x^1, 4x -> 2x^2 also alter Wert/(i+1) wenn i bei 0 anfaengt 
 +   
 +  for(int i = 0; i<c; i++){ 
 +    n.pushBack(f/i+1); 
 +  } 
 +   
 +  //Monom Kurve die die Ableitung repraesentiert 
 +   
 +  MonomCurve tmp = new MonomCurve(n); 
 +  return tmp.evaluateAt(b) - tmp.evaluateAt(a); 
 +  
 ==== Aufgabe 9 (Bezier-Kurven) ==== ==== Aufgabe 9 (Bezier-Kurven) ====
 **a)**\\ **a)**\\
Zeile 175: Zeile 272:
  
 **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)**\\