===== Forendiskussionen =====

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

===== Lösungsversuch =====

==== Aufgabe 1 - Komplexität ====
**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)

==== Aufgabe 2 - Speicherung dünn besetzter Matrizen ====

**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)**

<code>
|0 4 0 0|
|0 0 0 0| 
|0 0 3 2|
|0 2 1 4|
|0 0 0 0|
</code>

==== Aufgabe 3 - LU-Zerlegung ====

**a)**

<code>
    |1  0  0|
L = |2  1  0|
    |-2 3  1|
	
    |2  1  4|
U = |0  1  1|
    |0  0  2|
</code>

**b)**

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

==== Aufgabe 4 - Least-Square Approximation ====

**a)**

<code>
    |1 -1  1|
A = |0  0  1|
    |1  1  1|
    |4  2  1|

u = (a, b, c)^T
	
b = (1, -2, -1, 2)^T
</code>

**b)**

<code>
|14  5 -2|   |c|   |7|
| 5  5  0| x |b| = |7| 
|-2  0  5|   |a|   |3|
</code>

**c)**

QR-Zerlegung

==== Aufgabe 5 - Hauptkomponentenanalyse ====

**a)**

<code>
|28/5   18/5|
|18/5   16/5|
</code>

**b)**

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

==== Aufgabe 6 - Programmierung: Polynominterpolation ====

**a)**

<code cpp>
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;
	}
}
</code>

**b)**

<code cpp>
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;
}
</code>

**c)**

<code cpp>
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);
	}
}
</code>

**d)**

<code cpp>
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;
}
</code>

==== Aufgabe 7 - Programmierung: Bildbearbeitung ====

**a)**

<code cpp>
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);
		}
	}
}
</code>

**b)**

<code cpp>
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);
		}
	}
}
</code>

**c)**

(Sehr unsicher -> zu Überprüfen)
<code cpp>
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;
			}
		}
	}
}
</code>

==== Aufgabe 8 - Nichtlineare Optimierung ====

**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.
<code>
|x_i+1 - x_exact| <= c * |x_i x_exact|^2
</code>

==== Aufgabe 9 - Interpolation ====

**a)**

<code>
       { 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
</code>

**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)!

==== Aufgabe 10 - Bézier-Kurven ====

**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--