Hallo und willkommen zur zweiten Übung von Algorithmen.
Heute werde ich zusammen mit Christian Staud die Übung halten.
Und was wir heute vorhaben, ist hier auf dieser Folie zu sehen.
Wir werden eine kurze Wiederholung geben unter dem Nachtrag zum
Ukkakül, also kurze Wiederholung zum letzten Mal.
Dazu werden wir uns das Teil- und Herrscherparadigma anschauen, mit
dem wir letztes Mal schon angefangen haben.
Und das am Beispiel von Kara Zuber-Hoffmann anhand der Multiplikation
sehen.
Zusätzlich schauen wir uns Rekurrenzen an und Christian wird dann über
die amortisierte Analyse und über unbounded Arrays erzählen.
Nachtrag zu den Übungsblättern, das ist wichtig.
Bitte schreibt die Nummer des Tutoriums groß auf die erste Seite.
Zum Beispiel könnte man das einrahmen, oben rechts oder wie auch
immer.
Aber leserlich, darum möchten wir bitten.
Oder alternativ kann man dazu ein Deckblatt runterladen unter dieser
URL, die hier gegeben ist.
Und dort kann man eben automatisch generieren lassen zu seinem Namen
und zu seinem Tutorium ein automatisiertes Deckblatt generieren
lassen.
Genau, als PDF glaube ich.
Ein weiterer Hinweis, den ich hier noch geben möchte zu den
Übungsblättern ist, dass ihr bitte Quellen und Hilfsmittel, die ihr
zur Bearbeitung der Übungsblätter genommen habt, bitte auf den
Übungsblättern, die ihr abgebt, angebt.
Also alles, was ihr dazu verwendet habt, schreibt es bitte auf das
Blatt.
Oder macht es irgendwie kindlich, sodass wir sehen können, aus welchen
Quellen ihr Hilfe gezogen habt.
Ein Hinweis zu Blatt 2, Aufgabe 4a.
Die Aufgabe gibt keine Punkte, das ist optional, aber dennoch möchten
wir darauf hinweisen, dass die Aufgabenstellung lauten sollte, geben
Sie einen nicht trivialen rekursiven Algorithmus im Pseudocode an, die
fehlende Zahl, und jetzt kommt der Zusatz, der auf dem ursprünglichen
Blatt gefehlt hat, den O von N Schritten bestimmt.
Okay,
zur kurzen Wiederholung vom letzten Mal.
Womit haben wir uns beschäftigt?
Wir haben uns unter anderem mit der Effizienz von Algorithmen
beschäftigt.
Dabei haben wir uns angesehen, wie man das Problem, Sortieren von N
-Zahlen, algorithmisch lösen kann.
Wir haben uns dazu zwei Algorithmen angeschaut, die haben wir dann
verglichen, beispielhaft.
Dabei sind uns zwei Begriffe aufgefallen, zum einen ist das der
Begriff der Laufzeit und der Eingabegröße, und wir haben uns das O
-Kalkül angesehen und asymptotische Notationen.
Im zweiten Teil war Korrektheit von Algorithmen Gegenstand, und zwar
haben wir uns Invarianten angeschaut, aber insbesondere die
Schleifeninvarianten und haben das an Beispielen durchgemacht.
Beziehungsweise die Initialisierung, Fortsetzung und Terminierung und
wie finden wir Schleifeninvarianten, was muss gelten und dergleichen.
Einen Nachtrag habe ich noch zum O-Kalkül, wie gesagt, wir hatten
diese Definition das letzte Mal schon, bzw.
wir hatten das letzte Mal in der Übung die Definition von Groß O von G
von N, Groß Theta von G von N und Groß Omega von G von N.
Und hatten diese Mengen von Funktionen jeweils definiert, so dass wir
hier beispielsweise F von N eine obere Schranke mal Konstante, also G
von N mal Konstante ist eine obere Schranke für F von N für Groß O von
G von N.
Und zudem hatten wir noch Definitionen, die findet ihr in der
Vorlesung, Klein O von G von N und Klein Omega von G von N.
Dazu gehört auch, dass man hier in dem O-Kalkül, dass folgende
Äquivalenzen gelten.
Wir haben wieder für nicht negative Funktionen F und G, die aus der
Menge der natürlichen Zahlen, die aus der Menge der reellen Zahlen
gehen, folgende Äquivalenzen, die auf dieser Seite hier dargestellt
sind.
Beispielsweise gilt F von N gleich Groß O von G von N ist Äquivalenz
zu Null kleiner gleich Limes Superior, wobei wir N gegen Unendlich
laufen lassen.
Und den Quotienten hier haben, F von N durch G von N ist gleich C
-Konstante kleiner gleich Groß und Endlich.
Die anderen, das gilt hier für Groß O von G von N und analog dazu für
Groß Omega von G von N, für Klein O, für Klein Omega und für Groß
Theta von G von N, gelten eine entsprechende Aussage mit dem Limes
Superior oder Limes Inferior.
Dann kommen wir auch schon zu dem Teile- und Herrscheparadigma.
Das sind Folien, die wir uns letztes Mal ganz kurz am Ende angeschaut
haben.
Wir haben gesagt, dass viele Algorithmen rekursiv aufgebaut sind und
dieser Aufbau so gestaltet ist, dass diese Algorithmen sich mehrmals
ineinander aufrufen, um eng verwandte Teilprobleme zu lösen.
Und dabei kann man nach der Methode Teile und Herrsche arbeiten.
Das haben wir uns letztes Mal kurz angeschaut und das umfasst drei
Schritte auf jeder Rekursionsebene.
Das erste ist, wir teilen das Problem in verschiedene Teilprobleme
auf.
Der zweite Schritt ist, dass wir diese Teilprobleme beherrschen, durch
wiederum Rekursiven zu lösen und dann eine Stufe tiefer gehen.
Außer, wenn die Teilprobleme klein genug sind, das werden wir dann
bestimmen, durch Abfragen beispielsweise, dann lösen wir sie direkt.
Wir werden das gleich noch am Beispiel sehen.
Und dann verbinden wir alle Teillösungen wieder zusammen, sodass wir
dann in der Rekursion wieder nach oben steigen und das Ausgangsproblem
damit lösen.
Wir wollen das Ganze am Beispiel der Karasuba-Hoffmann-Multiplikation
mal durchspielen.
Und zwar diese Funktion kennt ihr aus der Vorlesung, da wurde eine
Funktion definiert, die heißt TrackMode und dort werden zwei Zahlen
eingegeben, a und b.
Was wir benötigen ist, dass a und b n Ziffern haben, wobei n eine Zahl
ist, die zusammengesetzt aus 2 mal k und n eine Zweierpotenz ist.
Wenn n gleich 1 ist, also wenn a und b die Ziffern jeweils 1 haben,
dann soll das direkte Produkt ausgegeben werden, a mal b.
Wenn das Teilproblem klein genug ist, geben wir das direkte Produkt
aus.
Ansonsten schreiben wir a als a1 mal b hoch k, wobei in unserem
Beispiel später b die Basis gleich 10 sein wird, also a1 mal 10 hoch k
plus a0.
Das gleiche machen wir mit b, b1 mal b hoch k im allgemeinen Fall oder
in unserem Fall später 10 hoch k plus b0.
Und dann berechnen wir den ersten Aufruf, der rekursiv die Zahlen a1
und b1 ein.
Zu bemerken ist, dass a1 und b1 jetzt genau die Hälfte der Ziffern
haben, die a und b haben.
Beim zweiten rekursiven Aufruf genauso.
Diesmal geben wir allerdings a0 und b0 ein.
Und ein rekursiven Aufruf, der zusammengesetzt ist aus den Summanden
von a1 und a0 bzw.
b1 und b0.
Und dann gibt es diese Formel, die sich zu dem, das haben wir jetzt
mal e genannt hier, e ergibt.
Das ist halt dieser erste rekursive Aufruf, der irgendwann einen
Rückgabewert in c11 speichert mal b hoch 2k.
2k ist gleich n.
Plus, und dann haben wir diesen Ausdruck hier in Klammern, c1010-c11
-c00 mal b hoch k und plus c00.
Alle diese Teile hier, diese Terme, haben wir vorher ausgerechnet und
können damit e bestimmen.
Und wir geben e zurück.
Und das passiert auf jeder Rekursionsstufe.
Und bei der Kara-Zuber-Hoffmann-Multiplikation lohnt es sich, so ein
Schema anzugeben.
Und zwar schreiben wir jetzt die a und b, a mal b in die linke Spalte
und berechnen hier diese rekursiven Aufrufe beispielhaft mal in der
rechten Spalte.
a1 mal b1 ist gleich RegMult von a1 b1 und analog dazu für a0 b0.
Und dann bilden wir die Summe von a1 plus a0 mal b1 plus b0.
Und das ist halt genau der rekursive Aufruf, den wir vorher hier an
dieser Stelle hatten.
Und dann können wir unser e zusammensetzen, weil wir haben quasi alles
gesammelt, was wir brauchen, um e zu bestimmen.
Und schreiben e dann wieder in die linke Spalte unten.
Und wie das aussehen könnte, haben wir mal an einem Beispiel
mitgebracht.
Die Zahl a wäre jetzt 1242, die Zahl b wäre 3163.
Und wir machen das a1 mal b1, a1 wäre 12, b1 wäre 31.
Schreiben wir hier in die rechte Spalte, a0 b0, 42 mal 63, genauso
hier.
Und dann rechnen wir die Summe aus, 12 plus 42, 54.
Und hierfür die Nullerteile eben genauso, 31 plus 64 ist 94.
Und jetzt haben wir Multiplikationen, die halt nur aus der Hälfte der
Ziffern besteht, der ursprünglichen eingegebenen Zahlen.
Und jetzt können wir die Rekursion weiter ausführen.
Das heißt wir bilden ein weiteres Rechteck, wir rechnen jetzt 12 mal
31, in der nächsten Rekursionsstufe aus 42 mal 63 und 54 mal 94.
Bei 12 mal 31 machen wir das Schema genauso, analog 1 mal 3, 2 mal 1
und 3 mal 4.
Diese Zahlen haben jetzt die Ziffernlänge 1, das heißt wir können sie
direkt ausrechnen, bzw.
unser Algorithmus macht das ja für uns.
Das heißt 3, 2 und das ergibt 12 und dann können wir e bestimmen durch
diese Formel, die wir vorhin im Algorithmus gesehen haben, das ergibt
372 und wir können rekursiv, gehen wir den Algorithmus wieder nach
oben und können für diese Multiplikation 12 mal 31, 372 eintragen.
Das gleiche passiert für 42 mal 63.
Wir teilen das wieder aus, rechnen e aus, tragen das Ergebnis hier
oben ein.
54 mal 94 genau dasselbe, teilen wir hier auf.
Allerdings muss hier jetzt beachtet werden, dass wir im letzten
Schritt hier eine Zahl erhalten, die aus zwei Ziffern besteht.
Das heißt wir müssen in der Rekursion noch einmal nach unten gehen,
salopp gesagt.
Und das machen wir auch, 9 mal 13.
Man kann sich die 9 auch als 0, 9 mal 13 vorstellen, deswegen 0 mal 1,
9 mal 3 usw.
Das können wir wieder direkt ausrechnen, weil die Anzahl der Ziffern
ist gleich 1 für jede Zahl, die hier unten eingegeben ist.
Der Algorithmus errechnet 117, wir gehen wieder nach oben, wir haben
hier die fehlende Zahl bestimmt, wir können über die Funktion, die wir
vorhin im Algorithmus gegeben haben, das E bestimmen, das ist 5076.
5076 ist das Ergebnis von 54 mal 94, wir gehen in der Rekursion wieder
nach oben und erhalten das Ergebnis dieser Zahl, der Multiplikation
von 1242 mal 3063.
Das haben wir auch schon gesehen, bzw.
in der Vorlesung war das dran, dass die Analyse von Kader-Zuber
-Hofmann eine Laufzeit von t von n kleiner gleich 1, für n gleich 1,
das ist der Teil, wo wir das Teilproblem in die Ziffernlänge 1 gelegt
haben.
Und der andere Fall ist, für n größer gleich 1, haben wir das in 3, 3
rekursive Aufrufe bestimmt, 3 rekursive Aufrufe mal die Laufzeit und
jetzt ist die Ziffernlänge halt nur noch halb so lang, deswegen halt
hier n halb nach oben abgeschätzt.
Plus der Overhead, der halt noch benötigt würde, um Additionen,
Subtraktionen zusammenzufassen.
Das passiert genau in jeder Rekursionsstufe und wenn wir diese Form
sehen, fällt uns vielleicht sofort das Mastertheorem ein, das in der
Vorlesung auch eingeführt wird, die einfache Form davon.
Das besagt, dass für positive Konstanten a, b, c, d, wobei n gleich b
hoch k, für eine natürliche Zahl k, folgendes aussagt, dass die
Laufzeit t von n gleich a ist, falls n gleich 1, das ist der
Basisfall, den wir vorhin gesehen haben.
Oder, dass die Laufzeit c für diese Konstante, die wir umgeben haben,
positive Konstante mal n plus d mal t von n durch b.
Und hier teilen wir die Probleme in kleinere Teilprobleme auf.
Und das ist die Anzahl der Teilprobleme.
Jetzt kann man Aussagen treffen, jetzt gibt uns das Mastertheorem
folgende Aussage, das heißt, wir erhalten t von n ist gleich Großtäter
von n, falls dieses d, was hier vor diesem t steht, kleiner als b ist.
Also dieses d, was hier unten, also d kleiner als b ist, da kriegen
wir halt Großtäter von n.
Und die anderen Fälle, falls d gleich b ist, halten einen Algorithmus,
der die Laufzeit Großtäter von n log n hat, beziehungsweise Großtäter
von n hoch log von d zur Basis b, falls diese Konstante größer ist als
b.
Und das Mastertheorem gibt uns sofort für die Karatsuba-Hofmann
-Multiplikation eine Laufzeit von Großtäter von n hoch log von 3 zur
Basis 2.
Zum nächsten Punkt jetzt Abschätzung von Rekurrenzen.
Also diese Laufzeit, die wir hier gesehen haben, bei der Karatsuba
-Hofmann -Multiplikation eignet sich dafür, dass wir das Mastertheorem
anwenden, aber was ist, wenn wir das jetzt nicht sofort könnten?
Das wollen wir uns mal anschauen.
Oft kann man die Lösung erraten, falls man sie nicht erraten kann,
beziehungsweise kann man das Mastertheorem anwenden, um die Lösung
halt rauszubekommen.
Falls das nicht der Fall ist, müssen wir obere Schranken zeigen,
beziehungsweise ist es eine Möglichkeit, obere Schranken zu zeigen.
Ein Beispiel, das wir hier mitgebracht haben, ist mal, wir haben hier
diese folgende Rekurrenz, die erstmal in einer Art und Weise anders
aussieht, als wir es vielleicht kennen.
t von 2n gleich 2 mal t von n plus 2n minus 1, wofür der Basisfall so
aussieht, t von 2 gleich 1.
Und das ist noch eine Randbedingung, n ist eine Zweierpotenz.
Was gilt denn jetzt für die Laufzeit, wenn wir das im O-Kalkül
ausdrücken müssen, Groß-O-Notation zum Beispiel, wobei g von n wie
oben auch im O-Kalkül definiert ist.
Also was für eine Laufzeit hat denn hier diese Rekurrenz?
Wie können wir die Rekurrenz in g von n darstellen?
Und da haben wir einen ersten Versuch, und zwar, dass wir diese
Rekurrenz, die wir gerade gesehen haben, vermuten wir mal, dass t von
n in n² liegt, bzw.
t von n die Laufzeit in n² ist.
Das heißt, wir müssen nach 2 von n zeigen, dass t von 2 von n gleich 2
von n² ist.
Und wie wir das machen, ist, wir setzen das Ganze einfach mal ein, wir
gehen her und sagen, t von 2 von n, dann setzen wir die Rekurrenz ein,
2tn plus 2n minus 1.
Im nächsten Schritt, wir haben ja vermutet, dass t von n gleich n²
ist, das heißt, das setzen wir mal ein.
Das ist gleich eigentlich, kleiner gleich, 2 von 2 mal n² plus 2n
minus 1.
Und dann gehen wir weiter, das Ganze ist kleiner als 2n zum Quadrat
für n größer gleich 1 oder n größer 0.
Und damit haben wir gezeigt, dass in der Tat n² eine obere Schranke
dafür ist.
Also die Rekurrenz kann man abschätzen in t von n kleiner als n².
Aber wir lagen daneben.
Unsere Vermutung, dass es gleich n² ist, ist jetzt nicht gegeben, es
ist kleiner als n².
Das heißt, unter anderem ist die Laufzeit geringer als n².
Das heißt, wir schätzen mal den zweiten Versuch und vermuten, dass
unsere Rekurrenz linear, dass die Laufzeit linear ist, mit einer
Konstante c davor.
Und das heißt, wir müssen wiederum zeigen, gehen wir wieder diesen
Schritt, t von 2 von n gleich Konstante mal 2n.
Und dann setzen wir wieder ein, wie wir es eben gesehen haben.
Und wir erhalten 2c von n plus 2n minus 1.
Und in der Tat ist es diesmal so, dass t von 2n größer ist als 2c mal
n, für n größer gleich 0.
Und das heißt, diese Rekurrenz, diese Abschätzung t von n ist größer
als c von n.
Das heißt, unsere Vermutung war auch wieder falsch.
Wir suchen also eine Schranke, die zwischen linear und quadratisch
liegt, die zwischen c von n und n² liegt.
Und was liegt dazwischen?
Probieren wir doch mal aus.
Wir vermuten, dass mal n log n, n log 2 von n.
Also n log von n zur Basis 2 mal n ist.
Das heißt, wir müssen sie wiederum zeigen.
Das ist wieder derselbe Schritt wie auf den Folien zuvor.
t von 2n gleich 2n log von 2 von n zur Basis 2.
Und wir setzen wieder ein und erhalten hier, wir haben es eingesetzt,
die Vermutung.
Jetzt müssen wir so einen kleinen mathematischen Trick machen.
Wir setzen log von 2 zur Basis 2 ist 1.
Und wir klammern dann, das können wir hier vorschreiben, wir klammern
dann 2 von n aus.
Das heißt, das ist offensichtlich gleich mit der Zeile zuvor, 1.
Und dann können wir mit dem Logarithmengesetz das zusammenfassen.
Das heißt, wir haben hier 2 mal n, Logarithmus von 2 von n zur Basis 2
minus 1.
Und das ist in der Tat kleiner als 2n log von 2 von n zur Basis 2.
Das heißt, unser Algorithmus ist kleiner gleich als n.
Also die Abschätzung t von n ist kleiner gleich n Logarithmus von n
zur Basis 2.
Das Ganze, wir haben ja diese Rekurrenz gerade gesehen, die ist nur
definiert für Zweierpotenzen von n.
Für n gleich 2 auf k, wobei k eine natürliche Zahl ist.
Und das Ganze gilt auch allgemein, das findet ihr auch in der
Literatur und überall, sodass wir die Funktion so schreiben können, t
von n ist gleich 2 mal t von, und jetzt n halbe und wir nehmen, wir
runden das nach unten hin ab auf die nächsten ganzen Zahlen.
Plus n minus 1.
Und wenn man sich das mal genau anschaut, stimmen beide Gleichungen
überein für n gleich 2 hoch k.
Das kann man mal einsetzen und dann kann man sehen, dass diese
Gleichungen genau übereinstimmen für, wenn dieses n nur Zweierpotenzen
sind.
Was wir jetzt zeigen wollen ist, wir haben diese Rekurrenz und wir
wissen, das gilt t von n ist kleiner gleich als t von n plus 1.
Und was passiert für solche n, die genau dazwischen liegen, die jetzt
keine Zweierpotenzen sind, die also zwischen diesem 2 hoch k minus 1
und 2 hoch k liegen.
Da liegen ja auch unter Umständen ganz viele Werte für n dazwischen.
Und was wir hier aus dieser Vorbedingung bekommen ist, dass t von 2
hoch k minus 1 kleiner gleich t von n ist, kleiner gleich t von 2 hoch
k.
Und dann setzen wir wieder ein,
wir haben halt hier gesehen, dass t von n kleiner gleich t hoch 2 von
k ist.
Und setzen das halt jetzt ein, was wir für den Logarithmus
ausgerechnet haben und wir halten c mal 2 hoch k Logarithmus von 2
hoch k halbe.
Und das kann man wiederum abschätzen, dass man hier 2 hoch n einsetzt
und hier hinten auch ein Logarithmus.
Und das kann man anders schreiben,
c1 mal n mal Log von n zur Basis 2 und damit erhalten wir, dass die
Rekurrenz halt in O von n Log n liegt.
Eine allgemeine Folie haben wir hier noch mitgebracht und zwar häufige
Form von Rekurrenzen oder Rekursionsgleichung.
Das heißt, wir haben eine Gleichung der Form t von g von n gleich a
von t von n, wobei dieses a ein Ausdruck ist, der eben die Funktion t
von n und n enthält.
So haben wir es auch gesehen vorhin in den ganzen anderen in der
Gleichung.
Und g ist halt eine Funktion, die von den natürlichen Zahlen in die
natürlichen Zahlen geht und genau den Wachstum der Rekurrenz
definiert.
Also als Beispiel können wir schon angeben, dass g von n t von 2n ist,
das haben wir vorhin gesehen in den Folien zuvor.
Und a von t,n ist gleich eben das, was wir vorher auch gesehen haben,
2 von t von n plus 2n minus 1.
Dann gibt es noch lineare Rekurrenzen, Chartaordnung.
Und die sind dargestellt als so eine Art Linearkombination, also t von
n ist dargestellt als Linearkombination mit Koeffizienten a1 bis ak
und alle Rekurrenzen, die von tn-1 bis tn-k gehen, das sind insgesamt
k viele.
Natürlich müssen wir Anfangswerte ti bestimmen, k Anfangswerte
bestimmen, um die Lineare Rekurrenz Chartaordnung auszurechnen.
Und in der Tat gibt es dafür auch Lösungsmöglichkeiten, die schauen
wir uns heute aber nicht an.
Was wir uns heute anschauen, sind Rekurrenzen aus den Weidenkonker
-Algorithmen.
Und das wird in einem Format genau auch verwendet.
Und die haben diese Formen, t von n gleich a, wie wir es vorhin
gesehen haben, also Art und Weise sehr ähnlich, jetzt noch allgemeiner
gefasst, a mal t von n durch b plus f von n.
Wobei f von n halt ein Funktionswert ist, der von n abhängig ist.
Und kurz und mal habe ich da das Mastertheorem hingeschrieben.
Das heißt, diese Weidenkonker-Algorithmen können oftmals mit dem
Mastertheorem gelöst werden, weil die Formen, dieses f von n, da haben
wir hier diesen Summanden hinten noch, der abhängig ist von n, kann
auf das Mastertheorem uns helfen, Laufzeiten abzuschätzen.
Was ist aber, wenn das nicht der Fall ist?
Und da schauen wir uns jetzt nochmal Variablenwechsel an.
Beispielsweise wenn wir Rekurrenzen haben, die so aussehen, t von n
gleich t von Wurzel aus n plus 1.
Und das Ganze ist definiert für alle n, also eigentlich für alle i.
Und somit für alle n, die diese Form haben, 2 hoch, 2 hoch i.
Und der Basisfall ist definiert als t von 4 gleich 1.
Wie löst man eigentlich Rekurrenzen dieser Form?
Also da können wir unmittelbar das Mastertheorem gar nicht anwenden
und was man macht ist, man substituiert.
Wir haben also diese Rekurrenz jetzt hier, t von Wurzel aus n plus 1.
Und was wir machen, wir nehmen uns eine Variable m her und setzen die
auf Log n.
Also gilt n gleich 2 hoch m.
Hier müsste eigentlich noch eine 2 hin, also wir wollen gerne den
Logarithmus von n zur Basis 2 haben.
Der fehlt hier.
Das Ganze ist offensichtlich äquivalent dann, wenn hier eine 2 steht,
zu n gleich 2 hoch n.
Das heißt wir können jetzt dieses n aus der Wurzel hier ersetzen mit 2
hoch n.
Dann haben wir also t von 2 hoch m ist gleich t von 2 hoch n halbe,
das ist die Wurzel, anders dargestellt, plus 1.
Was machen wir jetzt mit dieser Gleichung?
Naja, der Trick ist jetzt, dass wir Groß S von m, wir definieren jetzt
Groß S von m als t von 2 hoch n.
Was jetzt passiert ist, dass wir Groß S von m gleich...
Und jetzt ersetzen wir diesen Term hier mit, wir haben ja S von m
gleich t von 2 hoch m gesetzt.
Also ersetzen wir dieser Term hier S von m halbe, m halbe plus 1.
Und jetzt sieht diese Rekurrenz in der Art und Weise vielleicht ein
bisschen gefälliger aus.
Und vielleicht weiß schon jemand die Lösung oder hat eine Idee für
eine Lösung, was das sein könnte.
Also was ist die Rekurrenz in Groß O von...
Was man sehen kann ist, bzw.
wenn man diese Gleichung öfter schon mal gesehen hat, diese Art von
Rekurrenzen, dann kann man hergehend sagen, okay, diese Rekurrenz
liegt in Groß O von Log m.
Falls das nicht der Fall ist, na gut, was mache ich dann?
Ich führe das Ganze nochmal aus, die Substitution.
Das funktioniert nämlich genauso.
Wir führen die Substitution eben, wie gesagt, nochmal aus.
Das heißt, wir setzen uns diesmal eine Variable p als Log von m zur
Basis 2.
Machen das Ganze nochmal, das Ganze, was wir eben gemacht haben.
Damit erhalten wir das Äquivalent zu 2 hoch p gleich m.
Und dann setzen wir s von... m ist 2 hoch p.
Hier setzen wir 2 hoch p ein, ist gleich s von 2 hoch p minus 1.
Das ist dieses Halbe hier, mal 2 hoch minus 1.
Das ergibt sich zu s von 2 hoch p minus 1 plus 1.
Dann definieren wir uns ein Groß U von p und sagen, dass es s von m
gilt.
s von m ist aber wiederum gleich s von 2 hoch p, was wiederum
definiert, jetzt gucken wir uns dieses p von p minus 1 an, U von p
minus 1 plus 1, ja gut, und U von p gleich U von p minus 1 plus 1.
Wenn wir diese Rekurrenz auflösen, wissen wir, dass das in U von p
liegt.
Und dann setzen wir es rückwärts ein.
Also wir gehen her und wir setzen das rückwärts, wir setzen dieses p.
Für p haben wir ja Log m zur Basis 2 gewählt.
Und wenn wir jetzt das rückwärts einsetzen, erhalten wir nämlich genau
s von m ist gleich U von Log m.
Okay.
Dann setzen wir wieder rückwärts ein, die zweite Stufe, also wieder
zurück.
Und hier oben haben wir nochmal hingeschrieben, was wir alles jetzt
beisammen haben.
Dann haben wir T von n ist gleich T von Wurzel n plus 1 und m ist
gleich Log n.
Und dieses s von m, was wir uns definiert haben mit s m halbe plus 1.
Und wir wissen, dass s m gleich Groß O von Log m ist.
Und das liefert für n gleich 2 hoch 2 hoch i.
Liefert das genau.
T von n, das ist das, was wir bestimmen wollen, ist gleich T von 2
hoch m.
Wir haben für n das eingesetzt hier oben, die gleichen gilt.
Das heißt, T von 2 hoch m ist gleich s von m.
Das haben wir so definiert.
Und s von m wissen wir ist O von Log von n.
Und jetzt müssen wir nur noch m ersetzen.
Das heißt, wir erhalten O von Log von n.
Okay, das war der Variablenwechsel.
Und machen wir jetzt hier den Break und ich gebe an Christian.
Ich habe euch zwei Beispiele mitgebracht zu Inhalten, die schon in der
Vorlesung dran waren.
Das erste ist die amortisierte Laufzeitanalyse am Beispiel eines
Binärzählers.
Und das zweite ist ein Beispiel zum Platzverbrauch von Unbounded
Arrays.
Die amortisierte Laufzeitanalyse ist ziemlich wichtig, sicher auch
klausurrelevant.
Deswegen dieses zusätzliche Beispiel dazu.
Hier ein Beispiel von einem einfachen Binärzähler.
Einfach eine Zählvariable, die von 0 bis m hochzählt, allerdings in
Binärdarstellung.
Wir fangen bei 0 an.
Links ist die Binärdarstellung, rechts ist die Dezimaldarstellung,
ziemlich einfach.
Allgemein ergibt sich der Wert der Variable aus den Binärstellen Beta
i als Summe über Beta i mal 2 hoch i.
Wie könnte man das Hochzählen eines solchen Zählers implementieren?
Zum Beispiel mit dieser Funktion Binary Increment.
Im ersten Schritt addiert sie erstmal auf die erste Stelle eine 1
drauf.
Es ist klar, dass für diesen Binärzähler gelten muss, dass alle
Stellen entweder 0 oder 1 sind.
Alle Beta i entweder 0 oder 1.
Die 10 Variante wird zunächst mal verletzt, also es kann sein, dass
die Stelle zunächst mal 2 wird.
Um das zu korrigieren, braucht man diese Wildschleife darunter.
Falls Beta i 2 ist, wird diese Stelle auf 0 gesetzt und auf die
nächste Stelle wird 1 drauf addiert.
Und das so lange, bis alle Stellen wieder der In-Variante genügen.
Hier mal live ein Beispiel.
Wir dehnen auf diesem Zähler jetzt mal 1 drauf, fangen mit der ersten
Stelle an.
Da wird ein 2 draus, die In-Variante ist verletzt, wird durch 0
ersetzt und diese 2 schiebt sich also so durch, bis sie an die nächste
Nullstelle ankommt und da wieder eine 1 steht.
Damit ist der Zähler wieder korrekt.
Damit ist klar, dass das Verfahren korrekt ist.
Wie sieht es denn mit der Laufzeit aus?
Was für Kosten zählen wir da eigentlich?
Unser Modell ist, dass die Operation, deren Kosten wir zählen, dieses
Bitflip ist.
Also wir nehmen an, dass ein Bitflip Kosten 1 hat.
Dann zählen wir jetzt für dieses Beispiel mal die Anzahl der Bitflips
durch und das ist erstaunlich viel.
Das ist O von Log M.
Wir dehnen nur 1 dazu durch den Zähler und mussten trotzdem Log M
Bitflips machen.
Unerwartet hoch.
Man würde ja denken, dass das Addieren plus 1 eine sehr schnelle
Operation ist, die in konstanter Zeit funktioniert.
Allerdings haben wir jetzt Worst Case Komplexität O von Log M und das
ist nicht so schön.
Man kann allerdings zeigen, dass diese teuren Worst Case Operationen
so selten sind, dass sie aufgewogen werden von den anderen, viel
häufigeren und günstigeren Operationen.
Und genau das ist die Idee bei der amortisierten Laufzeitanalyse.
Wir haben ein Kostenmodell.
Wir nehmen an, dass T von M die Gesamtkosten für M Operationen sind
und die amortisierten Kosten sind einfach T von M durch M.
An der Stelle eine kurze Quizfrage.
Wer denkt, dass die amortisierten Kosten einer Increment Operation O
von 1 sind, also konstant?
Fast niemand.
Ein paar.
Wer denkt, dass die amortisierten Kosten einer Increment Operation O
von Log M sind?
Fast auch niemand.
Wir haben ja schon gesehen, dass die Worst Case Komplexität O von Log
M ist.
Deswegen muss natürlich A die Antwort sein.
Amortisiert ist eine Einfügeoperation in konstanter Zeit machbar.
Und das zeigen wir jetzt mal mit der amortisierten Analyse.
Es gibt im Wesentlichen zwei Methoden bei der amortisierten Analyse.
Das erste ist die sogenannte Aggregatmethode und das zweite ist die
sogenannte Bankkontomethode.
Ich fange mal mit der Aggregatmethode an.
Was wir da machen, ist, dass wir T von M direkt ausrechnen.
Das geht manchmal, in diesem Fall geht das ganz gut.
Was sind also die Kosten von den einzelnen Operationen?
Die erste Operation von 0 auf 1 flippen, flippt nur 1 Bit, kostet 1.
Die zweite flippt schon 2 Bits, kostet 2.
Die dritte wieder nur 1 und so weiter in dieser Reihe hier links.
Was wir uns jetzt schauen, ist, wir schauen uns die Kosten pro Stelle
an.
Also wie oft wird eine Stelle geflippt?
Und wir beobachten, dass die Stelle Beta 0 jedes Mal geflippt wird.
Beim Operationen also M mal.
Die zweite Stelle wird nur in dem zweiten Fall geflippt, also M halbe
und so weiter.
Wenn man das jetzt aufsummiert, kann man das durch diese Summe hier
abschätzen.
Und das ist dann gerade 2M.
Und wenn wir 2M durch 2 teilen, ist das eben 2 und das ist genau
konstant.
So, das ist die Aggregatmethode.
Es gibt noch eine zweite Methode, die auch in der Vorlesung behandelt
wurde.
Das ist die sogenannte Bankkontomethode oder auch Versicherungsmethode
genannt.
Hier sehen wir die Laufzeiten der einzelnen Operationen als eine Art
Gebühren an, die der Algorithmus zu bezahlen hat.
Wir sagen, dass der Algorithmus vor jeder Operation ein bestimmtes
Gehalt erhält.
Und was wir zeigen wollen, ist, dass der Algorithmus alle Operationen
auch von diesem Gehalt bezahlen kann.
Also nie sein Konto überzieht.
Er muss also bei günstigen Operationen etwas auf sein Konto legen,
etwas ansparen, um davon dann die teuren Operationen bezahlen zu
können.
Um das zu demonstrieren, muss man ein Gehalt G finden, mit dem das
funktioniert.
Das machen wir jetzt mal in diesem Beispiel.
Hier kann man zeigen, dass man mit einem Gehalt von zwei Chips, also
zwei Tokens, pro Increment-Operation auskommt.
Warum ist das so?
Man kann sich überlegen, dass der Zählvorgang bei so einem Increment
genau ein Bit auf eins setzt.
Das heißt, mindestens und maximal wird ein Bit auf eins gesetzt.
Und diesen Flip zahlen wir mit einem Chip ab.
Man kann sich weiter überlegen, dass irgendwann dieses Eins-Bit auch
wieder auf null gesetzt werden muss.
Also mit dem zweiten Chip, den wir bekommen, den wir ansparen, können
wir dieses Zurücksetzen auf null bezahlen.
Warum klappt das?
Man kann sich eine Invariante überlegen, dass der Kontostand, den man
aktuell gespart hat, immer gleich der Anzahl der Eins-Bits ist, die im
Moment gesetzt sind.
Und dann ist klar, wenn man irgendwann eine teure Operation hat, wo
man die alle wieder auf null setzen muss, dass man das auch bezahlen
kann.
Man kann diese Invariante beweisen mit Induktion, das überspringen wir
an dieser Stelle.
Um das anschaulich zu machen, noch ein paar Plots dazu.
Einfach für dieses Binary Increment mal die Kosten zu plotten.
Hier die Kosten pro Operation.
Da sieht man, es gibt viele Operationen, die sehr günstig sind, die
nur eins kosten.
Und es gibt dann immer wieder zwischendrin die teurer werdenden
Operationen.
Wenn man das jetzt mal aufsummiert bis zu einem bestimmten M, also
quasi den Summenplot von dem Plot vorherbilden, dann sieht man, es
steigt schon ziemlich stark an.
Allerdings, wie wir gezeigt haben, nicht stärker als die Gerade mit
der Steigung 2, also 2M.
Es bleibt immer drunter.
Und im nächsten Plot teilen wir jetzt mal TM durch M und sehen, dass
das immer durch 2 begrenzt ist.
Okay, das war das Beispiel zur amortisierten Analyse.
Im nächsten Beispiel geht es dann um Unbounded Arrays.
Also in der Vorlesung hatten Sie ja Unbounded Arrays bereits
kennengelernt, die dynamisch wachsen, wenn wir dort Elemente einfügen.
Und hier in diesem Beispiel geht es darum, abzuschätzen, wie viel
Speicherplatz man eigentlich im Worst Case, im allerschlimmsten Fall
braucht, gleichzeitig um N Elemente zu speichern.
Also es darf eine beliebige Folge von Pushback- und Popback
-Operationen ablaufen auf diesem Array.
Und was ist der Speicherverbrauch im schlimmsten Fall, um N Elemente
zu speichern.
Und hier gibt es noch vier mögliche Antworten und dazu würde ich auch
gerne wieder eine Umfrage machen.
Wer denkt, dass der Worst Case Speicherplatz 2N ist?
3N?
Ein paar?
Okay, 4N?
Ja, genauso viele.
Und wer glaubt, dass wir den sechsfachen Speicherplatz im Worst Case
brauchen?
Einer?
Okay, einer.
Gut, schauen wir mal was passiert.
Schauen wir mal das unbounded Array live an.
Also ich füge hier ein paar Elemente ein.
Jedes Mal, wenn es voll läuft, verdoppel ich die Größe.
So, das Array ist voll bis hier und jetzt wollen wir ein weiteres
Element zufügen.
Das heißt, wir brauchen ein Reallocate auf die doppelte Größe.
Und genau in dem Moment dieses Vergrößerungsschritts haben wir sowohl
das alte Array als auch das neue Array allokiert der Größe 2N.
Also brauche ich zu diesem Zeitpunkt schon mal 3N Speicher, um diese
Reallocate Operation durchzuführen.
Also in dem Fall sieht es so aus, als wäre Antwort B richtig.
Das bedeutet auch, schon in diesem Fall sieht man, dass wenn ich vorab
weiß, wie viel Platz ich für mein Array brauche, wie viele Elemente
ich speichern werde, dass es in diesem Fall sehr viel besser ist, ein
bounded Array zu benutzen und das vorzuallozieren, denn dadurch spare
ich schon mal in Faktor 3 einen Speicherplatz.
Soweit Antwort B, allerdings es geht weiter, es wird schlimmer als
das.
Bisher haben wir nur Elemente eingefügt, was passiert denn, wenn ich
jetzt Elemente wieder rausnehme?
Jetzt habe ich das zuletzt zugefügte Element wieder rausgenommen.
Jetzt noch eine kleine Zwischenfrage, warum schrumpft man denn nicht
sofort wieder das Array?
Es verspendet doch jetzt Speicherplatz, man könnte jetzt ja wieder
halbieren.
Der Grund ist natürlich, dass man die Zukunft nicht kennt, welche
Pushback -Popback-Operationen darauf wieder ausgeführt werden.
Wenn jetzt wieder ein Pushback kommt, müsste ich ja wieder ein
Reallocate aufrufen und eine Folge von N solcher Popback-Pushback
-Operationen würde einem quadratische Laufzeit liefern, was natürlich
auf jeden Fall vermieden werden muss.
Deswegen hatten wir in der Vorlesung schon gehört, dass wir erst dann
das Array schrumpfen, wenn wir bei einem Viertel der Kapazität
angekommen sind.
Das heißt, nehmen wir an, durch ein paar Popback-Operationen sind wir
jetzt kurz vor dem Zustand, wo wir das Array wieder schrumpfen würden.
Das heißt, hier sind nur noch vier Elemente gefüllt, die Arraygröße
wird halbiert.
Und genau zu dem Zeitpunkt, wo diese Schrumpf-Operation jetzt
stattfindet, habe ich den Platzverbrauch von 4n.
Also noch ein schlimmerer Faktor als vorher.
In dem Fall wäre dann Antwort D richtig gewesen.
Beziehungsweise Antwort C.
Hier ist ein Fehler in der Info.
Es geht allerdings noch schlimmer.
In dem Moment, wo ich das Array schrumpfe, habe ich ja sowohl das alte
Array, der Größe 4n, und ich habe das neue Array, das ich auf die
Größe 2n allozieren muss.
Also in dem Fall habe ich jetzt für diese n gleich 4 Elemente
Speicherplatz 6n verbraucht.
Und das ist jetzt der Worst Case.
Also die eine Person, die gesagt hat, Antwort D ist richtig, hat in
dem Fall recht.
Im Worst Case 6n Speicherplatz.
Das Ganze gilt natürlich nur, wenn ich keine Speicherverwaltung habe,
die mir so eine Schrumpf-Operation bietet, wo das ohne Umkopieren
funktioniert.
Das wäre auch denkbar.
Allerdings nehmen wir an, dass das Schrumpfen in diesem Fall nur
dadurch funktioniert, dass wir ein neues Array anlegen und die alten
Elemente rüber kopieren.
Das heißt also, wir haben diese zwei Parameter, diese zwei Konstanten,
mit denen wir spielen können.
Wenn mein Array voll ist, um wie viel vergrößere ich das?
Und wenn mein Array leerer wird, wann lasse ich es wieder schrumpfen?
Und diese beiden Parameter liefern uns einen Trade-Off zwischen dem
Platzverbrauch und der Geschwindigkeit.
Im Allgemeinen können wir von dem Vergrößerungsfaktor Beta sprechen,
bei uns bisher immer zwei.
Und eine Schranke für die Verkleinerung, Alpha, bei uns bisher immer
vier.
Sobald ich hier noch ein Viertel des Arrays belegt habe, wurde die
Arraygröße halbiert.
In der verallgemeinerten Version sieht das so aus, ich reduziere Beta
mal n Elemente, sobald das Array voll ist.
Und ich verkleinere, wenn mein aktueller Fillstand Alpha mal n kleiner
als die Arraygröße ist.
Und was man zeigen kann, ist, dass die amortisierten Laufzeiten
asymptotisch gleich bleiben, wenn Beta größer 1 ist und Alpha größer
Beta.
Wenn ich jetzt Alpha und Beta größer mache, dann bin ich schneller, da
ich mehr konstante Zeitoperationen machen kann, bevor ein Reallocate
notwendig wird.
Andererseits benötige ich auch mehr Speicherplatz.
Analog dazu, wenn man Beta und Alpha kleiner wählt, dann ist man
langsamer, dann benötigt aber weniger Speicherplatz.
Und mit diesen beiden Parametern kann man diesen Tradeoff zwischen
Speicherplatz und Geschwindigkeit beim Unbounded Array
parametrisieren.
Okay, das war auch schon dieses Beispiel zum Unbounded Array.
Und damit sind wir fertig mit der Übung für heute.