Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Aufgabe 1 - Komplexität   (Ü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:loesungws09 [29.01.2014 20:51] – Dawodopruefungen:bachelor:algoks:loesungws09 [20.07.2016 15:35] (aktuell) – Yannik
Zeile 2: Zeile 2:
 [[https://fsi.informatik.uni-erlangen.de/forum/thread/7529-Klausur-vom-Februar-2010-Loesungsversuch]] [[https://fsi.informatik.uni-erlangen.de/forum/thread/7529-Klausur-vom-Februar-2010-Loesungsversuch]]
  
-==== 1. Komplexität ====+==== Aufgabe 1 - Komplexität ==== 
   * O(n³)   * O(n³)
   * O(n)   * O(n)
Zeile 13: Zeile 14:
  
  
-==== 2. Multiple Choice ====+==== Aufgabe 2 - Multiple Choice ==== 
   * j= Ja   * j= Ja
   * n = Nein   * n = Nein
  
-=== a) ===+**a)** 
 n n j n j n n j n j
  
-=== b) ===+**b)** 
 n n n j n n n n j n
  
-=== c) ===+**c)** 
 n n n n j n n n n j
  
-=== d) ===+**d)** 
 j j n j j j j n j j
  
  
-==== 3. Dünnbesetzte Matrizen ==== +==== Aufgabe 3 - Dünnbesetzte Matrizen ==== 
-=== a) ===+ 
 +**a)** 
 <code> <code>
 0 0 1 0 3 0 0 1 0 3
Zeile 39: Zeile 47:
 </code> </code>
  
 +**b)**
  
-=== b) === 
   * Werte: 3 -1  2 4 -5   * Werte: 3 -1  2 4 -5
   * Zeile:   1  2  3  1  3   * Zeile:   1  2  3  1  3
   * ColPtr: 1  2  2  4  6   * ColPtr: 1  2  2  4  6
  
-==== 4. Lineares Ausgleichsproblem ==== +==== Aufgabe 4 - Lineares Ausgleichsproblem ==== 
-=== a) ===+ 
 +**a)** 
 A^T * A * x = A^T * b A^T * A * x = A^T * b
  
-=== b) ===+**b)** 
   *  m = 5/14   *  m = 5/14
   *   t = 3/14   *   t = 3/14
  
  
-==== 5. 2D Interpolation ==== +==== Aufgabe 5 - 2D Interpolation ==== 
-=== a) ===+ 
 +**a)** 
   * P1 = (9,12)^T   * P1 = (9,12)^T
   * P2 = (10,0)^T   * P2 = (10,0)^T
  
-=== b) ===+**b)** 
   * h1 = rho1*hR + sigma1*hS + tau1*hT = 120   * h1 = rho1*hR + sigma1*hS + tau1*hT = 120
   * h2 = rho2*hR + sigma2*hS + tau2*hT = 80   * h2 = rho2*hR + sigma2*hS + tau2*hT = 80
  
  
-=== c) === +**c)** 
-rho=1/3    sigma = 1/3    tau = 1/3+ 
 +ρ = 1/3 \\ 
 +σ= 1/3 \\ 
 +τ= 1/3 
 + 
 +**d)**
  
-=== d) === 
 Punkt P teilt Dreieck in drei Teil-Dreiecke. Das Verhältnis jedes Teil-Dreiecks (Punkt P und je zwei der anderen ursprünglichen Punkte) zum ganzen Dreieck ergibt jeweils eine baryzentrische Koordinate. Punkt P teilt Dreieck in drei Teil-Dreiecke. Das Verhältnis jedes Teil-Dreiecks (Punkt P und je zwei der anderen ursprünglichen Punkte) zum ganzen Dreieck ergibt jeweils eine baryzentrische Koordinate.
  
-=== e) === +**e)** 
-Bild 1: Gerade durch T und die Mittelsenkrechte der Strecke RS+ 
 +Bild 1: Gerade durch T und die Mittelsenkrechte der Strecke RS \\
 Bild 2: Gerade durch T und S Bild 2: Gerade durch T und S
  
 +**f)**
  
-=== f) === 
 f(P4) = 39 f(P4) = 39
 f(P5) = 57 f(P5) = 57
  
- +==== Aufgabe 6 - Coons-Patches====
-==== 6. Coons-Patches====+
 <code> <code>
                  s                  s
Zeile 89: Zeile 107:
  
 ==== 7. Filtern ==== ==== 7. Filtern ====
-=== a) ===+ 
 +**a)** 
   * F1: 1/2 (1, 0, 1)^T und 1/2 (1, 0, 1)   * F1: 1/2 (1, 0, 1)^T und 1/2 (1, 0, 1)
   * F2: geht nicht   * F2: geht nicht
   * F3: 1/4 (1, 1, 1)^T und 1/3 (1, 1, 1, 1)   * F3: 1/4 (1, 1, 1)^T und 1/3 (1, 1, 1, 1)
  
-=== b) ===+**b)** 
 Geringerer Aufwand Geringerer Aufwand
  
-=== c) ===+**c)** 
 <code> <code>
 x x x x x x x x x x
Zeile 107: Zeile 129:
  
  
-==== 8. Iterative Lösungsverfahren ==== +==== Aufgabe 8 - Iterative Lösungsverfahren ==== 
-=== a) ===+ 
 +**a)** 
   * x1 = 4   * x1 = 4
   * x2 = -5   * x2 = -5
   * x3 = 2   * x3 = 2
  
-=== b) ===+**b)** 
   * x1 = 4   * x1 = 4
   * x2 = -5   * x2 = -5
-  * x3 = 2.25+  * x3 = 9/4 
 + 
 +**c)**
  
-=== c) === 
 Für dünnbesetzte Matrizen besonders gut geeignet. Für dünnbesetzte Matrizen besonders gut geeignet.
  
  
-==== 9. LR- Zerlegung ==== +==== Aufgabe 9 - LR- Zerlegung ==== 
-=== a) ===+ 
 +**a)**
 <code> <code>
 1  0  0  0       2 -1  0  0 1  0  0  0       2 -1  0  0
Zeile 132: Zeile 159:
 </code> </code>
  
-=== b) ===+**b)**
 x = (3/2, 1, -4, 2)^T x = (3/2, 1, -4, 2)^T
  
  
-==== 10. Aitken-Neville ==== +==== Aufgabe 10 - Aitken-Neville ==== 
-=== a) ===+ 
 +**a)** 
 <code cpp> <code cpp>
 NewtonPolynom :: NewtonPolynom(const float *_x, const float *_y, const int _n) NewtonPolynom :: NewtonPolynom(const float *_x, const float *_y, const int _n)
Zeile 168: Zeile 197:
 </code> </code>
  
-=== b) ===+**b)** 
 <code cpp> <code cpp>
 float NewtonPolynom::operator()(const float x0) const float NewtonPolynom::operator()(const float x0) const
Zeile 176: Zeile 206:
  for (int i = n-2; i >= 0; i--)  for (int i = n-2; i >= 0; i--)
  {  {
- result = a[i] + (x0 - x[i]) * result;+ result = a[i] * (x0 - x[i]) + result;
  }  }
  
Zeile 182: Zeile 212:
 } }
 </code> </code>
-