FSI-Zimmer: geschlossen
Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Aufgabe 1 - Komplexität (Übersicht)
Dies ist eine alte Version des Dokuments!
Inhaltsverzeichnis
1. Komplexität
- O(n³)
- O(n)
- O(n²)
- O(n³)
- O(n²)
- O(n²)
- O(n)
- O(n³)
2. Multiple Choice
- j= Ja
- n = Nein
a)
n n j n j
b)
n n n j n
c)
n n n n j
d)
j j n j j
3. Dünnbesetzte Matrizen
a)
0 0 1 0 3 4 0 0 2 1 0 0 0 0 0 1 3 2 0 0
b)
- Werte: 3 -1 2 4 -5
- Zeile: 1 2 3 1 3
- ColPtr: 1 2 2 4 6
4. Lineares Ausgleichsproblem
a)
A^T * A * x = A^T * b
b)
- m = 5/14
- t = 3/14
5. 2D Interpolation
a)
- P1 = (9,12)^T
- P2 = (10,0)^T
b)
- h1 = rho1*hR + sigma1*hS + tau1*hT = 120
- h2 = rho2*hR + sigma2*hS + tau2*hT = 80
c)
rho=1/3 sigma = 1/3 tau = 1/3
d)
…
e)
f)
f(P4) = 39 f(P5) = 57
6.
s
F(s,t) = t
s^2*t + s*t^2 - s*t
7. Filtern
a)
- F1: 1/2 (1, 0, 1)^T und 1/2 (1, 0, 1)
- F2: geht nicht
- F3: 1/4 (1, 1, 1)^T und 1/3 (1, 1, 1, 1)
b)
Geringerer Aufwand
c)
x x x x x x 0 5 2 x x 0 4 2 x x 0 5 2 x x x x x x
8. Iterative Lösungsverfahren
a)
- x1 = 4
- x2 = -5
- x3 = 2
b)
- x1 = 4
- x2 = -5
- x3 = 2.25
c)
Für dünnbesetzte matrizen besonders gut geeignet
9. LR- Zerlegung
a)
1 0 0 0 2 -1 0 0 2 1 0 0 0 2 1 0 0 -2 1 0 0 0 1 1 0 0 -2 1 0 0 0 -1 L R
b)
x = (3/2, 1, -4, 2)^T
10. Aitken-Neville
a)
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])
}
//Übernehme Koeffizienten (der immer im höchsten Element ist)
a[k] = y[0];
}
}
b)
float NewtonPolynom::operator()( const float x0 ) const
{
float result = a[n-1];
for (int i = n-2; i > 0; i--)
{
result = a[i] + (x - x[i])*result;
}
return result;
}