Jetzt wollen wir hier eigentlich noch mal über die kompletten Folien
einmal schnell drüber gehen.
Wir haben jetzt noch eine halbe Stunde.
Ich schaue mal, wie weit ich komme.
Eigentlich wollte ich auch nur die Hälfte machen, also den Teil von
Christian Schulz und der Simon Gock wollte eigentlich einen zweiten
Teil machen.
Er ist jetzt aber auf einmal schon weg.
Von daher fange ich einfach mal an.
Genau.
Also am Anfang, naja, das ist jetzt alles vielleicht nicht so wichtig.
Der Professor Sanders hat dann die Einführung irgendwann in der
dritten, vierten Vorlesung gegeben.
Da wurden eben so allgemeine Sachen gesagt, Unterschied zwischen
Theorie und Praxis, was dann wirklich Algorithmen und Engineering ist.
Hier das Modell, ein bisschen Historie, dann Unterschiede zwischen der
Theorie und Praxis, was einem auf den ersten Blick jetzt vielleicht
doch nicht so auffällt, aber doch wirklich wichtig ist.
Genau, da möchte ich jetzt eigentlich so viel jetzt gar nicht drüber
sagen.
Den Teil kann ich jetzt genau...
Hier beginnt jetzt eigentlich das erste wirkliche Stoffthema, welches
wir auch ziemlich lang behandelt haben, kürzeste Wege.
Da haben wir eben erst mal von einem Punkt zum anderen Punkt das
Problem betrachtet.
Da gab es dann den Dijkstra's Algorithmus.
Erst mal zur Wiederholung, wie das in der Vorlesung funktioniert hat
und die Laufzeiten.
Und hier schon mal gesagt, okay, man kann irgendwie was mit Fibonacci
-Heap machen und dadurch wird man dann vielleicht ein bisschen
schneller.
Dann haben wir eine Analyse der Laufzeit im Durchschnitt uns ein
bisschen angeschaut
und haben da eben insbesondere auf die Decrease-Key-Operationen
geschaut und dann für eine spezielle Instanz von Graphen gesagt, okay,
wenn wir Dichte-Graphen haben, dann haben wir irgendwie lineare
Laufzeit.
Und genau, da betrachten wir eben noch mal, naja, wie viel Decrease
-Key -Operationen wir jetzt haben.
Das ist so ein allgemeiner Ansatz, wie man also dieser Beweis hier,
den haben wir an verschiedenen Stellen in der Vorlesung verwendet.
Und insbesondere der Beweis beruht dann eben auf dem Prinzip, dass man
hier eben diese Präfix-Minima einer Zufallsfolge sich anschaut und
ausrechnet.
Gut, dann hatten wir eben uns verschiedene Prioritätslisten
angeschaut.
Hier jetzt monotone, ganzzahlige Prioritätslisten.
Da gibt es auch immer einige Aufgaben in den Übungsblättern und auch
exzessiv in der Übung behandelt.
Da haben wir eben gesagt, okay, wir haben Minimum.
Neue Elemente sind immer mindestens so groß wie das Minimum und
höchstens um C Größe.
Und da hatten wir dann zwei Queues, einmal die Bucket Queue, wo wir
dann schon ein bisschen was beweisen konnten und die dann auch in den
Dijkstra -Algorithmus eingebaut haben.
Und dann eigentlich die viel interessantere Variante, die Radix Heaps,
die eigentlich auf dem gleichen Prinzip oder auf der gleichen Idee
beruhen.
Aber was man eben sagt, man hat in jedem Bucket nicht irgendwie einen
Schlüssel, den man verwaltet, sondern in Buckets, die weiter oder in
Buckets mit höherem Indizie verwaltet, man einen größeren Key Range
und hat damit eben ja noch bessere Laufzeiten hinbekommen.
Da haben wir insbesondere dieses Most Significant Discrediting Bit
oder sowas hieß es, glaube ich.
Also hier das erste Bit von links, welches sich unterscheidet und zu
zählen von 0 beginnt man eben von rechts.
Diese Operation hat man eben benutzt, um dann berechnen zu können, an
welche Position in der Tabelle man das Element dann schiebt.
Und genau in dem Beweis war es dann eben so, dass wenn man hier ein
Element aus dem ersten nicht leeren Bucket rausgenommen hat, dann hat
man eben zeigen können, alle Elemente aus dem Bucket, die kommen auf
jeden Fall irgendwie in Buckets davor.
Und da wir hier halt nur logarithmische Anzahl Buckets haben, müssen
wir halt jedes Element irgendwie nur an Lock C mal verschieben.
Gut, und dann eben die Delete Min Operation dazu beschrieben.
Wir haben dann in der Übung auch Beispiele dazu gemacht und das dann
in Dijkstra's Algorithmus eingebaut.
Dann haben wir uns All Path, Shortest Path angeschaut, wo man eben von
jedem zu jedem Knoten kürzesten Weg suchen konnte und dabei dann auch
gesehen, okay, wir können das sogar lösen, wenn wir negative
Kantengewichte haben.
Negative Kreise sind eben nicht erlaubt.
Und da hatten wir dann eben die Potenzial Methode als erstes
eingeführt, um neue Kantengewichte zu berechnen.
Mithilfe von so einem Hilfsknoten und haben dann.
Genau, haben das dann später auch nochmal verwendet.
Da haben wir uns dann nämlich verschiedene Speedup Techniken für den
Dijkstra allgemein angeschaut.
Also hier zum Beispiel vorwärts, rückwärts zu Zielgerichtete Suche A
Stern.
Und bei dem A Stern hier hat man dann eben genau nochmal diese neuen
Potenziale verwendet, um eben schon die Kantengewichte so zu wählen,
dass man die richtige Richtung sucht.
Dann hat man eben was Hierarchisches auch machen können und
Teilabschnitte tabelliert.
Gut, das ist jetzt alles speziell.
Genau, hier eben bidirektional von beiden Seiten hier A Stern, wo man
sich hier ein neues Potenzial definiert hat, entweder für den Kanten,
für den Knoten oder für die Kante.
Genau, man hatte eigentlich zwei Varianten, wie man das sich setzen
konnte.
Dann hatte man zwei Eigenschaften, die eben für die neuen Potenziale
gelten müssen.
Dann hatten wir die Tiefensuche ein bisschen in Detail angeschaut.
Erst mal allgemein das Pattern von der Tiefensuche und dann gesehen,
da gibt es eben verschiedene Stellen, an denen markante Sachen
passieren könnten in verschiedensten Algorithmen und haben dafür
erstmal leere Methoden eingeführt, haben dann gesehen, wie man die
leeren Methoden definieren muss oder was man da machen muss, um so
eine Nummerierung zu bekommen und haben dann die gleichen Lehrmethoden
auf andere Weise ausgefüllt, um dann starke Zusammenhangskomponenten
zu finden.
Bei den starken Zusammenhangskomponenten hatte man den Ursprungsgraph
und dann hat man sich einen Graph aus Zusammenhangskomponenten
aufbauen können, welcher dann eben der Schrumpfgraph war.
Und der Algorithmus selbst war dann eben auch ziemlich trivial, indem
man einfach die Tiefensuche ausgeführt hat und bei manchen Operationen
ein bisschen was Sophisticatedes machen musste und genau haben wir uns
das dann später im Beweis angeschaut, weil der Algorithmus selbst ist
eigentlich trivial.
Man muss sich nur einmal überlegen, warum der wirklich funktioniert.
Das nächste große Thema waren dann maximale Flüsse, beziehungsweise
das Pendant dazu, ein bisschen orthogonal Matchings.
Da haben wir uns erstmal angeguckt, was ist überhaupt ein
Flussnetzwerk, was kann man da in diesem Flussnetzwerk als Fluss
verstehen.
Wir haben Flüsse definiert, dass Fluss über eine Kante fließen kann
und der Fluss über eine Kante ist beschränkt.
Dann hatten wir den minimalen ST-Schnitt uns angeschaut.
Also man hat ein Netzwerk und da kann man einen Schnitt durchlegen.
Und wenn man maximal Fluss sich berechnet hat, dann ist der Fluss über
diesem Schnitt eben genau der maximale Fluss auf diesem Flussnetzwerk.
Das ist so die Verbindung zwischen minimalen Schnitt und maximalen
Fluss.
Man kann das mit linearer Programmierung lösen.
Man kann es aber auch besser lösen.
Da gibt es einen ganzen Bunch von Algorithmen.
Wir haben uns dann den Ford Falkassen angeschaut.
Beim Ford Falkassen hat man eben im Residual Graph sich einfach immer
irgendwie einen Pfad gesucht, der noch von S nach T existiert.
Und Pfad gibt es immer, wenn da auf dem kompletten Pfad alle Kanten
noch Kapazität frei haben.
Und hat dann genau diesen einen augmentierenden Pfad saturiert.
Und das hat man gemacht, bis man keinen Pfad mehr von S nach T im
Residual Graph gefunden hat.
Da haben wir dann gesehen, das funktioniert für schlechte Instanzen
nicht ganz so gut.
Dann hatten wir den DINITS Algorithmus.
Was wir da gemacht haben, wir haben blockierende Flüsse gesucht.
Da haben wir dann so eine Breitensuche ausgeführt, aus der
Breitensuche hatten wir dann so ein Netzwerk oder so einen Baum
aufgebaut und die Knoten, die weiter vom Baum oder von der Wurzel
entfernt waren, die hatten höhere Label.
Und was wir dann gemacht haben, wir haben den Fluss komplett über
diesen blockierenden, über diesen blockierenden oder über diesen
gefundenen Teilgraph gepusht.
Das war dann ein sogenannter blockierender Fluss.
Was man aber gesehen hat, naja, es reicht nicht, dass man das nur
einmal macht, sondern man muss es öfters machen.
Aber man kann eben zeigen, man muss es nur so und so oft machen, dass
dann die Gesamtlaufzeit trotzdem auf jeden Fall besser ist, als beim
Fort Falkersen.
Genau, und dann haben wir uns noch den Preflow-Push-Algorithmus als
dritten Algorithmus angeschaut.
Also wie gesagt, das waren erstmal augmentierende Pfade, also ein
Pfad, auf dem man noch was pushen kann.
Dazu haben wir uns dann erstmal in den Residual Graph definiert.
Das heißt, naja, eigentlich haben wir eine Kante von U nach V.
Und wenn die Kante aber komplett saturiert ist, beziehungsweise wenn
da schon Fluss drüber fließt, können wir den Fluss eben auch wieder
zurückschieben.
Und deswegen haben wir, wenn da ein Fluss über die Kante ist, auch
eine Rückwärtskante eingefügt.
Genau, dann haben wir diese augmentierenden Pfade gefunden.
Und die Pfade saturiert, das war dann schon der Fort Falkersen
-Algorithmus.
Und dann auch ein Beweis dazu, ein schlechtes Beispiel, warum das
nicht immer ganz so gut funktioniert.
Und dann haben wir uns blockierende Flüsse definiert.
Mit dem DINITS-Algorithmus.
Hier haben wir eben diese rückwärtsgerichtete Breitensuche.
Und dann haben wir eben diesen Layer Graph und finden diesen
blockierenden Fluss, der nicht nur eine Pfade ist, sondern über
mehrere Wege laufen kann und haben dann diesen kompletten
blockierenden Fluss auf dem Graph angewandt.
Dann eben noch mal zur Wiederholung.
Naja, wenn man einen bipartiten Graph hat, dann kann man bipartites
Matching auch mit Hilfe von Flussalgorithmen lösen.
Und genau, da hatten wir uns dann auch noch Spezialfälle angeschaut.
Dann den Pre-For-Push-Algorithmus.
Da sind wir weggekommen, dass wir irgendwie Pfade oder mehrere Pfade
suchen, sondern wir nehmen uns einfach Klonen raus, von denen wir
wissen, dass da mehr reinfließt als rausfließt.
Und wir haben versucht, das, was reinfließt, irgendwie rausfließen zu
lassen.
Und ja, das Prinzip war eben da, dass man dann auch sogenannte Labels
für die Knoten vergeben hat.
Bei S hat man am Anfang ein großes Label, bei T ein kleines Label.
Und die Labels haben dazu geführt oder die Definition von uns zum
Algorithmus, dass Fluss erst mal vom großen Label zu kleinen fließt,
also erst mal von S nach T.
Wir haben dann die Labels erhöht, wenn wir nicht mehr weiter was
fließen lassen können.
Irgendwann waren die so groß, dass die Größe waren als S und dann ist
der Fluss wieder zurückgeflossen.
So mal die allgemeine Idee zu diesem Algorithmus.
Dann eben der Korrektheitsbeweis bzw.
auch der Beweis von der Laufzeit.
Da hatten wir einige Lemmas, die dann am Schluss irgendwo
zusammengestöpselt wurden.
Und dann hatte man die Gesamtlaufzeit.
Genau das war dann diese Position in den Folien.
Und dann haben wir uns verschiedene Heuristiken angeschaut, zum
Beispiel First In, First Out, Preflow, Push und haben dann gezeigen
können, okay, hier haben wir dann oder können wir noch spezielle
andere Laufzeiten garantieren.
Hier im Allgemeinen eine bessere Laufzeit.
Hier haben wir das M durch ein N ersetzt.
Und wenn wir ein Highest-Level-Preflow-Push ausführen, dann haben wir
hier ein N durch ein Wurzel-M ersetzt.
Wurzel-M kann man höchstens N sein, aber wenn wir nicht ein voll
vermaschtes Netzwerk haben, ist es in der Regel kleiner.
Dazu dann eben auch wieder die Beweise.
Weitere Heuristiken, Resultate.
Das nächste Thema waren externe Algorithmen.
Da haben wir dann ein neues Speichermodell eingeführt, wo man eben von
dem großen Speicher hier immer Blöcke von Wörtern laden kann.
Und der Speicher, in dem man eigentlich seine Daten verwaltet, mit dem
man gerade aktiv rechnet, der hat eine begrenzte Kapazität.
Und da haben wir uns verschiedene Algorithmen angeguckt, wie zum
Beispiel den externen Stapel, externes Sortieren, wo man eben als
Eingabegröße die Anzahl der Elemente hat.
Und dann eben die Größe vom Speicher war dann M und B ist die
Blockgröße.
Und das externe Sortieren haben wir dann eben in eine externe Merge
-Phase aufgeteilt und die dann so nacheinander ausgeführt, dass wir
dann am Schluss eine sortierte Sequenz haben und am Anfang haben wir
eben solche Runs berechnet.
Genau, und wenn wir ein bisschen besser sein wollen, dann machen wir
mehr Wegewischen.
Also wir merchen nicht nur zwei Sequenzen, sondern mehr.
Und wie viel wir merchen können, hängt ja letztendlich davon ab, wie
viele Puffer man hier von der jeweiligen Sequenz im Speicher halten
kann.
Und die ist halt durch die Größe vom lokalen Speicher begrenzt.
Genau, dann haben wir noch Prioritätslisten.
Das ist aber schon ein bisschen stärkerer Tobak, finde ich.
Von daher gehe ich da jetzt ein bisschen schneller drüber.
Genau, das nächste Thema, was dann...
Ja, jetzt fangen so ein bisschen, finde ich, die kleineren Themen an.
Hier jetzt Fixed-Parameter-Algorithmen.
Da hat man eben ein K, wie es man definiert.
Und das ist in der Regel nicht irgendwie die Eingabegröße N, sondern
ein weiterer Parameter.
Und abhängig von diesem K wird...
Das Ziel ist eben, Algorithmen, die zum Beispiel NP-hard sind, kann
man teilweise so beschreiben oder Instanzen kann man so beschreiben,
dass die Schwierigkeit in Abhängigkeit von diesem Wert K wächst.
Also wenn man K macht, dann steigt die Laufzeit exponentiell.
Wenn man das K aber festhält und nur an der Eingabegröße dreht, zum
Beispiel, dann steigt die Komplexität auf einmal polynomiell.
Und dazu hatten wir dann eben hier ein Beispiel gerechnet.
Vertex-Cover und, naja, brute force kann man hier eben sehen.
Okay, hier hat man den Parameter K, der ist eben hier im Exponent.
Exponent und dann das N.
Und K hoch N ist halt für uns jetzt nicht so gut.
Und was wir dann eben gesagt haben.
Okay, ein Algorithmus ist fix parameter tractable, wenn wir einen
Algorithmus geben können, der so eine Laufzeit hat, sodass wir eine
Funktion F haben, die allgemein berechenbar ist und von K abhängt und
eine Funktion P, die polynomiell in N ist und nicht von K abhängt.
Und wenn wir hier jetzt eben das K festhalten, dann haben wir hier
eben nur noch polynomielle Laufzeiten in Abhängigkeit von N.
Und hier sind eben ein paar Beispiele.
Dazu, dann hatten wir dieses Vertex-Cover-Problem angeschaut und dazu
gab es eben zwei wichtige Methoden, die man anwenden konnte.
Einmal die Kernel-Bildung, aber das ist, sage ich mal, schon ein
bisschen tiefer im Problem drin.
Aber wirklich wichtig ist diese tiefenbestrengte Suche, wo man eben
sagt, okay, man hat dann irgendwie einen Baum, der soll K tief sein.
Und wenn man einen Baum hat, der K tief ist und einen fixen
Verzweigungsgrad hat, dann weiß man, okay, abhängig von K steigt die
Anzahl an Knoten eben ziemlich schnell.
Und wenn man dann eben einen Algorithmus so gebaut hat, dass man
innerhalb eines Knotens eine Laufzeit garantieren kann, die nicht
abhängig von K ist, sondern irgendwie polynomiell von N, dann hat man
eben so einen Fix-Parameter-Tractable-Algorithmus.
Und sowas haben wir eben beim Vertex-Cover-Problem hier in der
Vorlesung kurz skizziert, indem wir eben hier so zwei reklusive
Aufrufe haben.
Und hier haben wir eben genau so eine Laufzeit hier.
Das ist eben der Verzweigungsgrad, hier zwei, und das hier ist die
lokale Arbeit.
Und mit einer Rekurrenz kann man dann eben die allgemeine Laufzeit
ausrechnen.
Das haben wir in der Übung dann auch nochmal vertieft.
Da hatten wir eben dieses Puzzle-Problem gehabt, wo man von oben unten
links rechts reinschieben konnte.
Und da haben wir eben den gleichen Ansatz gewählt.
Man kann eben von oben unten links rechts reinschieben.
Sprich man hat Verzweigungsgrad 4.
Und man muss aber nur in jedem Knoten checken.
Okay, haben wir jetzt gerade eine Lösung.
Das kann man halt in dort n² Zeit lösen, wenn n die Seitenlänge von
dem Puzzle ist.
Genau, das ist eben die tiefenbeschränkte Suche, die Laufzeit.
Dann hatten wir parallele Algorithmen, auch nicht so tief behandelt,
wie es mir eigentlich recht wäre, weil ich parallele Algorithmen
ziemlich cool finde, was man halt hat.
Man hat ja P-Recheneinheiten.
Das können jetzt Threads sein oder auch Prozesse, je nachdem, auf
welchem Level man sich bewegt.
Die Ebene haben wir uns jetzt eigentlich gar nicht so genau
angeschaut.
Aber in der Regel kann man, wie gesagt, viele Algorithmen, die man auf
Thread -Basis programmiert, auch auf Supercomputern laufen lassen oder
irgendwie transferieren oder umgekehrt.
Genau, da hatten wir eben einmal dieses Modell, wo man hier ein
Netzwerk hatte und verschiedene Recheneinheiten und jeder hatte seinen
lokalen Speicher.
Und man hat eben über das Netzwerk kommuniziert.
Genau.
Andere Varianten sind eben, dass man verschiedene Recheneinheiten
haben und die greifen alle zusammen auf einen globalen Speicher zu.
Und dann haben wir uns eben nochmal im Detail angeschaut, wenn wir uns
eben in diesem Modell befinden, wenn wir über das Netzwerk
kommunizieren, dann haben wir eben diese Startups, über die ich vorhin
schon gesprochen habe und die Zeit, um einzelne Datenwörter zu
betragen.
Genau.
Dann hatten wir ja wichtig, Effizienz und Speedup definiert und Arbeit
von einem Algorithmus und ein paar Paradebeispiele für triviale oder
einfache parallele Algorithmen gegeben.
Hier zum Beispiel die Reduktion.
Reduktion erstmal allgemein, was es bedeutet, wie man das eben
ausführen kann mit so einem Baumprinzip, sodass man in Abhängigkeit
von der Anzahl Prozessoren irgendwie eine lokarithmische Anzahl an
Schritten machen muss und in einem Schritt vielleicht über mehrere
Daten drüber iterieren.
Und diese Reduktion, da kann man eben verschiedenste Operationen
reinpflanschen, zum Beispiel, wenn man in jedem Schritt das Minimum
ausrechnet, kriegt man dann eben das globale Minimum über alle
Datenelemente.
Also genau so sieht dann eben das allgemeine Pattern aus und je
nachdem, was für eine Operation man hier den Knoten ausführt, Min,
Max, was weiß ich, kriegt man eben verschiedene Ergebnisse.
Dann Präfixsumme war ein anderes Beispiel.
Da hatte man das eben auch baumartig ausführen können, beziehungsweise
im Hypercube.
Dann Sortieren, Paralleles Quicksort, Paralleles Mergesort.
Da hatten wir dann so ein bisschen beschrieben, wie man zum Beispiel
Paralleles Quicksort ausführen kann.
Die Theoretiker-Variante, ein bisschen Analyse.
Ich glaube, in der Klausur ist es wichtig, dass es solche Operationen
generell gibt, dass man sie parallel ausführen kann und dass sie halt
auch einigermaßen effizient sind.
Dann haben wir das verallgemeinert und hier die Variante mit
Mehrwegemischen.
Dann kommen wir zum achten Kapitel, welches sich dann um String
-Algorithmen dreht.
Da haben wir größtenteils Strings sortieren betrachtet, Pattern suchen
in gegebenen Texten, die man vorher vielleicht auch schon
vorbearbeitet hat und die Datenkompression haben wir uns angeschaut.
Da hatten wir eben einen naiven Algorithmus zum Pattern Matchen, der
nicht so gut funktioniert hat.
Der erste interessante Algorithmus, der auch wirklich, finde ich, auch
wirklich elegant ist, war dann eben der Knuth-Moore-Spread
-Algorithmus.
Was man da eben gemacht hat, man hat einen Text und einen Pattern.
Und wenn man jetzt auf einem Text nur einmal einen Pattern suchen
möchte, dann rentiert es sich nicht, den Text vorzuberechnen, sondern
man möchte für das Pattern irgendwie was vorberechnen.
Und sowas haben wir dann hier Border Array genannt beziehungsweise
Verschiebetabelle.
Die haben wir kurz vorberechnet und haben dann eigentlich nur einen
linearen Scan über den Eingabetext gebraucht, um dann jede Position
oder jedes Vorkommen von diesem Pattern P zu finden.
Und in dieser Verschiebetabelle beziehungsweise im Border Array hat
man sich eben an Position I gemerkt,
für den Text, der im Pattern von der Stelle 1 beginnt, bis zur Stelle
J -1.
Was ist da das längste echte Präfix, welches gleichzeitig Suffix ist?
Und damit hat man dann halt schöne Sachen machen können, indem man
nicht das Pattern immer nur um 1 verschoben hat, sondern dann um den
Wert Alpha verschoben hat, wenn Alpha eben ein Eintrag war.
Genau, weil was uns das Pattern, was uns das Border Array hier eben
genau sagt, ist eben, naja, wie viel wir eben vorher schon gematcht
haben, was jetzt, wenn wir es verschieben, immer noch passt.
Genau, dazu dann der Algorithmus.
Das finde ich jetzt ein ziemlich simpler Algorithmus, aber trotzdem
elegant und deswegen hat er auf jeden Fall auch einen Platz hier in
der Vorlesung verdient.
Genau, hier zum Border Array berechnen.
Und dann war als nächstes eben Multi-Key-Quicksort dran.
Das haben wir dann auch in der Vorlesung behandelt.
Genau.
Dann ging es eben darum, wenn wir jetzt auf einem Eingabetext mehrmals
oder öfters eine Anfrage ausführen wollen, dann rentiert es sich, den
Eingabetext vorzubearbeiten.
Und da war eben unser erster Einstieg, das Suffix Array, welches wir
dann aufgebaut haben, erstmal definiert und dann ein bisschen, das
kommt glaube ich erst später, einen Algorithmus kennengelernt haben,
wie man das Suffix Array in den Jahrzeiten aufbaut.
Es war so ein rekursiver Algorithmus, und mit Hilfe dieses Suffix
Arrays, ja, schöne Sachen machen kann.
Genau.
Und was man dann eben mit Hilfe dieses Suffix Arrays machen konnte,
mit Hilfe binärer Suche konnte man eben Muster suchen.
Wenn man das LCP Array zusätzlich hat, dann kann man die Anfrage
nochmal zusätzlich beschleunigen und das LCP Array kann man auch in
Linearzeit aufbauen.
Dann haben wir die Suffix Bäume betrachtet, da so ein bisschen die Vor
- und Nachteile herausgestellt, wie schnell man die aufbauen kann.
Und genau.
Das war dann der Algorithmus, um das Suffix Array in Linearzeit
aufzubauen.
Hier erstmal eine Variante, die noch nicht funktioniert.
Genau.
Und das hier, genau das ist die Variante, die nicht funktioniert.
Und das ist dann die schnellere Variante gewesen, die auch Linearzeit
garantiert.
Soweit ich das auf jeden Fall auf die Schnelle sehe.
Genau.
Und das ist eben dann nochmal ein Beispiel, wie das alles
funktioniert.
Einmal komplett durchgehen, die Analyse.
Und Implementierung dazu.
Genau.
Dann eben die Suche im Suffix Array.
Das LCP Array, das habe ich ja vorhin schon angesprochen, dass man,
wenn man das LCP Array hat, die Suche nochmal beschleunigen kann.
Wie man das LCP Array aufbaut, wie man den Suffix aus LCP Array und
Suffix Array aufbaut.
Also den Suffix Baum.
Genau.
Und dann ging es weiter mit Kompression.
Hier wollen wir eben immer verlustfrei komprimieren.
Genau.
Als erster Algorithmus muss dann für die Kompression der LZ
Algorithmus, LZ Kompression, die eigentlich auch wieder so ein
ziemlich eleganter, einfacher Algorithmus ist, der aber trotzdem schon
mal einiges bringt.
Da haben wir dann auch die Nachteile noch rausgestellt, weil das halt
dann nicht so ganz so toll ist.
Beispiel dazu.
Genau.
Dann ging es mit geometrischen Algorithmen weiter.
Die hatten wir dann jetzt auch ziemlich am Ende von der Vorlesung.
Erstmal, naja, was bedeutet Geometrie?
Was sind die typischen Fragestellungen?
Beispiel dazu.
Dann haben wir uns auf mehrere Algorithmen oder mehrere
Fragestellungen beschränkt oder haben uns mehrere Fragestellungen
angeschaut.
Hier zum Beispiel Streckenabschnitt.
Hier erstmal als wirklich einfaches Problem.
Wenn man orthogonale Streckenschnitte hat, dann genau der naive
Algorithmus.
Hier jetzt nicht mehr mehr orthogonal zueinander.
Eine untere Schranke, dann die Idee mit der Sweepline oder mit der
Plainline und diesen Ansatz von Algorithmus, den kann man halt auf
viele andere Fragestellungen anwenden und damit in der Geometrie auch
andere Probleme lösen.
Dann hatten wir dafür eben verschiedene Ausbaustufen von dem
Algorithmus.
Erstmal orthogonal, dann Verallgemeinerung, wenn man ja nicht
Orthogonalität hat, beziehungsweise später dann auch Nicht
-Orthogonalität und Streckenabschnitte, die komplett waagrecht liegen.
Dazu dann der Algorithmus, wie der funktioniert.
Beispiel dazu.
Dann eben, um die konvexe Hülle zu finden.
Da hat man am Anfang eben einmal sortiert und muss dann eben nur noch
einmal über die sortierte Folge drüber iterieren, beziehungsweise
einmal eben den oberen Teil der konvexen Hülle, den unteren Teil der
konvexen Hülle mit diesem Grahamscan.
Als nächstes haben wir uns dann den kleinsten einschließenden Ball
oder die kleinste einschließende Kugel hier im zweidimensionalen
angeschaut und dann einen ziemlich simplen Algorithmus gesehen, für
den es aber jetzt erst mal nicht ganz so ersichtlich ist, warum der
korrekt ist.
Und wenn man mal gesehen hat, wie korrekt er ist, dann hat man eben
sich auch noch mal angucken müssen.
Was ist die Laufzeit?
Und wenn man die dann verstanden hat, dann war man schon mal ganz gut.
Dann haben wir 2D Bereichsanfragen uns angeschaut.
Erstmal 1D, gut.
Später dann zweidimensional.
Und da haben wir dann eben sogenannte Rangequeries uns definiert, wenn
wir eben nur diese Operationen Binary, Search, Successor haben, wie
man eben aus einer Kombination oder aus einer bestimmten Variante
diese Operation mehrfach auszurufen,
wirklich die Bereichsanfragen ausführen kann.
Also hier hat man erstmal
genau ich glaube, da eigentlich das eigentlich Tolle passiert jetzt
erstmal hier.
Ich bin mir gar nicht mehr so ganz so sicher, aber auf jeden Fall
genau, der erste Teil bestand letztendlich darum, erstmal hier das
System, mit dem wir uns aufhalten, umzurechnen und dann diese Punkte,
welche von 1 bis N jeweils Werte haben, haben wir dann in diesem
Waveletree reingegeben und der Waveletree speichert zwar irgendwie die
räumliche Darstellung der Punkte und war in sich selbst aber eine
Baumrepräsentation und auf jedem Baum, in jedem Baumknoten hat man
sich ein Bitvektor gespeichert und der Bitvektor wird immer kleiner
und man hat eben in jedem Eintrag ein Bit für jeden Knoten, aber ist
halt nur ein Bit und nicht irgendwie ganz viel und deswegen ist es
eine ziemlich kompromierte Datenstruktur und man kann da dann auch
ziemlich elegant die Anfragen gestalten.
Jetzt war das ein Beispiel, man trennt die X-Achse jetzt in zwei
Teile, hat sich den Bitvektor dafür gemerkt, was links und was rechts
lag und hat dann rekursiv nur noch die linken Punkte und die rechten
Punkte behandelt und hat das rekursiv gemacht und was man sich
gespeichert hat, waren letztendlich nur diese blauen Bitvektoren.
Ich bin schon ein bisschen über der Zeit.
Also ich würde sagen, wenn ihr keine Lust mehr habt, geht ihr einfach.
Ich rede einfach noch ein bisschen.
Ich glaube, es kommt jetzt gerade so niemand.
Genau, also wie gesagt, das war das, was ich eigentlich vorhin gemeint
hatte, wie man eben mithilfe von dieser Dominanz Anfrage wirklich
Bereichsanfragen sich zusammenbauen kann.
Und ja, ich finde den Ansatz hier wieder ziemlich cool, es einfach auf
Bitvektoren runterzubrechen.
Genau.
Dann als nächstes Thema Online-Algorithmen, wo man immer mehr
Informationen über ein Problem bekommt, ein Graph zum Beispiel nach
und nach reintröpfelt oder man nach und nach mitbekommt, ob man jetzt
überhaupt Bock hat, Ski zu fahren oder nicht, und man das aber zum
Anfang noch gar nicht gewusst hat.
Aber man sich trotzdem irgendwann entscheiden muss, naja, kaufe ich
mir jetzt Ski oder nicht, ohne über sein Verhalten in der Zukunft ja,
Wissen zu haben.
Und da gibt es eben so parale Beispiele, Paging, dann Routing
innerhalb von Kommunikationsnetzwerken, Scheduling und hier eben das
Skifahren.
Genau.
Und dann haben wir eben diesen
kompetitiven Faktor, müsste es hier gewesen sein.
Genau, den kompetitiven Faktor, wo man eben die Qualität vom Online
-Algorithmus durch den Offline-Algorithmus teilt und dann alle
Instanzen anschaut, die eben für das Problem jetzt so als relevant
definiert sind.
Und da das schlechteste Verhältnis genommen hat und das ist dann eben
unser kompetitiver Faktor.
Und das Ziel ist eben, den kompetitiven Faktor möglichst klein zu
machen.
Also im schlechtesten Fall trotzdem noch möglichst nah an der
optimalen Lösung zu bleiben.
Da hatten wir dann verschiedene Beispiele dazu, Paging, Skiing.
Wichtig ist da eben das allgemeine Prinzip von Online-Algorithmus zu
verstehen und für verschiedene Probleme sich eben so ein bisschen
auszudenken, wie könnte man das irgendwie lösen.
Genau, das war dann hier die Competitive Ratio Conclusion Ja, das war
es schon.
Mensch, 450 Seiten.
Danke, dass ihr jetzt noch 5 Minuten über der Zeit ausgehalten habt.
Ich wünsche euch viel Spaß beim Vorbereiten auf die Klausur.
Wie gesagt, wenn ihr Fragen habt, meldet euch oder schreibt ins Forum,
kriegt Hilfe von den Kommilitonen, macht die Übungsblätter.
Vielleicht findet ihr auch irgendwo Klausuren.
Also die ergänzenden Materialien gehören schon noch zum
Klausurrelevanten Stoff.
Also alle Folien, sage ich mal, die wir hier verwendet haben, die sind
auch klausurrelevant.
Aber zum Beispiel bei der Boris-Wheeler-Transformation, so viel ich
weiß, ist die auch...
Ich weiß nicht, ob die hier auf den Folien ist.
Ja, die ist jetzt hier nicht auf den Folien.
Also die ergänzenden Materialien, die gehören schon dazu.
Also die Sache war, dass es hier jetzt manche Folien gab, zum Beispiel
auch über die Boris-Wheeler-Transformation,
die wir noch vielleicht in einem anderen Format hatten, wo wir gedacht
haben, dass die in diesem Format für euch vielleicht verständlicher
sind.
Also gerade bei der Textindexierung, da ist der Simon Gock Spezialist
und der hat seine eigenen Vorlesungen für die Vorlesung
Textindexierung.
Und wenn er seine Vorlesungen irgendwie cooler fand, dann hat er eben
seine Folien benutzt, die dann in der ergänzenden Materialien
eingefügt wurden, weil wir die nicht so einfach in die Folien hier
reinbauen dürfen.
Ja, es ist auch Klausur.
Ich frage mich jetzt, warum das hier nicht drin ist.
Ich würde es nochmal mit reinnehmen.
Genau, aber randomisierter Algorithmen war ja auch so ein Top-Level
-Thema, was so wichtig ist.
Die Sachen, die halt durchgenommen werden, die kriegt man, glaube ich,
schon ziemlich schnell gelernt.