Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Forendiskussionen   (Übersicht)

Dies ist eine alte Version des Dokuments!


Forendiskussionen

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(n²)

h) O(n)

Aufgabe 2 - Baryzentrische Koordinaten

a)

P1: ρ = 0, σ = 0, τ = 1
P2: ρ = 1/2, σ = 0, τ = 1/2
P3: ρ = 1/4, σ = 1/2, τ = 1/4
P4: ρ = 1, σ = 1, τ = -1

b)

Fläche 1:
Fläche oberhalb von der Strecke TS, jedoch ohne die beiden außeren Spitzen bei T und S.

Fläche 2:
Die äußere Spitze von R nach unten.

c)

f_P = 12

d)

f_P = 11

Aufgabe 3 - Falten und Filtern

a)

F1: Nicht separierbar
F2: (1, 2, 1)^T und (-1, 0, 1)
F3: Nicht separierbar
F4: (1, 1, 1)^T und 1/12 (1, 1, 1, 1)

b)

(N-2)² * 5²

c)

(N-2)² * 5 * 2

d)

|0  1  0|
|1 -4  1|
|0  1  0|

e)

Tiefpass: Glättung

Sobel: Kantendetektion

Aufgabe 4 - QR-Zerlegung

a)

x = (-1, 2, -1, 2)^T

b)

det(A) = det(R)

c)

Q = | -0.6  0.8|
    |  0.8  0.6|
	
R = | -5  -0.2|
    |  0  -1.4|

Aufgabe 5 - Nichtlineare Optimierung

a)

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

b)

t_0 = 1
x_1 = (1, 0)^T

s_1 = (1, 1)^T
t_1 = -3
x_2 = (-2, -3)^T

c)

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

d)

|x_i+1 - x*| <= c * |x_i - x*|

Pro Iterationsschritt nimmt der Fehler um einen konstanten Faktor ab.

Aufgabe 6 - Bézier-Kurven

a)

C(1/3) = (6, 5/3)^T

b)

c)

Aufgabe 7 - Singulärwertzerlegung und PCA

a)

Singulärwerte: 6/4, 3/4, 2/4
Rang: 3
Bildraum: span{1/3(-1, -2, -2)^T, 1/3(-2, 2, -1), 1/3(-2, -1, 2)}
Kern: span{1/2(1, -1, -1, 1)^T}
Konditionszahl: 3

b)

v_1 = (1, 0)^T wobei x_1 beliebig
v_2 = (0, 1)^T wobei x_2 beliebig

Aufgabe 8 - Polynominterpolation

a)

       {-1        -1 <= x <    0
k(x) = {2    für   0 <= x <  1.5
       {4        1.5 <= x <=   2

b)

l(x) = {3/2x + 1/2  für  -1 <= x <  1
       {2x                    1 <= x <= 2

c)

l_0: 1/6 * (x-1)(x-2)
l_1: -1/2 * (x+1)(x-2)
l_2: 1/3 * (x+1)(x-1)

L(x) = y_0 * l_0(x) + y_1 * l_1(x) + y_2 * l_2(x)

d)

n_0(x) = 1
n_1(x) = x + 1
n_2(x) = (x + 1) * (x - 1)

a_0 = -1
a_1 = 3/2
a_2 = 1/6

Aufgabe 9 - 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_s1.f(0) +
				(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) + 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_s1.f(0) +
				(1-t) * m_s1.f(0) + t * m_t1.f(1);
 
	return f_s + f_t - f_st;
}

Aufgabe 10 - Dünnbesetzte Matrizen

a)

CCSMatrix::CCSMatrix(unsigned int height, unsigned int width) {
	_height = height;
	_width = width;
	_nonZeroElements = 0;
	_values = new float[0];
	_rowIndices = new int[0];
	_colPtr = new int[width + 1];
}

b)

float CCSMatrix::getEntry(unsigned int i, unsigned int j) {
	for(int rowP = _colPtr[j]; rowP < _colPtr[j+1]; rowP++) {
		if(_rowIndices[rowP] == i)
			return _values[rowP];
	}
 
	return 0;
}

b)

CCSMatrix::CCSMatrix(Matrix& other) {
	_height = other._height;
	_width = other._width;
	_nonZeroElements = other._nonZeroElements;
	_values = new float[_nonZeroElements];
	_rowIndices = new int[_nonZeroElements];
	_colPtr = new int[width + 1];
 
	int t = 0;
	_colPtr[0] = 0;
 
	for(int c = 0; c < _width; c++) {
		for(int r = 0; r < _height; r++) {
			float elem = other.getEntry(r, c);
			if(el != 0) {
				_values[t] = elem;
				_rowIndives[t] = r;
				t++;
			}
		}
		_colPtr[c] = t;
	}
}

b)

Matrix Matrix::operator*(CCSMatrix& other) {
	Matrix result(_height, other._width);
 
	for(int r = 0; r < _height; r++) {
		for(int c = 0; c < other._width; c++) {
 
			float sum = 0.0f;
			for(int rowP = other._colPtr[c]; rowP < other._colPtr[c+1]; rowP++) {
				float v = other._values[rowP];
				sum += v * getEntry(r, other._rowIndices[rowP]);
			}
			result.setEntry(r, c, sum);
			if(sum != 0) {
				result._nonZeroElements++;
 
		}
	}
}