Du befindest dich hier: FSI Informatik » jahrgaenge » 2006 » "Muster"-Lösungen » Lösungsvorschlag: Algo3-Klausur vom 18. September 2006
Dies ist eine alte Version des Dokuments!
Lösungsvorschlag: Algo3-Klausur vom 18. September 2006
Aufgabe 1
a)
- Vektor-Matrix : O(n²)
- Matrix-Matrix : O(n³)
- LR (vollbesetzt) : O(n³)
- Vektor-Vektor Komponentenweise: O(n)
- Faltung : O(n³)
- FFT : O(nlog(n))
b) Aufwand geringer, da O(n²log(n)) < O(n³)
Aufgabe 2
a)
(x) Assoziativ
(x) Distributiv
(x) Kommutativ
b)
Das Eingangssignal x(t) wird unverändert an die Stelle t0 verschoben
c)
F(f*g) = sqrt(2pi) * F(f) * F(g) F(f) = Fouriertransormierte von f F(g) = „ - “
ro=a –> F(f) = 1 für |x|<1
= 0 sonst
F(g) = 1/sqrt(2pi)*exp(-x^2 / 2)
F(f*g) = exp(-x^2 / 2) für |x|<1
= 0 sonst
Aufgabe 3
2D Filter: O(M^2*m^2) 2*1D Filter: O(M^2*m*2) Vorraussetzung um Filter zu separieren: w(x1,x2) =w(x1)w(x2)
(f*w)(x1,x2)=SUM( SUM(f(t1,t2)*w(x1-t1)dt1) *w(x2-t2)dt2)
Aufgabe 4
a) Compressed Column Storage
values | 1 | -8 | 5 | 4 | 2 | 5 | 4 | 7 | -2 | 6 | -3 | -7 |
row index | 2 | 1 | 5 | 3 | 5 | 2 | 6 | 1 | 2 | 6 | 3 | 5 |
column pointer | 1 | 2 | 4 | 6 | 8 | 11 | 13 |
Aufgabe 5
Aufgabe 6
Aufgabe 7
Aufgabe 8
Aufgabe 9
Aufgabe 10