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
Lösungen ohne gewähr, da irgendwann zwischen 11 und 1 Uhr und 6-7 Uhr vor der Klausur schnell gemacht (ja abends, und morgens). Ich klatsche es nur hier hin, fuer die naechste Generation. Viel Spaß bei der Klausur
Aufgabe 1 - Komplexität
- a)
a) O(n)
b) O(n³)
c) ???
d) O(n log n)
e) 1
f) 2
g) O(h²)
h) O(h^5)
- b)
nein, nein, ja, ja
Aufgabe 2 - Lösen linearer Gleichungsszsteme
a) Erste iteration:
R_1 = |2 1 3| |0 1 -2| |0 3 -4|
Lösung:
R = |2 1 3| |0 1 -2| |0 0 2| L = |1 0 0| |2 1 0| |-2 3 1|
b)
x = |-3| |3| |2|
c)
x_1 = |8| |0| |0| |8| x_2 = |8| |-4| |-4| |8|
d)
x_1 = | 8| |-4| | 2| |-7|
e) Theoretisch exakt, praktisch wegen Rundungsfehlern oft als iteratives Verfahren angewendet.
Aufgabe 3 - Speicherung dünn besetzter Matrizen
a)
val 2 3 -4 7 3 2 2 -1 row_ind 2 3 4 1 2 3 1 3 col_ptr 0 0 3 6 6 8
b)
Speicherung erfolgt im CRS-Format. Hierzu muss nur row_ind als col_ind bzw. col_ptr als row_ptr interpretiert/kopiert werden.
c)
| 0 4 0 0 | | 0 0 0 0 | | 0 0 3 8 | | 0 2 -1 4 | | 0 0 0 0 |
Aufgabe 4 - Falten und Filtern
a)
ja (1 2 1)^T (1 2 1)
nein
ja (1 2 3)^T (-1 0 1)
b)
5^2 * (N-4)^2
c)
2*5*(N-4)^2
d)
double getValue (const unsigned int& x, const unsigned int& y) const { return data.at(2 * x + y); }
e)
void setValue (const unsigned int& x, const unsigned int& y, double value) { data.at(2 * x + y) = value; }
f)
filter { double filter[3][3] = { {0,1,0}, {1,-4,1}, {0,1,0} }; for(int x=1;x<src.getDim()-1; x++) { for(int y=1;y<src.getDim()-1; y++) { double newValue=0; for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { newValue+=src.getValue(x-1+i,y-1+j)*filter[j][i]; } } dest.setValue(x-1,y-1,newValue); } } }
g)
filter { Image tmp(src.getDim()); double filterX[3]={3,10,3}; double filterY[3]={1,0,-1}; for(int x=0;x<src.getDim();x++) { for(int y=1;y<src.getDim()-1;y++) { double newValue=0; for(int i=0;i<3;i++) { newValue+=src.getValue(x,y-1+i)*filterY[i]; } tmp.setValue(x,y-1,newValue); } } for(int x=1;x<src.getDim()-1;x++) { for(int y=1;y<src.getDim()-1;y++) { double newValue=0; for(int i=0;i<3;i++) { newValue+=src.getValue(x-1,y-1+i)*filterX[i]; } tmp.setValue(x-1,y-1,newValue); } } }
Aufgabe 5 - Interpolation
a)
y-Werte = 1, -1, 1, 2
von-nach: 0–0.5, 0,5–1,5, 1,5–3, 3–4(,5)
b)
| -2x+1 < 2x-3 | 1/2x
c)
m_1 = 0
m_2 = 3/2
d)
e)
f_p = 8
f)
rho = 1/4
sigma = 1/2
tau = 1/4
f_p = 7
Aufgabe 6 - Bezier-Kurven
meine Sexistische Bildbeschreibung
! i have no idea what i am doing here, schlimmste Bezier-Aufgaben den ich so begegnet bin !
a)
Schaut wie Busen (von oben) aus. :)
b)
Busen der links und rechts ausbuechst :)
c)
„Brustbein“ ist unterhalb des mitleren zackens
d)
Lösungsansatz: i have no idea what i am doing here Zuerst die Ecken:
c_0 = kp[0]; d_(kp.dim-1) =kp[kp.dim -1
Dann den rest mit dem Code aus der Vorlesung (oder Script)
for(k = 1, ....){ for(i...){ }
Vor ende der aeusseren For-Schleife die interesanten Werte uebernehmen:
c_k = kp_k d_kp.dim -k = kp_kp.dim-k }
Ggf. Arbeitskopie von kp machen, off by one Fehler
Aufgabe 7 - Singulaerwertzerlegung
a)
Singulaerwerte: 6, 3, 3
Rang: 3
Bildraum: <1/9(1 4 8)^T,1/9(4 7 -4)^T, 1/9(8 -4 1)^T>
Kern: <1/2 (-1 1 1 1)^T
Konditionszahl: 2
b)
| 5 | | -11 | | 9 | | 7 |
c)
1/18 * A A = | 6 6 6 -6 | | 24 24 24 -24 | | 48 48 48 -48 |
Aufgabe 8 - Nichtlineare Optimierung
a)
x_1 = (9/8 3) ^T
s_0 = (1 0)
b)
maxIter ||x_i+1 - x_i|| < epsilon ||F(x_i)|| < epsilon (Nullstellensuche)
c)
x^1 = (1 3)
d)
(1 0)^T
e) [5/4,13/4] T
Aufgabe 9 - Median Cut
Median Cut konnte ich aus den Vorlesungsfolien nicht nachvollziehen.