• https://fsi.informatik.uni-erlangen.de/forum/thread/9408-Klausur-Februar-2012 Gesamte Klausur

a) O(n)

b) O(n²)

c) O(n³)

d) O(n²)

e) O(n)

f) O(n)

g) O(n²)

h) O(n)

a)

val = 3, 1, 5, 6, -2, -1
col_idx = 1, 3, 1, 3, 1, 2
row_ptr = 0, 0, 2, 2, 4, 6

b)

m entspricht der Anzahl der Einträge im row_ptr - 1
n entspricht mindestens des größten Werts im col_ind + 1

c)

|0  0  0  0  0|
|0  4  0 -2  0|
|0  0  3  8  0|
|0  0  7  0  4|

a)

12
1. Trapez: (1,0), (1,5), (3,0), (3,1)
2. Trapez: (3,0), (3,1), (5,0), (5,5)

b)

10
1. Trapez: (1,0), (1,5), (2,0), (2,2)
2. Trapez: (2,0), (2,2), (3,0), (3,1)
3. Trapez: (3,0), (3,1), (4,0), (4,2)
4. Trapez: (4,0), (4,2), (5,0), (5,5)

c)

28/3

d)

28/3

a)

Für Q:
w_00 = 1/2
w_10 = 1/6
w_11 = 1/12
w_01 = 1/4

Für M:
w_00 = 1/4
w_10 = 1/4
w_11 = 1/4
w_01 = 1/4

b)

w_N = 1/2
w_S = 1/2
w_W = 1/2
w_O = 1/2
w_NO = -1/4
w_NW = -1/4
w_SO = -1/4
w_SW = -1/4

a)

Singulärwerte: 1, 1/2, 1/3
Rang: r = 3
Bild: span{(0, -1, 0)^T, (-1, 0, 0)^T, (0, 0, 1)^T}
Kern: span{(-1/2, 1/2, -1/2, 1/2)^T}
Konditionszahl: 1/(1/3) = 3

b)

U^T * (1, 0, -2)^T = (0, -1, -2)^T
S^~1 * (0, -1, -2)^T = (0, -2, -6, 0)^T
V * (0, -2, -6, 0)^T = (2, -4, -4, 2)^T

c)

|   0     0    0    0|
|-1/2  -1/2  1/2  1/2|
|   0     0    0    0|

a)

void Solver::decomposeLU(const Matrix& m, Matrix& l, Matrix& u) { 
	int d = m.getWidth();
	u = m;
	l.setIdentity();
 
	for(int c = 0; c < d; c++) {
		for(int r = c + 1; r < d; r++) {
			float factor = u(r,c) / u(c,c);
 
			for(int c2 = c; c < d; c++) {
				u(r, c2) = u(r, c2) - u(c, c2) * factor;
			}
 
			l(r,c) = factor;
		}
	}
}

b)

void Solver::solveSystem(const Matrix& m, const Matrix& b, Matrix& x) {
	int d = m.getHeight();
	Matrix u(d, d);
	Matrix l(d, d);
	Matrix y(d, 1);
	decomposeLU(m, l, u);
	forwardSubstitution(l, b, y);
	backwardSubstitution(u, y, x);
}

c)

float Solver::calcDeterminant(const Matrix& m) {
	int d = m.getHeight();
	Matrix u(d, d);
	Matrix l(d, d);
	decomposeLU(m, l, u);
 
	float res = 1.0f;
	for(int i = 0; i < d; i++) {
		res *= u(i,i);
	}
 
	return res;	
}

a)

void computeDerivativeXX(const Image& image, Image& result) {
	int d = image.getDimension();
 
	for(int r = 0; r < d; r++) {
		for(int c = 0; c < d; c++) {
			if(c < 2 || c >= d - 2)
				result(r,c) = 0.0f;
			else
				result = -2 * image(r,c) + image(r,c-2) + image(r, c+2);
		}
	}
}

b)

void computeLaplacian(const Image& image, Image& result) {
	int d = image.getDimensions();
 
	Image dX(d);
	Image dY(d);
 
	computeDerivativeXX(image, dX);
	computeDerivativeYY(image, dY);
 
	for(int r = 0; r < d; r++) {
		for(int c = 0; c < d; c++) {
			result(r, c) = dX(r,c) + dY(r, c);
		}
	}
}

c)

…

a)

s_0 = (0, -2)^T
t_0 = 1/2
x_1 = (1, 0)^T

s_1 = (-2, 0)^T
t_1 = 1/4
x_2 = (1/2, 0)^T

b)

s_x = 0, s_y beliebig
z.B.: (0, 1)^T

c)

Konvergenzordung:
Die Konvergenzordnung beschreibt, um welchen Grad die Genauigkeit einer Approximation pro Iterationsschirtt zunimmt.

Lineare Kovergenz:

Für alle c < 1 gilt:
|x_i+1 - x*| <= c * |x_i - x*|

Quadratische Kovergenz:
Potenzordnung p mit der der Fehler kleiner wird:

Für alle c < 1 gilt:
|x_i+1 - x*| <= c * |x_i - x*|²

a)

       { -x + 1    für  1 <= x < 3
L(x) = { 2x - 8    für  3 <= x < 5
       { -2x + 12  für  5 <= x < 7

b)

Interpolation: Graph verläuft exakt durch die Werte der Stützpunkte.
Approximation: Graph nähert sich den Werten der Stützpunkte an, verläuft aber nicht zwingend durch sie.

c)

Grad des Polynoms: 5
Damit: 6 Datenpunkte nötig

d)

c_0 = 0
c_1 = 2/π
c_2 = -8/3π²
c_3 = 16/6π³

p(x) = 2/π * x - 8/3π² * x (x - π/2) + 16/6π³ * x (x - π/2)(x - 3π/2)

a)

(55/2, 44)^T

b)

…

c)

…

d)

• Bézier-Kurven liegt in der konvexen Hülle
• Variationsreduzierend
• In den Endpunkten tangential an das Kontroll-Polygon
• Geht durch die Endpunkte des Kontroll-Polygons