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 [25.07.2012 15:00] – *Überschrift 6. Coons-Patches konsti4upruefungen:bachelor:algoks:loesungws09 [20.07.2016 15:35] (aktuell) – Yannik
Zeile 1: Zeile 1:
-==== 1. Komplexität ====+Link zum FSI-Thread: 
 +[[https://fsi.informatik.uni-erlangen.de/forum/thread/7529-Klausur-vom-Februar-2010-Loesungsversuch]] 
 + 
 +==== Aufgabe 1 - Komplexität ==== 
   * O(n³)   * O(n³)
   * O(n)   * O(n)
Zeile 10: 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+
  
-=== c) === +n n n j n
- n n n n j+
  
-=== d) === +**c)**
- j j n j j+
  
 +n n n n j
 +
 +**d)**
 +
 +j j n j j
 +
 +
 +==== Aufgabe 3 - Dünnbesetzte Matrizen ====
 +
 +**a)**
  
-==== 3. Dünnbesetzte Matrizen ==== 
-=== a) === 
 <code> <code>
 0 0 1 0 3 0 0 1 0 3
Zeile 36: 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+
  
-=== d) === +ρ = 1/3 \\ 
-...+σ= 1/3 \\ 
 +τ= 1/3
  
-=== e) === +**d)**
-[[http://img6.imagebanana.com/img/jyltkz6k/5e.jpg]]+
  
 +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)**
 +
 +Bild 1: Gerade durch T und die Mittelsenkrechte der Strecke RS \\
 +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 85: 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 103: 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)** 
 + 
 +Für dünnbesetzte Matrizen besonders gut geeignet.
  
-=== c) === 
-Für dünnbesetzte matrizen besonders gut geeignet 
  
 +==== Aufgabe 9 - LR- Zerlegung ====
  
-==== 9. LR- Zerlegung ==== +**a)**
-=== a) ===+
 <code> <code>
 1  0  0  0       2 -1  0  0 1  0  0  0       2 -1  0  0
Zeile 128: 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) === + 
-<code> +**a)** 
-NewtonPolynom :: NewtonPolynom(const float *_x , const float *_y, const int _n )+ 
 +<code cpp> 
 +NewtonPolynom :: NewtonPolynom(const float *_x, const float *_y, const int _n)
 { {
-    n = _n; + n = _n;
-    +
-    x = new float[n]; +
-    y = new float[n]; +
-    a = new float[n]; +
-    +
-    for ( int i = 0; i < n; i++) { +
-        x[i] = _x[i] ; +
-        y[i] = _y[i] ; +
-    } +
-    +
-    +
-    //Erster Koeffizient +
-    a[0] = y[0]; +
-    +
-        +
-    for ( int k = 1; k < n; i++) +
-    {        +
-        for (int i = 0; i < n-k+1; i++) +
-        { +
-            y[i] = (y[i] - y[i+1]) / (x[i]  - x[i+k])            +
-        }            +
-        +
-        //Übernehme Koeffizienten (der immer im höchsten Element ist) +
-        a[k] = y[0]; +
-    }+
  
 + x = new float[n];
 + y = new float[n];
 + a = new float[n];
 +
 + for (int i = 0; i < n; i++) {
 + x[i] = _x[i] ;
 + y[i] = _y[i] ;
 + }
 +
 + // Erster Koeffizient
 + a[0] = y[0];
 +
 + for (int row = 1; row < n; row++)
 + {
 + for (int col = 0; col < n-col; col++)
 + {
 + y[col] = (y[col+1] - y[col]) / (x[row+col] - x[col]);         
 + }
 +
 + // Übernehme Koeffizienten (der immer im höchsten Element ist)
 + a[row] = y[0];
 + }
 } }
 </code> </code>
  
-=== b) === +**b)** 
-<code> + 
-float NewtonPolynom::operator()( const float x0 ) const+<code cpp> 
 +float NewtonPolynom::operator()(const float x0) const
 { {
-    float result = a[n-1]; + float result = a[n-1]; 
-    + 
-    for (int i = n-2; i > 0; i--) + for (int i = n-2; i >= 0; i--) 
-    { + { 
-        result = a[i] + (x - x[i])*result; + result = a[i] * (x0 - x[i]) + result; 
-    } + } 
-    + 
-    return result;+ return result;
 } }
 </code> </code>
-