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.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungLetzte ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:algoks:loesungws09 [25.07.2012 15:00] – *Überschrift 6. Coons-Patches konsti4u | pruefungen:bachelor:algoks:loesungws09 [13.07.2016 12:05] – Kommaschreibweise in Bruch geändert. dom | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ==== 1. Komplexität ==== | + | Link zum FSI-Thread: |
+ | [[https:// | ||
+ | |||
+ | ==== Aufgabe | ||
* O(n³) | * O(n³) | ||
* O(n) | * O(n) | ||
Zeile 10: | Zeile 14: | ||
- | ==== 2. Multiple Choice ==== | + | ==== Aufgabe |
* 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 |
- | | + | |
- | === 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) === | ||
< | < | ||
0 0 1 0 3 | 0 0 1 0 3 | ||
Zeile 36: | Zeile 47: | ||
</ | </ | ||
+ | **b)** | ||
- | === b) === | ||
* Werte: 3 -1 2 4 -5 | * Werte: 3 -1 2 4 -5 | ||
* Zeile: | * Zeile: | ||
* ColPtr: 1 2 2 4 6 | * ColPtr: 1 2 2 4 6 | ||
- | ==== 4. Lineares Ausgleichsproblem ==== | + | ==== Aufgabe |
- | === 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 |
- | === 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/ | + | |
- | === d) === | + | ρ = 1/3 \\ |
- | ... | + | σ= 1/3 \\ |
+ | τ= 1/3 | ||
- | === e) === | + | **d)** |
- | [[http:// | + | |
+ | 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==== | + | |
< | < | ||
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)** |
< | < | ||
x x x x x | x x x x x | ||
Zeile 103: | Zeile 129: | ||
- | ==== 8. Iterative Lösungsverfahren ==== | + | ==== Aufgabe |
- | === 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) === | + | |
< | < | ||
1 0 0 0 2 -1 0 0 | 1 0 0 0 2 -1 0 0 | ||
Zeile 128: | Zeile 159: | ||
</ | </ | ||
- | === b) === | + | **b)** |
- | x = (3/2, 1, -4, 2)^T | + | x = (3/2, 1, -4, 2)^T |
- | ==== 10. Aitken-Neville ==== | + | ==== Aufgabe |
- | === a) === | + | |
- | < | + | **a)** |
- | NewtonPolynom :: NewtonPolynom(const float *_x , const float *_y, const int _n ) | + | |
+ | < | ||
+ | NewtonPolynom :: NewtonPolynom(const float *_x, const float *_y, const int _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]) | + | |
- | } | + | |
- | + | ||
- | // | + | |
- | 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]; | ||
+ | } | ||
} | } | ||
</ | </ | ||
- | === b) === | + | **b)** |
- | < | + | |
- | float NewtonPolynom:: | + | < |
+ | float NewtonPolynom:: | ||
{ | { | ||
- | | + | 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; |
} | } | ||
</ | </ | ||
- |