So, schönen guten Tag.
Ich begrüße Sie zur Fortsetzung der Vorlesung Effiziente Algorithmen.
Letztes Mal habe ich Ihnen einiges erzählt, auch schon über das, was
hier als erste Folie zu sehen ist.
Nein, wir hatten angefangen nochmal mit den Such-Sortier-Verfahren.
Da waren wir schon sehr weit fortgeschritten.
Wir hatten uns mit einer Reihe von Themen da schon beschäftigt.
Wir waren bei der Anzahl der Vergleiche beim Sortieren.
Also unter der Schranke für Anzahl der Vergleiche werden spezielle
Sortierverfahren angeschaut.
Selektionsverfahren hatten dann beim letzten Mal uns eine Variante von
Quick -Select angeschaut, die Selektion in linearer Zeit, wo das
Wesentliche war, dass man so Pivot-Element aussucht, dass man immer
einen festen Anteil, also mindestens etwa ein Viertel der Elemente
rauswerfen kann, sodass man einen klaren, rekursiven Abstieg hat in
der Größe und dadurch auf lineare Zeit kommt, auch im schlechtesten
Fall.
Das war das Wesentliche, war hier kurz analysiert worden auf zwei
Folien, wobei ich das nicht explizit nachgewiesen habe durch konkrete
Nachweise.
Die Rekursionsformel ist ein bisschen anders als sonst, weil wir hier
zwei Rekursionen haben, nicht nur eine, aber man kann eben zeigen, das
muss man dann einfach explizit ausrechnen, dass man hier eine
Konstante findet, sodass man eben im asymptotischen Verhalten dann
lineares Wachstum nur hat, auch im schlechtesten Fall.
Das war das Wesentliche.
Wichtig ist, dass man mit diesem Verfahren auch sehr gut daran gehen
kann, mit diesem Ansatz das Verfahren zu parallelisieren, was wir aber
nicht genauer gemacht haben.
Da haben wir uns mit den Suchverfahren beschäftigt, haben dort die 2-3
-4 -Bäume betrachtet.
Ich habe Ihnen erzählt, wie man dort in den 2-3-4-Bäumen damit umgeht,
dass man also 2-3-4 Nachfolger hat, wie man das so hinbekommen kann,
dass immer die Pfadlänge von der Wurzel zu den Blättern gleich ist in
so einem Baum.
Wir hatten dann auch gesehen, dass man hier dieses Top-Down-Teilen,
dass man dabei dafür sorgen kann, dass man nach dem Einfügen nicht
wieder nach oben zurücklaufen muss.
Man muss dann eben nur ein bisschen öfter beim Runterlaufen schon
heilen.
Wenn man Top-Down-Teilen macht, ist auf dem Pfaden maximal ein
Vierknoten vorhanden, sodass man dadurch eben den Aufwand für dieses
Aufteilen auch reduzieren kann insgesamt.
Das Löschen geht dann ganz analog, auch das habe ich Ihnen erläutert,
mit einigen Dingen, die da eine Rolle spielen.
Und dann haben wir uns mit Rot-Schwarz-Bäumen beschäftigt, bei denen
man sich das spart, eine Datenstruktur zu bauen, in der man 2-, 3-
oder 4-fach-Knoten dort unterscheiden muss und die Operationen
aufwendig realisiert.
Hier hatten wir gesehen, indem man einfach eine interne rote Kante
oder interne rote Kanten einführt, im Prinzip mit binären Bäumen, die
Logik der 2-3-4-Bäume nachbilden und dadurch eben eine Datenstruktur
haben, die sehr einfach ist.
Das sind einfach nur binäre Knoten, also Knoten mit zwei Nachfolgern,
sofern das innere Knoten sind.
Und die können halt rot oder schwarz sein, je nachdem, ob die
reinführende Kante rot oder schwarz ist.
Und damit hat man eine einfache Art, damit umzugehen und auch die
Operationen dann entsprechend einfach zu realisieren.
Das ist also die Datenstruktur, die sich als sehr gut herausgestellt
hat in der Anwendung.
Das waren die Operationen, oder waren die rot-schwarz-Bäume.
Dann sind wir zum nächsten Kapitel gegangen, zu den Graph-Algorithmen.
Ich habe Ihnen da schon ein bisschen was erzählt.
Der Hinweis nochmal, dass Sie sich bitte anmelden für die Klausur
rechtzeitig.
Bis 11.
Juli ist noch ein bisschen Zeit.
Ich habe Ihnen dann ein bisschen was erzählt, wie wir Graphen
modellieren, wie wir sie darstellen, welche Operationen wir darauf
haben, welche Themen wir eigentlich adressieren.
Ich habe Ihnen was erzählt darüber, dass wir Wege betrachten.
Und da ist natürlich wichtig, dass wir wissen, wir haben Knoten.
Von einem Knoten zum anderen geht ein Weg.
Ein Weg ist eine Folge von Kanten.
Ohne Knotenwiederholung ist es ein einfacher Weg.
Mit einer Knotenwiederholung ist es ein Kreis.
Sofern durch das Wreck neben einer Kante daraus ein einfacher Weg
wird.
Es darf keine komplexere Struktur sein, damit das ein Kreis ist.
Kreise sind immer einfache Kreise.
Dann hatten wir den Begriff der arztzyklischen Graphen, ungerichtete
Graphen haben wir uns angeschaut.
Und dann kommen hier die typischen Graph-Probleme.
Da waren wir letztes Mal aus irgendeinem Grund die Folie zu einem
Dijkstra -Algorithmus reingerutscht.
Ich habe keine Ahnung, wie das passiert ist.
Ich habe dann nicht so reagiert, als ob diese Folie herkommt, sondern
einfach den Dijkstra-Algorithmus erläutert.
Da haben wir ein bisschen was vorweggenommen, was eigentlich heute
erst später kommen sollte.
Ist egal.
Da haben wir uns anschließend angeschaut, nach dieser einen Folie zum
Dijkstra -Algorithmus, mit den kürzesten Wegen, dass wir zunächst mal
überhaupt das Problem der Erreichbarkeit von Knoten uns anschauen.
Geht über die Erreichbarkeitsmatrix bzw.
die Berechnung der transitiven Hülle.
Also wie kann ich darstellen, dass ein Knoten von einem anderen aus
über einen Weg erreichbar ist.
Und dafür gibt es verschiedene Verfahren, solche
Erreichbarkeitsinformationen zu berechnen, indem man einfach
Matrixmultiplikationen macht.
Das war aber nicht sehr effizient.
Und dann kommt hier die erste neue Folie von heute, wo ein Verfahren
vorgestellt wird, das Sie vielleicht schon kennen aus dem Operations
Research.
Da wird das manchmal der Tripple-Algorithmus genannt.
Das ist auch bekannt.
Oder der Worschals-Algorithmus, der das das erste Mal präsentiert hat.
Und das, was Sie jetzt hier sehen, sieht auf den ersten Blick
eigentlich genauso aus wie eine Matrixmultiplikation.
Und der einzige Unterschied ist also erstmal, was steht hier
überhaupt.
Da steht eine dreifach geschachtelte Schleife für K gleich 1 bis N.
Und es steht hier für IJ jeweils von 1 bis N.
Mache ich dann eine Operation, die so aussieht, AIJ gleich AIJ oder
AIK und AKJ.
Genau die Formel, die wir auch bei der Matrixmultiplikation im Inneren
haben.
Irgendwie sind hier nur die Indizes verrutscht.
Die K-Schleife ist außen und nicht innen.
Bei der Matrixmultiplikation ist die K-Schleife innen, hier ist sie
außen.
Hier machen wir also für jedes K diese Operation für alle IJ.
Und was wird hier geguckt?
Ich meine, ich habe hier auch ein Bild.
Genau, da habe ich kein weiteres Bild.
Also ich mache mal ein bisschen Bild hin.
Was steht hier eigentlich drin?
AIJ ist die Verbindung von I nach J.
Ich habe Knoten I und Knoten J.
Und die beiden können direkt verbunden sein.
Oder auch, ich weiß vielleicht, dass die über irgendeinen Weg bereits
verbunden sind.
Also es muss nicht unbedingt eine einfache Kante sein.
Es kann auch irgendein Weg sein.
Ich weiß, die beiden sind schon verbunden.
Ich weiß, ich kann von I nach J kommen.
Oder steht jetzt hier AIK und AKJ.
Das heißt, es gibt einen Knoten K.
Und ich weiß, ich kann von I nach K kommen und ich kann von K nach J
kommen.
Dann kann ich natürlich auch von I nach J kommen.
Deswegen wird dann AIJ entsprechend auf 1 gesetzt.
Das heißt, ich kann auch über den Weg dorthin kommen.
Sieht offensichtlich sinnvoll aus.
Und hier steht jetzt eben jeweils das A aus der Adjacenzmatrix.
Das heißt, ich erweitere das einfach.
Und das macht ihr einfach transitiv.
Und die Frage ist, ob das eigentlich schon ausreicht, die transitive
Hülle, die Erreichbarkeitsmatrix insgesamt damit zu berechnen.
Also ich schaue ja hier für K gleich 1, schaue ich nach, bei allen IJs
sind I und J bereits verbunden oder gibt es einen Weg über den Knoten
1.
Also ist I mit 1 verbunden und 1 mit J.
Für K gleich 2 schaue ich, gibt es einen Weg von I nach J oder gibt es
einen Weg von I nach 2 und von 2 nach J und so weiter.
Das heißt, das was hier drin stehen kann, auf den Kanten dazwischen,
das sind doch jeweils, ich schreibe das mal so hin, das können nur
Knoten sein auf dem Weg zwischen I und J von 1 bis K-1.
Nur die Knoten können dort aufgetaucht sein, weil die sind bereits in
früheren Iterationen für kleineres K berücksichtigt worden.
Das gleiche gilt auch hier.
Da können Knoten von 1 bis K-1 aufgetaucht sein.
Und jetzt kommt noch ein Knoten dazu.
Wenn ich also über einen Pfad der Knoten zwischen 1 und K-1 erhält
nach K kommen kann und von K entsprechend nach J, dann kann ich eben
auch von I nach J kommen und dann taucht auch ein Knoten K auf.
Natürlich taucht jeder Knoten nur einmal auf, wir haben ja keine
Kreise.
Und offensichtlich ist es so, wenn ich dann bei N angelangt bin, dann
habe ich iterativ natürlich bereits alle Pfade betrachtet, bei denen
die Knoten 1 bis N auftauchen können auf dem Pfad.
Und da kommt noch der Knoten N dazu.
Und damit habe ich dann wohl alle Möglichkeiten erwischt, von I nach J
zu kommen.
Also das zu beweisen, dass das korrekt ist, ist relativ einfach.
Das interessante ist, dieser Algorithmus insgesamt, der hat einen
Aufwand von N hoch 3.
Offensichtlich, dreifach geschachtete Schleife.
Wir hatten vorher gesagt, allein um festzustellen, ob es einen Weg der
Länge 2 gibt, zwischen zwei Knoten, mache ich eine Matrix
-Multiplikation.
Da hätte ich aber dann eine Schleife über I und J iteriert und dann
über alle K von 1 bis N geguckt, ob es einen Pfad gibt der Länge 2
zwischen I und J.
Über irgendeinen Knoten von K gleich 1 bis N.
Und hier mache ich das systematisch, fange einfach mit K gleich 1 an
als Zwischenknoten, dann K gleich 2 und so weiter.
Und offensichtlich ist es so, dass man damit bereits alle Pfade
erwischt hat.
Weil ich halt sukzessive das immer aktualisiere.
Bei dem Aij stecken bereits alle Pfade drin, wie hier angedeutet, die
Knoten zwischen 1 und K-1 auch enthalten können.
Und hier stecken entsprechend eben auch jeweils solche Pfade drin.
Und damit habe ich jeweils alle Pfade dann am Ende erwischt.
Eine Verbesserung ist sehr leicht möglich.
Also das hier ist, das linke ist die Originalversion, rechts ein
bisschen vereinfacht.
Ich kann natürlich gucken, ob überhaupt ein Pfad von I nach K
existiert.
Wenn also überhaupt kein Pfad von I nach K existiert, brauche ich mein
IJ nicht zu aktualisieren.
Ja, denn dann ändert sich ja nichts.
Und dann schaue ich für J gleich 1 bis N, wenn also es noch keinen
Pfad von I nach J gibt, ja, wenn die noch nicht verbunden sind, dann
setze ich AIJ auf AKJ.
Denn wenn es einen Pfad von K nach J gibt, und es gibt ja
offensichtlich einen von I nach K, gibt es auch einen von I nach J.
Und das brauche ich nur zu machen, wenn es bisher noch keinen Pfad von
I nach J gegeben hat.
Und das heißt, hier spare ich mir einige dieser Ausführungen dieses
Ausdrucks.
Im Prinzip ist das die gleiche Logik hier drin, aber eben etwas
vereinfacht.
Ich spare mir ein paar Operationen.
Reduziert den Aufwand um einen kleinen konstanten Faktor.
Aber so kann man das ein bisschen optimieren.
Wie gesagt, im Mittel etwas reduziert, schlechtesten Fall natürlich
immer noch O von N hoch 3.
Also wenn ich Glück habe, kann es passieren, dass ich hier wirklich
sehr selten nur überhaupt diesen Teil machen muss.
Und das heißt, es könnte sein, dass ich dann sogar in quadratischen
Aufwand reinkomme.
Aber das hängt eben sehr stark von den Graphen ab.
Auch hier bin ich immer noch in N hoch 3, auch im Mittel, aber das ist
trotzdem eine Verbesserung.
Ich habe das jetzt nicht explizit bewiesen, dass das so ist, aber ich
glaube, ich habe das anschaulich gemacht.
Induktiv macht man das genau über diese Art, über diese Überlegung,
dass ich halt hier induktiv zeigen kann.
Ich habe dann damit wirklich alle Pfade erwischt.
Jetzt kann man sich überlegen, dieser Algorithmus sieht doch genauso
aus wie das, was wir gemacht haben bei dem Mapping-Ansatz.
Da hatten wir bei der Mathematik-Multiplikation diesen schönen
algebraischen Ansatz, wie wir parallele Algorithmen erzeugen.
Schauen wir uns das mal hier an, für den Wortschallalgorithmus.
Auch ein schönes iteratives Verfahren.
Und jetzt machen wir daraus die Single Assignment Form.
Wir müssen ja für den Mapping-Ansatz Single Assignment Form machen.
Single Assignment Form heißt, ich habe zunächst mal, es gibt viele
verschiedene Möglichkeiten das zu tun, eine naheliegende ist zunächst
mal zu sagen, ich habe Variablen a, i, j, k jeweils, also mit drei
Indizes brauche ich ja.
Und zunächst mal schreibe ich da in a, i, j, 0 das a, i, j jeweils
rein.
Das heißt, das ist meine Anfangsmatrix.
So, und das was hier steht, dieser Teil hier, den muss ich jetzt
übersetzen.
Also a, i, j, k wäre das.
Was steht hier drin?
Da steht a, i, j aus der vorherigen Schleife.
Also hier ist ja, das hier wird unser, ich schreibe mal hier oben hin
k.
Da oben steht ja k-1, da steht auch k-1 und da steht auch oben drüber
k -1.
So, also, das ist das a, i, j aus der vorherigen Schleife, das ist das
a, i, k aus der vorherigen Schleife und das ist das a, k, j aus der
vorherigen Schleife.
Wenn ich mir diese Rekurrenzgleichung jetzt anschaue, das ist jetzt
Single Assignment Form, also am Ende natürlich t, i, j, die Transitive
Erreichbarkeitsmatrix ist natürlich das a, i, j, n für alle i, j, das
ist klar.
Wie sieht das mit den Abhängigkeiten aus?
Bei der ersten Stelle, i, also erste Stelle hier, erste Komponente, da
habe ich hier Abstand 0, da habe ich auch Abstand 0 und da komme ich
auf einen Index k.
Das heißt, hier habe ich i-k als Differenz.
Das heißt, die Datenabhängigkeit ist nicht gleichmäßig, wie bei der
Matrix -Multiplikation hatten wir jeweils den vorhergehenden Zeitpunkt
oder den benachbarten Index.
Hier ist es nicht der benachbarte Index, sondern eine Indexposition
mit Abstand i-k an der ersten Stelle.
Bei der zweiten Stelle analog kommt dann hier j-k da rein.
Bei der dritten Stelle ist es schön einfach nur Abstand 1.
Und hier sehen wir eben, wir haben keine Uniformabhängigkeiten für
alle Indizes i, j, k, die gleichen Abstände, aus denen jetzt die Daten
kommen, sondern das hängt ab von der jeweiligen Position, von dem
jeweiligen Index i, j, k, von welcher Stelle aus diesem Indexraum die
Daten kommen, die jetzt bearbeitet werden müssen.
Und wir sehen das auch gleich, wenn wir uns das nochmal anschauen,
wenn wir daraus einen parallelen Algorithmus machen wollen.
Also es ist offensichtlich, die Abhängigkeiten sind nicht uniform,
deswegen können wir das Verfahren, das wir gemacht hatten für die
Matrixmultiplikation, um dort parallele Varianten zu erzeugen, so
nicht einsetzen.
Und, ich muss mal kurz Fenster zumachen, wir haben eben keine einfache
Parallelisierung.
Jetzt zeige ich Ihnen, wie man das doch parallelisieren kann und dann
lernen Sie noch eine andere Art der parallelen Algorithmen kennen.
Parallele Variante.
Was müsste man denn jetzt machen?
Was muss ich eigentlich berechnen?
Ich muss ja überall diese, das ist meine Gleichung, die ich berechnen
muss.
Das ist die Aufgabe, die ich habe.
So, wenn ich an irgendeiner Stelle bin, hier zum Beispiel, A33, dann
brauche ich für K1 das Element und das Element.
Für K2 brauche ich das Element und das Element.
Dann K3 das und für K4 brauche ich dieses und dieses hier.
So, wie kann ich das hinbekommen?
Wie kann ich die zusammenbringen?
Irgendwie passt das nicht zu dem, was wir bei der Matrix
-Multiplikation gemacht hatten.
Jetzt machen wir folgende Idee.
Ich lösche das mal wieder weg, was ich gerade gemalt habe.
Diese Abhängigkeiten, die sind etwas problematisch.
So, jetzt schauen wir uns das nochmal an.
Die Idee, die wir jetzt machen, um das zu parallelisieren, ist
folgende.
Wir bewegen die erste Zeile von oben nach unten.
Also, A11 schreiben wir jetzt auch hier hin.
Das A12 auch da hin und hier entsprechend.
Wir schreiben das auch hier hin, A11 und auch da hin, A11.
Und speichere dabei die Werte in den durchlaufenden Prozessoren,
zusätzlich ringschieben.
Das heißt Matrixzeile I in Prozessorzeile I-1.
Was heißt das?
Ich bewege im Prinzip diese erste Zeile, so wie es hier angedeutet
ist, nach unten.
Und mache das in so einer Art Ringschieben.
Das heißt, das Ganze läuft hier so durch.
Und diese erste Zeile, die wird also überall abgespeichert in den
anderen Prozessoren.
Und gleichzeitig rutschen alle Zeilen I nach oben.
Ich vertausche also im Prinzip hier die beiden.
Dann vertausche ich die beiden, dann vertausche ich die beiden.
Und bin dann schon fertig.
Und lasse jeweils das A11 eigentlich an der Position dann stehen.
Ich zeige Ihnen das gleich nochmal ganz konkret auf der nächsten
Folie.
Das habe ich also in jedem Prozessor drin stehen.
Ich mache mal hier einen Prozessor da rein.
Was steht da drin?
Da stand ursprünglich drin mein AIJ.
Jetzt habe ich dazu geschrieben AIJ.
Wenn wir die erste Zeile runtergeschoben haben, habe ich hier das A1J
auch reingeschrieben.
Und jetzt schiebe ich die erste Spalte nach rechts.
Ich schiebe die erste Spalte nach rechts auf die gleiche Art und
Weise.
Also auch die hier in so einen Ring schieben.
Und wenn die Spalte darüber geht, dann heißt das, ich habe hier auch
noch das AI1 dort mit drin stehen.
Aus der Zeile I kommt das erste Element in alle anderen auch hinein.
In alle anderen Elemente der Zeile.
Wenn ich das mit der ersten Zeile und der ersten Spalte gemacht habe,
habe ich hier also das AIJ, das AI1 und das A1J.
Das heißt für K gleich 1 kann ich genau diese Operation dort
ausführen.
Das ist ein ziemlicher Aufwand.
Ich muss jetzt also, um das zu machen, die erste Zeile runter bewegen.
Ich muss die erste Spalte ganz nach rechts schieben.
Dann habe ich, weil das Ringschieben ist, die erste Spalte und die
erste Zeile jetzt unten und ganz rechts.
Ich habe aber überall die Elemente der ersten Zeile und der ersten
Spalte stehen gelassen, sodass ich eben überall jetzt diese drei
Elemente abgespeichert habe.
Jetzt kann ich in jedem Element das machen.
Das sind zunächst mal 2n-2 Operationen für das Verschieben und dann
nochmal einmal ausführen diese Operation.
Und das müsste ich jetzt für jedes K machen.
Das wäre ein ziemlicher Aufwand.
Das, was ich hier gemalt habe, steht hier nochmal Prozessor I-1J-1.
Diese drei Elemente stehen eben nicht im Prozessor IJ.
Wir sind ja um 1 nach oben gerutscht und um 1 nach links.
Das heißt, die sind an der Position I-1J-1.
Und da drin sind jetzt AIJ, AI1 und A1J.
Und ich kann dort genau diese Ausführung, diese Berechnung machen.
Wenn ich das N mal mache, dann habe ich den Wortschallalgorithmus
simuliert.
Für jedes K kann ich diese Operation machen.
Das wäre aber ein Aufwand, der quadratisch wäre mit einem
quadratischen Feld.
Das ist eine schlechte Effizienz.
Und jetzt ist die Idee, dass man diese Operation im Pipelining
-Verfahren durchführt.
Das schauen wir uns aber gleich auf der übernächsten Folie an.
Zunächst mal will ich das nochmal darstellen in diesem Beispiel mit
dem 4x4-Feld.
Wie gesagt, zu Anfang stehen hier diese AIJ in den Zellen drin.
Dann mache ich dieses Ringschieben mit der ersten Zeile.
Es sind alle Zeilen genau um 1 nach oben gerutscht.
Und die erste Zeile halt entsprechend nach unten.
Und es sind die Elemente der ersten Zeile überall drin
reingeschrieben.
Und entsprechend habe ich hier jetzt alle Spalten 1 nach rechts
geschoben.
Da ist also jetzt das A1-2 an der Position.
A1-3, A1-4, A1-1.
Und entsprechend hier A4-2 und so weiter.
Die zweite Spalte steht jetzt ganz links.
Und ganz rechts stehen die Elemente aus der ersten Spalte.
Beziehungsweise auch Elemente aus der ersten Zeile.
Also auf die Art und Weise habe ich das so verteilt.
Und das ist genau dieses Durchschieben in die beiden Richtungen.
Und das steht hier nochmal drin.
Endmalige Ausführung simuliert den Borschel-Algorithmus.
Und jetzt versuchen wir das in Pipelining-Verfahren zu machen.
Und das heißt, dieses Verschieben, das muss ich ja nicht gleichzeitig
machen, auf allen Elementen einer Zeile oder einer Spalte.
Ich mache das zeitversetzt.
Ich fange hier oben an mit dem obersten Element und mache das
Verschieben der ersten Spalte und der ersten Zeile.
Oder praktisch gleichzeitig.
Und lasse das sukzessive durchlaufen.
Also ich schiebe das nicht, so wie das ursprünglich gedacht war, hier
einfach so runter.
Also das mache ich nicht, sondern ich mache das eben so, dass ich hier
das, was ich machen muss, ich mache es mal anders auf,
das, was ich eben noch anders, das, was ich mache, ist, dass ich meine
Zeilen im Prinzip so versetzt hier und die Spalten versetzt im Prinzip
so durchschiebe.
Aber ich schiebe hier von außen nichts rein, sondern ich nehme die
Elemente, die ich in den Zellen drin habe, aber eben so zeitversetzt.
Und damit habe ich eben die Möglichkeit, diese Operation jeweils so
auf solchen Diagonalen, in solchen Wellen hier durchlaufen zu lassen.
Und es ist die Anzahl der Schritte, die ich brauche, für jetzt das
Verschieben der Zeile und Spalte, für K gleich 1 oder für irgendein K.
Das ist eine konstante Anzahl von Schritten.
Ich muss etwas von oben lesen, etwas von links lesen.
Ich muss etwas nach oben schieben, also der obere muss unten lesen und
der linke muss rechts lesen.
Wenn ich hier meine 4 Prozessoren habe, dann muss ich hier einen
Austausch machen.
Ich brauche diesen Austausch und damit habe ich die richtigen Elemente
dort stehen.
Und dann muss ich entsprechend die Operation ausführen auf den
Elementen.
Das ist nicht nur ein Schritt, das sind 3 oder 4 Schritte, die ich
machen muss.
Aber eben eine konstante Anzahl von Einzeloperationen, um dieses
Verschieben der Zeilen und Spalten zu simulieren, im Pipelining
-Verfahren oder in solchen Berechnungswellen.
Und dann habe ich einen konstanten Aufwand pro Welle und habe
insgesamt eine lineare Ausführungszeit für meinen Algorithmus.
Das heißt, ich habe dann mit N² Prozessoren eine Ausführungszeit, die
linear ist und damit einen optimalen Zeitgewinn gegenüber der
sequentiellen Ausführung des Warschall-Algorithmus.
Und das ist also die bestmögliche Art, wie man das machen kann.
Es gibt spezielle Rechner-Architekturen, die genau solche
Berechnungsstrukturen unterstützen.
Wavefront-Arrays, die man genau solche Operationen macht, kann man
viele verschiedene Arten von Problemen damit lösen.
Aber damit haben wir jetzt zwei Möglichkeiten, wie wir auf einem
zweidimensionalen Feld einen solchen Algorithmus ausführen können, der
so eine dreifach geschachtelte Schleife ist.
Wir hatten den Typ Matrix-Multiplikation.
Das war im Prinzip das Bild, das ich hier gerade nochmal gemalt hatte.
Da wussten wir, wie man das macht.
Und das andere ist jetzt hier diese Warschall-Algorithmus-Idee.
Auch hier ein Pipelining-Verfahren möglich, aber eine andere Art der
Bewegung der Daten als bei der Matrix-Multiplikation.
Das Problem, das wir hier kompensieren mussten, waren die
unterschiedlichen Entfernungen zwischen den Daten, die in dem
Rekursionsschritt jeweils bearbeitet werden müssen.
Das ist also optimaler Zeitgewinn gegenüber der sequentiellen
Ausführung des Warschall-Algorithmus und damit eine neue parallele
Variante.
Das ist das Prinzip der Wavefront Arrays oder der Instructional
Systolic Arrays, die ich Ihnen aber nicht im Einzelnen vorstelle.
Instructional Systolic Arrays sind Varianten von Parallelrechnern, die
vor langer Zeit mal in meiner Gruppe entstanden sind.
Die sind auch tatsächlich gebaut worden als Einschubkarten für PCs.
Aber wie so viele andere Parallelrechner haben die auch ihre Bedeutung
damals verloren, weil die Entwicklung der sequentiellen Rechner der
PCs einfach zu schnell war.
Heutzutage kann das Prinzip eigentlich wieder sinnvoll auch in
Multicore -Rechner eingesetzt werden.
Hatten Sie eine Frage?
Es werden die Elemente der Matrix da durchgeschoben.
Es wird dafür gesorgt, dass die Elemente aus der ersten Zeile verteilt
werden über das ganze Feld.
Also es ist so, ich sagte ja, die werden im Prinzip vertauscht.
Das Element aus der ersten Zeile geht nach unten.
Ich muss das erste Element runterschieben.
Das Element von unten muss ich nach oben schieben.
Also das A111 geht nach unten, bleibt dort aber gespeichert.
Das A211 geht nach oben.
Und hier kommt von links nichts dazu, das passiert hier eben auch.
Die Matrix wird nicht kleiner.
Die Größe bleibt ja gleich, weil die unterste Zeile wandert nach oben
und das A1 wandert dann praktisch daran vorbei und geht dann in die
letzte Zeile rein.
Das ist ja das, was Sie hier auf der vorherigen Folie...
Ich gehe nochmal auf die Folie 9.
Die erste Zeile ist anschließend unten.
Die sind dann natürlich nach unten gewandert und die erste Spalte
wandert nach rechts.
Das heißt, das erste Element der ersten Zeile liegt dann natürlich
auch hier ganz rechts.
Das heißt, wir haben das miteinander alles verschränkt und damit sind
genau diese Abhängigkeiten, die erforderlich sind, die drinstecken in
dem Warshall-Algorithmus, die sind damit berücksichtigt.
Ich habe die genau an dem richtigen Ort.
Ich habe an jedem Ort anschließend genau diese drei Elemente, die ich
brauche, um die Rekkurrenz auszuführen.
Dazu muss ich also die Elemente der ersten Zeile verteilen, die
Elemente der ersten Spalte und dann ausführen.
Wie man das macht, ist halt die Frage.
Ich habe gezeigt, man kann das in so einem diagonalen Verfahren
machen, in so einer Art Wellenbewegung.
Dadurch, dass ich das dann im Pipelining-Verfahren machen kann, kann
ich dann eben Zeit sparen.
Wenn ich das nicht im Pipelining-Verfahren machen würde, wenn ich das
durch sequenzielles Durchschieben machen würde, hätte ich jeweils
einen Aufwand von N, um die Elemente zu verteilen.
Im Prinzip muss ich ja die Elemente der Kartenzeile und der
Kartenspalte jeweils über das ganze Feld verteilen.
Und das mache ich halt systematisch, indem ich bei der ersten anfange
und so weiter.
Und das ist halt gerade diese Idee dieser Wavefront Arrays.
Und ganz am Ende habe ich natürlich dann wieder die an der richtigen
Position, weil ich dann ja die letzte Zeile, die 4K gleich N, die
Zeile N durchgeschoben habe.
Und dann ist die wieder am Ende an der richtigen Position unten
angekommen.
Am Ende habe ich die richtige Matrix drinstehen in meinem Feld und
habe dann dort jeweils die Werte der Erreichbarkeitsmatrix stehen.
Okay, das war Erreichbarkeit.
Jetzt kommt die Folie an der richtigen Stelle, mit der Annotation vom
letzten Mal.
Wir wollen nicht nur wissen, welche Knoten sind von welchen aus
erreichbar, sondern wir wollen auch wissen, was sind denn die
kürzesten Wege innerhalb dieser erreichbaren Knoten.
Wir nehmen also davon aus, wir haben einen zusammenhängenden Graphen,
oder muss gar nicht unbedingt sein.
Wir haben einfach irgendeinen Graphen und wollen wissen, was sind die
kürzesten Wege zwischen zwei Knoten.
Das haben wir letztes Mal schon angeschaut.
Sie erinnern sich, wir haben diese Menge S genommen, der sicheren
Knoten, bei dem wir wissen, wie der kürzeste Weg ist, von U nach den
Knoten in dieser Menge.
Und das Bild war eben dieses Bild, dass wir dann suchen nach dem
Knoten außerhalb der Menge S, der den kürzesten Abstand hat zu dem
Knoten U.
Das war dieser Knoten W.
Und den haben wir dann reingenommen in die Menge S.
Das war angedeutet durch diese Linie hier um das W herum.
Und dann haben wir alle anderen Entfernungen aktualisiert durch diese
Operation, die hier steht.
Minimum von dv und dw plus cwv.
Das heißt die Frage, inwieweit eine Kante von W nach irgendeinem
Knoten V außerhalb von S dazu führt, dass ich einen kürzeren Pfad
entdecke zu meinem Knoten U.
Das Verfahren ist Ihnen bekannt.
Aufwand ist quadratisch.
Und nochmal zur Korrektheit des Algorithmus.
Wir wählen ja immer den Knoten, der den kürzesten Abstand von U hat,
wobei nur Wege über zuvor gewählte Knoten betrachtet werden.
Das ist im Prinzip ein typisches Greedy-Prinzip.
Ich nehme also die nächstbeste Information, von der ich annehme, dass
ich nichts Besseres tun kann in dieser lokalen Situation.
Und in diesem Fall ist es tatsächlich so, dass eine Folge von lokal
-optimalen Entscheidungen hier das Optimum liefert.
Wir müssen eben zeigen, dass in dem Schritt 3, Schritt 3 ist dieser
Schritt hier, ich wähle diesen Knoten V, also diesen Knoten W aus, der
den minimalen Abstand hat zu dem Knoten U, dass das tatsächlich
richtig ist.
Also das DW muss an der Position tatsächlich die Länge des kürzesten
Weges von U nach W sein.
Ich habe ja einen Knoten W, von dem ich noch nicht sicher weiß, also
das ist V minus S, in S sind die drin, von denen ich sage, da habe ich
sicher die Information über den kürzesten Weg.
Und hier muss ich zeigen, wenn das jetzt der Knoten ist mit der
kürzesten Entfernung zu dem Knoten U, dann ist das tatsächlich die
Länge des kürzesten Weges in dem gesamten Graphen von U nach W.
Und wenn das nicht der Fall wäre, wenn diese Behauptung falsch wäre,
müsste es ja einen Weg geben von U nach W, also von U nach W.
W wird eigentlich ausgesucht, weil aktuell die Information in den
Abständen DW hat irgendeinen Wert.
Und es könnte ja sein, dass es einen Knoten X gibt, über den man nach
W gelangen kann.
Also von U nach W über einen Knoten X, das heißt es müsste hier noch
irgendeinen Weg von U nach X geben und dann irgendwie zu dem W,
wobei dann natürlich, wenn also das ein kürzerer Weg wäre von U nach
W, dann muss ja der Abstand von U nach X, dieses DX hier, kleiner sein
als der Abstand von U nach W, den man bisher gehabt hat.
Dann müsste das U nach X kürzer sein.
Wenn aber das X, was noch nicht in S drin liegt, einen kürzeren
Abstand hat zu U, wenn das DX kleiner als DW ist, dann hätte ja X
bereits gewählt werden müssen, dann hätte ja nicht W ausgewählt werden
müssen, weil ja in Schritt 3 hier das DW gerade sich auf den Knoten
bezieht, der den minimalen Abstand hat, von allen Knoten außerhalb von
S.
Und deswegen ist das ein Widerspruch dagegen, dass das X nicht aus S
ist.
Das kann so eine Situation gar nicht geben.
Und in Schritt 5, schauen wir uns den Schritt nochmal an, Schritt 5,
berechne ich, aktualisiere ich jetzt die ganzen Abstände und sage, ich
muss nur betrachten den bisherigen Abstand von einem Knoten zu U oder
den Abstand eines des Knoten W von U plus Kosten einer Kante von W
nach V.
Das heißt, wenn es zu einem Knoten V eine Kante gibt von W nach V,
dann kann es sein, dass der Weg über W ein kürzerer Weg ist, als der
bisher betrachtete Weg, der die Grundlage für das DV war.
Das heißt, ich habe bisher irgendeine Information, ich weiß, ich habe
hier irgendeinen Pfad von U nach W
und habe jetzt hier noch potenziell eine Kante von W nach V, das habe
ich hier, also das C, W, V, was noch dazu kommt.
Und ich muss sagen, dass tatsächlich für so einen Knoten V jetzt
dadurch ein kürzerer Weg dann gefunden wird, also der Weg von U über W
und irgendein X nach V, der kann natürlich nicht kürzer sein, als der
Weg von U über X direkt nach V oder der Weg von U über W in eine
weitere Kante.
Also die Gewichte sind alle größer gleich Null.
Wenn es einen kürzeren Weg gäbe von U nach V über irgendwelche anderen
Knoten hier aus der Menge S, dann wäre das V bereits gewählt worden,
wenn der Weg kürzer wäre als der Weg von U nach W.
Ist ja größer als der Weg von U nach W und wenn ein kürzerer Weg nicht
nur über eine solche Kante kommen würde, sondern auf andere Art und
Weise, wenn ich also noch über andere Knoten laufen müsste, um zu V zu
kommen, dann wäre der Weg ja noch länger und das heißt, da die
Gewichte alle größer Null sind, kann es keinen anderen kürzeren Pfad
gegeben haben da drin.
Das heißt, es wird hier tatsächlich die Länge der kürzesten Wege
bestimmt.
Ich hoffe, dass das einigermaßen verständlich war.
Also Dijkstra-Algorithmus ist Ihnen bekannt aus Operations Research,
ich habe also hier kein Beispiel dafür gemacht, ich habe nur das
Verfahren vorgestellt.
Wir wissen also jetzt, man kann mit Dijkstra-Algorithmus die kürzesten
Wege berechnen.
Wir wissen, dass der Prinzip der Dijkstra-Algorithmus an vielen
Stellen eingesetzt wird, insbesondere im Internet bei Algorithmen,
wenn sie dort das Routing machen, dann wird bei dem Open Shortest Path
First, ist ein Teil dann eben über den Dijkstra-Algorithmus die
kürzesten Wege zwischen all den Knoten zu bestimmen oder von dem
jeweiligen Knoten zu allen anderen und daraus ergibt sich dann die
Routing -Tabelle.
Jetzt kann man sich auch dafür interessieren, alle kürzesten Wege zu
berechnen, also nicht nur die kürzesten Wege von einem Knoten zu einem
anderen, sondern die kürzesten Wege zwischen je zwei Knoten.
Und das ist eigentlich ganz ähnlich, wie das, was wir vorher als
Erreichbarkeitsmatrix betrachtet haben.
Oder als Bestimmung der Erreichbarkeitsmatrix.
Ich möchte also für alle Paare uv aus v den kürzesten Weg von u nach v
haben.
Ich könnte das so machen, dass ich einfach für jeden Knoten den
Dijkstra -Algorithmus anwende.
Dann ist der Aufwand in N hoch 3.
Könnte man machen.
Der Dijkstra-Algorithmus war quadratisch.
Ich kann auch den Algorithmus von Floyd nehmen.
Und der sieht jetzt so aus.
Zunächst mal setze ich für jede Paar i und j, also jetzt sind hier i
und j meine Knoten, nicht u und v.
Ich nehme also an, dass meine Knotenmenge von 1 bis N durchnummeriert
ist und ich habe jetzt i und j von 1 bis N jeweils.
Da gucke ich mir die aktuelle Kantenbelegung an.
Cij ist entweder unendlich, wenn ich keine Verbindung habe, oder es
ist irgendein anderer Wert, wenn ich dort Kanten habe.
Und dann mache ich für k gleich 1 bis N, für i, j gleich 1 bis N, eine
Operation, die sieht so aus.
Ich schaue mir an, die Entfernung, wieder wie vorher, ich habe hier
meinen Knoten i, meinen Knoten j, ich habe einen Knoten k.
Und ich schaue mir an, das Minimum der Entfernung von i nach j, von i
nach k plus k nach j.
Also hier habe ich, das ist mein dij, das ist mein dik, und hier habe
ich mein dky.
Und damit bestimme ich jetzt den kürzesten Weg.
Das heißt, den kürzesten Weg bekomme ich dadurch, dass ich für jeden
Knoten mir anschaue, wie ist die Entfernung von i nach j, über
irgendwelche Knoten, oder gibt es einen Weg, der kürzer ist, wenn ich
über k laufe.
Und das ist eigentlich genau der Algorithmus, den wir vorher als
Waschall -Algorithmus bezeichnet haben.
Nur habe ich jetzt nicht mehr Werte 0 und 1 hier drin stehen, wie bei
dem Waschall-Algorithmus, sondern hier stehen jetzt die Entfernungen
drin, zwischen den jeweiligen Knoten.
Und hier steht also jetzt nicht mehr nur, ob die verbunden sind,
sondern welchen Kosten.
Und ich nehme dann immer gerade das Minimum dieser möglichen Pfade.
So, das heißt, also Korrektheit geht genauso zu beweisen wie vorher
auch bei dem Waschall-Algorithmus.
Kann man einfach induktiv zeigen, dass man dadurch alle kürzesten Wege
bekommt.
Wir wissen, wie man das parallelisiert.
Dadurch, dass wir den Waschall-Algorithmus parallelisiert haben,
können wir auch den Floyds-Algorithmus genauso parallelisieren.
Da brauchen wir nicht extra was anderes zu machen.
Aufwand in NO3, parallel, in linearer Zeit, durchführbar.
Und jetzt noch eine Frage.
Ich habe dann also eine Matrix.
Und da steht an jeder Position IJ, halt hier gerade das DIJ.
Ich weiß, wie weit die voneinander entfernt sind.
Ich möchte gerne auch noch haben, den vollständigen kürzesten Weg.
Ich möchte wissen, welches ist denn der Weg.
Für die Routing-Tabelle muss ich wissen, was ist der nächste Knoten
auf dem Pfad von I nach J oder von U nach V.
Das muss man sich überlegen, wie kriegt man das denn jetzt noch raus.
Da müsst ihr ja nochmal alles durchschauen.
Und jetzt ist einfach die Idee, oder ein naiver Ansatz wäre, für jedes
Paar UV, den kürzesten Weg vollständig abzuspeichern.
Aber Sie wissen, wenn ich sage Routing-Tabelle im Internet, da
speichern wir nur ab, was ist der nächste Knoten.
Ich bin bei einem Knoten, jetzt schaue ich einfach, hier ist mein
Zielknoten, was ist der nächste Knoten, zu dem ich gehen muss, damit
ich auf dem kürzesten Weg tatsächlich dann irgendwann meinen
Zielknoten erreiche.
Schauen wir nur den nächsten an.
Wenn ich den ganzen Weg abspeichern würde, für jedes Knotenpaar, hätte
ich einen Platzbedarf von N hoch 3.
Weil die Pfade im Prinzip die lineare Länge haben können in der Anzahl
der Knoten und damit wäre der Aufwand sehr hoch.
Und die Idee ist eben, es reicht nur zu wissen, was ist die letzte
Kante des kürzesten Weges von U nach V.
Das heißt, ich speichere mir hier jeweils den Knoten ab, den ich als
letztes besucht habe in diesem Algorithmus.
Wenn also dieses Cij kleiner und endlich ist, dann setze ich, das
heißt ich habe hier bereits eine Verbindung zwischen I und J, dann
speichere ich mir ab, dass ich von I nach J gekommen bin.
Das heißt, auf dem Weg von I nach J ist der letzte besuchte Knoten das
I, das ist der Start.
Und dann kommt hier der eigentliche iterative Algorithmus, wieder mit
einer leichten Vereinfachung.
Wenn überhaupt die Summe der Abstände zwischen I und K und K und J
kleiner ist als der Abstand von I nach J, also I, K und K, J habe ich
ja schon berechnet, die Abstände aus der vorherigen Schleife,
dann setze ich entsprechend das Dij auf das Dik plus Dkj.
Berechen das natürlich, also so würden Sie das niemals implementieren,
hoffe ich, weil Sie hier nämlich zweimal diesen Term berechnen würden.
Ich habe das hier nur zur Vereinfachung so hingeschrieben.
Sie würden hier natürlich nur einmal berechnen, diesen Wert.
Und dann speichere ich mir ab, dass der letzte Knoten, den ich besucht
habe, auf dem Weg von I nach J, dann der letzte Knoten ist, den ich
auf dem Weg von K nach J besucht habe.
Von I nach J über K.
Entweder war ich also auf dem alten Weg gelaufen oder ich bin über K
gelaufen.
Und das heißt, dann muss ich mir anschauen, was ist der letzte Knoten
auf dem Weg von K nach J gewesen.
Den speichere ich mir hier ab, der sitzt in der Variable WKJ.
Und das ist jetzt der letzte Knoten auf dem kürzesten Weg von I nach
J.
Und damit bin ich schon durch.
Das heißt, ich habe nur eine weitere Variable eingeführt,
beziehungsweise für jeden Weg, für jedes Paar eine weitere Variable.
Ich habe also nicht nur die Abstände, sondern auch jeweils die
Knoteninformationen.
Und ich weiß jeweils, was ist der zuletzt besuchte Knoten.
Und damit kann ich mich sukzessive durchhangeln nach vorne.
Ich habe also die Abspeicherung der Wege im Prinzip in die Matrix
selbst integriert.
Ich kann mich da durchhangeln, ich brauche das nicht explizit
abzuspeichern.
Ich denke, das ist offensichtlich, dass das so geht.
Und jetzt könnten wir daran gehen, weitere Probleme zu betrachten.
Wir könnten also Zusammenhangskomponenten bestimmen.
Also wenn ich einen großen Graphen habe, besteht der irgendwie aus
verschiedenen Komponenten.
Dann könnte ich mir angucken, gibt es hier irgendwelche Brücken, wenn
die verbunden sind.
Kann es sein, dass durch Wegnehmen einer Kante so ein Graph in zwei
Teile zerfällt.
Gibt es dort irgendwelche Knoten, die gerade dafür sorgen, wenn ich
einen Knoten rausstreiche, der Graph in zwei Teile zerfällt.
Das wären also die Brücken oder Zentren eines Graphen.
Ich möchte alle vollständig verbundenen Teilgraphen bestimmen.
Also vollständig verbunden heißt, das wäre dann ein gerichteter Graph.
Und in jeder Richtung kann ich jeden Knoten von jedem anderen
erreichen.
Das wäre im Prinzip die Suche nach den Klicken im Graphen.
Also das wären vollständig verbundene Teilgraphen, das wären Klicken.
Färbe den Graphen keine gleichgefärbten Nachbarn, auch das kann man
machen.
Den Durchmesser eines Graphen bestimmen.
Was ist der Durchmesser eines Graphen?
Der Durchmesser, da schaue ich mir an, die Abstände von irgendwelchen
Knoten.
Und ich betrachte den maximalen, minimalen Abstand zwischen zwei
Knoten.
Das heißt, ich gucke mir alle kürzesten Wege an und brauche im Prinzip
nur das Maximum der Matrix mir anzuschauen, die ich mit dem
Floyd'schen Algorithmus berechnet habe.
Das ist der Durchmesser des Graphen.
Oder die Weite bei Section Width, das ist auch interessant.
Ich habe einen Graphen und möchte den durchteilen in zwei etwa gleich
große Teile.
Und interessiere mich dafür, was ist die minimale Anzahl von Kanten,
die ich durchtrennen muss, damit dieser Graph in zwei etwa gleich
große Teile zerfällt.
Wenn diese Weite oder Bisection Width sehr klein ist, dann heißt das,
wann immer ich zwischen Teil A und Teil B Informationen hin- und
herschieben muss, brauche ich lange Zeit, um über diesen wenigen
Kanten die Informationen rüberzuschieben.
Wenn ich sehr viele Kanten habe, können die beiden Teile A und B sehr
gut miteinander kommunizieren.
Das heißt, über so eine Bisection Width bekomme ich Informationen über
die Kommunikationskomplexität innerhalb einer solchen Graphenstruktur.
Und insofern ist das eine wichtige Eigenschaft, diese Bisection Width
anzugucken.
Hier oben hatte ich noch vergessen, ist G K Kanten zusammenhängend.
K Kanten zusammenhängend heißt,
wenn ich eine Kante rausnehme, ist er nicht mehr zusammenhängend.
Kfach zusammenhängend heißt, ich kann bis zu K Kanten rausnehmen, oder
erst wenn ich K-1 Kanten rausnehme, er bleibt immer noch
zusammenhängend.
Und insofern ist das wichtig.
Man hat bei Energienetzen, redet man häufig davon, dass die eine N-1
Eigenschaft haben, das heißt, wenn eine Komponente ausfällt, ist der
Rest meines Netzes immer noch vollständig funktionsfähig.
Ich kann also Einfachfehler tolerieren.
Da bräuchte ich hier einen Zweifachknoten- oder Kantenzusammenhang,
damit ich bei Ausfall einer Kante oder eines Knotens immer noch den
Zusammenhang mit drin habe.
Oder ich möchte einen kürzesten Hamiltonischen Kreis bestimmen.
Kürzester Hamiltonischer Kreis, das Problem kennen Sie, das ist das
TSP -Problem.
Hamiltonischer Kreis ist ein Pfad, der alle Knoten besucht.
Ich habe eben nur einmal besucht.
Oder Sie wollen ein Layout eines Graphen zeichnen.
Sie wollen also irgendwie Ihre Knoten irgendwo anordnen.
Und jetzt müssen Sie Kanten malen.
Das ist die Schwierigkeit, wie malt man eigentlich jetzt einen Graphen
so, dass wirklich alle Kanten irgendwie vernünftig zu sehen sind.
Das ist keine schöne Zeichnung.
Wie kann man das schön machen?
Dass die gleichmäßig verteilt sind über meine Zeichenfläche, dass die
Anzahl der Kantenkreuzungen minimiert wird, dass ich Beschriftungen
noch anbringen kann, ohne dass dadurch andere Knoten überdeckt werden,
dass ich Symmetrien erkenne in meinem Grafstruktur und ähnliches.
Sehr interessante Fragestellung.
Es gibt eine große Community, die sich speziell mit Grafzeichnen
beschäftigt.
Hat viele wirtschaftliche Anwendungen.
Wenn Sie sich anschauen, wie Sie Streckenpläne zeichnen von
öffentlichem Nahverkehr und ähnliches.
Das hat sehr viel zu tun mit Grafzeichnen oder irgendwelche
Projektpläne zeichnen.
Die müssen übersichtlich sein, müssen verständlich sein, müssen auch
noch ansonsten vielleicht noch die Ablaufdauern, also die Entfernungen
zwischen Knoten irgendwie mit berücksichtigen.
Das muss übersichtlich bleiben.
Also es gibt hier wahnsinnig viele Probleme auf Grafen, die man
betrachten kann.
Werde ich aber in dieser Vorlesung nicht weiter verfolgen.
Müsste man in der eigenen Vorlesung machen über Grafprobleme.
Und dann kann man auch noch, was kürzeste Wege angeht, kann man zum
Beispiel auch noch sich anschauen, kürzeste Wege auf sehr, sehr großen
Grafen.
Wenn Sie also einen sehr, sehr großen Grafen haben und Sie wollen da
ganz viele Kanten und Sie wollen jetzt nur den Abstand zwischen zwei
Knoten bestimmen, ist halt die Frage, wie groß ist der Bereich, den
ich eigentlich anschauen muss, damit ich diesen kürzesten Weg finden
kann.
Ich muss ja nicht alle Knoten tatsächlich betrachten, um den kürzesten
Weg zwischen zwei Knoten I und J zu bestimmen.
Das kann ja sein, dass ich mich beschränken kann auf hier so einen
Bereich.
Und das gibt es vielleicht noch ein paar Alternativen.
Und die Frage ist halt, wie kann ich das sinnvoll einschränken.
Dazu gibt es sehr gute Ansätze hier aus den Gruppen von Dorothea
Wagner, Peter Sanders, die bei sehr großen Grafen den Aufwand, um
kürzeste Wege zu bestimmen, um mehrere Größenordnungen reduziert
haben.
Einfach durch eine geschickte Heuristik oder mehrere geschickte
Heuristiken, mit der man die Knoten, die man tatsächlich betrachtet,
Knoten und Kanten, die man betrachten muss, eben sehr stark reduziert.
Und die können damit also wesentlich effizientere Berechnungen machen
unter kürzesten Wegen.
Das sind Verfahren, die eben mittlerweile dann auch in zum Beispiel
Google Maps oder so mit drinstecken, wenn kürzeste Wege berechnet
werden.
Das ist dort alles mit eingeflossen.
Worauf ich nochmal darauf hinweisen wollte, ist, dass bei vielen
dieser Probleme, wenn Sie sich die genauer anschauen, wie man die
berechnet, stellt man fest, die sind entweder vom Typ
Matrixmultiplikation oder vom Typ Warschall.
Ich habe Ihnen gezeigt, Erreichbarkeit, kürzeste Abstände und so
weiter, das ist Typ Warschall.
Es gibt andere Probleme, die sind auch bei Grafen, haben eher den Typ
Matrixmultiplikation.
Und wir wissen genau, wie man die parallelisiert.
Das heißt, wir brauchen nicht mehr explizit zu gucken, wie mache ich
jetzt eine bestmögliche Parallelisierung dieser Verfahren für diese
einzelnen Probleme.
Ich fahre mir den Typ an und habe sofort die richtige
Parallelisierung.
Also das ist insbesondere entsprechend auch parallel effizient
bearbeitet werden.
Das ist halt der wesentliche Punkt.
Und Sie wissen, dass das eines meiner Anliegen ist, Ihnen Prinzipien
zu vermitteln, wie man Algorithmen entwirft.
Und das ist eben eine Art, wir wissen, wie man mit dem Mapping-Ansatz
Algorithmen parallelisiert, die von dem Typ Matrixmultiplikation sind.
Und ich habe Ihnen gezeigt, wie man eben beim Typ Warschall auch eine
gute Abbildung auf zweidimensionale Felder hinbekommen kann, über
diesen Pipelining-Ansatz bei der Ausführung dieses Warschall
-Algorithmus.
Okay, das war der Teil über Graph-Algorithmen.
Man könnte dann auch sehr viel mehr machen, dafür haben wir aber nicht
die Zeit.
Und deswegen will ich hier schon weitermachen mit dem nächsten
Kapitel.
Kapitel 7, Algorithmische Geometrie, ein
Thema, das auch große praktische Relevanz hat.
Dabei geht es jetzt um sowas, was hier unten angedeutet ist.
Da geht es darum, geometrische Probleme zu lösen.
Wir machen viel Bildverarbeitung, man muss sehr viele Objekte erkennen
können in Bildern.
Und dafür braucht man vernünftige Algorithmen, um eben solche Fragen
der Geometrie bearbeiten zu können.
Und was sind das für geometrische Fragen?
Das ganze Gebiet nennt sich Algorithmische Geometrie.
Und es geht um effiziente Berechnungsverfahren zur Lösung
geometrischer Probleme.
Wenn Sie sich an die Mathematikstunden in der Schule erinnern,
geometrische Probleme hat man mit Zirkel und Lineal gelöst.
Und wenn ich sage effiziente Berechnungsverfahren, wir haben leider im
Rechner noch nicht das Werkzeug Zirkel und Lineal.
Wir haben arithmetische Operationen.
Sie wissen, dass man da auch noch andere Operationen hatte.
Trigonometrische Funktionen, mit denen man Winkelberechnungen macht
und ähnliche Dinge.
Da haben wir es mit reellen Zahlen zu tun.
Mit Ungenauigkeiten muss man aufpassen, ob das alles auch so
vernünftig berechnet werden kann.
Also effiziente Berechnungsverfahren sind ein Thema bei Problemen, die
durchaus sehr viel praktische Relevanz haben.
Jetzt habe ich hier als Beispiel, wie man Galerien oder Geschäfte
überwacht.
Ein gutes Geschäft, das ist einfach.
Wenn Sie sich vorstellen, Sie haben ein einfaches Geschäft, einen
einfachen Laden, der so aussieht, können Sie einfach überwachen.
Sie stellen hier eine Kamera auf oder stellen da einen Mann hin und
der kann alles überwachen.
Jetzt haben Sie eine Galerie, eine toll gestaltete Galerie, die kann
ein bisschen anders aussehen.
Die kann irgendwie vielleicht sehr verschachtelt sein.
So zum Beispiel sowas.
Jetzt die Frage, Sie wollen den Innenraum überwachen.
Sie haben irgendwelche Höhlengänge oder ein tolles Museum, da haben
Sie irgendein Labyrinthartiges aufgestellt.
Es gibt auch Geschäfte, in denen man die Kunden auf irgendwelchen
Labyrinthwegen durchführt.
Die Frage ist, was ist die minimale Anzahl an Überwachungspersonal
oder Überwachungskameras, die ich installieren muss, um jeden Punkt
überwachen zu können.
Also, wenn ich hier irgendwas hinstelle, dann kann ich natürlich alles
abdecken, was da ist, was da ist und so weiter.
Hier kann ich auch alles abdecken.
Das sieht schon gar nicht schlecht aus.
Dann brauche ich aber noch irgendwas für diesen Bereich hier.
Ich brauche vermutlich noch irgendwas für diesen Bereich.
Und irgendwie hier oben, das muss ja auch noch alles betrachtet
werden.
Also Sie sehen, man muss sich überlegen, wie kann man die anordnen,
sodass ich tatsächlich mit einer minimalen Anzahl von Punkten
auskomme, um jeden Punkt hier drauf anschauen zu können.
Typisches Galerieüberwachungsproblem.
Es gibt ein dickes Buch über Galerieprobleme, wo man also solche Art
von Problemen betrachtet.
Geschäfte genauso, praktische Relevanz.
Oder Sie haben irgendwelche Punkte und Sie wollen jetzt wissen, welche
Punkte hier drin haben den kleinsten Abstand, sind am nächsten, welche
haben den größten Abstand.
Naiver Ansatz ist ganz klar, Sie müssen einfach nur alle paarweisenden
Abstände berechnen.
Wir gucken das Minimum und das Maximum an, dann wissen Sie das.
Wäre ein quadratischer Aufwand, geht das auch besser.
Das ist die Frage.
Natürlich geht es besser.
Sie können das in Nlog N hinkriegen.
Aber da muss man das geeignet anpacken, das Problem.
Oder Sie haben irgendwelche Objekte und Sie wollen die darstellen auf
dem Bildschirm.
Und jetzt steht hier noch ein anderes Objekt, ein anderes Haus.
Die Frage ist, welche Kanten überschneiden sich bzw.
welche Bereiche überdecken sich.
Dazu muss ich wissen, wie kann ich tatsächlich feststellen, welche
Rechtecke, Kreise, Leiterbahnen oder Häuser, Bildschirmfenster
überschneiden sich.
Wie kann ich das geeignet darstellen.
Liegt ein Punkt innerhalb oder außerhalb eines geometrischen Objekts.
Sie haben Ihren Bildschirm und da sind eine ganze Reihe Objekte drauf.
Und Sie wollen jetzt irgendwelche Bereiche mit der Maus anklicken.
Das heißt, ich muss jetzt feststellen können, wenn ich hier
irgendeinen Punkt anklicke, welches Objekt muss ich anschließend in
einer anderen Farbe darstellen.
Woher weiß ich also, wenn ich hier irgendeinen Punkt betrachte, wie
kann ich feststellen, ob der innerhalb oder außerhalb eines gegebenen
geometrischen Objektes liegt.
Dazu brauche ich also Informationen über die jeweiligen Objekte und
ich muss feststellen können, liegt der Punkt drinnen oder draußen.
Auch das Problem werden wir uns anschauen.
Oder ich habe eine Menge von Punkten und ich möchte wissen, was ist
der kürzeste Weg um diese Menge von Punkten herum.
Konvexe Hülle um eine Punktmenge herum.
Auch ein klassisches Problem, Berechnung der konvexen Hülle einer
Punktmenge.
Oder, klar, wie finde ich das nächste Teil in einem Puzzle.
Sie wollen einen Puzzle machen, suchen, Sie haben hier Ihre tollen
Teile liegen und jetzt haben Sie hier Ihr Bild und da sind
irgendwelche Bereiche noch frei.
Welches Teil gehört dort am sinnvollsten rein.
Wie kann ich also das über Algorithmen geeignet hinbekommen.
Offensichtlich gibt es viele verschiedene Probleme, die man da
bearbeiten kann.
Ein sehr interessantes Forschungsgebiet, das Ganze möglichst effizient
alles zu machen.
Und das Ganze geht eben nicht mit Zirkel und Linear, sondern durch
entsprechende arithmetisch-logische Operationen.
Und damit beschäftigen wir uns jetzt als nächstes, wie man das bei so
typischen Problemen machen kann.
Ich mache Ihnen einen kleinen Ausschnitt, gebe Ihnen ein paar
Beispielprobleme, die wir betrachten werden.
Und dann haben Sie einen gewissen Eindruck, mit welchen Art Themen man
sich hier beschäftigt.
Es gibt dort noch, wie gesagt, sehr sehr viel mehr Probleme, als die,
die ich Ihnen hier vorstelle.
Und um das machen zu können, müssen wir uns erstmal anschauen, was
sind eigentlich die geometrischen Objekte, um die es geht.
Es kann sein, dass wir Punkte betrachten.
Das ist das einfachste.
Ein Punkt ist eine nulldimensionale Teilmenge eines euklidischen
Raumes.
Also wir betrachten den euklidischen Raum, also das R hoch D, mit
euklidischer Metrik.
Wurzel der Abstandquadrate, der Summe der Abstandquadrate.
Das nächste sind Geraden, eindimensionale Teilmengen.
Ich habe einen Punkt und eine Richtung oder auch zwei Punkte, dadurch
kann ich eine Gerade definieren.
Unendliche Menge von Punkten.
Ich kann Linien bestimmen, also nicht die Gerade, die durchläuft,
sondern nur das Teilstück zwischen zwei Punkten, Anfangspunkt,
Endpunkt.
Ich kann eine Hyper-Ebene bestimmen, im D-dimensionalen euklidischen
Raum, eine D-1-dimensionale Teilmenge.
Im zweidimensionalen Raum ist eine Hyper-Ebene eine Gerade.
Im dreidimensionalen Raum ist es irgendeine Ebene, die dort irgendwo
drin liegt.
Zweidimensionale Teilmenge.
Oder ich betrachte Polygone.
Ich habe eine Menge von Punkten und von Kanten, die die verbinden.
Ich habe geschlossene Kantenzüge im zweidimensionalen Raum, gegeben
durch Folge von Eckpunkten.
Das sind Polygone.
Man könnte auch Polyeder oder Polytope betrachten.
Im D-dimensionalen Raum werden wir aber nicht machen.
Da kann man noch viele weitere interessante Probleme der
algorithmischen Geometrie betrachten, wie man geometrische
Eigenschaften von mehrdimensionalen geometrischen Objekten untersuchen
kann.
Wir machen das jetzt nur hier auf zwei Dimensionen bezogen.
Und Sie sehen, die können sehr unterschiedlich aussehen.
Offensichtlich ist dieses hier etwas völlig anderes als die anderen
drei Polygone.
Wenn es also darum geht, ich hatte gesagt, die Frage ist, liegt ein
Punkt innerhalb oder außerhalb eines Polygons?
Oder eines geometrischen Objekts?
Hier wäre das jeweils ganz klar zu beantworten.
Und hier?
Ist das das Innere?
Also kann ich bei so einem Objekt überhaupt sagen, was dort das Innere
und das Äußere ist?
Wenn das so angeordnet ist, wenn sich hier die Kanten überschneiden,
das ist da etwas schwierig zu definieren.
Da müsste man hier diesen Schnittpunkt noch dazunehmen.
Dann hätte ich hier zwei Polygone, die miteinander verbunden sind.
Und da kann ich sagen, bei den beiden Teilpolygonen, ob ein Element
drin liegt oder nicht.
Aber ansonsten für nur die vier Punkte kann ich das gar nicht
beantworten.
Bei dem Polygon, wo sich diese beiden Kanten überschneiden.
Oder ich kann auch gucken, wenn ich hier zwei Punkte habe, liegen alle
Punkte dazwischen innerhalb meines Polygons.
Das ist bei den Dreiecken, beim Viereck der Fall.
Hier natürlich nicht.
Da gibt es Punkte, wenn ich die verbinde, dann liegen dort Punkte auf
der Verbindungsgeraden außerhalb des Polygons.
Also das hier wären die Dreieck- und Viereck-konvexe Polygone.
Das obere links ist halt kein konvexes Polygon.
Da könnte ich mir die konvexe Hülle betrachten.
Dann hätte ich ein konvexes Polygon, bei dem diese Eigenschaft
erhalten wäre.
Oder vorhanden wäre, dass die Verbindung von je zwei Punkten im
Inneren auch vollständig im Inneren liegt.
Modellierung solcher Objekte ist relativ einfach.
Bei Punkten ist klar, da habe ich also Problemgrößen.
Bei Punktmenge Anzahl der Punkte, bei Geradenmenge die Anzahl der
Geraden.
Ich habe ja zwei Punkte, um eine Gerade zu definieren.
Insofern ist es klar, dass ich die Anzahl der Geraden nehmen kann.
Bei Polygonen Anzahl der Eckpunkte.
Ich habe genauso viele Knoten wie Kanten.
Also die Anzahl der Punkte offensichtlich.
Datenstrukturen auch alles relativ klar.
Wobei ich kann also bei Punktenmengen, die kann ich irgendwie als
Mengen darstellen.
Wie stelle ich Mengen dar?
Als Listen von Punkten.
Das kann ich in einer strukturierten Art und Weise machen.
Dann habe ich Suchbäume oder Arrays.
Jetzt habe ich das hier gar nicht dargestellt.
Also Suchbäume, Arrays.
Da gibt es viele verschiedene Arten von Suchbäumen.
Insbesondere gibt es hier auch die sogenannten Segmentbäume,
Intervallbäume usw.
Es gibt also spezielle Datenstrukturen, die man entwickelt hat für die
Darstellung von geometrischen Objekten.
Aber in der Regel beschränken wir uns hier auf Suchbäume, lineare
Listen oder auch Prioritätswarteschlangen.
Aufwandsabschätzung ist in diesem Fall der Aufwand für arithmetisch
-logische Operationen.
Platzaufwand, Anzahl, Register.
Entsprechend für parallele Algorithmen kann man das auch anwenden.
Das ist also nichts besonderes.
Und was wir hier häufiger machen werden, ist, dass wir zunächst mal,
bevor wir ein Problem tatsächlich lösen können, uns vorbereiten.
Wir hatten das schon mal gesehen bei der Auswertung von Polynomen.
Da haben wir gesagt, wenn wir die Koeffizienten kennen, dann machen
wir erstmal eine Vorbereitung.
Wir verändern die Darstellung des Polynoms und konnten dadurch die
Anzahl der Multiplikationen etwa auf die Hälfte reduzieren.
Hier werden wir öfter sehen, dass wir durch Vorbereitung drastische
Reduktionen in dem Aufwand bekommen können.
Ich werde jetzt ein paar typische Probleme Ihnen einfach zeigen, die
hier auftauchen.
Und dann schauen wir mal, was wir da für Algorithmen brauchen.
Das erste Problem, also AG1 steht für das erste Problem der
algorithmischen Geometrie, das ich Ihnen hier vorstelle.
Ich habe eine Menge von Punkten im zweidimensionalen euclidischen Raum
und ein achsenparalleles Rechteck.
Die Frage ist, wie viele Punkte meiner Menge liegen innerhalb des
Rechtecks.
Also Sie gehen irgendwie mit zum Fenster über Ihren Bildschirm rüber,
haben da alle mögliche Punkte drin.
Die Frage ist, wie viele Punkte liegen jetzt da drin.
Wie kann man das berechnen?
Sie können natürlich für jeden Punkt Ihrer Menge berechnen, ob der
drin liegt oder draußen.
Dazu haben Sie die Koordinaten der vier Eckpunkte.
Sie brauchen natürlich eigentlich nur zwei Koordinaten und haben damit
das Rechteck.
Zwei Punkte haben das Rechteck damit, können auch diese vier
Koordinaten betrachten, die vier Eckpunkte.
Und müssen einfach berechnen, sind die x- und y-Werte der Punkte, oder
welche Punkte liegen jetzt tatsächlich zwischen diesen Koordinaten der
vier Eckpunkte.
Dass wir jeden Punkt überprüfen möchten, ob er drin liegt oder nicht,
habe ich linearen Aufwand.
Platz ist auch linear, ich habe ja n Punkte, die ich abspeichern muss.
Vorbereitung, null.
Nichts gemacht.
Guck einfach alle Punkte durch.
Linearer Aufwand ist nicht schlecht, aber vielleicht geht es ja
besser.
Die Verbesserung, die läuft jetzt folgendermaßen.
Das sieht zunächst mal gar nicht wie eine Verbesserung aus, sondern
wie eine Verschlechterung.
Also wenn ich mir die Anzahl der Punkte anschaue, die in dem Rechteck
drin liegen, dann sind das die Punkte, die kleinergleich x-strich, y
-strich sind.
Das ist dieser Punkt hier oben.
Alle, die kleinergleich diesem Punkt sind.
Das heißt also, das sind alle Punkte, die in diesem Bereich liegen.
Da ist aber zu viele.
Da muss ich einige abziehen.
Alle, die kleinergleich x- und y-strich sind, die muss ich natürlich
wieder rausnehmen.
Und alle Punkte, die kleinergleich x-strich y sind, die muss ich ja
auch rausnehmen.
Und jetzt sehen Sie, habe ich diesen Bereich hier unten zweimal
abgezogen.
Das ist einmal zu viel.
Die muss ich noch einmal dazuzählen.
Alle die, die kleinergleich sind, das ist also dieser Bereich hier
unten, nochmal obendrauf zählen.
Das sieht aus, als wäre das viel aufwendiger, als das, was ich Ihnen
vorher gesagt habe.
Ich müsste jetzt ja mit einem naiven Ansatz erst einmal bestimmen, wie
viele Punkte sind denn kleinergleich x-strich y-strich, Aufwand n.
Wie viele Punkte sind kleinergleich x-strich y-strich, nochmal Aufwand
n usw.
Viel größerer Aufwand.
Warum ist das klug?
Das Kluge daran ist, ich habe jetzt nicht mehr die Frage, wie viele
Punkte liegen innerhalb des Rechtecks, sondern wie viele Punkte sind
kleinergleich irgendeinem gegebenen Punkt.
Und jetzt habe ich im Prinzip vier solche Anfragen.
Wie viele Punkte sind kleinergleich rechteroberer, linkeroberer,
rechterunterer, linkerunterer Punkt?
Und die Idee ist, ein bisschen nachzudenken und herauszufinden, wie
man dieses Problem in kürzerer Zeit lösen kann.
Und Sie werden sehen, dass man jede einzelne Punktanfrage mit
geeigneter Vorbereitung, mit logarithmischem Aufwand hinbekommen kann.
Das ist also die wesentliche Verbesserung, nicht linearer Aufwand,
sondern logarithmischer Aufwand in der Anzahl der Punkte, um diese
Punktanfragen zu lösen.
Und das ist bei vielen Punkten dann natürlich ein dramatischer
Zeitgewinn, wenn ich häufige solche Anfragen machen muss.
So, wie machen wir das?
Wir zerteilen unsere Ebene in ein Gitter und die Gitterlinien
entstehen durch die Punkte in meiner Punktmenge.
Das sind hier meine Punkte in meiner Punktmenge.
Und jeder Punkt hat zwei Koordinatenachsen, die durch ihn hindurch
laufen.
Und dadurch zerteile ich meine Ebene in ganz viele Rechtecke.
Ich habe also jetzt bei N Punkten, N² solche Rechtecke plus noch
Randflächen, also hier, da außen, das sind Randflächen, die sind ja
unbegrenzt.
Um das zu berechnen, die alle zu berechnen, habe ich natürlich einen
quadratischen Aufwand.
Ich muss ja alle diese N² verschiedene Rechtecke, die muss ich ja alle
irgendwie mir angucken.
Und jetzt berechne ich für jedes Rechteck die Anzahl der dominierten
Punkte.
Und dominiert, soll bedeuten, die Anzahl der Punkte der gegebenen
Menge, die kleiner oder gleich einem beliebigen Punkt im Rechteck
sind.
Das heißt, ich gehe hier in irgendeinen Punkt rein, in irgendein
Rechteck, und ich frage mich, wie viele Punkte meiner Ausgangsmenge
sind kleiner gleich diesem Punkt.
In dem Fall, das wäre also so eine Punktanfrage, der Punkt und der
Punkt, die wären beide kleiner.
Das heißt, ich berechne für jedes solche Rechteck die Anzahl der
dominierten Punkte und der Aufwand ist auch wieder N².
Ich muss ja für jedes solche Rechteck diese Anzahl der Punkte
bestimmen.
Dass das in N² geht, ist zunächst mal erstaunlich, weil ich ja N²
Rechtecke habe und ich muss das für jedes Rechteck bestimmen.
Aber offensichtlich kann man so im Prinzip von unten nach oben hier
durchlaufen.
Und wenn ich weiß, wie viele Punkte zum Beispiel von einem Punkt in
dem Rechteck dominiert werden, kann ich natürlich relativ einfach
berechnen, wie viele dann von einem Punkt in dem benachbarten, dem da
oben drüber, dominiert werden, weil das ja einfach nur inkrementell
etwas dazukommt.
Das heißt, ich kann hier einfach so durchlaufen, habe meine N²
Rechtecke, bei der ich was berechnen muss und das ist also durchaus
mit Aufwand N² zu machen.
Also so komplex ist es nicht, aber es ist eben nicht trivial.
Man muss schon in einer geschickten Art und Weise vorgehen.
Also den Aufwand kann ich jedenfalls so machen.
Ich habe also für jedes Rechteck die Anzahl der dominierten Punkte
berechnet.
Also alle Punkte, die kleiner gleich einem beliebigen Punkt im
Rechteck sind.
Innerhalb eines solchen Rechtecks liegt ja kein Punkt der Menge.
Die Punkte der ursprünglichen Menge liegen ja nur an den
Schnittpunkten der Linien.
Und jetzt sortiere ich die X-Koordinaten der Punkte und ich sortiere
die Y-Koordinaten der Punkte.
Ich muss das ja irgendwie abspeichern, das was ich berechnet habe.
Also ich gucke mir an, die X-Koordinaten, die Y-Koordinaten, die
sortiere ich jeweils.
Der Aufwand für das Sortieren ist N log N.
Wissen wir.
Jetzt beantworte ich meine Punktanfragen so, dass ich frage, wie viele
Punkte sind kleiner gleich XY.
Da muss ich also entsprechend an die entsprechende Position laufen.
Ich muss also das entsprechende Rechteck dadurch finden.
Ich bestimme durch binäre Suche auf den X- und Y-Koordinaten das
Rechteck, in dem XY liegt.
Und damit habe ich dann entsprechend mein Rechteck gefunden.
Für dieses Rechteck habe ich die Information und kann dadurch den Wert
festlegen.
Die Zahl gebe ich an und habe damit die Punktanfrage beantwortet.
Der Aufwand dafür, für die Vorbereitung ist quadratisch, dominiert
also durch die ersten beiden Aufgaben.
Das N log N spielt ja keine Rolle.
Der Platz ist natürlich quadratisch, so muss ich das abspeichern.
Und dann habe ich für jede Punktanfrage Aufwand log N.
Also für meine vier Punktanfragen, um festzustellen, wie viele Punkte
liegen in einem Rechteck, auch nur logarithmischer Aufwand.
Und damit haben wir also das erste Problem der logarithmischen
Geometrie schon betrachtet und gelöst.
Und Sie sehen, Vorbereitungsaufwand ist hier entscheidend, um den
Aufwand sehr stark drücken zu können.
Macht natürlich nur Sinn, wenn man viele solche Punktanfragen hat.
Okay, ich denke, das ist für heute genug.
Nächstes Mal werden wir das noch ein bisschen weiter treiben.
Vielen Dank für die Aufmerksamkeit.