• https://fsi.informatik.uni-erlangen.de/forum/thread/8754-LOeSUNGSVERSUCH-Klausur-5-August-2011 Gesamte Klausur

a) O(n²)

b) O(n)

c) O(n³)

d) O(n)

e) O(n²)

f) O(n)

g) O(h²)

h) O(h^4)

a)

val = 2, 3, -4, 7, 3, 2, 8, 1, -3 row_idx = 2, 3, 4, 1, 2, 3, 1, 3, 4 col_ptr = 0, 0, 3, 6, 9, 9

b)

Die Transponierung kann sehr einfach erreicht werden, indem man die bestehenden Arrays als CRS-Format interpretiert. val_trans = val col_idx = row_idx row_ptr = col_ptr

c)

|0 4 0 0|
|0 0 0 0| 
|0 0 3 2|
|0 2 1 4|
|0 0 0 0|

a)

    |1  0  0|
L = |2  1  0|
    |-2 3  1|
	
    |2  1  4|
U = |0  1  1|
    |0  0  2|

b)

x = (-10, 6, -3/2, -1)^T

a)

    |1 -1  1|
A = |0  0  1|
    |1  1  1|
    |4  2  1|

u = (a, b, c)^T
	
b = (1, -2, -1, 2)^T

b)

|14  5 -2|   |c|   |7|
| 5  5  0| x |b| = |7| 
|-2  0  5|   |a|   |3|

c)

QR-Zerlegung

a)

|28/5   18/5|
|18/5   16/5|

b)

1. Hauptachse: (-1, 1)^T 2. Hauptachse: (1, 1)^T

a)

Matrix MonomialCurve::getCoefficientMatrix() const {
	int cp = getNumControlPoints();
	Matrix m(cp, cp);
	std::vector<Point2D>& p = getControlPoints();
 
	for(int r = 0; r < cp; r++) {
		m(r, 0) = 1;
 
		for(int c = 0; c < cp; c++)
			m(r, c) = m(r, c-1) * p(r).x;
	}
}

b)

float MonomialCurve::evaluateAt(const Matrix% coeff, const float x) const {
	int h = getNumControlPoints();
	float result = coeff(h-1, 0);
 
	for(int i = h - 2; i >= 0; i--) {
		result = result * x + coeff(i, 0);
	}
 
	return result;
}

c)

Matrix NewtonCurve::getCoefficientMatrix() const {
	int cp = getNumControlPoints();
	Matrix m(cp, cp);
	m.setZero();
	std::vector<Point2D>& p = getControlPoints();
 
	for(int r = 0; r < cp; r++) {
		m(r, 0) = 1;
 
		for(int c = 1; c < r; c++)
			m(r, c) = m(r, c-1) * (p(r).x - p(c-1).x);
	}
}

d)

float NewtonCurve::evaluateAt(const Matrix% coeff, const float x) const {
	int h = getNumControlPoints();
	float result = coeff(h-1, 0);
	std:vector<Point2D>& p = getControlPoints();
 
	for(int i = h - 2; i >= 0; i--) {
		result = result * (x - p(i).x) + coeff(i, 0);
	}
 
	return result;
}

a)

void computeDerivativeX(const Image& image, Image& result) {
	int dim = image.getDimension();
 
	for(int r = 0; r < dim; r++) {
		for(int c = 0; c < dim; c++) {
			prev = (c == 0) ? c : c - 1;
			next = (c == dim - 1) ? c : c + 1;
			result(r, c) = -2 * image(r, c) + image(r, prev) + image(r, next);
		}
	}
}

b)

void computeLaplacian(const Image& image, Image& result) {
	int dim = image.getDimensions();
 
	Image derivX(dim);
	Image derivY(dim);
 
	computeDerivativeX(image, derivX);
	computeDerivativeY(image, derivY);
 
	for(int r = 0; r < dim; r++) {
		for(int c = 0; c < dim; c++) {
			result(r, c) = derivX(r,c) + derivY(r, c);
		}
	}
}

c)

(Sehr unsicher → zu Überprüfen)

void solveLaplacianEquation(Image& image, const Image& mask, unsigned int iterations) {
	int dim = image.getDimension();
 
	Image result;	
	Image laplacian;
 
	computeLaplacian(image, laplacian);
 
	for (unsigned int i = 0; i < iterations; i++) {
		for (int r = 1; r + 1 < dim; r++) {
			for (int c = 1; c + 1 < dim; c++) {
				if (mask(r, c) == 0.0f)
					continue;
 
				float tmp = laplacian(r, c);
 
				tmp = tmp - result(r - 1, c    )
				          - result(r + 1, c    )
				          - result(r    , c - 1)
				          - result(r    , c + 1);
				tmp = tmp / (-4.f);
 
				result(r, c) = tmp;
			}
		}
	}
}

a)

Zum Beispiel: s_1 = (1, 0)^T s_2 = 1/sqrt(2) * (1, 1)^T

b)

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

c)

x_i+1 = (0, 3)^T

d)

Mit jedem Iterationsschritt nimmt die Genauigkeit des Ergebnisses um die Potenz 2 zu.

|x_i+1 - x_exact| <= c * |x_i x_exact|^2

a)

       { 5/4 x + 5/2    für -2 <= x < 0
L(x) = { 3/4 x + 5/2    für  0 <= x < 2
       { 1/4 x + 7/2    für  2 <= x < 4

b)

y_1' = 1 y_2' = 1/2

c)

P_1: ρ = 2/3, σ = 0, τ = 1/3 P_2: ρ = 0, σ = 0, τ = 1 P_3: ρ = 1/3, σ = 1/2, τ = 1/6

d)

α_R = α_S = α_T = 1/3

f_pR = 12 f_pS = 56 f_pT = 48

f_p = ρ * f_pR + σ * f_pS + τ * f_pT = 40

Hinweis: Bei den Baryzentrischen Koordinaten handelt es sich um die des Punktes P_3 aus Teilaufgabe c)!

a)

(19/2, 14)^T

b)

c_0 = (0, 32)^T

c_1 = (0, 16)^T

c_2 = (16, 8)^T

c_3 = (28, 8)^T

d_0 = (28, 8)^T

d_1 = (40, 8)^T

d_2 = (48, 16)^T

d_3 = (32, 32)^T

c)

DeCasteljau und Midpoint Subdivision grafisch.

d)

b_0 = (32, -4)^T

b_1 =(0, -4)^T

b_2 =(0, -68)^T

b_3 =(32, -36)^T

e)

–fehlt–