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 [20.07.2016 00:31] – 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) ====
Zeile 74: Zeile 77:
     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)**
-  Points2d result; +  Point2d MedianCut::GetRepresentative(const std::vector<Point2d>& pointcloud) { 
-  result = new Point2d(0,0); +    Points2d result; 
-  for(auto a : pc){ +    for(auto &a : pointcloud){ 
-    result.x += a.x; +      result += a; 
-    result.y += a.y;+    } 
 +     
 +    result /= pointcloud.size(); 
 +    return result;
   }   }
-   +
-  result.x /= pc.size(); +
-  result.y /= pc.size(); +
-  return result; +
-  +
 **d)** **d)**
-  MedianCutRecursion(m_cloudpoint,0,nCuts,&result);+  std::vector<Point2d> MedianCut::ComputeMedianCut(int nCuts) { 
 +    std::vector<Point2d> result; 
 +    MedianCutRecursion(m_cloudpoint, 0, nCuts, result); 
 +    return result; 
 +  } 
 **e)** **e)**
-  std::vector<Point2d> sc = subpointcloud; +  void MedianCut::MedianCutRecursion(std::vector<Point2d> subpointcloud, int cCuts, int nCuts, std::vector<Point2d>& result) { 
-  if(sc.size()==1){ +    if (subpointcloud.empty()) return; 
-    result.push_back(sc[0]); +    std::vector<Point2d> sc = subpointcloud; 
-    return; +     
-  }elseif{ +    if(sc.size() == 1 || cCuts >= nCuts) { 
-    result.push_back(GetRepresentative(&sc)); +      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);
      
-  Point2d min; +    std::size_t const half = sc.size() / 2; 
-  Point2d max; +    std::vector<Color> left(sc.begin(), sc.begin() + half); 
-  ComputeBoundingBox(&subpointcloud,&min,&max);+    std::vector<Color> right(sc.begin() + half, sc.end());
      
-  if(std::abs(max.x - min.x) >= std::abs(max.y-min.y)) +    MedianCutRecursion(left, cCuts+1, nCuts, result); 
-    SortPointCloudAlongXAxis(&sc); +    MedianCutRecursion(right, cCuts+1, nCuts, result);
-  else +
-    SortPointCloudAlongYAxis(&sc); +
-   +
-  // vielleicht hat ein C++ Profi hier ne bessere Idee +
-  sdt::vector<Point2d> scn1(0); +
-  sdt::vector<Point2d> scn1(0); +
-  for(int i = 0; i<sc.size(); i++){ +
-    if(i<sc.size()/2) +
-      scn1.push_back(sc[i]); +
-    else +
-      scn2.push_back(sc[i]);+
   }   }
-   
-  MedianCutRecursion(scn1,cCuts+1,nCuts,result); 
-  MedianCutRecursion(scn2,cCuts+1,nCuts,result); 
-  return; 
  
 ==== Aufgabe 5 (Iterative Loesungsverfahren) ==== ==== Aufgabe 5 (Iterative Loesungsverfahren) ====
Zeile 171: 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 191: 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 212: Zeile 209:
  
 **b)**\\ **b)**\\
-       |  6 | +       |  4 | 
-  x = | -4 | +  x = | -2 | 
-       | -4 |+       | -2 |
                
 ==== Aufgabe 8 (Programmierung: Polynominterpolation) ==== ==== Aufgabe 8 (Programmierung: Polynominterpolation) ====
Zeile 275: Zeile 272:
  
 **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)**\\