Guten Morgen, ich begrüße sie zur Vorlesung Algorithmen 2.
Wir werden heute das Kapitel über maximale Flüsse abschließen und
damit auch den etwas größeren Teil der Vorlesung über fortgeschrittene
Graphen -Algorithmen.
Ich möchte, da das jetzt bei den Maximum-Flow-Algorithmen doch etwas
über einen etwas größeren Zeitraum ging, noch mal einen ganz kurzen
Überblick geben, wo unsere Reise hinging, weil wir jetzt mehrere
Algorithmen gesehen haben.
Wir haben zunächst mal den Ford-Fackersen-Algorithmus gesehen, der
einzelne augmentierende Pfade im Residualgraphen berechnet, damit das
Max -Flow-Min-Cut-Theorem kennengelernt und das wichtige Konzept des
Residualgraphen, auf dem dann die ganzen folgenden Algorithmen ohnehin
beruht haben.
Wir haben dann gesehen, dass der im schlechtesten Fall sehr langsam
ist, noch nicht mal stark polynomiell und haben dann mit einer
speziellen Art solcher Augmentierungen zu finden, nämlich dem DINITZ
-Algorithmus und blockierenden Flüssen, eine recht effiziente Variante
dieses Algorithmus kennengelernt.
Wir haben da auch die Technik kennengelernt, mit einer
rückwärtsbreiten Suche vom Ziel, sozusagen die Suche nach guten
Flüssen zielgerichtet zu machen.
Das haben wir dann später beim Preflow-Push-Algorithmus erstmal über
Bord geworfen, aber wir werden heute den Bogen wieder zurückschlagen
dahin.
Die Laufzeit von DINITZ-Algorithmus war von m mal n², also bei dichten
Graphen bis zu n hoch 4, oder bei dünnen ist es vielleicht sogar noch
schlimmer, bis zu kubisch in der Eingabegröße, aber immerhin stark
polynomiell.
Und ich hatte auch schon gesagt, dass der Algorithmus in der Praxis
oft ganz gut funktioniert und dann sogar annähernd lineare Laufzeit
produziert.
Die Analyse beruhte darauf, dass wir einzelne Operationen haben und
zählen, wie oft die stattfinden.
Und das haben wir dann später bei Preflow-Push auch übernommen.
Dann hatten wir gesehen, dass man den DINITZ-Algorithmus in
Spezialfällen, insbesondere bei Kantenkapazitäten, die alle 1 sind,
noch bessere Schranken zeigen kann.
Und dass er da in der Praxis auch sehr gut funktioniert.
Und dann haben wir gesagt, das kann doch nicht alles sein.
Immer wieder augmentierende Pfade finden kann sehr langsam sein, wenn
die Pfade sehr lang werden.
Und wir haben uns deshalb den Preflow-Push-Algorithmus angeguckt.
Dessen Fluch und Segen, würde ich jetzt mal sagen, ist, dass er eine
viel lokalere Sicht hat.
Also dadurch sparen wir uns den Aufwand, immer gleich lange Pfade zu
suchen, um nur ein bisschen Fortschritt zu machen.
Wir haben das Ganze sehr viel feinkörniger mit diesen Push
-Operationen.
Was wir dafür brauchten, war das Konzept des Preflows, wo wir also
sagen, wir gucken uns nicht nur Flows an, sondern erlauben auch, dass
zumindest während der Berechnung des Algorithmus einzelne Knoten einen
Exzess haben.
Also mehr eingehenden Fluss als ausgehenden Fluss.
Und das hilft uns halt, die Aktivität des Algorithmus dort zu
fokussieren, wo man tatsächlich Fortschritte erzielen kann.
Die Korrektheit des Algorithmus und in einer recht indirekten Weise
auch die Steuerung dessen, was es bedeutet, Fluss vorwärts zu...
Fortschritt zu erzielen, war über diese Level-Funktion, von der wir
schon gesagt haben, die soll eine Näherung sein der kürzesten
Wegedistanz zum Ziel.
Aber wir haben das keineswegs irgendwie vernünftig approximiert
bisher.
Und das ist vielleicht auch einer der Gründe, warum die
Laufzeitschranken hier noch nicht so toll waren.
Wir hatten dann den generischen Preflow-Push-Algorithmus uns
angeschaut, der im Prinzip eine einzelne Schleife hat.
In jeder Schleifen-Iteration wird eine Push-Operation oder eine
Relable -Operation ausgeführt.
Alles davon braucht mehr oder weniger konstante Zeit, wenn man absieht
davon, dass man Kanten finden muss, die zulässig sind.
Wir haben dabei auch argumentiert, dass die Suche nach zulässigen
Kanten kein Flaschenhals ist.
Und wir hatten die Unterschieden bei den Push-Operationen zwischen
saturierenden Push-Operationen, die die ausgehende Kante dann komplett
saturieren, das heißt, deren Kapazität komplett ausnutzen, oder nicht
-saturierende, bei der das nicht der Fall ist, was jetzt erstmal
langweilig klingt, aber die, so wie wir das meistens dann
implementieren, die spannende Eigenschaft haben, dass sie den Knoten
deaktivieren, weil sie den ganzen Exzess loswerden.
Was ja auch in gewisser Weise Fortschritt ist.
Aber wir müssen dann diese sehr lokalen Arten von Fortschritt, ich
saturiere eine Kante, oder ich deaktiviere einen Knoten, oder ich
relabel einen Knoten, die müssen wir dann zusammensetzen zu einer
globalen Laufzeitanalyse des Algorithmus.
Und das ist es, was die Analyse von Push-Algorithmen interessant
macht, aber eben auch nicht so ganz einfach.
Wir hatten dann hier so eine Beispiel-Operation gesehen, mit zwölf
Push -Operationen.
Korrektheit gezeigt.
Und bei der Laufzeit war das so ein bisschen so ähnlich wie bei der
Analyse vom D-Netz-Algorithmus.
Wir haben die einzelnen Operationen gezählt, auf eine recht triviale
Art und Weise.
Also man muss da ein bisschen denken, aber eigentlich ist das meiste
davon trivial und auch sehr grob.
Also die Hoffnung ist, dass das in der Praxis sehr viel weniger ist.
Also Relabels können wir höchstens 2n² haben, weil wir zeigen können,
dass sie unbeschränkt wachsen können, nicht über 2n hinaus.
Und es gibt eben nur n Knoten.
Die saturierenden Pushes konnten wir auch wieder mit Relabel
-Operationen in Verbindung bringen und dann insgesamt eine Zahl von n
mal m saturierende Pushes zeigen.
Das ist auch nicht der Flaschenhals.
Die schlechte Nachricht war halt, dass der generische Preflow-Push
-Algorithmus n² mal m nicht saturierende Push-Operationen braucht.
Und das ist dann auch der Flaschenhals für den Algorithmus.
Selbst das war nicht ganz einfach zu zeigen.
Wir mussten da eine neue Technik für die Algorithmenanalyse, also für
uns neu, einführen, nämlich Potentialfunktionen, die man nicht
verwechseln sollte mit den Knotenpotentialen in Graphen-Algorithmen.
Sondern es ist jetzt ein mathematisches Konzept, das den Fortschritt
eines Algorithmus beschreibt und jetzt nicht notwendigerweise was mit
Graphen -Algorithmen zu tun haben muss.
Das würde ich eher vergleichen mit dieser Kontomethode oder der
Versicherungsmethode bei amortisierter Analyse von Algorithmen.
Das ist eher, was wir hier tun.
Genau, da konnten wir mit einer sehr einfachen Potentialfunktion, die
einfach die Levels aufsummiert, zeigen, dass die Gesamtzahl nicht
-saturierender Push-Operationen O n² mal m ist, indem wir gesagt
haben, ein nicht-saturierender Push dekrementiert dieses Potential.
Das Potential ist immer größer gleich 0.
Und wir konnten beschränken, wie viel die anderen Operationen das
Potential erhöhen.
Und da wir wissen, wie oft die anderen Operationen ausgeführt werden,
konnten wir sozusagen die Gesamterhöhung des Potentials über die
Laufzeit des Algorithmus abschätzen.
Und da die nicht-saturierenden Pushes das verringern um mindestens 1,
ist das dann gleichzeitig ein Schrank für die nicht-saturierenden Push
-Operationen.
Gab es dazu noch Fragen?
Über diese Story, die ich bis jetzt erklärt habe.
Genau.
Und dann waren halt diese nicht-saturierenden Push-Operationen
sozusagen der Knackpunkt.
Alles andere ist viel schneller in dem Algorithmus.
Und das wäre jetzt ein Ansatzpunkt, das zu verringern.
Wie können wir die Anzahl nicht-saturierender Push-Operationen
verringern?
Ich habe das erwähnt, dass wenn man die FIFO-Regel anwendet, das
heißt, wir speichern die aktiven Knoten in einer First-In, First-Out
Queue, dann kann man eine verbesserte Schranke zeigen, statt n² mal m,
n hoch 3.
Das nützt uns bei dünnen Graphen nichts, aber ist schon mal ein
Fortschritt.
Ist übrigens auch in der Praxis durchaus eine erfolgreiche Regel, da
werden wir noch zu kommen.
Ich wollte hier was zeigen, was zumindest in der Theorie noch stärker
ist und wo ich auch finde, dass das irgendwie ein bisschen cleverer
ist.
Also FIFO ist irgendwie, das macht man, wenn einem nichts Besseres
einfällt.
Man kann sich überlegen, dass das schon besser ist, als stack zu
nehmen, aber ansonsten ist es nicht so clever.
Highest Level hat so die Idee, wir versuchen, aktive Knoten zu
bearbeiten, die möglichst weit weg sind von der Senke, einfach weil
dann die Hoffnung ist, dass sich der Fluss weiter unten ansammelt,
bevor ich ihn weiterschiebe und ich mir damit Push-Operationen spare.
Tatsächlich wollen wir jetzt zeigen, dass wir hier von diesem n² mal m
bei dem generischen Algorithmus oder n³ bei FIFO auf n² mal Wurzelm
kommen für diesen Highest Level Preflow Push.
Ich hatte dann ein Beispiel vorgeführt, wo man dann tatsächlich mit 9
statt diesen 12 Push-Operationen auskommt in unserem
Standardbeispielgrafen.
Und jetzt möchte ich das beweisen.
Es geht jetzt im Wesentlichen darum, zu zählen, wie viele nicht
-saturierende Push-Operationen wir haben.
Weil die ganzen anderen Operationen, da haben wir Schranken, die sind
ohnehin viel besser als n² mal Wurzelm.
Jetzt fällt erstmal ein Tuning-Parameter K vom Himmel.
Wir werden später sehen, dass man den auf Wurzelm setzen sollte.
Ist aber für die Analyse jetzt erstmal nicht wichtig.
Und wir haben jetzt eine Potentialfunktion, die nicht mehr ganz so
naiv ist, wie das, was wir beim generischen Algorithmus hatten.
Wo man auch sagen kann, das ist vielleicht ein großer Teil der
Kreativität bei der Algorithmenanalyse.
Ich kann auch jetzt nicht genau erklären, ehrlich gesagt, wie man auf
diese Potentialfunktion kommt.
Aber was wir machen, ist, dass wir uns direkt diese Distanzfunktionen
aufsummieren in unserem Potential.
Und eine Funktion D' aufsummieren.
Wieder über alle aktiven Knoten.
Bei beiden Varianten ist die Idee so ein bisschen, je größer das
Potential ist, desto unsauberer ist dieser Preflow.
Desto mehr ist noch zu tun.
Das ist bei der Generik irgendwie relativ klar.
Es erhöht sich mit der Anzahl aktiver Knoten und damit, wie weit weg
die noch vom Ziel sind.
Und jetzt messe ich die Umsauberkeit aber anders.
Ich sage, D' von V ist jetzt nicht die Distanz selber, sondern wie
viele andere Knoten auf gleichem Level oder weiter unterhalb sind.
Das ist die Anzahl Knoten, zu denen ich noch was schieben kann oder
soll.
Aber irgendwie nicht ganz, weil die, die gleich weit weg sind,
mitzähle, ist hier sogar ziemlich wichtig.
Vielleicht ist die Komplexität von denen gleich weit eher sowas wie
die Unsicherheit dessen, wo hier überhaupt was zu tun ist.
Wie auch immer.
Das ist eine Definition, die ich machen kann.
D' von V ist die Anzahl anderer Knoten mit einem kleineren oder
gleichen Level.
Und diesen Wert summiere ich jetzt über alle aktiven Knoten.
Allerdings bei dem D' von V zähle ich alle Knoten, nicht nur die
aktiven.
Und was jetzt noch mehr Voodoo ist und auf den ersten Blick irgendwie
unsinnig oder überflüssig, aber wir werden sehen, dass das relevant
ist, wir teilen diesen Wert durch unser Tuning-Parameter K.
Wir werden später sehen, warum das Sinn macht.
Ein anderer Wert, der wichtig ist für die Analyse, ist D' Stern.
Das ist der maximale Level eines aktiven Knotens.
Das ist nicht so unverständlich, dass wir das brauchen, weil dieser
Highest -Level-Algorithmus sucht sich den immer und macht da was.
Und wir sagen jetzt, eine Phase des Algorithmus sind alle Push
-Operationen zwischen zwei aufeinanderfolgenden Änderungen von D'
Stern.
Das heißt, wenn D' Stern sich ändert, das ist nicht Teil des
Algorithmus, sondern Teil der Analyse, also ich beobachte jetzt
einfach alle Zeitpunkte, wo D' Stern sich ändert und fasse jetzt die
Operationen dazwischen jeweils zu einer Phase zusammen und meine
Analyse summiert jetzt über die Phasen.
Da habe ich gewisse Einheitlichkeit in dem, was passiert.
Wir werden sehen, worin diese Einheitlichkeit besteht.
Und ich muss jetzt außerdem noch unterscheiden zwischen teuren und
billigen Phasen.
Und da kommt jetzt wieder unser Tuning-Parameter ins Spiel.
Teure Phasen sind einfach die, die mehr als K-Push-Operationen
enthalten und billige sind die anderen.
Kann ich machen.
Also hier fallen jetzt schon ein paar Dinge vom Himmel.
Wie gesagt, ich weiß auch nicht genau, wie man da drauf kommt, aber
danach ist die Analyse dann auch nicht mehr trivial, aber
nachvollziehbar.
Aber ich wollte Ihnen hier wirklich mal ein Beispiel einer nicht
-trivialen Analyse mit Potentialfunktionen zeigen.
Und wir haben hier unsere Chili.
Also Sie werden das jetzt nicht im Detail reproduzieren müssen.
Aber Sie sollten wissen, was das Ergebnis ist.
Und das heißt, Level halten bestimmte Garantien.
Das ist jetzt so einer der wenigen Beweise unserer Vorlesung, der halt
nicht einfach auf eine Folie passt.
Den ich aber trotzdem versucht habe so aufzubereiten, dass man jeweils
die wichtigen Informationen auf einer Folie zu sehen kriegt.
Wir beweisen jetzt im Prinzip fünf Claims.
Jeder dieser Claims werde ich jetzt auf einer Folie dann beweisen.
Das heißt, der Nummer 2, der ist ziemlich trivial.
Und daraus folgt dann sozusagen die Analyse.
Also das ist jetzt mal eine relativ volle Folie.
Deshalb lasse ich mir da jetzt vielleicht ein bisschen Zeit zu
erklären, was da passiert.
Die einzelnen Claims müssen Sie jetzt erstmal glauben.
Die werde ich aber später zeigen.
Und daraus kann ich dann den kompletten Beweis zusammensetzen.
Wir werden zeigen, dass es höchstens 4n² mal k nicht saturierende Push
-Operationen in den billigen Phasen gibt.
Also das ist ja sowieso das Kernding.
Wir wollen ja die Anzahl nicht saturierender Push-Operationen zählen.
Das ist nicht einfach.
Deshalb machen wir jetzt eine Fallunterscheidung nach billigen und
nicht billigen.
Und lassen uns außerdem noch ein bisschen Flexibilität, was genau
billig ist.
Zweite Claim ist, diese Potentialfunktion ist immer größer gleich 0.
Das ist trivial.
Und sie ist am Anfang kleiner gleich n² durch k.
Das ist auch
trivial.
Aber das ist vielleicht mal was zum Aufwachen.
Hier ist diese Potentialfunktion.
Warum ist die kleiner gleich n² durch k?
Genau, n² und das Ganze durch k geteilt.
Also das ist ausnahmsweise mal einfach.
Dann haben wir gesagt, die Idee bei diesen Potentialfunktionen ist
immer, man guckt sich an, welche Operationen erhöhen das und welche
verringern es.
In dem Fall, die, die es verringern, sind halt die, die wir eigentlich
zählen wollen.
Diese nicht-saturierenden Push-Operationen.
Und die schlechte Nachricht ist jetzt, nicht alle nicht-saturierenden
Push -Operationen verringern
die Potentialfunktion tatsächlich.
Aber unsere Fallunterscheidung hilft uns hier raus.
Die anderen können es erhöhen.
Wir werden zeigen, eine Relatable oder saturierende Push-Operation
erhöht den Potentialwert um höchstens n durch k.
Dann viertens, es kann zumindest nichts ganz Übles passieren mit einer
nicht -saturierenden Push-Operation.
Die kann das Potential nicht erhöhen.
Also es wird kleiner oder es bleibt gleich.
Und jetzt kommt der spannende Teil, der uns überhaupt hilft, da
weiterzugehen.
In teuren Phasen,
die eben Q größer gleich k nicht-saturierende Push-Operationen machen,
verringert sich das Potential um mindestens k.
Und das ist ganz okay, weil wir haben in 1 ja bereits beschränkt, wie
viele von den non-saturierenden Pushes in den billigen Phasen gibt.
Also genügt es jetzt zu zählen, was in den teuren Phasen passiert.
Und da ist es im Endeffekt so, in einer Phase mit q nicht
-saturierenden Push-Operationen verringert sich das Potential um
mindestens q.
Oder mit anderen Worten, die nicht-saturierenden Push-Operationen in
teuren Phasen verringern das Potential um mindestens 1.
Das ist also eigentlich sogar genau das gleiche wie im generischen
Algorithmus, nur dass das Potential eine komplett andere ist.
Und wir nur die nicht-saturierenden Pushes in teuren Phasen haben.
Das sind die Claims.
Dann habe ich noch Ergebnisse aus der generischen Analyse, die wir
übernehmen können.
Lemma 7 und Lemma 8, da erinnert sich wahrscheinlich keiner daran, was
das war, deshalb habe ich das hier in der Tabelle noch mal angegeben.
Lemma 7 beschränkt die Anzahl Relabel-Operationen und sagt, das sind
höchstens 2n².
Lemma 8 beschränkt die Anzahl saturierender Push-Operationen, das sind
höchstens O von n mal m.
Und der Claim 3 sagt, naja, diese Operationen erhöhen das Potential um
n durch k.
Also die Gesamterhöhung dadurch ist dann 2n² plus n mal m in Klammern
mal n durch k.
Und Claim 2 sagt, dass es am Anfang n² durch k ist.
Das addiere ich noch.
Und so habe ich jetzt eine Schranke für die maximale Erhöhung, die
stattfindet und damit auch die maximale Senkung.
Und damit kann ich jetzt beschränken die Anzahl nicht saturierender
Push -Operationen in teurem Phasen.
Das ist Claim 5.
Das ist jetzt einfach dieses Ding ausmultipliziert.
Also 2n² mal n durch k ist 2n hoch 3 durch k.
n mal m mal n durch k ist mn² durch k und n² durch k steht hier drin.
Also jetzt habe ich das alles auf einen Nenner gebracht.
Also ich habe höchstens 2n hoch 3 plus n² plus mn² durch k nicht
saturierende Push-Operationen in teuren Phasen.
Jetzt nehme ich Claim 1 dazu.
Dann habe ich insgesamt dieser Bruch plus 4n² mal k nicht saturierende
Push -Operationen in billigen Phasen und damit die Gesamtzahl nicht
saturierender Push-Operationen.
Und jetzt kann ich verstehen, warum man jetzt ausgerechnet k gleich
Wurzel m wählen sollte.
Kann mir das jemand sagen, warum das sozusagen der beste Wert ist?
Also ich habe hier eine Funktion, das ist ein Polynom von n und m und
das k tritt darin auf.
Und da ist ein Term, der wird durch k geteilt und ein Term, womit k
multipliziert wird.
Und jetzt kann man sich überlegen, wenn man will, sogar analytisch,
indem man das nach k differenziert und gleich 0 setzt, dass für k
gleich Wurzel m diese Summe minimiert wird.
Wenn ich jetzt k gleich Wurzel m einsetze, steht hier n hoch 3 durch
Wurzel m.
Aber n durch Wurzel m ist kleiner gleich Wurzel m.
Dann habe ich also den Term durch n Quadrat Wurzel m beschränkt.
n Quadrat durch Wurzel m, das ist sowieso ein unwichtiger Term, der
ist ja kleiner als der.
Und m mal n Quadrat durch Wurzel m ist Wurzel m mal n Quadrat.
Und hier steht n Quadrat mal Wurzel m.
Alle diese 4 Terme sind o von n Quadrat Wurzel m.
Man kann sich überlegen, dass keine andere Wahl von k einem
asymptotisch etwas besseres lief.
Rechnen wir mal aus.
Was war das?
n hoch 3 durch k.
Das schätze ich jetzt so ab, dass es kleiner gleich n Quadrat mal m
durch k.
Also ich mache aus einem von den n mache ich ein m.
Immerhin der Annahme, dass m gleich Theta n ist, weil Omega n, weil
wenn ich weniger Kanten als Knoten habe, dann habe ich isolierte
Knoten, die kann ich auch gleich wieder rausschmeißen.
Die können zu einem Flow nichts beitragen.
Diese Annahme m größer gleich n muss man irgendwie ganz oft machen,
sonst kommt man nicht zu sinnvollen Aussagen.
Und das ist eben n Quadrat mal m durch Wurzel m.
Und jetzt m durch Wurzel m ist Wurzel m.
Jetzt müssen wir noch diese Claims beweisen.
Wir haben höchstens 4 n Quadrat mal k nicht saturierende Pushes in den
billigen Phasen.
Das ist eigentlich ganz simpel.
Wir zeigen jetzt einfach, dass es höchstens 4 n Quadrat Phasen gibt.
Das ist nicht so schwierig, weil sich dieser Wert von d Stern nur
ändern kann bei einer Relabel-Operation.
Und wir haben bereits gezeigt, dass es höchstens 2 n Quadrat Relabel
-Operationen gibt.
Er kann sich öfter ändern, aber er kann sich nur erhöhen.
d Stern kann sich nur erhöhen bei einer Relabel-Operation.
Davon gibt es 2 n Quadrat.
Dann kann er sich entsprechend auch höchstens 2 n Quadrat mal
verringern.
Dann kriegen wir 4 n Quadrat.
Wir wissen jetzt, wie viele Phasen es gibt.
Und wir haben einfach definiert, eine Phase ist billig, wenn es
höchstens k Pushes gibt.
Also 4 n Quadrat mal Phasen mal kleiner gleich k Pushes heißt kleiner
gleich 4 n Quadrat mal k nicht saturierende Push-Operationen.
Fragen dazu?
Also der ist relativ einfach.
Der zweite hatten wir sowieso schon abgehakt.
Der war sogar mehr oder weniger trivial.
Der dritte Claim Relabel oder saturierende Push-Operationen erhöhen
das Potential um höchstens n durch k.
Um das zu verstehen, schauen wir uns den Knoten des Relabels an.
V also der Knoten, dessen Label geändert wird.
Der wird ja inkrementiert.
Und dann kann er jetzt schon zusätzliche andere Knoten dominieren.
Im Worst-Case sogar alle.
Ganz großzügig.
Dann sind es vielleicht bis zu n Knoten, die er jetzt zusätzlich
dominiert.
Das erhöht dann entsprechend die Größe dieser Menge.
Aber das Ganze wird dann nochmal durch k geteilt.
Also haben wir die Veränderung n durch k.
Und sonst ändert sich am Potential nichts.
Ich habe das sogar überschätzt, weil es könnte ja sein, dass andere
aktive Knoten den jetzt nicht mehr dominieren.
Dadurch wird sich das Potential wieder ein bisschen verringern.
Aber ich bin auf der sicheren Seite.
Die einzige Erhöhung ist die Strichwerte, die bei einem Relabel
passieren kann.
Bei einer Saturierenden Push-Operation U nach W kann der Zielknoten
aktiviert werden und dadurch die Strichwerte in der Summe, die das
Potential definiert, auftauchen.
Aber der dominiert halt auch höchstens n Knoten.
Und das ist das Problem.
Beitrag n durch k und sonst ändert sich nichts an dieser Summe.
Fragen dazu?
Das sind alles Claims, die wenn man sie jetzt erstmal liest, denkt man
sehr abstrakt.
Und warum ist das so?
Aber wenn man dann genau hinguckt, ist jeder dieser Claims recht
leicht zu beweisen.
Jetzt muss ich noch zeigen, dass eine nicht-saturierende Push
-Operation das Potential nicht erhöht.
Das liegt daran, wenn jetzt der aktive Knoten V ist, von dem das nicht
-saturierende Push kommt, dann wird der ja deaktiviert.
Das verringert das Potential.
Jetzt muss man nur aufpassen, der Zielknoten wird möglicherweise
aktiviert und das erhöht das Potential wieder.
Aber der Trick ist, der D-Strichwert von dem Zielknoten kann niemals
größer sein als der D-Strichwert von dem Knoten, von dem der Fluss
kommt, weil wir den Fluss ja nur abwärts schieben, also bei
verringernden D-Werten.
Und deshalb ist die Netto-Veränderung des Potentials so, dass es
höchstens nach unten gehen kann.
Und jetzt ganz entscheidender Claim, in den teuren Phasen verringert
sich das Potential proportional zu der Anzahl nicht-saturierender Push
-Operationen.
Dabei hilft es, dass während einer Phase dieser Wert D-Stern für das
höchste Label eines aktiven Knotens konstant bleibt.
Das heißt, ich habe jetzt ganz viele nicht-saturierende Push
-Operationen bei einem konstanten Wert von D-Stern.
Jedes dieser nicht-saturierenden Push-Operationen deaktiviert einen
dieser Knoten mit Level D-Stern.
Das heißt, ich habe am Anfang ganz viele und es werden immer weniger.
Das heißt, die Zahl geht immer weiter runter.
Und jetzt gucken wir uns mal den Beitrag dieser Knoten mit dem Level D
-Stern an für das Potential.
Wir wissen, dass jeder davon am Anfang der Phase alle anderen in dem
Level dominiert.
Das ist diese Definition, dass das ...
...
Da zähle ich ja alle Knoten mit einem Level, der kleiner gleich ist.
Also ich zähle die mit, die auf diesem Level D-Stern sind.
Das ist jetzt ganz wichtig.
Und ich zähle vor allem auch die nicht-aktiven mit.
Das heißt, ich kann jedes Mal verringert sich das Potential um Q, wenn
ich so einen von den Knoten auf diesem Level deaktiviere.
Da das Q größer gleich K ist, bedeutet das aber auch, dass selbst wenn
ich das durch K teile, dass eine Verringerung des Potentials um
mindestens 1 bedeutet.
Und dann habe ich diese Abschätzung.
Jeder nicht-saturierende Push verringert die Anzahl aktiver Knoten im
Level.
Deshalb ist die Anzahl hier Q.
Also jeder nicht-saturierende Push vermindert das Potential durch die
Differenz zwischen dem V.
Und jetzt muss ich vorsichtig sein.
Der Zielknoten wird natürlich möglicherweise aktiviert.
Aber der Trick ist, der Zielknoten hat einen Level, der unter D-Stern
liegt.
D.h.
der dominiert diese ganzen Q-Knoten darüber nicht und deshalb
verringert sich dann tatsächlich die Größe dieser Menge um mindestens
Q.
Und das ist wiederum mindestens K.
Also steht da größer gleich K durch K gleich 1.
Fragen dazu.
Damit habe ich diese ganzen Claims gezeigt und die Argumentation eben,
wie ich das dann zusammen mit der Anzahl Relabel und Saturierenden
Push Operationen und der geeigneten Wahl von K dann zu der Analyse der
Anzahl nicht-saturierenden Push Operationen.
Und wenn ich das jetzt wieder zusammenbringe mit der Analyse des
generischen Algorithmus, kriege ich halt die Behauptung über die
Gesamtlaufzeit.
Weil da war die Anzahl nicht-saturierender Push Operationen der
einzige Flaschenhals.
Fragen dazu?
So, also jetzt haben wir theoretisch sozusagen das erstmal rausgeholt,
was man aus diesem einfachen Algorithmus rausholen kann.
Ich werde gleich auch noch Messergebnisse dazu zeigen.
Die schlechte Nachricht ist, dass das alleine noch nicht zu
praktikablen Maximum-Flow-Algorithmen führt.
Das liegt vor allem daran,
ja, es liegt an mehreren Dingen.
Also es liegt zum einen daran, was auf dieser Folie steht.
Wir haben einen Best Case unseres Algorithmus von Omega n².
Und jetzt frage ich sie nochmal, warum der einen Best Case von Omega
n² hat.
Sieht das jemand?
Also ich habe hier eine Initialisierung, die läuft in Linearzeit.
Ich habe hier eine einzelne Schleife, die mehr oder weniger konstante
Zeit pro Iteration braucht.
Vergessen Sie mal diese Suchkosten nach Kanten, da haben wir schon
gezeigt, dass die kein Flaschenhals ist.
Egal wie gut es läuft, egal wie leicht das Problem ist ein Best Case
von Omega n².
Also das Problem ist einfach dieses inkrementieren
des Distanzwertes.
Ich habe ganz grob gesagt, ich habe n Knoten und man kann mehr oder
weniger zeigen, dass man eigentlich all diese Knoten auf ein Level von
n heben muss.
Oder sogar höher, um überhaupt das Problem beenden zu können.
Das heißt, ich habe hier ganz viele Relabel-Operationen, die in vielen
Fällen auch völlig trivial sind und die ich eigentlich nicht haben
will.
Aber ich gebe jetzt zu, warum das Best Case ist, ist auf dem Folio
nicht klar.
Das muss ich vielleicht nochmal checken.
Aber trotzdem gibt es jetzt zunächst mal eine relativ simple Art, wie
man das verringern kann.
Wenn ich jetzt tatsächlich eine Situation habe, wo der Knoten, den ich
habe, da gibt es keine ausgehenden Kanten, die runter gehen.
Und ich will irgendwann mal am Schluss da rausholen, dann ist es
irgendwie klar, dass ich mehrere Relabel-Operationen eigentlich
hintereinander machen muss.
Der Level muss mindestens ein größer sein, als der kleinste Level
eines Nachbarn im Residualgraf.
Und der Trick ist, damit kann ich auch nichts falsch machen, weil die
einzige nicht triviale Invariante, die ich hier aufrechterhalten muss,
ist, dass es keine Steep Edges gibt.
Aber das ist genau der größte Wert, mit dem ich sicherstelle, dass es
keine Steep Edges gibt.
Ich darf nicht eine Kante im Residualgraf haben, die um mehr als eins
runter geht.
Und das stelle ich hiermit gerade sicher und bin somit auf der
sicheren Seite und habe dieses Problem gelöst, dass ich immer so ganz
pedestrian immer nur einen höher mache, obwohl es klar ist, dass
vielleicht ganz viele Relabels auf einmal passieren müssen.
Wenn Sie das jetzt implementieren, merken Sie eigentlich nichts.
Das Ganze hat immer noch viel zu wenig globale Sicht darauf, wie man
überhaupt Fluss zum Ziel bringt.
Aber es ist eine Komponente, die ich später brauche.
Was viel wichtiger ist, ist Global Relabeling.
Was man jederzeit machen kann und was man ganz am Anfang machen
sollte, wo man sich das dann...
wie oft man es macht, sage ich gleich was dazu.
Aber im Prinzip, was man jederzeit machen kann, ist, dass man sagt,
anstatt dass dieser Distanzwert irgendwie eine Schätzung davon ist,
wie weit es zur Senke ist, kann ich einfach wie beim D-Netz
-Algorithmus eine rückwärts Breitensuche von der Senke machen und den
Abstandswert auf diesen Breitensuchdistanzwert setzen.
Das kann ich in linearer Zeit machen.
Wenn ich das jetzt immer und immer wieder mache, züttel ich das Kind
mit dem Bader aus.
Dann mache ich nur noch Breitensuche.
Aber was ich machen kann, ist, dass ich sage, ich messe in meinem
Algorithmus, zähle ich irgendwie mit, wie viele andere Operationen
mache ich.
Oder vielleicht auch noch detaillierter, feinkörniger, wie viel Arbeit
mache ich, wie viele Kanten schaue ich mir an oder sowas.
Und wenn das O von M Stück sind, der konstante Faktor ist jetzt wieder
ein Tuning-Parameter, der aber nicht besonders wichtig ist, dann weiß
ich, aha, wenn ich jetzt außerdem noch mal so eine Breitensuche mache,
kostet mich das nur einen konstanten Faktor in der Laufzeit, im
schlimmsten Fall.
Kann mir aber irgendwie quadratische Kosten sparen, dafür, dass ich
irgendwie rumirre mit meiner Last.
Insbesondere kann ich damit eben ganz schnell Relabel-Operationen
machen, die ganz schnell Knoten auf den Level schieben, den ich haben
will.
Also diese Global Relabeling-Heuristik, da bietet sich dann an, die
zusätzlich zu machen, die ist eigentlich die wichtigste überhaupt, die
sich dann in den Experimenten herausstellt und füllt eigentlich erst
diese abstrakte Idee, dass diese Level-Funktion irgendwie eine
Näherung für die BFS-Entfernung ist, füllt das erst mit Leben.
Hiermit stellt man sozusagen sicher, dass es nicht irgendeine Näherung
ist, sondern eine gute Näherung.
Dann ist es so, wenn man sich die Details des Algorithmus anschaut,
ja, man hat irgendwie eine gute Intuition davon, dass jetzt den Exzess
so Richtung der Senke schieben, dass das irgendwie sinnvoll ist.
Aber danach passieren noch genauso viele Operationen, bei denen man
dann den Fluss auch wieder zurück, den Exzess, der übrig bleibt,
wieder zurück zur Quelle schieben muss.
Und das ist aber eigentlich ein viel einfacheres Problem, weil man
eigentlich weiß, wie der Fluss dahin gekommen ist.
Und dann kann man das auch relativ leicht wieder rückgängig machen.
Was man dann deshalb tut, ist, dass sobald ein Knoten ein Level von
Größe gleich N hat, weiß man dass es keinen Pfad mehr geben kann von
diesem Knoten zur Senke, weil dann hätte man ein Steep Edge.
Das heißt, der ganze Exzess, der da noch ist, muss irgendwie zurück
zur Quelle und man spart sich das erstmal, sich das genau anzuschauen,
wie man das macht.
Und macht Relabel-Operationen nur für die Knoten mit kleinerem Level,
weil die sozusagen echt den Fluss noch erhöhen können.
Und wenn es dann keine aktiven Knoten mehr gibt mit Level kleiner N,
macht man halt sozusagen eine spezielle Operation zum Zurückschieben
des Flusses.
Das geht, glaube ich, in linearer Zeit.
Ist auch nicht besonders schwierig.
Werde ich aber jetzt nicht auf die Details eingehen.
Und dann gibt es noch eine Heuristik, die auch nett aussieht, die aber
nur in sehr speziellen Fällen was bringt, die Gap-Heuristik.
Wenn ich irgendeinen Level finde, der leer ist, das heißt, wo es keine
Knoten gibt, die diesen Level haben, dann kann da auch nie mehr Fluss
drüber gehen.
Und dann kann ich sozusagen vorzeitig meine Berechnung beenden.
Weil dann weiß ich, okay, alles mit Levels jenseits dieses Gaps
brauche ich gar nicht mehr betrachten.
Da kann ich dann auch den Fluss zurückschieben und muss nur noch da
unten weitergehen.
Fragen dazu?
Gut.
Das sind jetzt alles Heuristiken in dem Sinne, dass die keine
beweisbare Verbesserung der Worst-Case-Laufzeit gibt.
Aber in Experimenten funktionieren die ganz gut.
Und da das, wie ich behauptet habe, ganz entscheidend ist für die
praktische Komplexität, will ich dazu jetzt ein paar Experimente
vorführen.
Die sind alle aus dem Buch von Melon und Nair über Leda.
Und da in dieser Library of Efficient Data Structures und Algorithms
sind halt eine ganze Reihe von Varianten von Preflow-Push
implementiert.
Und auch diese Heuristiken.
Und die haben das dann auf relativ kleinen Graphen ausprobiert, aber
schon mit deutlich sichtbaren Ergebnissen.
Sie haben sich insbesondere drei verschiedene ne, sogar fünf, vier
verschiedene Familien von Instanzen angeschaut.
Eine davon erkläre ich jetzt explizit, weil die relativ einfach ist.
Wir haben n Knoten, beziehungsweise genauer gesagt n plus 2.
Wir haben also also
wir haben eine Quelle, eine Senke und dann haben wir n normale Knoten.
Wir haben
eine Kante von der Senke zu all diesen Knoten und dann von der Quelle
zu all diesen Knoten und von da zu der Senke.
Und dann wählt man glaube ich Uniform, zufällige Ach ne, und jetzt
wählt man nochmal m
zufällige Kanten zwischen diesen normalen Knoten.
Ja, also da kann man Fluss hin und her schieben.
Und was ich jetzt leider nicht mehr weiß, ist wie man die Kapazitäten
wählt.
Wahrscheinlich sind die Kapazitäten hier und hier dann auch irgendwie
zufällig.
Aber ich weiß jetzt nicht mehr nach welcher Verteilung.
Interessant ist natürlich der Fall, wenn der hier reingehende Fluss
die hier reingehende Kapazität größer ist als die hier rausgehende.
Sagen wir mal nicht gleich.
Weil dann lohnt es sich auf diesen horizontalen auf diesen Querkanten
hier den Fluss hin und her zu schieben, um einen maximalen Fluss zu
bekommen.
Das ist jetzt keine triviale Instanz.
Dann gibt es aus dem Paper von Tchaikowsky und Goldberg zwei Graph
-Klassen die meines Wissens dafür konstruiert wurden, einfache
Augmenting -Flow-Algorithmen schlecht aussehen zu lassen.
Und dann noch eine Klasse aus einem Paper von Ahuja, Magnanti und
Orlin oder aus dem Buch, aus dem ersten Paper glaube ich.
Die alle so ein bisschen so sind, dass die versuchen, nicht ganz
einfache Instanzen zu produzieren.
Und dann ist es schon ganz gut, wenn man mehrere verschiedene von
diesen Klassen hat, dann sieht man schon ein bisschen, wie Algorithmen
funktionieren.
Das Ganze ist jetzt auch mal ein bisschen ein Beispiel, wie
experimentelle Validierung funktioniert im Algorithm-Engineering.
Ich will jetzt an der Stelle auch schon ein bisschen Kritik äußern.
Also eigentlich, was man gerne hätte, wäre neben diesen synthetischen
Graphen Real-World-Anwendungen.
Also es gibt ganz viele Anwendungen von maximalen Flüssen, auch damals
schon.
Also das ist jetzt von Ende der 90er Jahre.
Aber irgendwie hat man zumindest damals es noch nicht geschafft,
Instanzen tatsächlich systematisch zu sammeln.
Das ist nicht unbedingt den Leuten da jetzt vorzuwerfen.
Firmen sind meistens sehr zögerlich damit, einem reale Instanzen, was
ihre Probleme zu geben.
Oft aus rechtlichen Gründen oder aus wettbewerblichen Gründen.
Das Internet war damals auch noch nicht ganz so ausgeprägt.
Ich glaube, inzwischen wäre es möglich, da eine etwas größere Sammlung
von Instanzen zu konstruieren.
Zum Beispiel aus Anwendungen wie Bildverarbeitung, wo eigentlich sehr
gut dokumentiert ist, was man da machen will.
Also das ist jetzt eine, ich sage mal, aussagekräftige Studie, aber
noch nicht das Ideale, was man gerne hätte.
Trotzdem können wir daran ein bisschen was lernen.
Ich habe also hier jetzt vier Folien.
Jeder als eine von diesen Instanzfamilien.
Und dann eine fünfte, wo die Skalierung über unterschiedlich große
Eingaben noch mal angeschaut wird.
Genau.
Die sind jetzt alle gleich aufgebaut, die nächsten vier Folien.
Eine für jede der Familien.
Die Eingabegrößen sind 1000 oder 2000 Knoten und M ist als 3n Kanten
festgelegt.
Ich habe immer Paare von Zeilen.
FF steht für FIFO.
Also die FIFO-Auswahlregel für aktive Knoten.
Highest Label steht für Highest Label-Auswahl.
Und MF ist irgendwie so eine modifizierte FIFO-Regel.
Dann habe ich immer eine Zeile für die kleine Eingabe und darunter
eine Zeile für die große Eingabe.
Und auf den Spalten habe ich ganz links den generischen Algorithmus.
Und dann werden sukzessive Heuristiken hinzugefügt.
LN macht dieses Ding, dass man Knoten, die auf den Level N erreicht
haben, speziell bearbeitet.
Dann LRH ist die Local Relabel-Heuristik.
GHH ist die Global Relabel-Heuristik.
GAP ist dann zusätzlich die GAP-Heuristik.
Also das ist immer so additiv.
Ich mache immer eine Heuristik dazu.
Und LDA ist dann die tatsächliche Implementierung in LDA, die halt
irgendwie offenbar noch was zusätzliches macht.
Die aber auf Highest Label beruht und deshalb sind die Einträge hier
immer leer.
Was wir jetzt sehen für Random Graphs ist eigentlich bei allen drei
Auswahlregeln, dass ich hier einen massiven Drop habe, sobald ich die
Global Relabel-Heuristik einbringe.
Also nehmen wir uns mal nur die allererste Zeile hier.
Die Basis-Operation war 5 Sekunden für 1000 Knoten.
Das ist schon ziemlich lange.
Dieses N-Level-Ding ist ein paar Prozent langsamer.
Da sollte man sich jetzt nicht zu viel denken.
Local Relabel-Heuristik spart ein bisschen 15% oder so.
Na gut, nicht so spannend.
Und dann bei Global Relabel geht es aber um einen Faktor, fast einen
Faktor 100 runter die Laufzeit.
Das heißt, da habe ich einen massiven Effekt.
Und noch spannender ist, wenn ich mir die Skalierung angucke, wenn ich
die Eingabegröße verdopple, habe ich hier grob von 6 auf 36, wäre eine
Versechfachung der Laufzeit bei Basic.
Oder mehr als Verfünffachung.
Das heißt, das sieht so aus, als ob das mindestens quadratisch wächst.
Das kann man später bei dem Skalierungsexperiment noch besser sehen.
Während hier bei Global Relabel ist es dann nur wenig mehr als eine
Verdopplung.
Also da komme ich in Richtung annähernd lineare Laufzeit.
Dieses MF werde ich jetzt gar nicht mehr darüber reden.
Soweit ich das sehe, ist das bei all den Experimenten nicht deutlich
anders als das FIFO.
Also wir unterscheiden jetzt noch FIFO und Highest Level.
Und was wir sehen ist, Highest Level ist irgendwie ein bisschen
langsamer.
Ich habe offenbar einen zusätzlichen Overhead für diese Bucket
-Datenstruktur.
Aber das bringt mir nicht wirklich was in der Verringerung der
Komplexität.
Was noch schlimmer ist, ist, dass dann Global Relabel zwar hier auch
mehr als eine Größenordnung bringt, aber nicht so viel wie bei FIFO.
Also scheinbar ist Highest Level hier kein richtiger Gewinn.
Allerdings ist es so, dass die Leder-Implementierung offenbar dieses
Problem teilweise wieder löst.
Leider schreiben sie in ihrem Buch nicht, was die zusätzliche
Heuristik von dem Leder-Ding ist.
Das müsste man sich jetzt wieder anschauen.
Fragen bis hierher?
Also wir haben jetzt erstmal gesagt, FIFO bringt was, Global
Relabel...
FIFO ist gut und einfach, Global Relabel bringt massiv was.
Und GAP kann man eigentlich vergessen.
Das schadet nicht, aber es kostet meistens ein bisschen.
Was witzig ist, ist, GAP bringt was, wenn man Highest Level hat.
Dann bringt GAP was, bei FIFO bringt es nichts.
Da sieht man auch wieder, man hat eine Interaktion zwischen
verschiedenen Optimierungen.
Und eigentlich, oder in Abwesenheit weiterer Einsicht in das Problem,
müsste man, wenn man N oder K Heuristiken hat, irgendwie 2 hoch K
Algorithmenkonfigurationen ausprobieren.
Und gucken, welche Konfiguration ist die beste.
Das ist natürlich nicht möglich, weil das viel zu auswendig wäre.
Folglich muss man, wenn man ganz viele Verbesserungsheuristiken hat,
sich halt sorgfältig überlegen, wie man die kombiniert.
Das ist vielleicht auch eine Lehre hier, wo man hier ein bisschen
Beispiele dafür sieht.
Bei dieser CG1 Instanz, das sind wieder die gleichen Eingabegrößen.
Die Laufzeiten sind
auch so ähnlich.
Ich habe allerdings bei Global Relabel jetzt nicht diese radikale
Verbesserung, die ich bei den Random Graphs gesehen habe.
Das zeigt, dass diese CG1, also CG steht jetzt einfach für Tchaikowsky
-Goldberg.
Und jetzt muss man in das Paper gucken, um zu sehen, was die genau
machen.
Das heißt, dem ist es offenbar gelungen, eine Instanzfamilie hier zu
bauen, die schwieriger ist als diese Random Graphs.
Und das wird eigentlich erst richtig sichtbar, wenn man einen guten
Algorithmus hat, wie dieses Global Relabel.
Also hier ist es offenbar so, dass das Global Relabel nicht so
effektiv ist wie bei Random Graphs, um den Fluss mehr oder weniger
sofort zum Ziel zu ruhen.
Und man sieht dann auch, dass man ganz viele Relabel-Operationen
braucht, Global Relabel-Operationen auch, die dann immer wieder das
Maß anpassen.
Ansonsten sieht man hier nicht so viel Neues.
Also wieder ist Highest Level eigentlich schlechter, obwohl wir da ja
bessere theoretische Schranken gezeigt haben.
Aber das ist kein Widerspruch, weil die theoretischen Schranken, die
wir gezeigt haben, sozusagen jenseits von Gut und Böse sind.
Für diese Instanzfamilien, alle vier, die hier getestet wurden, ist
die praktische Komplexität von allen Varianten sogar viel besser als
die Worst Case Schranken, die wir gezeigt haben.
Das heißt, dass die Worst Case Schranken jetzt für diese relativ
einfachen Instanzen keine wirkliche Information liefern.
Das ist schon sehr spannend.
Das geht, soweit ich weiß, sogar so weit, dass es für zumindest die
besseren dieser Varianten, sagen wir mal FIFO mit Global Relabeling
oder Highest Level mit Global Relabeling ist es seit mehreren
Jahrzehnten immer noch ein offenes Problem, was überhaupt die echte
Worst Case Schranke ist.
Wir haben also nur diese relativ losen Schranken, die ich hier
hergeleitet habe.
Aber bisher hat niemand Instanzfamilien angeben können, bei denen die
Komplexität tatsächlich so schlecht ist.
Vielleicht ist es so, dass man nur hergehen muss und die Analyse
verbessern, um zu zeigen, dass die Laufzeit nicht so schlecht ist.
Ich glaube, Theta N mal M oder so was, solche Instanzen kann man noch
produzieren.
Aber schlechtere sind nicht bekannt.
Wir haben hier Worst Case Schranken, die nicht besonders brauchbar
sind.
Obwohl ich sie jetzt eine halbe Stunde mit dem Beweis belästigt habe.
Das ist unangenehm, aber ich hoffe, Sie verzeihen mir das, weil ich
den Beweis wirklich sehr elegant finde und der einem Analyse-Techniken
demonstriert, die man auch für viele andere Probleme anwenden kann.
Okay, dann CG2.
Hier ist jetzt mal der Highest Level Algorithmus tatsächlich der
Beste.
Dann mit Global Relabeling und GAP bringt auch ein bisschen was.
Ist der zehnmal so schnell wie FIFO und siebenmal so schnell wie
dieses Modified FIFO und die Leda-Implementierung davon verbessert das
nochmal.
Das bedeutet insbesondere, dass wir eigentlich jetzt keine eindeutige
Antwort haben.
Bei den meisten Instanzfamilien ist FIFO besser als Highest Level,
aber bei der hier ist Highest Level deutlich besser.
Das heißt, eigentlich gibt es nicht die Implementierung von MaxFlow,
die man irgendwie immer verwenden sollte, sondern man muss irgendwie
gucken, was die Instanzen sind, die man hat.
Tatsächlich ist es so, die wichtigste Anwendung, die ich kenne von
Maximum -Flow-Berechnungen, das sind verschiedene Varianten von
Bildverarbeitungsproblemen und da gibt es nochmal ganz andere
Algorithmen, die da nochmal Größenordnungen besser sind als die
Algorithmen, die ich Ihnen hier vorgeführt habe.
Das heißt, man muss tatsächlich je nachdem, welche Anwendung man hat,
seine konkreten Algorithmen anpassen darauf, wie die Instanzen
aussehen.
Ammo...
Da ist Highest Level wieder deutlich schlechter, außer mit den
magischen Verbesserungen.
Aber ansonsten auch nicht so viel Neues.
Jetzt gucken wir uns nochmal diese Skalierung an.
Jetzt haben wir zumindest mal für drei Eingabegrößen, die auch größer
sind, nicht mal 1000 und 2000, sondern 5000 bis 20000.
Die verschiedenen Algorithmen, immer drei Zahlen nebeneinander.
Und was man jetzt machen kann, ist so ein Spiel, ich rate Asymptotik.
Ich habe ja gesagt, die Worst-Case-Schranken sind eigentlich nicht
genau genug, um die tatsächliche Asymptotik für eine bestimmte
Instanzfamilie vorherzusagen.
Jetzt...
Drei Eingabeinstanzgrößen...
Das ist jetzt auch nicht so die ideale Art, wie man Asymptotik aus
Experimenten rausliest.
Aber man kann schon ein paar Dinge sehen.
Man kann, wenn man ein bisschen sorgfältiger das macht, mit mehr
Eingabegrößen vielen zufälligen Instanzen aus einer Familie oder sowas
dann schon auch numerisch irgendwelche Funktionen drauffinden.
Und manchmal sieht man dann was.
Es ist dann kein Beweis, aber es hilft einem Hypothesen zu entwickeln,
wie die asymptotische Leistung von Algorithmen ist.
Und dann versuchen wir das mal für...
Vielleicht fangen wir mal an mit dem FIFO, der ja meistens der beste
ist.
Können wir denn sehen bei den Instanzen, was die Asymptotik ist?
Und dann vielleicht auch mal mit dem ganz einfachen...
Rani, der ganz einfache ist hier jetzt leider nicht mal da drauf.
Der Global Relabeling ist so das Simpelste, was ich da habe.
Aber vielleicht sehen wir ja was.
FIFO, Global Relabel.
Bei den Random 0,16, 0,41, 1,16.
Also wir haben jeweils eine Verdoppelung der Eingabegröße und ein
bisschen mehr als eine Verdoppelung der Laufzeit.
Also es ist irgendwie...
sicherlich nicht linear, aber auch nicht viel schlechter.
Das ist so das, was man hier das Gefühl kriegt.
Für diese Random Instanzen.
Bei Highest Level ist das irgendwie so ähnlich.
Bei CG1 haben wir hier genauer...
Hier haben wir jetzt bei CG1 plötzlich von 3,6 auf 16,06.
Das ist mehr als eine Vervierfachung.
Und 16 mal 4 ist auch deutlich weniger als 69.
Also hier haben wir mehr als eine Vervierfachung bei einer
Verdoppelung der Eingabegröße.
Das scheint mindestens quadratisch zu gehen, die Laufzeit.
Bei FIFO, wenn wir Highest Level uns anschauen, dann haben wir hier
auch nicht ganz eine Vervierfachung.
Und hier brachte ja GAP eine ganze Menge.
Aber asymptotisch sehen wir, dass da auch nicht viel passiert.
Also hier haben wir schon ein quadratisches Verhalten.
Selbst bei dem Leder-Ding habe ich mindestens eine Vervierfachung.
Bei CG1 ist das auch irgendwie...
Bei CG2 ist das auch irgendwie quadratisch.
Für FIFO, ja.
Mindestens Vervierfachung.
Aber wenn ich jetzt Highest Level nehme, dann habe ich plötzlich
ungefähr eine Verdoppelung in jeder Stufe.
Also scheinbar bei der Familie CG2 mit der Highest Level Heuristik
habe ich tatsächlich so etwas wie eine lineare Laufzeit.
Während die anderen Verfahren quadratisch sind.
Und damit habe ich natürlich bei großen Eingaben gewaltige
Verbesserungen.
Hier zum Beispiel bei den größten Eingaben mit CG2 habe ich mehr als
einen Faktor 100 in der Laufzeit gegenüber FIFO.
Das ist natürlich schon eine ganze Menge.
Und bei dieser AMO-Instanz habe ich jetzt keine so großen Änderungen.
Das ist allerdings scheinbar auch wieder sowas, wo ich in jeder Stufe
ungefähr eine Verdoppelung habe.
Also diese AMO-Instanzen sind auch relativ leicht.
Ich habe annähernd lineare Laufzeit.
Wir haben hier Iran und die AMO-Instanzen haben jeweils mehr oder
weniger in der Nähe von lineare Laufzeit.
Während die Worst-Case-Garantien, die ich habe, insbesondere für FIFO
sind kubisch.
Also ich bin wirklich ganz weit weg von dem tatsächlichen Verhalten
des Algorithmen.
Ich denke, es wäre spannend, sich dann neue Analysetechniken
auszudenken.
Wie kann ich denn zeigen, dass diese Algorithmen eigentlich viel
besser sind als die bisherigen Fragen?
Oder zumindest für wichtige Familien von Instanzen.
Da gibt es, glaube ich, noch wichtige Sachen in der Theorie, die dann
auch die Lücke zwischen Theorie und Praxis wieder verringern können.
So, noch Fragen zu den Messungen?
Damit können wir jetzt tatsächlich unser Kapitel für Maximum Flows
abschließen.
Ich möchte jetzt nochmal die wichtigsten Messages zusammenfassen, die
ich versucht habe rüberzubringen.
Zunächst mal als Problemstellung ist es irgendwie ein natürlicher
Schritt innerhalb unserer Vorlesung, dass wir sagen, wir machen erst
Pfade, zum Beispiel kürzeste Pfade oder starke
Zusammenhangskomponenten und gucken uns jetzt ein Problem an, bei dem
man viele Pfade auf einmal braucht, die dann eben insgesamt einen
Fluss darstellen.
Es gibt sehr viele Anwendungen.
In gewisser Weise sind Flüsse und Matchings und verschiedene Varianten
davon gibt es auch noch sind sowas wie die schwierigsten und
allgemeinsten Graph-Probleme, die ich kenne zumindest, die sich mit
kombinatorischen Algorithmen in polynomialer Zeit lösen lassen.
Das ist jetzt eine Aussage, die subtiler als sie vielleicht auf den
ersten Moment klingt.
Es ist so, dass Sie die ganzen Sachen hier als lineare Programme
formuliert kriegen.
Das hatte ich am Anfang auch mal gezeigt.
Sie können zum Beispiel Maximum Flows als ein lineares Programm
formulieren und da gibt es schon lange Polynomialzeit-Algorithmen und
mit linearen Programmen sind sie auch noch viel flexibler.
Sie können ganz viele andere Dinge mit linearen Programmen auch noch
tun.
Sie können sie alle in polynomialer Zeit lösen, aber spannenderweise
sind das keine kombinatorischen Algorithmen, sondern ich sag mal
grobnumerische Algorithmen.
Sie rechnen da irgendwie mit Fließkomma-Zahlen rum und am Ende
konvergiert das irgendwie asymptotisch gegen eine optimale Lösung und
dann kann man auch zeigen, nach polynomial vielen Schritten kann ich
das irgendwie so runden, dass ich dann dieses ursprüngliche diskrete
Problem wieder gelöst habe.
Wir haben ja hier bei maximalen Flüssen, wenn alle Kantenkapazitäten
ganz zahlig sind, ist es klar, dass die Lösung, die ich am Ende haben
will, auch wieder ganz zahlig zumindest sein kann.
Das kann man beweisen.
Aber Sie müssen dann sozusagen, wenn Sie das mit Hilfe von linearer
Programmierung lösen und dabei Algorithmen einsetzen wollen, die
garantiert polynomielle Laufzeit haben, müssen sie sozusagen sehr
numerisch rechnen.
Iterative, numerische Lösungen, die am Ende dann runden.
Und das ist sowohl aus theoretischer Sicht als auch aus praktischer
Sicht nicht ganz so zu befriedigen.
Und tatsächlich ist es eben auch so, dass ganz oft, wenn man einen
kombinatorischen Algorithmus hat, der dann sowohl schneller ist als
auch stabiler.
Also der hat eben dann keine Probleme mit Rundungsfehlern und solchen
Geschichten.
Aber je nachdem, wer jetzt hier im Hörsaal stände, könnte das auch
wieder zu Kriegen zwischen den Kollegen führen.
Also es gibt dann natürlich welche, die finden die numerischen Sachen
ganz toll.
Ich will mich da nicht so einmischen, aber ich wollte darauf
hinweisen, dass wir hier sozusagen an so einer Stelle sind, wo der
Übergang zwischen leichten und schwierigen Problemen, aber auch die
Grenze zwischen was ist ein kombinatorisch zu lösendes Problem und was
ist ein numerisch zu lösendes Problem, irgendwie ein wissenschaftlich
ganz spannendes ist.
Ich habe Ihnen hier anhand von maximalen Flüssen Beispiele für nicht
-triviale Algorithmen-Analysetechniken gegeben, insbesondere die
Potentialmethode.
Ich habe Ihnen aber auch ein nicht-triviales Beispiel für Algorithm
Engineering gegeben, wo man sieht, dass der Praktische und der Worst
Case weit auseinander sind und wo Heuristiken, über die man
theoretisch wenig zeigen kann, sowie Eingabe- eigenschaften und
Details des Algorithmus ganz wichtig sind und um mehrere
Größenordnungen die Laufzeit von Algorithmen beeinflussen kann.
Wir haben außerdem wieder Datenstrukturen gesehen, eine Variante von
Bucket Queues Details von Graph-Repräsentationen, die wir auch noch
nicht gesehen hatten.
Und ein bisschen drüber hinweg gegangen bin, bin ich über eine
fortgeschrittene Datenstruktur Dynamic Trees.
Das war die, bei der man
nicht -triviale Operationen über Pfade der Länge n in logarithmischer
Zeit machen kann.
Insbesondere konnte man damit dann Flussaugmentierungen machen.
Ich hatte Ihnen also dann Schranken für die Netz-Algorithmus gegeben,
die sowas wie n mal m log n waren.
Was ich nicht gezeigt habe, ist, dass man diese Datenstruktur auch in
Varianten von Preflow-Push- Algorithmen einsetzen kann.
Und dann auch wieder entsprechende Verbesserungen der Worst-Case
-Laufzeiten kriegt, die aber auch wieder so sind, dass sie in der
Praxis sich nicht wirklich auswirken.
Beziehungsweise bei diesen Dynamic Trees ist es dann in der Praxis oft
sogar so, dass sie dann die Laufzeiten eher verschlechtern.
Fragen zu Flows und Matchings.
Kleine Testfrage.
Ich habe die ganze Zeit über Flows geredet.
Außer ein paar Folien.
Weiß noch jemand, was die Matchings waren?
Was die mit Flows zu tun haben?
Ich hatte zwischendurch gezeigt, wie man also Matchings sind Mengen
von Kanten, die sich nicht berühren dürfen.
Da gibt es auch ganz viele Anwendungen von und ich habe halt mal
gezeigt, wie man in bipartitengraphen das Maximum-Cardinality-Matching
- Problem als maximales Flussproblem formulieren kann.
Da gibt es jetzt auch wieder viele Varianten davon mit gewichteten
Matchings und nicht nur bipartitengraphen, aber Varianten von
Flussproblemen sind damit jeweils eng verwandt.
Weitere Fragen zu diesem Kapitel?
Dann möchte ich die letzte Viertelstunde nutzen, um einen Start zu
machen mit dem Kapitel über randomisierte Algorithmen.
Wir kennen die im Prinzip schon aus Algorithmen 1, aber ich möchte
noch ein paar zusätzliche Dinge hier bringen, ohne dass wir hier
randomisierte Algorithmen wirklich in großem Detail behandeln können.
Es gibt da eine eigene Vorlesung von Thomas Walsch.
Ich glaube, die ist auch im Bachelor, aber ich weiß nicht, ob man die
auch im Master hören kann.
Das ist immer so ein bisschen in unserer kaputten Studienordnung.
Ich weiß nicht genau, was da kaputt ist.
Die muss kaputt sein wegen irgendwelcher Gesetze.
Jedenfalls ist das eine Vorlesung, die man möglicherweise nur im
Bachelor hören kann, obwohl sie im Master genauso nützlich ist.
Die ist dann in beiden Modulernbüchern drin, oder wie funktioniert
das?
Ah, genau, dann ist die im Master.
Dann kann man sie über Master-Vorzug im Bachelor schon hören.
Wie viele Leute hier sind denn im Bachelor-Studiengang noch?
Eine ganze Reihe.
Vielleicht nehme ich das mal als Gelegenheit darauf hinzuweisen, dass
dieser Master-Vorzug bzw.
man darf ja im Wahlbereich ohnehin Master-Veranstaltungen hören.
Da sollten Sie darauf achten.
Es gibt ganz viele spannende Vorlesungen, die nicht unbedingt schwerer
sind als Bachelor-Vorlesungen, die wir beim Master haben, einfach
damit die Master-Studenten die hören dürfen.
Schauen Sie sich die auch an.
Gerade wenn Sie sich für Algorithmen interessieren, sind das
eigentlich viele von unseren Algorithmen.
Auch meine parallele Algorithmen-Vorlesung zum Beispiel, die überlege
ich in den Bachelor zu ziehen, aber ich will auch, dass die Master
-Leute die hören können.
Genau, also da gibt es eine eigene Vorlesung dafür.
Hier ist eher so ein bisschen ein Appetizer, wo ich ein paar
fortgeschrittene Aspekte davon mal vorführen will.
Und dann konkret auch Sachen, die, soweit ich weiß, nicht in der
Vorlesung von Thomas Worsch vorkommen.
Oder das meiste davon nicht.
Wir haben in der Algorithmen-1-Vorlesung mehrere randomisierte
Algorithmen gesehen.
Zum Beispiel Clicksort oder Hashtabellen, Gartenstrukturen.
Die hatten aber alle eine Eigenschaft, die man auch als Las Vegas
-Algorithmus bezeichnet.
Es gibt mindestens zwei vom Charakter her sehr unterschiedliche Arten
von randomisierten Algorithmen.
Die Las Vegas-Algorithmen produzieren immer das korrekte Ergebnis.
Also zum Beispiel Hashtabellen.
Wenn man da eine Suchoperation macht, kriegt man das Element genau
dann, wenn es in der Datenstruktur drin ist.
Also wenn es jemand mal eingefügt hat.
Alles, was man einfügt, bleibt auch drin.
Und Clicksort produziert immer eine sortierte Ausgabe.
Das Einzige, was durch den Zufall beeinflusst wird, ist die Laufzeit.
Es gibt aber auch andere Algorithmen.
Die nennen man dann Monte-Carlo-Algorithmen.
Da kann das Ergebnis mit einer bestimmten Wahrscheinlichkeit p
-inkorrekt sein.
Das ist oft sogar in der Basisformulierung eine recht große
Wahrscheinlichkeit.
Also eine Konstante, ein Halb oder so.
Aber der Trick ist, wenn man das Ganze dann k-mal wiederholt, sinkt
die Fehlerwahrscheinlichkeit auf p hoch k.
Und dann kann man eben mit sehr wenig Wiederholungen eine sehr große
Verringerung der Fehlerwahrscheinlichkeit herstellen.
Und deshalb sind das dann oft nützliche Algorithmen.
Ich glaube, insbesondere in der Kryptografie gibt es einige Monte
-Carlo -Verfahren, wie zum Beispiel Primzahltests, um die man
eigentlich kaum herumkommt, die ganz wichtig sind, um vernünftige
Berechnungen zu machen.
Und deshalb möchte ich zumindest mal ein Beispiel eines Monte-Carlo
-Algorithmus vorführen, das außerdem eine Gelegenheit gibt für ein
nicht triviales Beispiel für Program Checking.
Und zwar stellen Sie sich vor, Sie haben einen Sortieralgorithmus und
Sie wollen überprüfen, ob der auch korrekt ist.
Idealerweise würde man gerne eine formale Verifikation des Algorithmus
machen und irgendwie Theorem dieser Algorithmus sortiert.
Leider ist das nicht immer so einfach.
Der Kollege Bernhard Beckert hat da tatsächlich schon Forschungen zu
gemacht.
Wir haben dann zum Beispiel mit formalen Verifikationsmethoden eine
Bug in der offiziellen Library-Implementierung des Java-Sortierers
gefunden, was irgendwie recht peinlich war.
Und da war das möglich, weil das ist so 100 Zeilen oder so, das war
eine Variante von Quicksort, die leider einen Bug hatte.
Jetzt ist es leider so, wir haben uns...
Wir kennen inzwischen durchaus Sortieralgorithmen, die besser sind als
Quicksort.
Wir haben zum Beispiel gerade vor zwei Jahren erst einen Algorithmus
gemacht, der vor allem als paralleler Algorithmus dann auch ein Faktor
3 oder sowas schneller sein kann als Quicksort für große Eingaben und
über ein breites Spektrum von Eingaben.
Die schlechte Nachricht ist, es sind ein paar tausend Zeilen Code.
Wir arbeiten jetzt auch daran, den tatsächlich dann in die
Standardlibraries einzubringen.
Aber das Problem ist wirklich, wir haben auch selber noch Bugs
gefunden, so Corner Cases, wo der dann falsch läuft.
Man will eigentlich in der Standardbibliothek was haben, was
garantiert korrekt ist.
Aber man will auch was Schnelles haben.
Und es gibt eben einen Ansatz, wie man sozusagen eine goldene Mittel
findet, dass man zumindest überprüfen kann, ob das Ergebnis, das ein
Algorithmus berechnet hat, auch korrekt ist.
Was man dann zum Beispiel machen kann, ist, dass man dann erst mal den
schnellen Algorithmus ausführt.
Dann überprüft man, ob das Ergebnis korrekt ist.
Und wenn das der Fall ist, ist man fertig.
Und wenn nicht, kann man ja vielleicht sogar noch mal langsam einen
Algorithmus drüberlaufen lassen, von dem man eher überzeugt ist, dass
der korrekt ist.
Aber dafür müsste man im Fall von Sortieren erst mal gucken, wie
überprüfe ich eigentlich das Ergebnis eines Sortierergebnisses.
Ich schätze, wenn ich in einem Jobinterview...
Algorithmische Fragen sind ja auch bei Google und großen Firmen
beliebte Jobinterview-Fragen.
Ich schätze, wenn ich diese Frage bei einem Jobinterview einem x
-beliebigen Informatiker in der Welt stelle, wenn der überhaupt
versteht, was ich ihm sage, wird der sagen, ja, kann ich machen.
Ich gehe einfach durch das Ergebnis und überprüfe, ob das sortiert
ist.
Leider, wenn das die einzige Anforderung wäre, kann ich einen ganz
schnellen Sortierer angeben.
Ich überschreibe einfach alles mit Null.
Oder ich überschreibe die ganze Eingabe mit dem ersten Element.
Offenbar brauchen wir irgendwie noch eine andere Eigenschaft als die
Sortiertheit.
Und diese leider ein bisschen schwieriger zu checken.
Ich will nämlich zeigen, dass die Ausgabe eine Permutation der Eingabe
ist.
Der beste deterministische Algorithmus, den ich dafür kenne, ist, dass
ich beides sortiere und vergleiche.
Aber erstens beißt sich die Katze da in den Schwanz und zweitens hätte
man gerne ein Verfahren, bei dem das Überprüfen irgendwie schneller
geht, als das Sortieren selber.
Man könnte wahrscheinlich Las Vegas Algorithmus dafür wäre, die
Elemente in eine Hashtabelle zu schieben und dann zu gucken, ob die
sozusagen die gleiche Hashtabelle erzeugen.
Aber dann braucht man ziemlich viel Platz.
Was man gerne auch hätte wäre, dass dieser Checker wenig zusätzlichen
Platz braucht.
Und hier ist jetzt ein Algorithmus, der diese ganzen Eigenschaften
hat.
Was ich mache einfach ist, ich interpretiere meine Permutationen als
Polynome.
Und zwar Polynome in einem
bezüglich eines Körpers F.
Ich sage jetzt erstmal nicht dazu, was das ist.
Das ist auch egal.
Der muss halt die Eigenschaften eines Körpers haben.
Addition und Multiplikation, die sind Kommutativ, Assoziativ und ich
habe bezüglich Addition und Multiplikation ein inverses Element.
Dann kann ich in diesem algebraischen Struktur Polynome definieren.
Und ich brauche jetzt eine Operation Field, die gegeben den Schlüssel
eines Elements oder eigentlich muss ich das ganze Element nehmen, weil
assoziierte Informationen will ich ja auch nicht kaputt machen.
Also bezüglich des Elements selber.
Das abbildet auf einem Element dieses Körpers.
Das sollte irgendeine injektive Funktion sein.
Genau.
Und jetzt definiere ich den Polynomen Q von Z.
Das ist die Differenz zwischen zwei Polynomen.
Das eine Polynom ist das Produkt von Monomialen, also einzelnen
Faktoren.
Z ist meine Variable.
Und davon wird immer abgezogen im Prinzip mein Element interpretiert
als Feldelement.
Da die Multiplikation in diesem Körper kommutativ ist, kriege ich
mathematisch gesehen das gleiche Polynom, egal wie ich meine Elemente
permutiere.
Das heißt, ich kodiere meine Permutations-Eigenschaft jetzt in das
Kommutativ -Gesetz für den Körper.
Was ich jetzt mache ist, ich habe ein anderes Polynom.
Das ist das Produkt für das permutierte Ding.
Und dann ist ganz klar, dieses Polynom ist genau dann das Nullpolynom,
wenn das eine eine Permutation von dem anderen ist.
Das Blöde ist, ich kann jetzt nicht hergehen und diese Polynome
explizit aufstellen.
Das wäre auch wieder ein linearer Platz mit relativ hohem Aufwand.
Und was ich erst recht nicht tun sollte, ist die Dinger irgendwie
ausmultiplizieren und dann die Koeffizienten zu vergleichen oder so.
Das wäre auch super teuer.
Aber man kann auf solchen algebraischen Objekten oft mit
probabilistischen Dingen einiges machen.
Man kann hier tatsächlich Eigenschaften, die man aus der Algebra
kennt, einsetzen.
Was nämlich bekannt ist aus der Algebra, ist, dass ich habe hier zwei
Polynome vom Grad N.
Die subtrahiere ich voneinander und ich kriege einen Polynom vom Grad
höchstens N.
Und so ein Polynom hat höchstens N Nullstellen.
Das gilt für beliebige Körper.
Ja.
Was ich jetzt einfach mache, ist, ich werte dieses Polynom an einer
zufälligen Stelle aus.
Ich wähle einen zufälligen Wert aus dem Körper und setze ihn hier für
Z ein.
Und dann werte ich das aus.
Das kann ich in linearer Zeit.
Das kann ich insbesondere für diesen Term hier vor der Berechnung
machen.
Und ich merke mir einfach das Ergebnis.
Und nach der Berechnung mache ich es dann halt für diesen Term,
subtrahiere die beiden Elemente voneinander und gucke, ob das Null
ist.
Ja.
Das heißt, ich habe mit konstantem Platz eigentlich die Repräsentation
von der Eingabe mir gemerkt.
Insbesondere wenn ich einen Algorithmus habe, der in place sortiert,
brauche ich mir nichts anderes speichern als nur diesen Wert da.
Und jetzt ist es so.
Ich kann natürlich falsch liegen, dass ich irgendwie einen Wert für Z
eingesetzt habe, der blöderweise eine Nullstelle von diesem Polynom Q
ist.
Dann liefert die Evaluation Null, obwohl die Dinger nicht gleich sind.
Das eine ist keine Permutation des anderen.
Aber es gibt nur N Stellen, wo mir das passieren kann.
Und ich habe ja gleichmäßig zufällig ein Element des Körpers gewählt.
Und die Wahrscheinlichkeit, dass ich eine Nullstelle gewählt habe, ist
höchstens N durch Größe dieses Körpers.
Das heißt, ich habe jetzt eine Fehlschlagswahrscheinlichkeit, die ist
N durch Größe des Körpers.
Ich müsste dann natürlich gucken, dass ich einen möglichst großen
Körper nehme.
Und ich kann wieder das Spiel machen, dass ich das mehrfach mache.
Also ich merke mir das nicht für eine zufällige Stelle, sondern
vielleicht für zehn.
Da muss ich aufpassen, dass ich es nicht für zu viele mache, sonst
braucht das wieder ziemlich viel Zeit.
Aber ich kann sozusagen diese Wahrscheinlichkeit noch beliebig kleiner
machen, indem ich das an mehreren Stellen mache.
Und das ist jetzt ein gutes Beispiel für ein Monte Carlo Algorithmus.
Also was die sagen ist, man sollte einen Wert wählen, der nicht
bereits eine Nullstelle von einem von den Dingern...
Also sie wollen jetzt eine Methode haben, wir haben jetzt nicht mehr
so viel Zeit,
einen Wert zu finden, den sie ja einsetzen, bei dem sie wissen, dass
sie keine Nullstelle haben.
Da muss ich drüber nachdenken.
Ich fürchte, dadurch, dass man da was subtrahiert und dadurch, dass ja
alle möglichen Fehler auftreten können, können sie das nicht so mit
Sicherheit sagen.
Also es gibt schon einen Grund, das probabilistisch zu machen.
Aber ich denke mal drüber nach und an der Stelle können wir beim
nächsten Mal wieder anfangen.
Ohnehin geht es dann beim nächsten Mal nicht mehr um diesen Checker,
sondern um Hashtabellen, fortgeschrittene Aspekte von Hashtabellen.
Vielen Dank.