===== 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)\\
FT(f*g) = FT(f) * FT(g) //siehe e-mail von Prof.Strehl [https://fsi.informatik.uni-erlangen.de/forum/thread/5586]] \\
FT(f) = Fouriertransormierte von f\\
FT(g) = "   -   "\\

ro = a = 1 \\

   FT(f) = / 1 für |x|<1 
           \ 0  sonst  

   FT(g) = 1/sqrt(2pi)*exp(-x^2 / 2)

**ERGEBNIS:**
   F(f*g) = / 1/sqrt(2pi) *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 |
b)
CRS

**Aufgabe 5**

**Aufgabe 6**
a)

A*x = b => L*R*x = b => L*y = b\\
=> y ausrechnen\\
=> R*x = y\\
=> x ausrechnen

b)                     A    =   L     +    R
                   (2  2  1)  (1 0 0) (2 2 1)
                   (2  4  2)  (1 1 0) (0 2 1)
                   (2 10  6)  (1 4 1) (0 0 1)

c) Ly=b mit b (4 6 14)^t

    y1= 4 y2=2 y3=2

    dann damit Rx=y ergibt

    x1=1 x2=0 x3=2

**Aufgabe 7**

**Aufgabe 8**

**Aufgabe 9**

**Aufgabe 10**