Musterlösung Blatt 7:

H-26
Koeffizientenfolgen sind A = <-10,1,-1,7,0,0,0,0>
und B = <3,-6,0,8,0,0,0,0>. 

DFT(A) = < -3 , -10-3sqr(2)-(1-4sqr(2))i , -9-6i , -10+3sqr(2)+(1+4sqr(2))i  , 
          -19 , -10+3sqr(2)-(1+4sqr(2))i , -9+6i , -10-3sqr(2)+(1-4sqr(2))i  >

DFT(B) = < 5 , 3-7sqr(2)+sqr(2)i , 3-14i , 3+7sqr(2)+sqr(2)i ,
               3+7sqr(2)-sqr(2)i , 3+14i , 3-7sqr(2)-sqr(2)i  >

C = DFT(A)DFT(B) 
  = < -15 , 4+62sqr(2)-(65-9sqr(2))i , -111+108i , 4-62sqr(2)+(65+9sqr(2))i ,
      -19 , 4-62sqr(2)-(65+9sqr(2))i , -111-108i , 4+62sqr(2)-(65-9sqr(2))i >

DFT(C) = < -240 , 0 , 448 , -64 , -272 , -424 , -72 , 504 > 

DFT^(-1)(C) = < -30 , 63 , -9 , -53 , -34 , -8 , 56 , 0 >

also ist das Produkt A(x)B(x) = 
   56x^6 - 8x^5 - 34x^4 - 53x^3 - 9x^2 + 63x -30


H-27
Sei w die n-te Einheitswurzel e^(i 2pi/n).


Es sei D := DFT(C) = <d0 ,...d(n-1)> mit

  dk = Summe(cj w^(kj) ; j=0..n-1)
     = Summe(Summe(a(l-j mod n) bj w^(kj) ; j=0..n-1) ; l=0..n-1)

Läuft j bei festem l von 0 bis n-1, so durchläuft auch l-j mod n 
die Werte von 0 bis n-1. Also benennen wir die Summationsindizes
um und erhalten:
  
  dk = Summe(Summe(al bj w^(k(l+j mod n)) ; j=0..n-1) ; l=0..n-1)
     = Summe(Summe(al bj w^(kl+kj) ; j=0..n-1) ; l=0..n-1)

wobei diese Gleicheit gilt, da sich k(l+j mod n) und k(l+j) 
nur um ein Vielfaches von n unterscheiden. Dies ist 

     = Summe(al w^(kl) ; l = 0..n-1) Summe(bj w^(kj) ; j=0..n-1)
     
also das Produkt der k-ten Glieder von DFT(A) und DFT(B). 


H-28
Das Polynom, das genau die Nullstellen x0 , ... , x(n-1) hat,
ist (x-x0)...(x-x(n-1)).
 
Dieses Produkt kann man rekursiv wie folgt ausrechnen:
Sei X die Liste <x1 , ... , x(n-1)>

 Poly(X) 
   X1 := <x1 , ... , x(n/2-1)>
   X2 := <x(n/2) , ... , x(n-1)>
   P1 := Poly(X1)
   P2 := Poly(X2)
   return P1 * P2

Die Multiplikation in der 5. Zeile wird mit FFT ausgerechnet,
braucht also O(n log n). 
Die Laufzeit T(n) erfüllt also die Rekursion:

  T(n) = 2 T(n/2) + O(n log n) 

Deren Lösung ist laut Lösungshinweis O(n(log n)^2). 
 

H-29 
Sortiere zunächst die Punkte lexikographisch nach x- und y-
Koordinaten. Seien diese p1 ... pn in der sortierten Ordnung.

Für jeden Punkt pi sortiere nun die Punkte p(i+1) ... pn nach
Polarwinkel. Bilden zwei Punkte pj und pj' den gleichen Polarwinkel
mit pi, so liegen pi, pj und pj' auf einer Geraden.

Liegen umgekehrt drei Punkte auf einer Geraden, so ist einer von ihnen
der erste in der obigen Ordnung, und die anderen zwei bilden mit ihm
den gleichen Polarwinkel, also werden die drei Punkte auch gefunden.

Aufwand: Anfangs einmal sortieren , danach werden für jeden der n
Punkte die anderen sortiert, also (n+1) * O(n log n) = O(n^2 log n).