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!
Inhaltsverzeichnis
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(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)
|0 4 0 0| |0 0 0 0| |0 0 3 2| |0 2 1 4| |0 0 0 0|
Aufgabe 3 - LU-Zerlegung
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
Aufgabe 4 - Least-Square Approximation
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
Aufgabe 5 - Hauptkomponentenanalyse
a)
|28/5 18/5| |18/5 16/5|
b)
1. Hauptachse: (-1, 1)^T 2. Hauptachse: (1, 1)^T
Aufgabe 6 - Programmierung: Polynominterpolation
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; }
Aufgabe 7 - Programmierung: Bildbearbeitung
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; } } } }
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.
|x_i+1 - x_exact| <= c * |x_i x_exact|^2
Aufgabe 9 - Interpolation
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)!
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)
…
d)
(32, -4)^T (0, -4)^T (0, -68)^T (32, -36)^T
e)
…