Wir hatten in der letzten Stunde uns die doppelt verketteten Listen
angeschaut, das sind die hier.
Und jetzt können wir mal zurückgehen, welche Operationen gibt es so
auf solchen Sequenzdatenstrukturen, was haben wir da gelernt?
Also was wir schon mal sehen, ist fast alles hier konstanter Aufwand.
Also in gewisser Weise sind diese doppelt verketteten Listen die
flexibelste Datenstruktur zur Repräsentation von Sequenzen.
Das Einzige, was nicht konstant geht, ist hier das Find Next, aber das
sieht man, also die anderen haben es noch nicht kennengelernt, aber da
ist offenbar so, das kann auch nicht besser gehen, wenn ich sage, ich
habe eine ungeordnete Liste und ich suche irgendwas, da muss ich halt
alles angucken.
Das Einzige, wo wir einen Nachteil haben, ist bei dem Zugriff über die
Position.
Also die Frage war, was diese Dinger bedeuten, das kommt später, also
ich bin hier nur in dieser Spalte.
Aber wenn Sie 10 Minuten warten, erkläre ich Ihnen, was S-List ist,
wenn Sie 30 Minuten warten, erkläre ich Ihnen, was U-Array ist und C
-Array kommt dann...
Also wichtig ist, dass man diese beiden Spalten hier jetzt vielleicht
schon eine Idee hat, worum es da geht.
Bei einer verketteten Listen-Datenstruktur ist halt die Achillesferse
der Zugriff über die Position.
Weil ich alles nur über diesen Next-Zeiger erreiche, muss ich mich
dann halt vom Anfang entsprechend viele Stücke bis zu der Position
hinhangeln, was natürlich langsam ist, alles andere geht schnell,
insbesondere hier auch sowas wie Remove, was man bei anderen
Datenstrukturen im Allgemeinen nicht hat.
Man kann sowohl am Anfang als auch am Ende beliebige Elemente einfügen
und löschen und man kann sogar ganze Listen konkatenieren in
konstanter Zeit, auch wenn die beliebig lang sind.
Gibt es dazu Fragen noch?
Diese List-Items, ganz wichtig war, dass wir diese super einfache
Datenstruktur in Variante hatten und um die wirklich universell zu
garantieren, hatten wir dann diese Dummy-Header eingeführt, die uns
sehr viele Vereinfachungen eingebracht haben.
Dann hatten wir halt eine entsprechende Listen-Klasse dafür im
Pseudocode vorgestellt, unser Workhorse war sozusagen die Operation
Splice.
Nehme eine Teilliste, schneide eine Teilliste irgendwo heraus und
setze sie woanders wieder rein.
Damit konnte man dann so Sachen wie MoveAfter, MoveToFront, MoveToBack
implementieren.
Ein bisschen zusätzliche Arbeit brauchte man bezüglich
Speicherverwaltung.
Da hatten wir gesagt, wir machen jetzt hier zur Demonstration eine
relativ einfache Lösung über eine Freiliste, wo dann halt nicht mehr
benötigte Listen-Items reingehängt werden und wenn die halt leer ist,
dann wird über die eigentliche Speicherverwaltung der
Programmiersprache halt frische Items besorgt, sozusagen.
Ja, auch Konkatenieren oder Lehren waren dann Einzeiler.
Beim Suchen hatten wir einen Trick kennengelernt, wie man sogenannte
Wächterelemente einsetzt und das war dann die einzige Stelle, an der
wir dieses Elementobjekt für das Dummy-Item tatsächlich auch benutzt
haben.
Ansonsten war immer egal, was da drin steht.
So, ja, dann war da noch so ein Beispiel, Listenlängen können wir
explizit mitverwalten oder nicht und was davon besser ist, hängt halt
davon ab, welche Operationen man wie oft benötigt.
So, dann möchte ich weitermachen mit einer Variante von
doppeltverketteten Listen, nämlich einfachverketteten Listen, auch als
ein allgemeines Beispiel dafür, wie gehe ich überhaupt mit
verschiedenen Varianten von Datenstrukturen um, wie mache ich mir
darüber Gedanken, wie ich Vor- und Nachteile abwäge und so.
Also die Idee ist hier, wir haben jetzt die List-Items, aber wir
speichern nur noch den Nachfolger, nicht mehr den Vorgänger.
Es gibt weiterhin die Dummy-Items, die halt jetzt als Nachfolger das
erste Element haben.
Und insgesamt bilden die wieder eine zyklisch verkettete Liste.
Ich werde dann gleich vorstellen, wie sich dann die Operationen, die
wir unterstützen, verändern und wie die Implementierungen davon sich
verändern, das ist aber alles relativ simpel.
Das heißt, ich hoffe, ich kann jetzt schon so ein bisschen allgemeiner
diskutieren, Vor- und Nachteile.
Offenbar brauchen wir weniger Speicherplatz, weil wir die
Vorgängerzeiger nicht mehr speichern.
Und unter Umständen kann das auch einen Zeitvorteil bedeuten, weil wir
halt entsprechend weniger Daten zugreifen, entsprechend weniger Daten
im Cache Platz belegen und damit andere wichtige Daten verdrängen und
so weiter.
Ich habe den Eindruck, der Lärmpegel ist ein bisschen hoch, da jetzt
zumindest die meisten da sind, sollten wir vielleicht versuchen, das
wieder ein bisschen zu senken.
Andererseits kann man bestimmte Dinge halt nicht so gut.
Überlegen wir uns zum Beispiel mal einen Remove.
Da war das bei den doppeltverketteten Listen so, ich habe einen Zeiger
übergeben auf ein Item, das ich löschen will und dann konnte ich das
da ziemlich problemlos rausschneiden.
Wenn ich jetzt zum Beispiel dieses Ding löschen will, dann habe ich
ein Problem, weil ich müsste ja den Vorgänger kennen, um dessen
Nachfolger hier auf das nächste zeigen zu lassen.
Also um dieses Element hier zu überspringen.
Aber der Vorgänger ist hier nicht explizit gespeichert.
Den jetzt zu bestimmen, nur mithilfe der Nachfolgerpointer, würde
bedeuten, einmal um die ganze Liste rumzulaufen.
Und das ist natürlich teuer, kostet Zeit, linear in der Größe der
Liste und ich hätte es gerne in konstanter Zeit.
Das geht aber so nicht.
Wenn man jetzt wirklich löschen will, kann man sich behelfen mit einem
etwas merkwürdigen Interface.
Ich definiere nämlich nicht das Element, das ich löschen will, sondern
dessen Vorgänger als Parameter.
Und das wäre dann eine Operation, die man Remove After nennen könnte.
Hier ist eine Position, bitte lösche das Element nach dieser Position.
Nur leider ist das oft nicht das, was man wirklich haben will.
Weil aus dem Anwendungskontext nur rausfällt, was man löschen will und
nicht, was der Vorgänger in dieser Liste ist.
Können wir uns auch mal überlegen, was wäre denn die
Datenstrukturinvariante für einfach verkettete Listen?
Die konnte ich ja bei doppeltverketteten Listen einfach als einen
Ausdruck hinschreiben, der sich auch in konstanter Zeit immer
überprüfen lässt.
Hier ist es nicht so einfach, ich habe mich jetzt mal versucht, das
mathematisch erstmal hinzuschreiben.
Wir definieren einen Graphen G, dessen Knotenmenge sind halt die Items
und dessen Kantenmenge sind halt gerade diese Zeiger.
Also wenn ich ein Item U habe, dann gibt es eine Kante U, U Punkt Next
in diesem Graphen.
Offenbar ist das ein Graphen mit einem Ausgangsgrad von 1, das folgt
aus der Definition von E.
Ich will natürlich, das ist aber eine reine Typprüfgeschichte, dass
dieses Next immer auf ein Item zeigt, ich will auch keine Nullzeiger.
Und was ich eigentlich zusätzlich haben will, ist, dass der
Eingangsgrad auch 1 ist.
Man könnte hier ja problemlos mehrere Items auf den gleichen
Nachfolger zeigen lassen, aber das ist klar, dass das dann irgendwann
zu einem Problem führt.
Das können wir jetzt halt auch so schreiben, Eingangsgrad in dem
Graphen G ist 1, oder gleichbedeutend damit, der Graph ist eigentlich
eine Kollektion von Kreisen, der einzige gerichtete Graph, bei dem
alle Knoten Eingangsgrad 1 und Ausgangsgrad haben, besteht aus einem
oder mehreren Kreisen, gerichteten Kreisen, aber das ist halt eine
Bedingung, die wir jetzt nicht effizient testen können während der
Laufzeit.
Das muss uns aber nicht unbedingt daran hindern, das jetzt als
Spezifikation mit hinzuschreiben.
Das wird man dann nicht routinemäßig immer mitlaufen lassen, diesen
Test, aber wie gesagt, hinschreiben kann man es, und es ist eben auch
ganz wichtig, um den Entwurf präzise zu machen, und wenn man später
Dinge beweisen will, hilft einem das halt auch.
Gibt's Fragen zu der Definition von einfach verketteten Listen?
Okay.
Ja, dann hier wieder unsere wichtigste Operation, das Splice.
Da war es ja bei dem Doppeltverketteten Listen so, dass wir so einen
Bereich A bis B spezifiziert haben, das geht jetzt nicht mehr, weil
wir müssen jetzt den Vorgänger von A, A' spezifizieren, also wenn wir
hier sagen, Splice A' B, T, dann heißt das, dass der Bereich, der vom
Nachfolger von A' bis zu B geht, wird hinter T eingehängt.
Der gleiche Grund wie bei diesem Remove After, dann kann man sehr
übersichtlich das hier ja hinschreiben, das ist jetzt vielleicht auch
eine Pseudocode-Spezialität, die Sie noch nicht so wahrgenommen haben,
wir hatten das einmal schon bei der Potenzierungsfunktion drin, aber
hier ist das jetzt besonders wichtig, wir haben so eine
Vektorzuweisung hier, die Semantik davon ist eine parallele Zuweisung,
also wir lesen erst, also eine Möglichkeit, so eine Zuweisung hier zu
implementieren, besteht darin, erstmal alle rechten Seiten auszulesen,
in temporären Variablen zu speichern und dann erst die Zuweisung an
die linken Seiten zu machen.
Damit kann man sich unübersichtlichere Formulierungen, die dann
explizit irgendwelche temporären Variablen enthalten, sparen, man hat
hier also wieder eine abstraktere Formulierung des Pseudocodes, es
gibt glaube ich auch Programmiersprachen, die sowas können, aber die
Standardprogrammiersprachen, da muss man das glaube ich immer noch von
Hand hinschreiben oder hat irgendwelche komplizierten Konstrukte, die
man dann lieber nicht benutzt.
Ganz witzig, was Splice hier macht, wir wollen ja A bis B
rausschneiden, also wird der Nachfolger von A' auf B' gesetzt, also
den Nachfolger von B.
Andererseits sollen wir das AB hier zwischen T und T' wieder
einsetzen, dafür setzen wir den Nachfolger von T auf A und den
Nachfolger von B auf T'.
Also eigentlich noch viel einfacher als bei den doppeltverketteten
Listen, das kommt daher, dass wir halb so viel Zeiger hier verändern
müssen, nur drei, nachdem wir diese parallele Zuweisung verwendet
haben.
Was auch ganz witzig ist, das A'next steht hier einen weiter unten auf
der rechten Seite, das T'next steht hier einen weiter unten, dieser
drei Zeiger, die wir da vornehmen.
Wäre vielleicht auch eine einfache Übungsaufgabe, überlegen Sie sich
mal, wie man diese Zuweisung hier durchführt mit nur einem einzigen
temporären Variablen.
Ich habe Ihnen ja gesagt, eine naive Variable zu verwenden, wie macht
man das mit einer temporären Variable und wie mache ich das für
beliebige zyklische Verschiebungen?
Weil solche Sachen treten eigentlich immer wieder auf, ich finde es
hier ein bisschen überraschend, dass so eine relativ strukturierte,
komplizierte Operation wie Splice einfach eine zyklische Verschiebung
von drei Pointern ist.
Interessante Beobachtung, würde ich aber jetzt auch keine tiefere
Bedeutung reininterpretieren.
Oder fällt jemandem was dazu ein, noch Fragen?
Jetzt können wir uns halt überlegen, wieder anhand dieser Liste,
welche Operationen können wir in konstanter Zeit implementieren.
Wie gesagt, wir haben ja hier dieses Dummy-Element sowieso schon
eingeführt, man kann sich überlegen, dass damit ein Push-Front, also
Einfügen am Anfang sehr einfach ist, weil das ist ja wie ein Insert
-After diesem Head-Element.
Wir können natürlich auch das erste Element löschen, indem wir das
einfach überspringen.
Das heißt, die Operationen am Anfang sind ganz leicht, aber am Ende
ist es irgendwie schwierig, weil wir gar keinen expliziten Zeiger auf
das Ende haben.
Da kann man sich allerdings insofern behelfen, dass man sagt, okay, in
dieser Klasse Singly-Link-List speichern wir noch einen zusätzlichen
Zeiger auf das letzte Item.
Und dann kann man auch das Push-Back machen, nämlich indem man dann
sagt, Insert-After diesem Ding.
Und dann hat man hier ein neues Item und setzt entsprechend diesen
Zeiger auf das neue Ende.
Das ist insofern wichtig, als das bedeutet, dass Sie mit einer einfach
verketteten Liste nicht nur einen Stapel implementieren können,
nämlich einfach indem Sie Einfügen und Löschen immer am Anfang machen,
sondern auch eine FIFO-Queue, also eine First-In, First-Out
-Warteschlange, wo Sie am Anfang einfügen und am Ende löschen.
Entschuldigung.
Sie würden dann am Ende einfügen und am Anfang löschen.
Das können Sie machen und indem Sie die Semantik einmal rumdrehen,
haben Sie dann auch eine Warteschlange mit der normalen Semantik.
Das ist wichtig, weil diese Warteschlangen braucht man ziemlich oft in
Anwendungen und da will man natürlich keine übermäßig komplizierte
Datenstruktur haben,
die nur sehr begrenzte Operationen verlangt.
Nämlich an einem Ende einfügen und am anderen Ende löschen.
Wie gesagt, dann speichern Sie wieder Platz und Zeit, indem Sie
lediglich eine einfach verkettete Liste verwenden.
Was jetzt leider nicht geht, ist das Popback.
Weil dafür müssten Sie ja den Vorgänger vom letzten Element kennen.
Wir haben aber hier nur das letzte Element selber abgespeichert und
man kann sich überlegen, dass es auch nicht helfen würde, hier einen
zweiten Zeiger zu speichern, der auf das zweitletzte Element zeigt.
Dann könnten Sie zwar einmal das Ding hier löschen, aber dann ist ja
das zweitletzte Element das neue letzte und welches bitte ist dann das
neue zweitletzte Element.
Also wir haben hier tatsächlich eine fundamentale Beschränkung.
Wir können nicht alle vier Operationen Pushfront, Popfront, Pushback,
Popback gleichzeitig unterstützen mit doppelt verketteten Lists.
Mit einfach verketteten Lists, Entschuldigung.
Also gehen wir vielleicht nochmal auf diese Tabelle.
Da.
Also jetzt kennen Sie nicht nur diese Spalte, sondern auch diese S
-List, die Singling-List.
Gucken wir uns die Unterschiede zwischen den beiden Dingern an, die
bestehen hier beim Insert.
Da habe ich nur ein Insert-After, beim Remove habe ich nur ein Remove
-After.
Und das Popback fehlt.
Das sind die wichtigsten Unterschiede bei dieser Liste von Standard
-Operationen.
Aber immerhin, rein numerisch gesehen, wirkt das so, als wären
Singling -List fast genauso mächtig wie Doubling-List.
Mit Ausnahme einiger weniger Operationen und dafür spare ich Platz und
Zeit.
Das sind also beides sinnvolle Datenstrukturen.
Wir werden die Singling-List zum Beispiel dann auch im nächsten
Kapitel bei Hashtabellen wiederfinden, weil wir da auch ein sehr
begrenztes Spektrum von Operationen nur benötigen.
Fragen zu dieser Spalte hier?
Dann können wir jetzt zusammenfassen, was wir über verkettete Listen
gelernt haben.
Also vielleicht auch noch allgemeiner.
Dynamische Datenstrukturen sind ein ganz wichtiges Thema, weil man
damit sehr viele Dinge tun kann.
Verkettete Listen sind nur das einfachste Beispiel dafür.
Wir werden noch komplexere Datenstrukturen kennen, die halt trotzdem
eine ähnliche Idee haben.
Wir haben solche Items, in denen Nutzdaten gespeichert werden, sowie
Zeiger auf andere Items.
Und damit kann man halt sehr viel machen.
Also insbesondere werden wir statt reinen Listen auch baumförmige
Datenstrukturen kennenlernen, zum Beispiel für Suchbäume, damit
verwaltet man sortierte Listen, oder Prioritätslisten.
Damit verwaltet man Listen, die man zwar nicht komplett sortiert hält,
wo man aber jeweils das kleinste Element schnell zugreifen möchte.
Wir haben kennengelernt interessante Beispiele für
Datenstrukturinvarianten und wir haben hoffentlich gelernt, dass die
der Schlüssel zu einfachen und effizienten Datenstrukturen sind und
eben auch einen formalen Zugang dann ermöglichen.
Wir haben noch allgemeiner, auch jenseits von Datenstrukturen, ein
Beispiel gesehen für Dummy-Elemente und Wächter, die es einem
ermöglichen, Sonderfälle einzusparen.
Das ist eine Technik, die man nicht nur in Datenstrukturen braucht,
sondern auch in vielen Algorithmen oder auch allgemein bei der
Programmierung, selbst wenn man das jetzt nicht als Algorithmus
auffassen würde oder da gar nichts Komplexes, Algorithmisches
passiert.
Und diese Einsparung von Sonderfällen macht halt die Programme
einfacher, lesbarer, testbarer und schneller.
So, gibt es jetzt noch Fragen zu verketteten Listen?
So, dann kommen wir jetzt zu dem zweiten Teil des ersten Kapitels.
Weg von den Keepos hin zu den Keilschrifttafeln, eigentlich noch
einfacher und älter, Arrays.
Das kennen Sie alle als Teil von Programmiersprachen wie Java schon.
Insbesondere sind beschränkte Arrays eigentlich nichts anderes als ein
Stück Hauptspeicher in unserem RAM-Modell.
Wir sagen, okay, dieses Stück Hauptspeicher, da gibt es eine
Anfangsadresse, eine bestimmte Größe und mit ein bisschen
Adressrechnung kann ich das syntaktisch ein bisschen schöner schreiben
als ein Array, wo ich die Elemente zum Beispiel von 0 bis n-1
durchnummeriere bei n Elementen.
Und insbesondere habe ich halt die Operation, gibt mir das it-Element,
kann das in konstanter Zeit mithilfe von Adressrechnung machen.
Also wenn ich eine Basisadresse b habe und einen Index i, dann ist die
Speicheradresse von a i halt b plus i oder allgemeiner b plus Größe
eines Elements mal i oder sowas.
Wir wollen jetzt ein bisschen was Allgemeineres uns anschauen.
Das sind unbeschränkte Felder, Unbounded Arrays.
Da haben wir die zusätzlichen Operationen Pushback und Popback mit der
gleichen Semantik wie bei den verketteten Listen.
Das heißt, wenn wir so ein Array e0 bis en haben, können wir ein neues
Element e am Ende einfügen und dann hat das Ding danach halt n plus 1
Elemente oder in dem Fall sogar n plus 2.
Oder wenn wir Popback sagen, wird das letzte Element gelöscht.
Und wir können zusätzlich noch die Größe abfragen.
Das ist eine Funktionalität, die von den Standardbibliotheken und
auch von Java funktioniert.
Es funktioniert auch so ähnlich, wie hier in der Vorlesung
beschrieben.
Allerdings gibt es, glaube ich, einen Unterschied, zumindest bei c++
und das letzte Mal, als ich geguckt habe, war es so, wenn Sie jetzt
ein großes anbauendes Array aufbauen und es danach wieder stark
schrumpfen lassen, wird kein Speicher freigegeben.
Wir werden hier eine Variante vorstellen, die den Speicher auch wieder
freigibt.
Die insbesondere zu jedem Zeitpunkt höchstens einen konstanten Faktor
mehr Platz braucht, als tatsächlich Elemente gespeichert sind von
diesem logischen Array.
Faktor 4 werden wir uns da als Beispielparameter anschauen.
Gibt es Fragen zur Semantik von...
Vektoren werden dynamisch, Felder sind halbdynamisch, in welchem Sinne
sind Felder halbdynamisch?
Können Sie mir das erklären?
Dann sind sie also gar nicht dynamisch, sondern statisch, oder?
Am Anfang, okay.
Insofern halbdynamisch.
In Fortran-Versionen musste man die Größe schon zur Compile-Zeit
festlegen.
Halbdynamisch oder beschränkt, habe ich das genannt, sind diese
eingebauten Dinger.
Vektoren sind dynamisch, das ist korrekt.
Unbeschränkte Arrays oder Vektor-Datenstrukturen.
Weitere Fragen dazu?
Ja, gucken wir uns mal an, warum braucht man das?
Naja, weil man manchmal nicht von vornherein weiß, auch zur Laufzeit
nicht, wenn ich das Array anlege, wie viel kommt da rein.
Wenn Sie zum Beispiel sagen, jemand übergibt Ihnen einen Dateinamen
und Sie wollen jetzt eine Prozedur haben, die liest diese Datei in ein
Array von Strings.
Aber in der Datei steht halt nicht am Anfang drin, wie viele Zeilen
das sind, also Sie wollen einen String für jede Zeile haben, aber das
steht halt nicht irgendwo am Anfang, sondern es gibt halt irgendwie so
eine End-of-File-Zeile am Ende der Datei, die Ihnen das anzeigt.
Und dann ist es am einfachsten und wohl auch am effizientesten, so
eine Vektordatenstruktur zu nehmen, wo Sie die Zeilen sofort einlesen,
also sofort in dieses Array reinschreiben, beim ersten Mal Durchlesen
der Datei.
Sonst müssten Sie wahrscheinlich sowas machen, irgendwie so ein Zwei
-Pass -Algorithmus, der einmal die Datei komplett durchliest und nur
mitzählt, wie viele Zeilen es gibt, dann das Array allociert und dann
erst einliest.
Dann müssten Sie die Datei aber zweimal lesen.
Und das ist in jedem Fall langsamer, als das sofort zu machen.
Oder wir werden dann etwas abstraktere Beispiele sehen, von
Datenstrukturen wie Stapeln, Warteschlangen und Prioritätslisten, wo
Sie halt eigentlich auch nicht am Anfang schon festlegen wollen, wie
viele Elemente da maximal eingefügt werden, sondern das von sehr
vielen Aspekten der Anwendung abhängen kann.
Gut, gucken wir uns mal die Grundidee an.
Die ist eigentlich super simpel.
Wir wissen schon, wie man beschränkte Felder macht, das ist ein Stück
Hauptspeicher.
Genauso aussehen lassen, wie die statischen Arrays, damit dieser
Befehl, gib mir ein Element des Arrays zurück, mit gegebenen Daten,
eigentlich genauso schnell sein, wie bei den unbeschränkten Arrays.
Das heißt, das ist eine wichtige Designentscheidung, auch was die
Effizienz unserer Programme angeht.
Die Hoffnung ist, wir haben eigentlich nur wenige von diesen
Operationen, die die Größe ändern, und viele, die tatsächlich da
Zugriffe machen.
Und die sollten so schnell wie möglich sein.
Da gibt es auch diese Engineering Prämisse, makes a common case fast.
Macht den schnell, den üblichen Fall schnell, oder den häufigen Fall
schnell.
Gut, wenn wir diese Entwurfsentscheidung getroffen haben, kann man
sich überlegen, wie man das dann genau umsetzt, und da gibt es ein
paar Tricks.
Pushback?
Naja, wir hängen das Element am Ende an.
Also wir schreiben es an eine Speicherstelle, die halt einen weiter
hinten liegt, als vorher das letzte Element.
Können wir machen, wir müssen halt nur aufpassen, wenn dieses Stück
Hauptspeicher, das wir da alloziert haben, nicht groß genug ist.
Und irgendwann passiert das dann ja.
Oder auch, ja, kann man noch drüber reden, passiert das irgendwann?
Können wir gleich mal drüber reden.
Jedenfalls im Standardmodell von Programmiersprachen muss ich halt
diese Größe am Anfang einmal festlegen, aber es könnte darüber hinaus
wachsen.
Und dann ist halt die Idee, wenn das passiert, alloziere ich halt ein
neues Array irgendwo anders, das entsprechend größer ist, kopiere die
Daten um, und dann habe ich wieder Platz.
Und das gleiche Spiel, wenn ich Popbank mache, wenn die Größe kleiner
wird, wenn ich dann in irgendeiner Weise zu viel Platz belege,
verglichen mit dem, was tatsächlich an Nutzdaten gespeichert ist, kann
ich auch irgendwann ein kleineres Array neu anlegen und umkopieren.
Und die naive Art, das zu implementieren, wäre zu sagen, wir haben
immer genau den passenden Platzverbrauch, dann müsste ich aber bei
jeder Pushback- und Popback-Operation so eine Umkopier-Operation
machen.
Und man kann sich überlegen, dass dann zum Beispiel eine Folge von N
Pushback -Operationen quadratisch viel Zeit braucht.
Weil dann würde ja die Ite-Pushback-Operation Zeit O von I brauchen,
also insgesamt O von Summe I gleich 1 bis N bis I.
Das kennen Sie hoffentlich aus HM, das ist gerade I mal I minus 1
halbe, N mal N minus 1 halbe, also Theta N Quadrat.
Und die Frage ist, geht das schneller?
Kann mir das jetzt schon jemand sagen, der noch nicht auf die nächste
Folie geguckt hat, wie geht es schneller?
Grundidee?
Mehr, genau, mehr allocieren, als nur für ein Element benötigt wird,
das ist so die wichtigste Grundidee.
Und das will ich Ihnen jetzt hier vorführen.
Hier haben wir jetzt wieder ein bisschen Pseudocode, also klasse,
unbounded Array, und jetzt wissen Sie auch schon, was U-Array
bedeutet, ja?
Wieder so was Generisches, das kann man parametrisieren mit einem
beliebigen Elementdatentypen.
Und die logische Größe, ja?
Also die Anzahl Nutzdatenelemente, die wir gerade gespeichert haben.
Und es gibt eine Datenstrukturinvariante, die sagt, wir dürfen halt
nie mehr speichern, als wir alloziert haben.
Wir wollen aber auch nicht viel mehr alloziert haben, als wir
gespeichert haben, also Alpha ist glaube ich gleich 4, in dem, was wir
hier machen.
Und dann muss man aber, das hier kann nicht immer gelten, weil wenn
man gar nichts gespeichert hat, will man vielleicht trotzdem erlauben,
irgendwas alloziert zu haben, deshalb ist für N gleich 0, gibt es hier
einen Spezialfall, ein bisschen hässlich, aber haben wir halt so
gemacht.
Und die eigentlichen Nutzdaten stehen dann in einem Array B mit
Indexbereich 0 bis W-1.
Und B ist aber eigentlich ein Zeiger auf dieses Stück Speicher.
Also in C oder Java haben sie halt hier so ein Objekt-U-Array, das
eben besteht aus zwei skalaren Werten und einem Zeiger im Endeffekt.
Und was gibt es für Operationen?
Der Array-Zugriff wird einfach durchgereicht an den Zugriff auf B.
Und da kann man, wenn man will, noch hier so eine Assertion reingeben,
die dann einen Bound-Check durchführt.
Ich darf niemals den Element zugreifen, das kein Nutzdatenobjekt ist.
Also wohlgemerkt, hier würde ein Fehler ausgegeben, wenn ich irgendwas
zwischen N und W zugreife, obwohl das alloziert ist.
Und Size gibt halt einfach diese Größe N zurück.
Gibt es dazu Fragen?
Also die spannenden Operationen kommen jetzt noch.
Wie geht Pushback und Popback?
Hier ist jetzt das Pushback.
Dann habe ich hier mal gleich ein Beispiel auf der rechten Seite als
Kommentar mit reingebaut.
Das ist mit Nutzdaten bereits vollgeschrieben.
Ich kann nichts einfach hintendran schreiben.
Was ich dann mache ist, ich mache eine Realozierung mit doppelter
Größe.
Wenn das nicht der Fall ist, dann ist es trivial, dann schreibe ich
einfach E an die Position BN.
Wohlgemerkt, wir fangen bei 0 an zu adressieren, das heißt, die
Nutzdaten stehen im Moment zwischen 0 und N-1 und jetzt schreibe ich
es halt an die N-te Stelle und ich inkrementiere N.
Der spannende Fall ist natürlich, wie mache ich jetzt dieses
Reallocate?
Das ist hier beschrieben, dem übergebe ich die neue Größe W'.
W wird auf W' gesetzt.
Neues Array B', das halt die Größe W' hat.
Das ist im Moment, am Anfang zeigt das auf uninitialisierte Daten.
Dann kopiere ich den Inhalt des alten Arrays in das neue Array.
Implementieren oder vielleicht mit einem System aufrufen, M-Copy oder
sowas, heißt das in C.
Aber ich hoffe, es ist klar, was gemeint ist.
Und erst, wenn Sie diese Kopieoperation durchgeführt haben, können Sie
das B tatsächlich deallozieren, das alte.
Und dann können Sie erst diesen Pointer hier überschreiben.
Danach zeigt dann halt B auf dieses ausgeweitete Ding.
Also, wohlgemerkt, am Anfang zeigt P hier auf ein Stück Speicher, in
dem 0, 1, 2, 3 drinsteht.
Am Ende zeigt das auch auf ein Speicher, in dem 0, 1, 2, 3 drinsteht.
Aber diese gestrichelten Linien sagen aus, da ist jetzt halt
zusätzlicher Platz.
Und dann würde erst nach diesem Aufruf tatsächlich das nächste Element
geschrieben in dem Beispiel.
Fragen dazu?
Ah, gute Frage.
Unsere Speicherverwaltung im Pseudocode, da haben wir Schlüsselwörter
allocate und dispose.
Allocate heißt Allozieren von Speichern, dispose heißt expliziertes
Deallozieren.
In Java gibt es das ja nicht, da würden Sie das einfach weglassen.
Und die garbage collection würde halt irgendwann merken, dass dieses
Array, auf das B verweist, überhaupt nicht mehr referenziert wird von
irgendeinem Objekt Ihres Programms und das dann in irgendeiner Form
wiederverwenden.
Aber in anderen Programmiersprachen wie C++ müssten Sie ein explizites
dispose aufrufen.
Also dispose ist jetzt auch wieder Pascal-Syntax, ich glaube, wie war
das?
In C ist es free und in C++ delete.
Und Sie können das auch irgendwie mischen.
Und vielleicht habe ich es jetzt auch gerade verwechselt.
Jedenfalls müssen Sie dann explizit sagen, das wird nicht mehr
gebraucht, was es dann ermöglicht, diese Speicherverwaltung etwas
effizienter und vorhersagbarer zu gestalten als in Java.
Aber dafür können Sie auch mehr falsch machen.
Vor allem, wenn Sie das vergessen, kriegen Sie ein sogenanntes
Speicher -Lag.
Es kann sein, dass Ihr Speicher unerklärlich überläuft, obwohl die
Nutzdaten gar nicht so viel sind, weil die Speicherverwaltung nicht
mitgekriegt hat, dass da alle möglichen Daten im Speicher rumliegen,
die keiner mehr braucht.
Weitere Fragen dazu?
Ja, das Popback geht so ähnlich.
Ein leeres Array, da was zu löschen, ist mir nicht so klar, was dann
passiert.
Da verbieten wir das mal.
Ansonsten wird halt n, die Anzahl Nutzdatenobjekte, dekrementiert.
Und dann haben wir hier eine Bedingung, wenn w mehr als viermal so
groß ist, wie die Eingabe und n nicht null ist, dann wird realoziert.
Also hier habe ich ein Beispiel, wo n gleich von 5 auf 4 runtergeht.
Also wir haben hier 0, 1, 2, 3, 4.
Und wir wollen, diese 4 wird jetzt nicht wirklich gelöscht, aber sie
ist sozusagen nicht mehr Teil der erklärten Nutzdaten und sowas Arrays
B.
Deshalb hier dieses gestrichelte.
Und das Ganze ist jetzt, ich glaube 16 Einträge haben wir realoziert.
Und das wäre dann die Grenze, wo man sagt, wir wollen es jetzt
reduzieren auf 8 Einträge.
Im Allgemeinen eine Reduktion von w gleich 4n auf w gleich 2n.
Das wirkt jetzt ein bisschen komisch.
Ich habe gemerkt, dass ich nur ein Viertel meines Platzes brauche.
Das klingt schon sehr verspätet.
Und jetzt sollte man ja meinen, dass es eine gute Idee ist, wenn ich
das gemerkt habe und schon mal Aufwand investiere aufs Realozieren,
das dann auch gleich richtig mache und dann wegen der Nutzdaten kann
mir jemand sagen, was dagegen spricht.
Ja.
Ja,
genau richtig beobachtet.
Also was dann passieren würde, wenn Sie das auf genau die richtige
Größe setzen und dann danach wieder ein Element einfügen, dann wird es
gleich wieder verdoppelt.
Und das ist noch schlimmer, Sie können das beliebig oft wiederholen.
Dann löschen Sie wieder eins, ein Element,
dann würde wieder geschrumpft, wieder verdoppelt, geschrumpft, damit
könnten Sie dann wieder mit N-Operationen einen quadratischen Aufwand
produzieren.
Wir werden gleich sehen, dass wir hier eine beweisbare
Leistungsgarantie kriegen durch diese scheinbar merkwürdigen Regeln
mit dem 4N und 2N.
Frage dazu?
Ja.
Das ist auch eine gute Frage.
Ist dieses 4N, kann man da irgendwas dran tunen oder sowas?
Sie könnten natürlich jetzt hergehen, weitere Operationen definieren,
wie diese Parameter da ändern, wann man umschaltet.
Das wird meistens nicht gemacht, aber was man macht, ist, man hat eine
Resize -Operation, wo man dann sagen kann, jetzt weiß ich plötzlich,
wie groß mein Array maximal wird.
Bitte alloziere es mal auf die Größe und danach passiert dann nichts
mehr oder sowas.
Da kann man sich verschiedene Sachen überlegen.
Wie gesagt, sind auch die Implementierungen in den
Standardbibliotheken so, dass sie überhaupt nicht schrumpfen.
Das heißt, da ist dann nur das Problem, dass es sein könnte, dass man
irgendwie 1025 Elemente gespeichert hat und dann ist halt fast doppelt
so viel Platz alloziert und dann kann man dem auch sagen, bitte jetzt
alloziere mal auf Größe 1025 und dann, weil man weiß, das ist die Ende
der Fahnenstange und dann wird er auch nicht mehr brauchen.
Also da kann man durch Definition geeigneter zusätzlicher Operationen
dafür sorgen, dass hier der Verschnitt nicht zu groß wird.
Aber Sie haben recht, wenn man diese Vektordatenstrukturen naiv
benutzt, muss man damit rechnen, erhebliche Kontrollen...
Sie haben ja hier während des Reallocates haben Sie ja plötzlich zwei
allozierte Arrays und das kann durchaus entscheiden, wann Ihnen die
Speicherallokation um die Ohren fliegt, wenn Sie sehr große
Datenmengen verarbeiten wollen.
Es gibt sicherlich auch noch Datenstrukturen, die ein bisschen
vorsichtiger mit dem Platz umgehen, als diese ganz einfachen Unbounded
Arrays.
Da kann man auch schöne Übungsaufgaben draus machen.
Aber das ist eigentlich eher Gegenstand der Vorlesung Algorithm
Engineering, wo wir dann das noch detaillierter diskutieren, was da
die Trade-offs sind.
Genau, das war die Kürzungsoperation.
Was geht schief, haben wir auch diskutiert.
Ja, ich glaube, das ist jetzt auch ein guter Moment, um auf die Übung
umzuschalten.
Wir haben ja Mittwoch keine Vorlesung und da die Übung jetzt
eigentlich ein bisschen Bedarf ist, diese ganzen Sachen weiter zu
erklären, haben wir uns gedacht, wir sollten die nicht ausfallen
lassen.
Machen wir heute halb Übung, halb Vorlesung.
Und dann geht es in der nächsten Woche wieder normal weiter.
Montags Vorlesung, Mittwoch geteilt Übung und Vorlesung.
Okay, weitere Fragen zu unbeschränkten Arrays?
Okay, dann übergebe ich jetzt an den Christian Schulz.
Dann herzlich willkommen zur zweiten Übung.
Das sieht jetzt so aus, wir sind ja letztes Mal in der Übung nicht
ganz fertig geworden.
Wir machen heute den Rest von dort, machen noch ein paar andere
Beispiele und noch ein bisschen esoterisch am Ende.
Ihr habt wahrscheinlich auch mitbekommen, am Mittwoch ist Feiertag.
Da findet weder Übung noch Vorlesung statt.
Und es finden auch keine Tutorien statt.
Also die, die an diesem Tag ein Tutorium hätten, die bitten wir
einfach, sich in ein anderes Tutorium diese Woche reinzusetzen.
Und am besten das einfach zufällig auswählen, weil sonst hat man ein
Problem mit der Anzahl Studenten in den Tutorien.
Da ist ein Induktionsbeweis, wo ein Fehler zu finden ist.
Und jetzt ist es tatsächlich so, dass in der ersten Version von diesem
Übungsblatt hat sich ein Fehler eingeschlichen, der da nicht hin
sollte.
Aber der ist jetzt behoben, also einfach nochmal das Blatt runterladen
und genau, dann sollte alles richtig sein.
Also als erstes die Frage nochmal, was kann man denn so schönes mit
Graphen modellieren?
Also einfach nochmal auf die Webseite gehen und runterladen.
Nochmal, was kann man denn so schönes mit Graphen modellieren?
Ich habe heute drei Beispiele mitgebracht.
Einmal Graphen färben, dann Routenplanung und Graph-Partitionierung.
Die Frage ist, man hat jetzt irgendwie Europa gegeben und man möchte,
wie so häufig bei Karten, die Länder so färben, dass benachbarte
Länder erstens verschiedene Farben haben und zweitens, dass ich
möglichst wenig Farben brauche, um diese Karte zu färben.
Okay, hier ist, wie man das mit Graphen machen kann.
Also man sagt dann, für jedes Land, was man hier hat, Spanien zum
Beispiel oder Frankreich, fügt man einen Knoten ein und man fügt eine
Kante zwischen diesen Knoten ein, wenn die benachbart sind.
Und das grafentheoretische Problem, was jetzt hier hinter steht, um
das ursprüngliche Problem zu lösen, ist jetzt nichts anderes, als
finde eine Abbildung auf den Knoten in die Zahlen 1 bis K, das sind
hier die Farben, also wir sagen jetzt hier nicht Rot, Blau oder Grün,
sondern wir sagen einfach, das ist die Farbe 1, 2, 3, 4 und 5.
Und diese Abbildung soll zusätzlich die Eigenschaft haben, dass wenn
die Knoten in dem Graphen benachbart sind, dann soll die Farbe
verschieden sein.
Das ist also genau das, was ich gerade gesagt habe.
Wir wollen die Länder so färben, dass benachbarte Länder verschiedene
Farben haben und ein möglichst kleines K, also eine möglichst kleine
Anzahl Farben.
Hier sieht man mal, wie das dann aussieht.
Also wir haben jetzt dieses ursprüngliche Problem
auf der Karte projiziert, auf ein grafentheoretisches Problem haben
wir das hier gelöst.
Das sind jetzt hier drei Farben.
Übrigens gibt es einen Satz, der sagt, beliebige Länderkarten kann ich
mit vier Farben einfärben.
Genau, aber wir haben jetzt dieses Problem hier in diesem Graph-Modell
gelöst und sind dann glücklich wieder mit unserem ursprünglichen
Problem und haben dann die Landkarte eingefärbt.
Ja, ja, genau.
Das ist der Vier-Farben-Satz.
Naja, das können wir ja nachher noch darüber diskutieren.
Eine Färbung mit zwei Farben existiert, das kann man effizient
entscheiden.
Da gibt es, ich glaube, auf dem siebten oder achten Übungsblatt eine
Übungsaufgabe zu.
Die ist ein bisschen versteckt und ein bisschen anders, aber
vielleicht erkennt ihr das ja nachher trotzdem.
Und zu entscheiden, ob ein Graph mit drei Farben zu färben ist, das
ist NP-Vollständig.
Und dann ist das so, immer wenn man so etwas NP-Vollständig, also ein
Problem ist NP-Vollständig sieht und man in der Praxis trotzdem
Lösungen braucht, dann macht man entweder Approximationsalgorithmen,
das lernt man ein bisschen später, generell in der Algorithmik, oder
man benutzt Heuristiken.
Und dieses Problem, was man hier hat, ist übrigens etwas, worüber man
auch Bachelorarbeit schreiben kann.
Bei uns gibt es gerade eine Bachelorarbeit, da soll man sich dann
Algorithmen überlegen, wie das hier gut geht, mit Heuristiken zu
machen.
Das zweite Ding ist Routenplanung.
Ich habe das Straßennetzwerk von Europa zum Beispiel gegeben und ich
möchte jetzt von A nach B kommen.
Und die Frage ist, wie berechne ich so eine Route?
Was sind Modellierungen, was sind Optimierungskriterien?
Hat jemand Ideen für normale Optimierungskriterien aus der Praxis?
Genau, zum Beispiel die kürzeste Route oder was gibt es noch?
Ja.
Genau, und was können Gewichte sein?
Genau, zum Beispiel die Entfernung.
Ganz klassisch will man heutzutage die schnellste Route haben.
Wer will schon 5 Stunden fahren, wenn er auch 3 Stunden brauchen
könnte?
Okay, und dann ist das so, das machen wir auch in der Vorlesung, dann
gibt es einen Algorithmus, der Deichstra hat sich den damals
ausgedacht, mit dem man dieses Problem aus der Praxis wieder lösen
kann.
Also wir haben unser allgemeines Problem, wir modellieren das als
Graph -Problem.
Wir modellieren das als Graph-Problem und haben dann auf diesen
abstrakten Graphen, nachdem wir abstrahiert haben...
Auf diesen abstrakten Problemen können wir einfach unseren Algorithmus
anwenden, ohne über die Anwendung überhaupt nachzudenken.
Also wir kodieren irgendwas rein in den Graphen, haben den
Algorithmus, der uns den kürzesten Weg liefert und sind dann
glücklich.
Genau, und dann hier ist noch eine ganz interessante Geschichte, also
vor ungefähr 10 Jahren war dieser Algorithmus von Deichstra so
ziemlich das Schnellste, was man machen konnte.
Es gab damals noch diese ganzen Routenplaner für die Autos, wo man
seine Route eintippt und dann rechnet dieses Gerät 3, 4, 5 Sekunden
lang und dann hat man die kürzeste Strecke.
Was dann in den letzten 10 Jahren passiert ist, es gibt so eine
Methodik, die nennt sich Algorithm Engineering, das hat der Professor
Sanders, glaube ich, schon gesagt, das heißt, man macht ganz, ganz
viele Experimente und entwickelt Verfahren, die in der Praxis gut
funktionieren.
Und was dann passiert ist, ist, dass man für dieses kürzeste
Wegeproblem Vorberechnungstechniken entwickelt hat.
Also man investiert eine gewisse Zeit vorne rein für diesen
Algorithmus und ist dann in der Lage, diese Weganfragen, also von
Madrid nach Berlin, schneller zu beantworten.
Und das war dann so ein Wettrennen zwischen Microsoft Research und
unserem Institut hier und dann ging das fast im Jahrestakt eine
Größenordnung runter und heute ist man so weit, dass dieses statische
Routenplanungsproblem mit Vorberechnungen natürlich sozusagen
ausgeforscht ist.
Wenn ich von Madrid nach Berlin will, um das zu berechnen, also nach
der Vorberechnung natürlich, brauche ich noch so viel Zeit wie für 5
bis 10 Speicherzugriffe, was ziemlich erstaunlich ist.
Also diese ganzen Kanten, die dazwischen sind, muss man gar nicht mehr
alle anschauen, sondern nur noch das, was wichtig ist.
Ein weiteres Problem, was ziemlich interessant ist in der Praxis, ist
Graph -Partitionierung.
Was man da machen will, ist, man hat diesen Graphen hier gegeben und
möchte den in eine vorgegebene Zahl Teile teilen, das ist diese Zahl K
hier oben.
Und zwar so, dass die Kanten, die zwischen den Teilen verlaufen,
möglichst klein sind.
Und auch da ist es so, dass dieses Problem entweder vollständig ist,
das heißt, man muss sich für die Praxis Verfahren überlegen, mit denen
man das effizient lösen kann.
Ich gehe jetzt nicht so sehr da auf dieses Mehrlevel-Verfahren hier
ein, aber es gibt halt einen ganzen Haufen von Techniken, die man da
verwendet und insbesondere, was mir persönlich ziemlich wichtig ist,
in diesem Mehrlevel-Verfahren werden alle möglichen Techniken
verwendet, die wir hier in der Vorlesung machen.
Also man berechnet hier Matchings, man hat hier Dynamic Programming,
man hat lokale Suchen, das kommt am Ende der Vorlesung noch, maximale
Flüsse, das lernen wir in Algorithmen 2, diese ganzen Basistechniken,
die kommen alle wieder bei den komplizierten Problemen, die man in der
Praxis hat.
Und hier sind Beispiele für Anwendung von dem Problem, was ich euch
gerade gezeigt habe.
Hier sieht man zum Beispiel ein soziales Netzwerk, was man gerne
analysieren möchte, also Facebook würde zum Beispiel gerne wissen, was
sind denn Gruppen, die sich gut kennen in diesem Netzwerk, aber
zwischen den Gruppen wenig gut kennen.
Oder Vorberechnungstechniken für die Straßennetzwerke, die wir gerade
gesehen haben, brauchen auch Partitionierungen von dem Graphen.
Oder was man hier sieht zum Beispiel, wenn man die Strömung simulieren
möchte an so einer Turbine hier, dann ist das häufig so, dass die
Geometrie, die dahinter steckt, nachher so fein aufgelöst ist, dass
die erstens nicht mehr in den Speicher von einer einzigen Maschine
passt, und zweitens, dass die Rechenzeit so lang wird, dass man da
nicht drauf warten möchte.
Und da kommen dann auch wieder Graph-Partitionierungen ins Spiel, in
denen man sagt, man möchte...
und die Kommunikation, die man hat, modelliert man als Kanten, und
dann kann man dieses Problem hier effizient auf mehrere Rechner
einfach verteilen.
Und zwar so, dass die möglichst wenig kommunizieren.
Oder beim Lösen von linearen Gleichungssystemen, oder beim Chip-Design
wird das auch verwendet.
Also die Moral von der Geschichte ist, mit Graphen kann man eine ganze
Menge machen, und vor allem kann man, oder das ist ein generelles
Prinzip in der Wissenschaft, man nimmt dieses Problem aus der Praxis,
fängt das an zu projizieren auf irgendwas Abstraktes, was eventuell
auch mehr Anwendungen hat, arbeitet auf diesem abstrakten Problem und
kriegt dann nachher die Lösungen für seine Realweltprobleme.
Okay, das sozusagen als Ausblick.
Noch ein bisschen Technik.
Intelligentes Rat.
Manchmal ist das so in der Praxis oder in den Klausuren oder in den
Übungsblättern, dass dieses Master-Theorem, was man lernt, gar nicht
passt.
Also wenn ich diese Rekurrenz hier zum Beispiel habe, also T von 2n
ist gleich 2 mal T von n plus 2n minus 1, dann kann ich hier nicht das
Master -Theorem anwenden.
Zumindest erstmal nicht direkt.
Und jetzt ist die Frage, was macht man?
Naja, also meistens sind wir eh in obere Schranken interessiert.
Deswegen könnte man probieren, diese Funktion T von n einfach mal zu
raten und dann einfach zu zeigen, dass das gilt.
Hat jemand eine Idee, was wir raten könnten?
Also was wäre ein guter Versuch zu raten für diese Rekurrenz hier?
Okay,
wer ist für quadratische Laufzeit?
Ja, da gibt es ein paar.
Wer ist für lineare Laufzeit?
Okay, und wer ist für n log n?
Der Rest, okay.
Bitte?
n log n.
Okay, probieren wir mal n².
Also wir raten jetzt, dass T von n kleiner gleich n² ist.
Genau, und das zeigen wir jetzt induktiv.
Also für den Induktionsanfang gilt das offensichtlich.
Und induktiv sieht man das folgendermaßen.
Also ich will jetzt die Laufzeit von T von 2n abschätzen und ich weiß
aber schon, dass die Laufzeit von T von n kleiner gleich n² ist.
Was sich dann zeigt, ist, dass T von 2n gleich n² ist.
Okay, also gehen wir mal rein in diese Gleichung, die wir da haben.
Setzen unsere Annahme ein.
Das ist nämlich dieses T von n ist kleiner gleich n².
Da muss übrigens ein kleiner gleichen.
Und dann kriege ich genau 2n² plus 2n minus 1.
Und das ist echt kleiner als 2n².
Also die Behauptung, die ich da gerade aufgestellt habe, n², die gilt
offensichtlich.
Okay, geht das vielleicht noch besser?
Also unsere nächste Vermutung ist Linearzeit.
Waren ja auch einige dabei, die dachten, okay, das könnte ja
Linearzeit sein.
Also die Idee ist, ich sage jetzt okay, es existiert eine Konstante c,
sodass meine Laufzeit T von n kleiner gleich c mal n ist.
Okay, also...
...für den Induktionsanfang.
Und was sich dann zeigen muss, ist wieder T von 2n kleiner gleich c
mal 2n.
Okay, und jetzt probieren wir, das wieder nachzurechnen.
Dann steht hier nichts anderes als T von 2n.
Wieder meine Vermutung eingesetzt.
Aber das Ding hier, das ist offensichtlich größer als 2cn.
Also funktioniert das nicht.
Also die Idee ist jetzt einfach, eine Schranke dazwischen zu suchen.
Und das ist jetzt die letzte Schranke, die wir uns überlegen, nämlich
T von 2n log n.
Und jetzt probieren wir das einfach nochmal.
Wir sagen jetzt, T von 2n ist wieder unsere Gleichung, unsere
Definition, genau, setzen wir ein.
Dann unsere Voraussetzung wird eingesetzt, dann haben wir 2n log 2n.
Das ist nichts anderes als das n hier ausgeklammert und dann das 2n
ausgeklammert und dann steht hier log 2,2, das ist nämlich gerade 1.
Jetzt benutzt man die Rechenregeln für den Logarithmus und kriegt dann
2n log 2,2n-1.
Genau, das ist jetzt in der Tat so, dass das ziemlich nah dran ist an
der tatsächlichen Laufzeit von dieser Rekurrenz hier.
Jetzt haben wir einen allgemeineren Fall.
Also genau, was ich sagen wollte.
Die Gleichung hier ist erstmal nur definiert für n gleich 2 hoch k für
irgendeinen k an n.
Und die Gleichung hier, das ist jetzt ein bisschen allgemeiner.
Also ich sage jetzt, für beliebige n in n gilt die Gleichung t von n
ist gleich 2 mal t von n halber abgerundet plus n-1.
So, das ist jetzt für n gleich 2 hoch k genau die Gleichung, die hier
oben steht.
Ich kann aber beliebige n einsetzen.
Und der Trick ist jetzt, dass ich mit genügend Schlampigkeit und
intelligentem Raten eine Lösung finde.
Also genau, wenn ich mit dieser Gleichung hier konfrontiert bin, mache
ich nichts anderes als diese Klammern hier weglassen und n gleich 2
hoch k setzen und dann ein bisschen rumprobieren.
Und genau das sehen wir jetzt quasi in einem Rückschritt.
Also erstmal ist diese Gleichung hier monoton steigend, das sieht man
induktiv.
Das mache ich jetzt nicht vor, das kann man sich gut überlegen.
Und auf der anderen Seite, wenn ich jetzt ein n habe, dann ist das
sicher von einem 2 hoch k und einem 2 hoch k minus 1 umzingelt, also
für n ungleich 2 hoch k.
Das heißt, ich habe die Abschätzung t von 2 hoch k minus 1 kleiner
gleich t von n kleiner gleich t von 2 hoch k.
Und der Trick ist jetzt, dass wir für diese 2 hoch k wissen wir schon,
wie diese Gleichung aussieht, wie sie beschränkt ist.
Das heißt, das t von n ist kleiner gleich t von 2 hoch k.
Das ist jetzt nichts anderes als c mal 2 hoch k log 2 hoch k.
Und das ist nichts anderes als c mal 2 n log 2 n.
Das ist nämlich genau die Definition, die ich da habe.
Also das ist kleiner gleich, genau.
Und damit habe ich hier eine andere Konstante, kleiner gleich c mal n
log n.
Und das ist genau das, was ich zeigen wollte.
Für beliebige n habe ich jetzt die Laufzeit von, oder die Funktion
hier beschränkt ist durch c mal n log 2 n.
Geht es sogar noch schwieriger, also wenn ich jetzt die Gleichung noch
erweitere, durch einen Plus x innerhalb von diesem t, dann kann ich
immer noch genauso schlampig raten und einfach durch Induktion zeigen,
dass diese Behauptung, die ich da gemacht habe, gilt.
Okay.
Also ich habe das eben ja vorgemacht, hier ist so ein bisschen so ein
Kochrezept, wie das geht.
Das nennt man auch Substitutionsmethode.
...gegeben, die durch den Ausdruck t, durch den Ausdruck a definiert
ist, und der Ausdruck nimmt jetzt die Abbildung t und n und macht
damit irgendwas.
Also zum Beispiel g von n ist gleich 2n, atn ist gleich 2tn plus 2
minus 1, und dann sind wir genau bei dem Beispiel, das wir vorhin
gesehen haben.
Was man jetzt macht, ist man dreht einfach die obere Schranke und
zeigt die dann.
Also das ist beides hier nichts anderes.
Also bei dem einen verwendet man das hier dann quasi als
Induktionsschritt.
Okay, gibt es Fragen dazu?
Das ist eigentlich nicht so schwierig.
Das ist eine ziemlich praktische Variante, weil wenn man verschiedene
Schranken einfach ausprobiert, dann kommt man da ziemlich schnell zum
Ziel.
Okay.
Hier ist noch eine andere Technik.
Manchmal kommt man auch wieder nicht mit dem Mastertheorem weiter.
Also in dem Fall t von n ist gleich t von Wurzeln plus 1.
Für n gleich 2, auch 2, auch i.
Und die Sache ist, das Mastertheorem hilft uns hier wieder überhaupt
nicht.
Also wir müssen uns überlegen, was machen wir, um hier trotzdem eine
Lösung zu finden.
Genau, also eine Möglichkeit ist die folgende.
Ich sage jetzt einfach, m ist gleich log n.
Dann ist n gleich 2, auch m.
Und ignoriere mal einfach die Ganzzahligkeit.
Beziehungsweise, das ist hier sogar gegeben, weil ich ja dieses n ist
gleich 2, auch 2, auch i definiert habe.
Was ich dann kriege ist, t von 2, auch m ist gleich t von 2, auch m
halbe plus 1.
Jetzt kommt der nächste Trick.
Jetzt sage ich, s von m ist t von 2, auch m.
Dann kriege ich eine Rekurrenzengleichung, s von m ist gleich s von m
halbe plus 1.
Und wer weiß, was das hier für eine Laufzeit hat?
Weiß das jemand, oder?
Ah ja, hier vorne.
Log m?
Genau.
Also das Ding hat jetzt log m Laufzeit.
Genau, und dann kriegen wir mit dieser Laufzeit für diese neue
Rekurrenz, kriegen wir die Laufzeit von der ursprünglichen Rekurrenz,
indem wir einfach rücksubstituieren.
Also jetzt ist t von n, hatten wir ja gesagt, ist s von 2, auch m.
Das ist das gleiche wie s von m.
Das ist aber o von log m.
Und jetzt setzen wir für das m wieder die Definition ein.
Dann kriegen wir, dass t von n gleich o von log log n ist.
Okay, das ist also eine von diesen Standardtechniken.
Genau.
Hier sieht man nochmal das Standardmaster-Theorem.
Das ist 1 zu 1 aus der Vorlesung übernommen.
Das ist relativ, also in der einfachen Form ist das relativ praktisch.
Und man kann sich relativ gut überlegen, warum die Fälle eigentlich so
sind, wie sie da sind.
Allerdings lasse ich das jetzt weg, weil wir sonst ein bisschen
Zeitprobleme haben.
Und übergebe an den Timo.
Machst du selber?
Ne, mach mal.
Schalt mal auf dieses... ah ne, mach mal erst Video.
Was soll ich anmachen?
Wir müssen ja nachher gleichzeitig nachmachen.
So, hallo.
Schauen wir mal, ob die Technik hier funktioniert.
Genau.
Ja, ähm...
Alle.
Okay, was macht also?
Da muss ich ja nicht viel erklären.
Man spielt das so.
Doch, doch.
Okay, Ziel ist es natürlich, das ganze Ding hier rüber zu bringen.
Das ist schon irgendwie langweilig, aber ich wüsste jetzt natürlich
gerne, wie lange das braucht.
Na, das war nicht gut.
Okay.
Wobei...
Ne, das war jetzt auch zu viele Schritte.
Okay, wie viele brauche ich minimal?
Naja, wir machen hier Rekurrenzen.
Danke, ja toll.
So, aber...
Ich will den Ganzen hier rüber bringen.
Wie drücke ich das als Rekurrenz aus?
Die Schwierigkeit ist natürlich, dass man hier jetzt nicht so wirklich
eine Rekurrenz sieht.
Sprich, irgendwie...
Ich dürfte kurz überlegen, während ich hier versuche, dieses andere
Projektor -Ding da zu machen, zu bekommen.
Jaja, jetzt brauchen wir die Folien da, dieses Foliending.
Weil dann müssen wir den nämlich da reinstecken.
Jaja.
Also, was ich gerne hier hätte, ist so eine Gleichung, T von N ist
gleich etwas anderes.
Damit ich weiß, wie lange ich hier minimal sitze, um hier den ganzen
Stapel rüber zu wandern.
Ja, gleich, ich brauche noch etwas zu schreiben.
Ja, jemand?
Niemand?
Jetzt sind meine Türmlein wahrscheinlich weg, aber ist egal, ihr wisst
ja, worum es geht.
Naja, die Idee dieser Rekursion...
Ich habe N-1 Scheiben hier rüber getan, ich tue eine darüber.
N-1 Scheiben und eine zusätzliche.
Meine Rekurrenz, das war jetzt der schwierige Teil.
Der leichtere Teil ist, die Rekurrenz jetzt zu lösen.
Was wir schon die ganze Zeit machen.
Was wir nicht die ganze Zeit gemacht haben, ist die Rekurrenz exakt
gelöst.
Meistens ging es ums O.
Ich will jetzt aber wissen, wie viele Schritte ich da tatsächlich
habe.
Und jetzt machen wir mal eine andere Art von Raten, wir rechnen
einfach mal die ersten Werte aus.
Also, T von 0 macht jetzt hier ausnahmsweise keinen Sinn, 0 Scheiben,
aber T von 1 ist eine Bewegung, das ist so ein Induktionsanfang.
T von 2, da muss ich zweimal eine Scheibe bewegen und dann eine
weitere.
T von 3, zweimal drei Scheiben und eine weitere.
Sieht man das?
Wow, das sieht man richtig gut.
Und wenn ich vier Scheiben, dann muss ich zweimal sieben Scheiben
durch die Gegend und eine dazwischen.
Auch noch eine.
Zweimal 15 Scheiben plus eins, das sind 31.
Hat jemand eine Vermutung, was es ist?
Genau.
Tn könnte 2 hoch n-1 sein.
Die Informatiker sehen ja lauter zwei Potenzen.
Glaubt man mir jetzt erstmal hier für den Anfang, jetzt machen wir
noch kurz Induktion.
Dann von n-1, Induktion von n-1 nach n.
Als kleiner Beweis, wir wollen T von n ausrechnen.
Nehmen an, dass T von n-1 2 hoch n-1 ist, also machen wir 2.
Mal T von n-1 plus 1.
Induktions- heißt das Ding also.
Das, was ich annehme, Induktionsannahme, ist, dass das hier, dass
meine Gleichung für den Teil hier gilt.
1, Entschuldigung.
Und dann multipliziere ich mir das aus.
2 hoch n minus 2 plus 1.
Und das Ganze liefert tatsächlich das, was ich gerne gehabt hätte.
Jetzt wurmt mich natürlich die Frage, das sind neun Scheiben.
Also ist mein T von neun 2 hoch 9 minus 1.
Also 511.
Das ging jetzt schneller, als die Scheiben durch die Gegend zu
schieben.
Coole Rekkurrenz, sehr leicht auszurechnen.
Ah, richtig.
Dank dem Chris haben wir jetzt auch noch Folien.
Nö.
Ah.
Genau.
Also das ist die einfache Form, Rekkurrenzen auszurechnen.
Man rechnet mal ein paar Werte und guckt, ob man was sieht.
Das, was man sieht, ist meistens Gefühlssache, ob man dann tatsächlich
was findet.
Eine etwas fortschrittlichere Methode sind erzeugende Funktionen.
Oder generierende Funktionen, das gleiche.
Einfach ein Name für ein anderes, more advanced guessing System.
Liefert keine exakten, es ist ganz wichtig, dieses System liefert
keine garantierten Lösungen, sondern man muss sie immer nachprüfen
nachher.
Was man macht, ist sehr viel komplizierter, es gibt wahrscheinlich
eine ganze Vorlesung dazu.
Ich möchte hier ein kleines Beispiel durchrechnen, damit ihr so ein
bisschen Gefühl bekommt.
Der Chris sagt nachher noch was zur Klausurrelevanz, damit wir uns
nicht vergessen.
Okay, erzeugende Funktionen.
Am Hand von dem netten Fibonacci-Beispiel, was ihr schon kennt.
Also die Fibonacci-Folge.
Kennt ihr schon.
Drückt sie mal als große F, als kleine F aus.
0 ist 0.
1 ist 1.
Und alles was drüber ist, setzt sich aus der Summe der vorhergehenden
zwei Zahlen zusammen.
Wenn man da ein bisschen ausrechnet, sieht man keinerlei Zusammenhang.
Also kann man ausrechnen, 1, 2, 3, 5, 8, 13, irgendwas.
Hab ich einen Fehler gemacht?
Nee.
Gut.
Erzeugende Funktionen machen einen ganz anderen Schritt, und zwar
gehen sie über Potenzreihen.
Ich werde euch da viele Sachen einfach vorführen.
Man kann dieses Schema, was anhand dieses Beispiels gezeigt ist, auf
viele andere Sachen anwenden.
Und zwar, was man macht, ist man schaut sich die Potenzreihe an, eine
große F von z.
Ich erkläre euch gleich was zu z.
Als Summe über sämtliche von diesen Koeffizienten.
Und zwar ist dieser seltsame Parameter z hier einfach...
Dieser ganzen Potenzreihenrechnung interessiert einen überhaupt nicht,
ob diese Potenzreihe hier konvergiert jemals.
Am Ende muss man deswegen nachprüfen, dass das Ergebnis, was
rauskommt, auch richtig ist.
Ob man da nicht irgendwo zwischendrin einen unendlichen Fehler gemacht
hat.
Was man jetzt macht, ist jetzt setzen wir einfach mal unsere
Folgenglieder hier ein.
Wir wissen, dass f von 0, also f von 0 mal z hoch 0 ist f von 1
plus...
Weil wir hier erst eine Rekurrenzgleichung ab 2 haben.
Und setzen erstmal unsere Werte ein.
f von 0 ist 0, deswegen fliegt das weg.
0 von 1 ist genau 1z.
Und jetzt wird es interessant, es kommt nämlich in diese Summe hier
unsere Gleichung für diese Rekurrenzgleichung.
f von n-2 z hoch 1.
Ich sollte vielleicht mal sagen, worum es hier überhaupt geht.
Es geht darum, eine geschlossene Formel zu finden für diese Frage.
Ja, ja, ja, es ist immer wieder Ruhe.
So, okay, die können wir auseinanderziehen und die Indizes
transformieren.
Das machen wir in zwei Schritten, sonst geht alles hier verloren.
So,
z hoch n plus den zweiten Teil, gleich 2.
Endlich, f von n-1, 2, z hoch n.
Und jetzt transformieren wir die Indizes, weil ich hätte gern überall
hier unten Nuller.
Hier geht es jetzt nicht in einem Schritt, da machen wir als n gleich
1.
Dann steht nämlich hier in diesem Term f von n,
umkommende plus 1 hin.
Und hier steht Null.
Endlich, f von n, z hoch n plus 2.
Es wird hier, diese ganze Rechnung wird darauf hinauslaufen, wieder
hier oben anzukommen.
Also wieder auf der ursprünglichen Term, und zwar mit Null unten.
Dann kriegen wir das hin.
Indem wir hier jetzt ganz brutal unten die Null dran schreiben.
f von n, z hoch n.
Diese plus 1 können wir dadurch erledigen, dass wir vorne hin z
schreiben.
Und jetzt haben wir hier was verloren, nämlich das erste Glied, das
müssen wir wieder abziehen.
Nicht verloren, wir haben was dazu gemacht, deswegen müssen wir es
wieder abziehen.
Und hier müssen wir nur dieses z Quadrat rausziehen.
Warum so gemacht?
Ganz einfach, weil ich jetzt hier oben das hier ersetzen kann.
Ach ja, hier, das ist Null.
Wunderbar.
Hier vorne steht immer noch f von z.
Das ist meine seltsame formale Potenzreihe.
Und jetzt rechnen wir aus, was der Wert dieser gesamten Potenzreihe
ist.
Und zwar kann man jetzt, muss ich wahrscheinlich nicht ausführen, aber
f von z ist jetzt gleich einfach.
Wir nehmen die ganzen Terme hier nach links, dann gibt es Minus, oben
steht ein z, unten steht ein 1-z-z Quadrat.
Ziemliche Magie und erstmal auch unerklärlich.
Ziel der ganzen Geschichte jetzt wird es sein, die geometrische Reihe
anzuwenden.
Wieder vergessen, was das ist, deswegen schreibe ich es hin.
Gleich 1 durch 1-z.
Ziel der Geschichte wird es sein, das hier zu verwenden, also das hier
auseinanderzunehmen, sodass man das hier verwenden kann.
Deswegen wollen wir das umschreiben, und zwar
so, alpha z, plus oben irgendetwas, 1-beta z.
Weil, wenn wir das so geschrieben haben, können wir das hier anwenden.
So, und jetzt kommt der hässliche Teil der Rechnung.
Deswegen gibt es den da drüben.
Und zwar geht es jetzt darum, eine Partialbruchzerlegung hier zu
machen.
Ihr habt ganz viel Mathe gehabt letztes Semester, das war
höchstwahrscheinlich auch dabei.
In dem konkreten Fall wollen wir hier jetzt eine Partialbruchzerlegung
machen, um das da zu haben.
Die können wir dann irgendwann mal hier benutzen, um f von z
festzuzurren.
Da das nicht mehr viel Zeit ist, wie lange war das?
15?
Bis 15 geht es, gell?
Okay, da wir nicht viel Zeit haben, muss ich euch bitten, falls euch
die Rechnung tatsächlich interessiert, dann irgendwie auf den Folien,
die wir ins Netz stellen, nachzugucken.
Man rechnet hier mit Koeffizientenvergleich einfach alpha und beta
aus.
Das ist nichts anderes als eine quadratische Gleichung, die ihr alle
gelernt habt zu lösen, mit der Mitternachtsform.
Man macht Koeffizientenvergleich hier nach z, z und z², weil z ist
einfach nur irgendein formales Etwas und rauskommt hier nur eine
quadratische Gleichung für alpha und die ist 1 ± √5½.
Das ist hier die Mitternachtsform für diese quadratische Gleichung.
Vorschritt abschreiben gibt es im Netz, das ist nur hässliche
Rechnerei.
Das Ergebnis ist dann diese Zahl, das ist so eine der mystischen
Zahlen, nämlich der goldene Schnitt.
Für manche Leute mystisch, allein weil er so heißt, für uns mystisch,
weil er genau diese beiden Eigenschaften hat.
Beziehungsweise der goldene Schnitt, das sind eigentlich zwei Zahlen,
nämlich 1 ± √5½ in diesem Kontext.
Wenn ich die beiden Zahlen multipliziere, kommt minus 1 raus und Adir
kommt plus 1 raus.
Das sind genau die beiden Zahlen, die wir hier brauchen in unserer
Partialbruchzerlegung, der Fibonacci-Zahl.
Die ganze hässliche Rechnerei ist gibtlich.
Für die Partialbruchzerlegung, also das sind die Nennerzahlen, das ist
das Alpha und Beta, hier drin, und die Zählerzahlen, das A und B hier,
ich skippe jetzt komplett die Rechnung, das ist einfach 1 · √5 und
minus 1 · √5.
So schnell findet man Partialbruchzerlegungen.
A war 1 · √5, glaube ich.
B war minus 1 · √5.
Und Alpha ist dieser goldene Schnitt namens Phi.
1 · √5½.
Und Phi' dach ist 1 · √5½.
Dürft ihr mal nachrechnen, wenn ihr wollt.
Das kann man jetzt einsetzen.
Und genau, jetzt haben wir eine neue Formel für das F von Z.
Nämlich diese Partialbruchzerlegung.
Ich verwende weiter die Buchstaben, sonst schreibe ich mich hier zu
Tode.
Und kann diese geometrische Reihe hier anwenden.
Das ist nämlich der Sinn der ganzen Geschichte, das jetzt wieder als
Reihe auszudrücken.
Und zwar, indem ich das A einfach vorne hinschreibe, jetzt die Summe
von gleich Null bis unendlich.
Und dieses Z ist in diesem Kontext beides.
Bzw.
hier sollte ich Phi hinschreiben, das sind die goldenen Schnitte.
Jetzt geht mir doch mein Papier aus.
Wunderbar, jetzt guckt man sich nochmal an, was hier steht.
F von Z war nämlich nichts anderes als unsere aufsummierten Fibonacci
-Koeffizienten.
Und das ist jetzt tatsächlich gleich einer zweiten Reihe, die bis ins
Unendliche reicht, nämlich A mal Phi hoch N, das B mal Phi Dach hoch
N, Z hoch N.
Und jetzt liegt die Vermutung doch sehr nahe, dass dieses F von N
tatsächlich das rechte ist.
Das muss man aber nochmal per Induktion beweisen.
Das ist nur eine Vermutung.
Wir machen mal nicht die komplette Induktion.
Ich schreibe mal die tatsächlichen Werte hierhin nochmal.
Das A war 1 durch Wurzel 5, mal dieses Phi, das war 1 plus Wurzel 5
Halbe durch hoch N.
So, und jetzt kann man das B, das war das B da drüben.
Das war Minus, genau deswegen, das steht schon vorne da.
1 Minus Wurzel 5 Halbe hoch N.
Das ist tatsächlich jetzt die vermutete Formel für die Fibonacci
-Zahlen, für jedes N.
Wir prüfen das mal für die ersten paar nach und dann dürft ihr daheim
den Rest ausrechnen.
F von 0, Wurzel 1 durch Wurzel 5, mal Phi hoch 0 minus Phi anderes
hoch 0 gibt 0.
Ja, weil F bis hoch 0 ist 1.
Noch einen mache ich.
Phi hoch 1, sprich 1 plus Wurzel 5 Minus dem da, das Wurzel 5.
Ergibt oben 2 Wurzel 5, unten Wurzel 5 Halbe, gibt 1.
Übrig bleibt jetzt Induktionsschritt.
Und zwar braucht ihr da 2 auf N.
Das dürft ihr dann mal ausrechnen, kleiner Tipp.
Phi Quadrat ist 1 plus Phi.
Damit kriegt ihr...
Fragen, natürlich, Fragen über Fragen.
Erzeugendenfunktionen, eine Riesentheorie, aber auch nur eine reine
Ratetheorie.
Man geht irgendwie in unendliche Reihen, um irgendwie die
Koeffizienten umzumodeln, bis man wieder zurückkommt.
Jetzt darf der Chris noch was dazu sagen, ob das Klausurrelevant ist.
Genau, also dazu eine kleine Geschichte.
Also als ich vor 8 oder 9 Jahren in Informatik 2 saß, gab es genau
diese Methode und ich selber finde die Methode ziemlich faszinierend.
Abgefahren.
Abgefahren, genau, weil bis vor ein paar Jahren wusste man überhaupt
nicht, wie man die explizite Formel für die Fibonacci-Zahlen berechnet
und jetzt hat man hier sowas, wo das extrem einfach geht.
Und der Übungsleiter sagte damals zu uns, dass das nicht
klausurrelevant sei und dann kam es doch in der Klausur ran.
Und deswegen für euch der Tipp, es kommt nicht in der Klausur ran.
Also wirklich nicht, ja, weil sonst fände ich es echt unfair.