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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:algoks:loesungws09 [25.07.2012 22:19] – *Link zum FSI-Thread konsti4upruefungen:bachelor:algoks:loesungws09 [13.07.2016 12:05] – Kommaschreibweise in Bruch geändert. dom
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+
  
-=== 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 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+
  
-=== 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 88: 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 106: 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 131: 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>
-