Musterlösung Blatt 6:

H-21
Aggregatmethode:
Jede Operation kostet 1 Einheit, die bei Zweierpotenzen i zusätzlich
i-1. Die Zweierpotenzen unterhalb von n sind 2^0, 2^1, ... ,
2^([log n]). Also sind die Gesamtkosten von n Operationen

 T(n)  =  n + Summe( 2^i - 1 , i = 0 .. [log n] ) 
      <=  n + Summe( 2^i , i = 0 .. [log n] ) 
       =  n + 2^([log n] + 1) - 1
      <=  n + 2 * 2^[log n] = n+2n = 3n .

Also amortisierte Kosten jeder Operation 3 Einheiten.

Kontomethode:
Durch Probieren errät man amortisierte Kosten von 3.  Für die
Operationen i, wo i keine Zweierpotenz ist, kann ich damit zahlen und
behalte 2 übrig, die ich auf das Konto einzahle.
Bei einer Operation i = 2^k habe ich also mindestens 2*(2^(k-1)-1) =
2^k-2 auf dem Konto, aus den Operationen 2^(k-1)+1 , 2^(k-1)+2 , ... ,
2^k-1. Mit den 3 Einheiten für Operation i habe ich also genug,
nämlich 2^k-2+3 = 2^k+1, um für Operation i zu bezahlen.

Potenzialmethode:
Das Potenzial der Datenstruktur Di nach der Operation i 
sei Phi(Di) = 2*(i-2^[log i]).
Ist i keine Zweierpotenz, so ist die Potenzialdifferenz
Phi(Di) - Phi(D(i-1)) = 2, also sind die amortisierten
Kosten 1+2 = 3.
Ist i=2^k, so ist Phi(Di) = 0 und Phi(D(i-1)) = 2*(2^k-1-2^(k-1))
= 2^(k+1) - 2^k - 2 = 2^k-2, also sind die amortisierten Kosten
 2^k + 0 - (2^k - 2) = 2. 
(Man sieht: dies ergibt die schärfste Analyse.)


H-22
Für einen Heap H sei das Potenzial Phi(H)=Summe([log i],i=1..n)
wobei n = heapsize[H]. 
Tatsächliche Kosten eines Heap-Insert sind [log (n+1)], und eines
Heap-Extract-Max [log n]. 

Amortisierte Kosten für Heap-Insert:
 [log (n+1)] + Summe([log i],i=1..n+1) - Summe([log i],i=1..n)
 = 2[log (n+1)] = O(log n)

Amortisierte Kosten für Heap-Extract-Max
 [log n] + Summe([log i],i=1..n-1) - Summe([log i],i=1..n)
 = [log n] - [log n] = 0  = O(1)


H-23:
 
z = (1+i)^5 :  
 Re(z) = -4  Im(z) = -4  |z| = 4*Wurzel(2)  arg(z) = -3 pi/4
 
z = (3-4i)/(3i+4) 
 Re(z) = 0   Im(z) = -1  |z| = 1  arg(z) = -pi/2

z = (4+i)/(5i-12)
 Re(z) = -43/169  Im(z) = -32/169 
 |z| = (1/13)*Wurzel(17)   arg(z) = arctan(32/43) - pi

z = ( 1/2 + Wurzel(3)/2 I)^4 
 Re(z) = -1/2  Im(z) = -Wurzel(3)/2   |z| = 1  arg(z) = -2 pi/3
 

H-24:
{ z in C ; |z -i| = Wurzel(2) } ist ein Kreis um den Punkt i
vom Radius Wurzel(2). 

Die zweite Menge { z in C ; 1 + z^2 in R+ } kann man auch so
beschreiben: Re(1+x^2)>=0 und Im(1+z^2)=0.
 
Ist z = (a+bi) für a,b in R, so ist 1+z^2 = a^2-b^2+1 + 2abi,
also ist Im(1+z^2) = 2ab. Daher muss a=0 oder b=0 sein.
Alle Punkte z in der Menge liegen also auf der reellen oder 
der imaginären Achse. 

Weiter soll a^2-b^2+1 >= 0 sein. Für b=0 heißt das a^2 >= -1,
also liegt die ganze reelle Achse in der Menge.
Für a=0 folgt b^2 <= 1, also |b| <= 1, das heisst M enthält
noch die Punkte auf der imaginären Achse zwischen -i und i.


H-25:

Sei die Komplexe Zahlenebene als Koordinatensystem auf die Insel
gelegt.  Es sei G die Position des Galgens, P die der Palme und B die
der Felsbrocken.  Rotation eines Ortsvektors um einen rechten Winkel
nach links enspricht der Multiplikation mit i, und nach rechts der
Multiplikation mit -i.  Daher ist die Position der ersten Fahne
F1 = P + i(P-G).  Entsprechend steht die zweite Fahne bei 
F2 = B - i(B-G).
Der Schatz ist also bei
 
 S = (F1+F2)/2 = (P + iP - iG + B - iB + iG)/2 = (P + B + iP - iB)/2. 

Man sieht also, dass die Position S des Schatzes nicht von G abhängt.
Man erreicht also die gleiche Position S, wenn man für G irgendeinen
festen Startpunkt wählt und der Vorschrift der Karte folgt.