===== Forendiskussionen ===== * [[https://fsi.informatik.uni-erlangen.de/forum/thread/10559,2-Klausur-23-Juli-2012]] Gesamte Klausur ===== Lösungsversuch ===== ==== Aufgabe 1 - Komplexität ==== **a)** O(n²) **b)** O(k²n) **c)** O(n) **d)** O(n³) **e)** O(n) **f)** O(n) **g)** O(n²) **h)** O(n) ==== Aufgabe 2 - Lineare Gleichungssysteme ==== **a)**


    | 3  3  0 |
R = | 0 -1  1 |
    | 0  0  2 |

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

**b)** Rx = Q_t*b\\ x = (-11/3, -1, 0, 0)^T \\ wobei x_3 und x_4 beliebig wählbar sind ==== Aufgabe 3 - SVD ==== **a)**


    |  1/3  -2/3  2/3 |
U = | -2/3   1/3  2/3 |
    |  2/3   2/3  1/3 |
	
    | 2  0   0  |
S = | 0  1   0  |
    | 0  0  1/2 |

    | 1  0  0 |
V = | 0  0  1 |
    | 0  1  0 |

**b)** Norm: 6 Konditionszahl: 3 Rang-1-Approximation:


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

==== Aufgabe 3 - Baryzentrische Koordinaten ==== **a)** P1: ρ = 1/3, σ = 0, τ = 2/3 \\ P2: ρ = 0, σ = 1, τ = 0 \\ P3: ρ = 1/3, σ = 1/3, τ = 1/3 \\ P4: ρ = -1, σ = 1, τ = 1 \\ **b)** Fläche links unterhalb von R, wenn man eine Gerade zwischen R und S sowie R und T ziehen würde. **c)** α = 1/3, β = 1/2, γ = 1/6 **d)** α = 0, 0 <= β <= 1, 0 <= γ <= 1 **e)** f_M = 1 **f)** Einfach die 4 Eckpunkte miteinander verbinden, dass oben ein verzerrtes Viereck entsteht. ==== Aufgabe 5 - Bézier-Kurven ==== **a)** c_0 = (8, 8)^T \\ c_1 = (4, 8)^T \\ c_2 = (4, 6)^T \\ c_3 = (6, 5)^T \\ d_0 = (6, 5)^T \\ d_1 = (8, 4)^T \\ d_2 = (12, 4)^T \\ d_3 = (16, 8)^T \\ **b)** ... **c)** ... **d)** ... ==== Aufgabe 6 - Programmierung: Coons Patches ==== **a)**


float CoonsPatch::evaluateAt(float s, float t) {
	float f_t = (1-s) * m_t0.f(t) + s * m_t1.f(t);
	float f_s = (1-t) * m_s0.f(s) + t * m_s1.f(s);
	float f_st = (1-t) * (1-s) * m_t0.f(0) + (1-s) * t * m_t0.f(1)
                    + (1-t) * s * m_t1.f(0) + t * s * m_t1.f(1);
	
	return f_s + f_t - f_st;
}

**b)**


float CoonsPatch::evaluateDerivativeS(float s, float t) {
	float f_t = (-1) * m_t0.f(t) + 1* m_t1.f(t);
	float f_s = (1-t) * m_s0.d(s) + t * m_s1.d(s);
	float f_st = (1-t) * (-1) * m_t0.f(0) + (-1) * t * m_t0.f(1) +
				(1-t) * m_t1.f(0) + t * m_t1.f(1);
	
	return f_s + f_t - f_st;
}

==== Aufgabe 7 - Programmierung: Nichtlineare Optimierung ==== **a)**


double optimizer::optimize(double x0, double y0, const unsigned int maxIter) const {
	double x = x0;
	double y = y0;
	
	for(int k = 0; k < maxIter; k++) {
		double sx, sy;
		
		searchDirection(x, y, sx, sy);
		
		double t = lineSearch(x, y, sx, sy);
		
		x = x + t * sx;
		y = y + t * sy;
		
		if(Math.sqrt(sx * sx + sy * sy) < m_gradientEpsilon)
			break;
	}
	
	return m_targetFunction.f(x, y);
}

**b)**


double optimize::lineSearch(const double x, const double y, const double dx, const double dy) const {
	double line, fct;
	double t = m_tMax;

	do {
		double gx, gy;
		m_targetFunction.gradf(x, y, gx, gy);
		
		double tmp = dx * gx + dy * gy;		
		line = m_targetFunction.f(x, y) + t * m_c1 * tmp;
		
		fct = m_targetFunction.f(x + t * dx, y + t * dy);
		
		t = t * m_reductionFactor;
	} while(line > fct);
	
	return t;
}

**c)**


void gradient_ascent_optimizer::searchDirection(double x, const double y, double& dx, double& dy) const {
	m_targetFunction.gradf(x, y, dx, dy);
	
	dx = -dx;
	dy = -dy;
}

**d)**


void newton_optimizer::searchDirection(const double x, const double y, double& dx, double& dy) const {
	double h11, h12, h21, h22, gx, gy;
	m_targetFunction.inverseHessian(x, y, h11, h12, h21, h22);
	m_targetFunction.gradf(x, y, gx, gy);
	
	dx = h11 * gx + h12 * gy;
	dy = h21 * gx + h22 * gy;
	
	if(dx < 0 || dy < 0) {
		dx *= -1;
		dy *= -1;
	}
}

==== Aufgabe 8 - Falten und Filtern ==== **a)** {{:pruefungen:bachelor:algoks:algoks_12sose_a8a.png|}} **b)** ... **c)** F1: nicht separierbar \\ F2: separierbar mit (1, 2, 3)^T und (-1, 0, 1) \\ F3: nicht separierbar ==== Aufgabe 9 - Jacobi, Gauss-Seidel ==== **a)** (1, -1/2, 0, 2)^T **b)** (1, -1/2, 3/2, 2)^T **c)** B: Starkes Spaltensummenkriterium \\ -> Jacobi-Verfahren konvergiert für B C: ist unzerlegbar \\ schwaches Zeilen- und Spaltensummenkriterium \\ mindestens für eine Zeile/Spalte gilt, dass der Wert auf der Diagonalen größer als die restlichen Einträge in der Zeile/Spalte ist (im Betrag) \\ -> Jacobi-Verfahren konvergiert für B ==== Aufgabe 10 - Nullstellensuche ==== **a)** x_2 = 1, x_3 = 2 **b)** x_1 = 3, x_3 = 2,75 **c)** x_1+1 = (3/16, 1/4)^T **d)** Frage 1: \\\ Nein, das Newton-Verfahren ist nur lokal konvergent Frage 2: \\\ Nein, das Sekanten-Verfahren ist nur lokal konvergent Frage 3: \\\ p = 2 für einfache Nullstellen \\ p = 1 für mehrfache Nullstellen \\