So, schönen guten Tag.
Ich begrüße Sie zur Fortsetzung der Vorlesung effizienter Algorithmen.
Wir haben uns letztes Mal beschäftigt mit, zunächst mal, auch mit den
rot -schwarzen Bäumen, wir haben uns zunächst mal die
Selektionsverfahren angeguckt, das Verfahren für die Bestimmung des
Medians zum Beispiel.
Ich hatte Ihnen Quick Select vorgestellt, ich hatte Ihnen die
Selektion in linearer Zeit vorgestellt, also insbesondere
Medianbestimmung in linearer Zeit.
Etwas, was eigentlich so aussieht, wenn man das Problem sieht, dass es
deutlich wesentlich einfacher ist als sortieren und es zeigt sich eben
auch, dass es tatsächlich geht.
Quick Select hat es schon im mittleren Fall linear und mit diesem
Verfahren, wo man eben dafür sorgt, dass man im Prinzip Quick Select
macht, aber das Pivot-Element effizient so bestimmt, dass man bei
jedem rekursiven Schritt eine ausreichend große Folge abschneiden
kann.
Das hat dann halt lineare Laufzeit insgesamt.
Wir hatten uns das angeschaut, gesehen, dass man das auch sehr gut
parallelisieren kann, zumindest erwähnt, dass man das machen kann und
wir sind dann zu den Suchverfahren gekommen.
Ich habe Ihnen vorgestellt, die verschiedenen Baumarten, mit denen man
so etwas macht.
Wir hatten gesehen, was ein binärer Suchbaum ist.
Ich hatte Ihnen erzählt, dass es dazu die höhenbalancierten Bäume
gibt, die AVL-Bäume.
Es gibt eine Vielfalt von anderen Bäumen.
Wenn Sie sich anschauen, Literatur zu Suchverfahren, Datenstrukturen
für Suchen, gibt es sehr, sehr viele verschiedene Strukturen.
Ich habe Ihnen hier nur einen ganz kleinen Ausschnitt dargestellt,
aber die 2-3-4-Bäume sind eben, insbesondere mit der Variante der Rot
-Schwarz -Bäume, dann eine Datenstruktur, die sich als sehr effizient
herausgestellt hat.
Je nachdem, was für Anwendungsszenarien man hat, welche Arten von
Suchen man hat, wie die Dateien strukturiert sind, gibt es aber noch
eine Vielfalt anderer Datenstrukturen, die man dort sinnvoll einsetzen
kann.
Splash -Trees und so, also wirklich eine Vielfalt von Bäumen, die ich
Ihnen hier alle nicht vorstellen kann.
Ich wollte einfach nur diese klassischen Verfahren Ihnen darstellen.
Und wir hatten gesehen, bei den 2-3-4-Bäumen haben wir halt eine
Struktur, die dazu führt, dass wir tatsächlich einen einigermaßen
ausgeglichenen Baum bekommen, wobei eben die Ungleichgewichte in den
Knoten sind, dadurch, dass wir dort 1-3 Schlüssel haben, aber die
Pfadlängen sind alle die gleichen.
Und im Prinzip ist das eine Variante der B-Bäume, eben hier mit einer
sehr kleinen Anzahl von Schlüsseln, die maximal in dem Knoten drin
sein können, während das beim B-Baum bis zu Blockgröße im
Speicherbereich sind, können das hier eben nur maximal 3 Schlüssel
sein pro Knoten.
Und ich hatte Ihnen dann verschiedene Operationen dargestellt, wir
hatten gesehen, was für Probleme da auftreten können, und dann haben
wir uns die Rot-Schwarz-Bäume angeschaut, hatten gesehen, wie man die
realisieren kann und hatten dann diskutiert, inwieweit das jetzt
wirklich ein Vorteil ist.
Und natürlich gibt es da auch Operationen, die man sich anschauen
muss, es ist nicht sehr trivial, wie man dort die Operation macht, das
Umbauen von einem Knoten, also wenn man das aufteilt, dass man eben
weiß, welche Knoten darunter sind und so weiter, dass man feststellt,
ob ein Knoten tatsächlich ein Vierknoten ist.
Hier in dem Fall, wo man da hinkommt, muss man erstmal feststellen,
welche beiden Nachfolger sind, das haben wir das letzte Mal
diskutiert.
Aber es gibt insgesamt schon eine effiziente Art, das zu
implementieren, und damit hat man eine Suchbaumstruktur, die man sehr
gut verwenden kann, die einem eben eine Durchführung der Operationen
in logarithmischer Zeit ermöglicht, das, was man gerne erreichen
möchte.
Damit sind wir durch dieses klassische Gebiet Suchen und Sortieren
durch, und ich komme zum nächsten Problem, zum nächsten Problemklasse,
die Sie wahrscheinlich auch kennen aus anderen, eventuell aus
oberrechtlichen Schülern, das müssten Sie eigentlich Grafen auch
kennengelernt haben.
Ich werde hier jetzt die Algorithmen für solche Grafen nochmal genauer
bei mir angucken, und insbesondere werden wir uns auch ein paar
parallele Varianten anschauen.
Es geht also hier um typische Probleme in Grafen.
Was sind typische Probleme in Grafen?
Zunächst mal, was ist ein Graf?
Wir können ihn gerichtet betrachten, da haben wir irgendwelche Knoten,
und diese Knoten sind verbunden durch irgendwelche Kanten, und die
Knotenmenge ist eine Menge V für Vertices, und die Kantenmenge ist E
für Edges, und damit haben wir als Kantenmenge hier bei einem
gerichteten Grafen jeweils ein paar von Knoten, also in dem Fall hier
wäre das hier die Kante 1,4.
Das ist also ein typisches Beispiel für solche Grafen, und wir wissen,
dass man damit zig verschiedene Dinge in der Welt modellieren kann,
dass viele Probleme, die man bearbeitet, als Probleme auf Grafen
modelliert werden können.
Hier sind alle möglichen Dinge aufgeführt, Leitungsnetz,
Flussdiagramm, Kontrollfluss, Schaltnetz, Projektstrukturen,
Relationen im Internet, die ganzen Verbindungen, die wir dort haben,
Fahrpläne und Ähnliches, also wenn Sie Fahrplansuchen machen, was Sie
bei der Bahn herausfinden können, kürzere Verbindungen zwischen zwei
Wegen, Navigationsprobleme, Sie wollen von A nach B und suchen dafür
den bestmöglichen Weg.
Das sind alles typische Probleme, die man hier bearbeiten muss, oder
Sie wollen in einem Grafen feststellen, was passiert, wenn ein Knoten
wegfällt, oder eine Kante wegfällt, ist ja immer noch vollständig
verbunden.
Das sind zig Probleme, die sehr hohe praktische Relevanz haben.
Und solche Grafen sind halt dargestellt, wie gesagt, durch Knoten und
Kanten.
Wie ist die Problemgröße hierbei?
Da guckt man sich an, die Anzahl der Knoten und die Anzahl der Kanten
spielt natürlich auch eine Rolle, die Anzahl der Kanten kann
quadratisch sein in der Anzahl der Knoten.
Wenn Sie einen vollständig verbundenen Grafen haben, haben Sie n²
halbe Kanten, und das heißt, man muss genau aufpassen, wie aufwendig
dann die Algorithmen werden, die darauf laufen.
Also zur vollständigen Beschreibung eines Grafen brauchen Sie im
Prinzip n² Platz, wenn Sie n Knoten haben, oder Sie brauchen halt
genau Platz m, wenn m die Anzahl der Kanten ist.
Damit haben Sie eigentlich den Vollständigen beschrieben,
beziehungsweise Maximum von n und m.
Wenn Sie keine Kanten hätten, hätten Sie halt trotzdem die Anzahl der
Knoten, sich hinzuschreiben.
Also, das ist die Problemgröße.
Wie stellt man das Ganze dar, einen solchen Grafen?
Sie können das machen über eine Adjacenzmatrix, also wenn Sie hier
einen Knoten i und einen Knoten j haben, schreiben Sie hier rein, ob
der verbunden ist.
Das heißt, wenn die Kante drin ist, haben Sie dort eine 1 stehen.
Sie können das noch anders machen, Sie können da auch noch irgendeine
Zahl hinschreiben, dann haben Sie da nicht nur die Information, da ist
eine Verbindung da, sondern hätten Sie noch ein Gewicht an der Kante
oder eine Entfernung oder ähnliches.
Das heißt, diese Matrix kann noch interessantere Inhalte haben, als
nur einfach eine Bool'sche Matrix zu sein, oder wäre das eine Matrix
über ganzen Zahlen.
Also, da gibt es verschiedenste Varianten.
Platzbedarf dafür ist selbstverständlich quadratisch.
Und Sie hätten also hier in dieser Zeile von i alle Kanten, die die
Quelle i haben, und in der Spalte des Knotens j alle Kanten mit Ziel
j.
Das ist also eine sehr einfache Darstellung, kann aber eine deutlich
zu große Darstellung sein, insbesondere wenn Sie Planarengrafen haben,
also einen, bei dem Sie alle Kanten ohne Überschneidungen hinmalen
können in der Ebene, dann haben Sie immer nur eine lineare Anzahl von
Kanten in der Anzahl der Knoten, das heißt, dann bräuchten Sie nicht
n², sondern nur Aufwand n, um das zu machen.
Für solche Zwecke wäre es sinnvoller, nicht eine Adjacenzmatrix
-Darstellung zu nehmen, sondern Adjacenzlisten, das heißt, Sie würden
jeweils zu jedem Knoten hinschreiben, mit welchen anderen Kanten der
verbunden ist, ähnlich wie das, was wir vorher gemacht hatten bei den
Matrizen, dass wir dünn besetzte Matrizen betrachtet haben, im Prinzip
kann es sein, dass interessante Grafen dünn besetzt sind, dann würde
man eben solche Listen der Knoten nehmen, die von einem Knoten i aus
über eine Kante erreicht werden und dann wäre der Aufwand eben gerade
Anzahl der Knoten plus Anzahl der Kanten und insbesondere bei
Planarengrafen wäre dann also der Aufwand für die Datenstruktur
linear.
Da muss man genau gucken, was man braucht, was für die Praxis wichtig
ist und auch, welche Art von Operation man darauf macht, wie effizient
man die dann auf diesen Datenstrukturen ausführen kann.
Ich will auf die Datenstrukturen gar nicht so lange drauf eingehen,
das ist eigentlich alles Standard.
Welche wichtigen Begriffe brauchen wir hier?
Wir betrachten Wege über irgendwelche Kanten, also hier von einem
Knoten, wenn das hier u1 ist und das hier un, hätten wir also hier
einen Weg von u1 nach vn, genau, immer Knoten uv, und das wäre also
über eine Folge von Kanten dann dargestellt.
u1 wäre hier die Quelle des Weges, vn wäre das Ziel des Weges und wir
haben die Länge, das ist die Anzahl der Kanten und wenn wir also hier
e1 bis en als Kanten haben, haben wir halt so eine Länge n, dann gibt
es einfache Wege, bei denen wir nur unterschiedliche Knoten haben oder
auch Wege mit Knotenwiederholungen, dann wären das irgendwelche
Zyklen, das wäre also hier ein typischer Kreis, den wir dort drin
hätten, und dann betrachten wir auch a-zyklische Graphen, Graphen, die
keine Kreise enthalten, also das sind alles typische Begriffe, die Sie
alle kennen.
Und dann betrachten wir nicht nur gerichtete Graphen, sondern wir
betrachten auch ungerichtete Graphen.
Ungerichtet heißt, ich habe eine Kante zwischen zwei Knoten, wie hier
angedeutet, aber diese Verbindung gilt in beide Richtungen, ich kann
über diese Kante von i nach j oder auch von j nach i kommen und um das
anzudeuten, schreibt man in der Regel solche Kanten als Menge i, j und
damit habe ich also ausgedrückt, dass die Reihenfolge keine Rolle
spielt, während bei der Tupelschreibweise natürlich die Reihenfolge
eine Rolle spielt.
Tupel sind immer gerichtet, Mengen halt nicht.
Jetzt nennen wir einen ungerichteten Graphen zusammenhängend, wenn wir
von jedem Knoten zu jedem anderen Knoten kommen können.
Man kann ja auch bei gerichteten Graphen von zusammenhängenden Graphen
reden, dann müssen wir unterscheiden, zusammenhängend und streng
zusammen oder stark zusammenhängend.
Beim gerichteten Graphen, wenn wir da die Bedingung haben, dass ich
für alle Knoten einen Weg von i nach j haben muss, dann müssen das
gerichtete Wege sein und dann wird das der starke Zusammenhang.
Hier betrachten wir nur den ungerichteten Graphen, der ist
zusammenhängend, wenn es also für je zwei Knoten einen Weg von i nach
j gibt.
Das heißt, dieser Graph zerfällt nicht in zwei Teile oder mehrere
Teile und bei einem Baum, da gehen wir also davon aus, Baum ist halt
so definiert, dass das ein zusammenhängender und a-zyklischer Graph
ist, also zusammenhängend, ich habe also hier irgendwelche Knoten und
Sie wissen alle, was ein Baum ist, das ist ein typischer Baum und
sobald wir hier irgendeine Kante hätten, die zwei Knoten weiter unten
verbindet, hätten wir im ungerichteten Graphen damit sofort einen
Kreis.
Das wäre dann also zyklisch oder ein Zyklus, das darf nicht sein, so
ist es ein Baum.
Sobald wir eine Kante dazwischen hätten, auf Knoten, die auf
verschiedenen Pfaden liegen, hätten wir halt einen Kreis dort drin.
Also dieses, natürlich muss man dabei noch berücksichtigen, dass das
ij, also diese eine Kante hier, wenn ich mir das hier anschaue, könnte
ich sagen, da habe ich einen Kreis.
Im gerichteten Graphen könnte ich sagen, ich habe hier einen trivialen
Kreis, der zwei Knoten miteinander verbindet, aber das betrachten wir
halt nicht als einen echten Kreis, sondern beim echten Kreis bräuchten
wir halt mehr als zwei Knoten in dem Fall.
So, das zu diesen typischen Begriffen, die Sie eigentlich aus den
anderen Vorlesungen kennen.
Wenn ich zu schnell mache, müssen Sie mich stoppen.
Ich gehe hier ein bisschen schnell durch, durch diese Teile.
Wir wollen dann jetzt bestimmte typische Probleme anschauen.
Und da gibt es zunächst mal den Begriff der Erreichbarkeit.
Also ich will feststellen, welche Knoten kann ich eigentlich von einem
anderen aus erreichen.
Sie erinnern sich bei, wenn Sie alle Grundlagen der Informatik 2
gehört, da haben wir die Automaten minimiert und haben dort die
erstmal vereinfacht, indem wir alle nicht erreichbaren Zustände
rausgeschmissen haben.
Alle, die nicht vom Anfangszustand aus erreichbar waren.
Und das heißt, da ist man an sowas interessiert.
Erreichbarkeit ist etwas ganz Wichtiges.
Und das heißt, wenn ich hier irgendwelche zwei Knoten habe, möchte ich
wissen, gibt es irgendeinen Pfad, der mir diese Knoten hier, diese
Source und Target miteinander verbindet.
Das habe ich natürlich zunächst mal in der Adjacenzmatrix so nicht
drin stehen, da stehen nur die einzelnen Kanten drin, um daraus die
Erreichbarkeitsmatrix zu machen.
Möchte ich eine Matrix haben, die hier mit Tg bezeichnet ist, das
heißt, das Tij soll 1 sein, wenn es einen Weg gibt von I nach J.
Also irgendeine Folge von Kanten.
Und das T, oder man nennt die, T hat ja mit Erreichbarkeit nichts zu
tun.
Aber T hat was mit transitiver Hülle zu tun.
Und Transitivität einer Relation kennen Sie alle, wenn ich zwei
Elemente habe, I und K, die in Relation stehen, und außerdem K und J.
Wenn daraus folgt, dass I und J auch in Relation stehen, dann ist das
eine transitive Relation.
Und bei einer Erreichbarkeit, wenn ich also eine Matrix aufschreibe,
die eine Erreichbarkeitsmatrix ist, dann habe ich eben genau diese
Eigenschaft, dass ich sage, also alle Knoten, die irgendwie
miteinander über eine Folge von Kanten verbunden sind, sind dann auch
bei der transitiven Hülle direkt über einen solchen Eintrag hier
miteinander verbunden.
Also das ist praktisch nur die Erreichbarkeit.
Wenn K von I erreichbar ist und J von K, ist natürlich J auch von I
erreichbar.
So, man kann das jetzt definieren, dass man sukzessive sagt, ich
betrachte diese auf dem Weg bis zu dem Tg, ich betrachte hier eine
Menge Tg hoch R, so, dass das Tg hoch R gerade gleich 1 ist, genau
dann, wenn es einen Weg der Länge maximal R gibt von I nach J, das Tg
hoch 1 wäre dann gerade die Adjacenzmatrix, und das ist also das, was
hier steht, das ist das Aij, Tij hoch 1 wäre gerade das Aij, und das
Tij2 wäre dann Aij, also das heißt, IJ sind über einen Weg der Länge 2
verbunden, entweder wenn I und J direkt oder maximal, kleiner gleich R
steht hier, wenn I und J direkt verbunden sind oder es gibt einen
Knoten, so dass I mit K verbunden ist und K mit J verbunden ist.
Das wäre ein Weg der Länge 2.
Das andere wäre ein Weg der Länge 1 oder Weg der Länge 2, das wäre
Tij2.
Tijn würde entsprechend bedeuten, entweder sind I und J direkt
verbunden oder es gibt einen Knoten, so dass der Knoten I direkt mit K
verbunden ist und der Knoten K über einen Weg der Länge N maximal mit
dem Knoten J.
Das heißt, wenn ich hier meinen Knoten I betrachte und den Knoten J, I
und J, dann sage ich, entweder sind die direkt verbunden, das ist das
Aij, oder es gibt einen Knoten K, mit dem das I direkt verbunden ist
und danach gibt es einen Pfad der Länge maximal N-1, so dass das K mit
dem J verbunden ist.
Dann ist der Knoten I über einen Pfad maximal der Länge N mit J
verbunden.
Das kennen Sie alles.
Wenn Sie eine solche Formel sehen, dann müsste Sie das an etwas
erinnern.
Wir hatten ähnliche Gleichungen schon mal gehabt, nämlich bei der
Matrixmultiplikation.
Die sahen ganz ähnlich aus.
Ja?
So ist es.
Ja, genau.
Das ist einfach eine Boole'sche Matrixmultiplikation.
Wer ist das nicht?
Also ganz einfacher Algorithmus.
Steht ja auch direkt unten drunter.
Haben Sie auch alle vorliegen gehabt.
Das ist eine einfache Operation.
Und Aufwand?
Naja, ich mache einfach Boole'sche Matrixmultiplikation.
Boole'sche Matrixmultiplikation.
Wissen wir, wie der Aufwand ist.
Naives Verfahren.
N hoch 3.
Das wäre aber ein ziemlicher Aufwand.
Dann hätten wir Aufwand N hoch 4.
Nur das sukzessive Machen.
Wenn man es ein bisschen effizienter macht, könnte man auf N hoch 3
log N kommen.
Indem man sagt, naja, ich möchte ja gerne, eigentlich muss ich ja nur
das Tg hoch N berechnen.
Und wenn ich etwas hoch N berechnen möchte, brauche ich ja nur, das
ist ja das übliche Problem, irgendein X hoch N, Endpotenz einer Zahl.
Wissen wir, geht in logarithmischer Zeit durch sukzessives Quadrieren.
Das ist ja eigentlich kein Problem.
Also das wäre sofort N hoch 3 log N.
Aber auch das ist noch nicht wirklich effizient.
Und effizient wird es, wenn wir zum Beispiel den Warschall-Algorithmus
nehmen.
Kennt jemand den Begriff Warschall-Algorithmus unter dem Namen?
Nicht?
Sie kennen vielleicht den Begriff Trippel-Algorithmus.
Kennen Sie auch nicht?
Sie kennen den.
Also das ist im Prinzip der Trippel-Algorithmus, heißt aber nach dem
Autor Warschall-Algorithmus.
Was habe ich jetzt Ihnen hier hingeschrieben?
Das ist doch das Übliche, was wir kennen.
Das ist doch die Marktesmultiplikation.
Sieht man doch sofort.
Dreifach geschachtelte Schleife.
Hier haben wir in der Mitte oder im Kern haben wir hier unten diesen
Rumpf.
Das ist genau die Marktesmultiplikation.
Was ist daran besonders?
Wenn man genau hinguckt, ist es eben nicht die Marktesmultiplikation,
sondern hier haben Sie etwas, das ist anders aufgebaut.
Bei der Marktesmultiplikation hatten wir eine Marktesmultiplikation.
Da ging die Schleife über I und J und innen drin hatten wir K.
Und hier steht jetzt, für K gleich 1 bis N, iteriere ich über alle I
und J und habe dann innen drin diesen Term hier auszuwerten.
Und die Behauptung ist, mit diesem Algorithmus bin ich schon fertig,
wenn ich ihn einmal ausführe.
Zunächst mal sieht das so aus wie eine Marktesmultiplikation.
Wir sagten gerade, wir müssen aber A hoch N berechnen.
Wieso reicht da ein solches Verfahren aus?
Es ist zunächst mal nicht klar, dass das tatsächlich reicht.
Und das liegt eben hier an diesem K.
Was macht man hier?
Nochmal aufgemalt.
Ich weiß nicht, habe ich hier nicht aufgemalt.
Also, das ist genau das, was hier unten steht.
Ich glaube, ich habe es nicht aufgemalt.
Dann male ich das hier nochmal auf.
Also, ich habe hier meinen...
Wo kommt da noch irgendwas?
Da ist noch irgendein Bild.
Das ist die Verbesserung.
Also, ich habe Platz, um das aufzumalen, habe ich hier unten.
Wir haben unseren Knoten I, wir haben den Knoten J.
Und die beiden werden angeguckt.
Es ist also entweder hier bereits, wenn ich mir diese Anweisung
anschaue, entweder ist dieses hier bereits bekannt, dass I und J
verbunden sind.
Und zwar kann das nur bekannt sein dadurch, dass ich etwas gemacht
habe für Werte kleiner als K, für 1 bis K-1 in diesem Fall.
Jetzt gucke ich mir den Fall K an.
Das heißt, was hier bei diesen Betrachten von dem I und J an Ks
aufgetreten sein kann, ist irgendetwas, das können also Knoten sein
hier, aus der Menge K-1.
1 bis K-1 können aufgetreten sein.
Der Knoten K kann dort unten auf diesem Weg nicht aufgetaucht sein,
weil ich in den vorherigen Iterationen immer nur Werte kleiner als K
betrachtet habe.
So.
Es ist also I und J verbunden über einen Weg der Länge K-1.
Das ist also das, was hier steht.
Hier steht es über eine Kante verbunden, aber gemeint ist ja
eigentlich, dass die aufgrund der Information, die ich aktuell habe in
dieser Iteration, und diese Information bezieht sich darauf, dass ich
schon die ganzen vorherigen Iterationen durchgeführt habe, also
verbunden über den Weg der Kante, in dem Knoten 1 bis K-1 auftauchen.
Oder I ist verbunden mit einem Knoten K, mit dem Knoten K, über einen
Pfad, auf dem auch wieder nur Kanten auftauchen aus der Menge 1 bis K
-1.
Und K ist mit J verbunden, auch wieder nur mit einem Pfad, in dem nur
Knoten auftauchen von 1 bis K-1.
So.
Wenn Sie sich dieses Bild anschauen, dann ist schon klar, dass dieser
Algorithmus eigentlich korrekt sein muss, weil wir nämlich, wenn wir
hier durchlaufen bis N,
dann haben wir für K gleich N, haben wir dann überprüft, ob I und J
verbunden sind über einen Weg, bei dem irgendwelche anderen Knoten
vorkommen aus der Menge 1 bis N, oder ich muss über den Knoten N
laufen und die Wege dahin zu dem Knoten N dürfen irgendwelche anderen
Knoten aus der Menge 1 bis N-1 enthalten.
Das heißt, es muss dann der Knoten N dort auch mit auftauchen.
Das ist das, was man sich hier anschaut.
Und wenn ich die letzte Iteration gemacht habe, habe ich
offensichtlich alle Möglichkeiten betrachtet, weil ich dann für je
zwei Knoten genau das untersucht habe, ob es einen Pfad gibt von I
nach J, der über irgendwelche anderen Knoten in dem Graphen läuft.
Irgendwelche anderen heißt Knoten aus der Menge 1 bis N.
Man sieht sofort, wie man das über Induktion beweisen kann, dass
dieser Algorithmus tatsächlich korrekt ist.
Und er läuft halt, wie man hier sieht, dreifach geschaltete Schleife
läuft trivialerweise in Zeit N hoch 3.
Und damit haben wir also hier eine Alternative zu dem, was ich vorher
sagte, N hoch 3 log N ist auch nicht schlecht, aber das hier ist ja
selbstverständlich besser.
Und jetzt kann ich das noch ein bisschen verbessern.
Ich kann also hier zum Beispiel sagen, naja, wenn I mit...
Also ich kann erst mal gucken, ob I mit K verbunden ist, ob ich das
bereits drin habe.
Nur dann macht es Sinn, überhaupt die weiteren Schritte zu betrachten.
Wenn das I gar nicht mit K verbunden ist, über einen Weg, bei dem
Knoten aus der Menge 1 bis K auftauchen, dann brauche ich das hier gar
nicht weiter zu betrachten.
Und dann schaue ich mir an, für alle möglichen Zielknoten, nur wenn
also I nicht mit J verbunden ist, dann wäre ich ja schon fertig, dann
wäre das ja schon verbunden, dann schaue ich mir an, ob K mit J
verbunden ist und dann setze ich natürlich A, I, J auf.
Also wenn A, I, J nicht gilt, dann muss ich nur überprüfen, ob
eventuell eine Verbindung von I nach J über diesen Knoten K existiert
und das ist dann der Wert, auf den ich das A, I, J setze.
Also eigentlich könnte ich das sogar noch mehr vereinfachen, da ich
hier oben ja bereits getestet habe, ob das A, I, K gilt, könnte ich
hier auch hinschreiben, A, I, J gleich A, K, J.
Ich brauche hier gar nicht hinzuschreiben A, I, K und A, K, J, sondern
es reicht hinzuschreiben A, I, J gleich A, K, J, weil ich ja das hier
oben bereits abgetestet habe.
Also das ist eine sehr einfache, eine kleine Variation, die ändert an
der Laufzeit insgesamt nichts, also nichts asymptotisch, aber für den
praktischen Fall ist das ein bisschen eine Verbesserung.
Das ist der klassische Algorithmus, um Erreichbarkeit in Graphen
festzulegen, um die transitive Hülle zu bestimmen.
Und Sie sehen, was es ausmacht, wenn man einfach hier die Reihenfolge
dieser Iterationen verändert.
Das hat drastische Auswirkungen für dieses Verfahren, wenn Sie hier
eben nur für I und J laufen würden und in der Mitte und unten dieses K
überprüfen müssten, dann müssten Sie eben das immer wieder machen,
weil Sie immer nur prüfen würden, würden Sie nur für alle I und J
prüfen, ob es einen Pfad gibt, der über den Knoten 1 geht usw.
Das würde Ihnen insgesamt, da hätten Sie gerade nur die Wege der Länge
1, dann die Wege der Länge 2, Länge 3 usw.
Hier haben Sie beliebige Längen automatisch mit drin.
Das ist ein genialer Algorithmus, ist, wie gesagt, bekannt, wird im
Operations Research manchmal Triple Algorithmus genannt, nach dem
Autor heißt er aber Warshall's Algorithmus.
Im Mittel haben Sie bei dieser Verbesserung den Aufwand reduziert, im
schlechtesten Fall, wie gesagt, immer noch N hoch 3, aber ist auf
jeden Fall ein schönes Verfahren.
Und das, was mich jetzt interessiert, ist Ihnen zu zeigen, wie man das
Ganze parallelisieren kann.
Wir wissen, wie wir parallel Matrixmultiplikationen machen können.
Aber hier haben wir jetzt keine Matrixmultiplikation.
Und jetzt schauen wir uns mal an, wenn ich den Warshall-Algorithmus
auf einem zweidimensionalen Gitter ausführen möchte.
Und ich habe in dem zweidimensionalen Gitter meine
Erreichbarkeitswerte drin, die aij.
Also ein n mal n Gitter und in jedem Element steht gerade so ein aij
drin.
Und jetzt möchte ich gerne diese Operation ausführen.
Ich möchte gerne diese Operation ausführen.
Das ist der Rumpf, den ich dort im Prinzip durchführen muss.
Und Sie erinnern sich, wir hatten das bei der Matrixmultiplikation
ganz einfach.
Da haben wir einfach so die Werte so durchlaufen lassen von oben und
unten oder von links und von oben und hatten die dann direkt
miteinander verbunden.
Es trafen sich immer die richtigen Elemente.
Jetzt schauen wir uns das mal an.
Für k gleich 1 bis n müssen wir dafür sorgen, wir wollen also zum
Beispiel diesen Wert hier ausrechnen, a33.
Dann müssen wir berechnen a33 oder a31 und a13.
a31 ist der Wert aus diesem, der Wert aus dem Prozessor.
Dann brauchen wir als nächstes, für k gleich 2 brauchen wir den Wert
und den Wert.
Dann brauchen wir, natürlich das ist trivial, das ist irrelevant, und
dann brauchen wir diese beiden.
Das heißt, wir müssen hier Elemente zusammenführen, die relativ weit
auseinander sind.
Die Distanzen der Elemente, die wir hier in einem Knoten miteinander
verbinden müssen, die sind alle unterschiedlich.
Und das ist nicht sofort ersichtlich, wie man das eigentlich gut
hinbekommen kann.
Das funktioniert nicht so, wie wir das vorher gemacht haben, mit dem
einfach Durchschieben der Matrizen, sodass die sich jeweils treffen.
Das läuft hier nicht auf diese Art und Weise.
Also, wie kann man das hinbekommen?
Und die Idee ist folgende, im ersten Schritt bewegen wir einfach die
erste Zeile von oben nach unten.
Also diese Zeile hier schieben wir hier einmal ganz durch.
Und bei diesem Durchschieben, das ist ein zyklisches Ringschieben, das
heißt anschließend ist die Zeile, also erst haben wir hier, also diese
geht praktisch nach oben, die geht jeweils eins nach oben.
Und diese erste Zeile hier, die wandert ganz nach unten.
Also die wandert da ganz nach unten.
Aber eben nicht direkt, sondern sie wandert sukzessive durch diese
einzelnen Zeilen hindurch.
Und bei diesem Durchwandern lasse ich jeweils das Element dort stehen.
Also im Prinzip mache ich das so, dass ich das A11 bis A14 nach unten
schiebe, in jedem Knoten dieser Spalte das Element aufbewahre und
anschließend noch alles eins nach oben schiebe.
Das heißt anschließend habe ich hier drin, wenn ich mir das hier
aufmale, hätte ich hier drin stehen, da oben A21 und A11, wenn ich mir
die erste Zeile anschaue, da unten drunter hätte ich dann das A31 und
A11, ich hätte das A41 und A11 und unten hätte ich A11 und A11.
Und entsprechend in den anderen Zeilen, also hier hätte ich dann
entsprechend A23 und A13.
Ja, ja, und A13.
Ich überlege gerade, was habe ich jetzt hier gemacht?
Okay, das muss nun stimmen.
Dann hätte ich hier A33 und A13,
die muss ich doch gar nicht verbinden.
Was habe ich denn jetzt hier an?
Das stimmt jetzt nicht, ist egal, ich werde das schon herausfinden,
was ich hier gemacht habe.
A43 und A13 und hier hätte ich A13 und A13.
So, die lasse ich alle so rüberlaufen, durch Ring schieben und im
zweiten Schritt bewege ich die erste Spalte von links nach rechts und
speichere dabei die Werte in den durchlaufenden Prozessoren.
Das heißt, diese erste Spalte, das wären diese A21, A31 bis A41, die
schiebe ich jetzt nach rechts und speichere entsprechend die Werte in
den durchlaufenden Prozessoren.
Das heißt, dann hätte ich anschließend in dem Prozessor, wo vorher
schon A23 und A13 abgelegt waren, hätte ich dann noch A21 drin stehen.
Also da würde anschließend hier in diesem auch noch drinstehen das A21
und hier würde noch das A31 drinstehen und da würde noch das A41
drinstehen und da das A11.
Jetzt hätte ich also die Elemente A21, A23 und A13 dort drinstehen.
Mit diesen drei Elementen kann ich jetzt die Berechnung machen, A23
ist gleich, A23 oder A21 und A13.
Ich habe diese drei Elemente dort drinstehen.
Ich habe also in jedem Prozessor, habe ich jetzt genau, ich habe also
in diesem zum Beispiel, in dem Prozessor, der jetzt hier eins nach
links geschoben ist, habe ich die Elemente A43, ich habe A41 und A13
drin.
Das heißt, ich kann in jedem Prozessor genau die Operation machen, die
ich brauche für K gleich 1.
Nach diesem Ringschieben der Zeile und der Spalte, habe ich jetzt in
jedem Prozessor, in jeder Zelle genau die drei Elemente, die ich
brauche, um diese Operation auszuführen.
Und zwar habe ich die jetzt nicht, also vorher war dieses Element an
der Stelle und das ist jetzt um eins nach oben verschoben worden und
um eins nach links.
So, das ist dieses Durchschieben der Zeile und durchschieben der
Spalte.
Und dann kann ich diese Operation ausführen und anschließend mache ich
im Prinzip das Gleiche nochmal.
Ich schiebe die oberste Zeile nach unten und schiebe die linkeste
Spalte nach rechts.
So, die oberste Spalte nach unten heißt, jetzt schiebe ich hier oben,
ich habe jetzt zwar hier drin stehen, also dieses A21, jetzt wird
dieses nach unten geschoben und dann habe ich im Prinzip überall die
Möglichkeit, die Operation für K gleich 2 zu machen.
Weil ja die zweite Zeile oben steht und die zweite Spalte links, wenn
ich die nach unten und nach rechts schiebe, habe ich anschließend die
Möglichkeit, in allen Prozessoren die Operation zu machen für K gleich
2.
Und anschließend mache ich das Ganze nochmal und habe dann die
Möglichkeit, das Ganze auszuführen für K gleich 3 und so weiter.
Das ist auf der nächsten, also hier ist es jetzt dargestellt, ich
wische das einfach weg, in der Aufzeichnung ist es ja zu sehen und
damit haben wir hier nochmal das Allgemein dargestellt.
Nach, das ist genau das, was ich hier aufgeschrieben habe, hatte ich
vor dort hingemalt, nach diesem Teile nach unten schieben und Spalte
nach rechts schieben, habe ich in Prozessor I minus 1, J minus 1, das
A, I, J stehen, das A, I, 1 und das A, 1, J.
Und die kann ich jetzt verbinden, das war das für K gleich 1.
Und wenn ich das jetzt für das Normal mache, habe ich das für K gleich
2, für K gleich 3 und so weiter.
Ich kann dort jeweils diese Operation machen.
Ich muss das N mal durchführen.
Und damit hätte ich genau den Wortschallalgorithmus simuliert.
Ich kann genau die Operation des Wortschallalgorithmus, die hier
dargestellt sind, das war die Operation, das mache ich jetzt für K
gleich 1 bis N, in allen Prozessoren I, J diese Operation.
Der Aufwand ist natürlich groß.
Ich muss die Zeile durchschieben, das ist Aufwand, das ist lineare
Aufwand, parallel.
Ich muss die Spalte rüberschieben, nochmal lineare Aufwand.
Dann muss ich einmal die Operation machen, das ist konstanter Aufwand.
Und das Ganze muss ich N mal machen, dann hätte ich also quadratischen
Aufwand.
Und das stört mich.
Hier ist das nochmal dargestellt, wie man das, was ich gerade auf der
vorigen Folie dargestellt hatte, sieht man hier nochmal, wie die
Elemente dort zusammengewürfelt sind.
Also das, was ich vorher sagte, das ist jetzt der Prozessor, der halt
das Element A22 enthält.
Also der Prozessor I1 enthält das Element A22.
Der Prozessor I2 enthält das Element 23 und so weiter.
Und das Element 13, das ist halt hier unten hingewandert.
Und in schwarz ist jeweils das Matrix-Element angegeben, das mich
interessiert.
Und in rot und in blau sind angegeben die Elemente, die ich durch das
Zeilenverschieben und Spaltenverschieben hier reinbekommen habe.
Das ist also die ganze Idee.
Und der Aufwand ist halt relativ hoch.
Das ist hier genau nochmal das dargestellt, hier visualisiert, was für
Elemente dort in die einzelnen Zellen reinkommen.
Und jetzt habe ich also quadratische Zeit.
Und jetzt mache ich das Ganze anders.
Wenn ich das erste Element hier nach unten schiebe und das dann noch
weiter schiebe und noch weiter, dann könnte ich ja eigentlich
gleichzeitig das Element darüber schieben.
Also diese Operation, ich habe jetzt hier nach unten geschoben.
Ich hole natürlich auch ein Element von unten nach oben, das Element
aus der zweiten Zeile.
Aber diese Operation, das war eine Operation auf diesen, im Prinzip
muss ich mir diese drei Elemente angucken.
Hier drin möchte ich gerne ein Element von dort haben und ein Element
von dort.
Und das kann ich lokal erledigen.
Das ist im Prinzip eine Operation, die bezieht sich nur hier oben auf
einen bestimmten Bereich.
Ihr habt gesehen, das kommt nach oben und nach links.
Also eigentlich muss ich dieses Element hier.
Dieses Element muss nach oben geschoben werden und dahin geschoben
werden.
Das kann ich aber durch einige Operationen machen.
Ich kann das im Prinzip so in Diagonalen laufen lassen.
Und wenn ich die hier verschoben habe, dann bin ich eigentlich mit
diesem Element fertig.
Dann habe ich dort meine drei Elemente A2-2, A2-1 und A1-2 drin
stehen.
Und entsprechend kann ich das noch weiter durchlaufen lassen.
Und sobald ich damit fertig bin, kann ich eigentlich hier drin die
Operation ausführen, das Warschallalgorithmus, und kann anschließend
anfangen, die nächste Iteration zu machen.
Das heißt, ich brauche hier eine bestimmte Anzahl von Operationen,
also hier die Breite dieser Berechnungswellen, das ist eine Anzahl von
Operationen C, die ich brauche, um die Elemente aus den benachbarten
Zellen zu verschieben und die Warschall-Operationen zu machen.
Wenn ich diese C-Operation gemacht habe, dann kann ich die nächsten C
-Operationen anfangen, von der zweiten Iteration für K gleich 2, dann
für K gleich 3, für K gleich 4 und so weiter.
Das heißt, ich habe nur eine konstante Anzahl von Operationen zu
machen, in so einem diagonalen Band, und das läuft so sukzessive hier
durch.
Das heißt, ich brauche nur C mal N, nicht ganz, das N muss ja auch
ganz durchlaufen.
Also C mal N, um das hier oben hinlaufen zu lassen, und dann nochmal
das Ganze durch, also C mal N plus entsprechend hier ganz durchlaufen.
Und damit habe ich aber insgesamt linearen Aufwand.
Ich habe nicht quadratischen Aufwand.
Und jede Berechnungswelle besteht aus einer konstanten Zahl von
Diagonalen insgesamt.
Um hier ganz durchzulaufen von diesem Schritt bis zu dem Schritt, wo
ich am Ende dann hier unten die Ende-Operation mache, habe ich
insgesamt einen Aufwand, der linear ist.
Und damit kann ich das Ganze auch noch mit Single Instruction Multiple
Data machen.
Also könnte ich so machen.
Ich kann es auch noch anders machen.
Ich kann das machen mit einem, das habe ich jetzt hier, genau, hier
habe ich es nochmal dargestellt.
Ich kann das, was ich mit Single Instruction Multiple Data machen
möchte, wo ich in jedem Knoten die gleiche Operation mache, kann das
noch verbessern um konstanten Faktor, indem ich sogenannte Wavefront
Arrays betrachte.
Im Prinzip sind das hier Wavefront Arrays, wo ich eine Operation oder
eine komplexere Operation in so einer Wellenart sukzessive durch eine,
also ich habe hier meine einzelnen Wellen und die schiebe ich durch so
ein zweidimensionales Feld durch.
Das ist eben ein Programmierprinzip, das ich Wavefront Array nenne.
Es gibt eine andere Variante, die nennt sich Befehlsystolische Felder
oder Instructional Systolic Arrays.
Diese Wavefront Arrays, die sind von,
es gibt ein schönes Buch von S.Y.
Kung dazu und dieses hier Instructional Systolic Arrays, das sind im
Wesentlichen Arbeiten von Lang und noch ein paar anderen Leuten, wo
mein Name auch mit auftaucht.
Also Instructional Systolic Arrays, die haben wir früher mal in Kiel
entwickelt.
Das ist also Instructional Systolic Arrays.
Was sind Systolische Felder?
Systolic Arrays, haben Sie schon mal gehört den Namen bei den Matrix
-Multiplikationen?
Da wurden Daten durch ein Feld geschoben.
Bei den Instructional Systolic Arrays, da schieben wir im Prinzip
Programme, das ist also hier ein Programm, durch ein Feld durch und
wir schieben hier so eine Art Selektoren durch ein Feld durch.
Also Informationen, die dann jeweils in einer Zelle kombiniert werden,
da kommt dann ein Befehl und ein Selektor rein und ein Befehl wird
ausgeführt, wenn der Selektor einen bestimmten Wert hat.
Das ist in dem Sinne ein Befehlsystolisches Feld, weil wir dort
Befehle durch ein Feld durchschieben.
Das geht über den Umfang dieser Vorlesung hinaus, wenn ich Ihnen dazu
noch zu viel erzähle, aber das ist auch ein interessantes Konzept
gewesen für die Programmierung von zweidimensionalen Feldern.
Also, das zu den parallelen Varianten, wenn ich die erste Idee
verwende, muss ich in einer naiven Parallelisierung quadratische Zeit
spendieren, immerhin ein Vorteil gegenüber Zeit n hoch 3, aber ich
kann es eben verbessern, indem ich diese Wavefront-Array-Ideen
verwende, bei denen ich sukzessive die Operationen in einer diagonalen
Art und Weise mache und dadurch dann dafür sorge, dass diese
Berechnungsregeln nacheinander parallel ausgeführt werden können und
dann habe ich insgesamt einen linearen Aufwand.
Dann habe ich mit n Quadratprozessoren einen linearen Aufwand, bin
also von n hoch 3 runtergekommen auf lineare Zeit, das heißt, das ist
eine bestmögliche Parallelisierung des Warschall-Algorithmus.
Und damit sind wir durch diesen Warschall-Algorithmus schon durch.
Und jetzt ist das Interessante, wenn man sich viele Probleme anguckt
im Bereich der Graphen, dann stellt man fest, dass Sie sehr viele
dieser Probleme lösen können durch algorithmische Ansätze, die
entweder sind vom Typ Matrixmultiplikation, das heißt eine Iteration,
bei der Sie i, j, k in dieser Reihenfolge geschachtelt haben, oder von
Typ Warschall, k, i, j, die drei Iterationen, mit gewissen Varianten
in dem, was in dem Rumpf steht, aber im Prinzip taucht diese Struktur
immer wieder auf.
Und das heißt, wenn man eine parallele Variante hat für diesen
Warschall -Algorithmus, stellt sich gleich heraus, kriegt man sofort
parallele Varianten, effiziente parallele Varianten für eine große
Klasse von anderen Graph-Problemen.
Und das ist das Interessante bei dem Warschall-Algorithmus und der
parallelen Variante, dass das so ein Muster ist, das ich immer wieder
verwenden kann, wobei ich nur das, was in dem Rumpf drinsteht, also
dieses a, i, j oder a, i, k und a, k, j, das sieht dann ein bisschen
anders aus.
Sie sehen das gleich hier.
Dijkstra's Algorithmus.
Dijkstra's Algorithmus kennen Sie auch, denke ich, den haben Sie schon
mal gehört, im Bereich der Berechnungs-Research.
Einfacher Algorithmus, wir haben gewichteten Graph, jede Kante hat
also noch ein Gewicht.
Wir möchten nicht nur feststellen, sind die verbunden, sondern was ist
der kürzeste Weg.
Und ich habe also hier noch so eine Funktion c dabei.
Für jede Kante wird ein Wert dort angegeben, irgendeine ganze Zahl,
eine nicht negative ganze Zahl.
Und wenn die Kanten nicht verbunden sind, dann ist das c, i, j gleich
unendlich.
So, und jetzt möchte ich für irgendeinen Ausgangsknoten in so einem
Graphen die kürzesten Wege bestimmen.
Das heißt die Wege mit kürzester Gewichtssumme zu allen anderen Knoten
v.
So, was mache ich?
Ich beginne, der Dijkstra-Algorithmus läuft so, dass ich mit einer
Menge s beginne, oder ich fliege, ich arbeite mit einer Menge s,
zunächst mal in der Knoten u, zudem kenne ich den kürzesten Weg, das
ist nachdem ich die Länge 0.
Und jetzt setze ich für alle anderen Knoten v, betrachte ich als dv
die Kosten der Kante von u nach v, oder des Weges von u nach v.
Zu Anfang ist das nur die Kante.
Da wird also, wenn die nicht verbunden sind, wenn ich also hier
irgendeinen Knoten v habe, sind die direkt verbunden, wenn ich hier
oben einen Knoten v habe, die vielleicht nicht verbunden sind, wird
das unendlich sein.
Jetzt habe ich also dieses dv, ich habe eine Menge von Distanzen, und
jetzt wähle ich einen Knoten aus, der nicht in s liegt, sodass die
Distanz dv minimal ist.
Also ich wähle einen Knoten v, von dem ich weiß, die Distanz, also das
wird iteriert, die Distanz dv ist minimal.
So, das ist also der Knoten, der nach aktueller Kenntnis den kürzesten
Weg hat von u nach v mit der Distanz dv.
Und dann füge ich das w zu der Menge s mit hinzu.
Und das w war eben vorher noch nicht in s mit drin, das heißt, bei den
vorherigen Iterationen war das w weiter entfernt als andere Knoten.
Jetzt hat es unter denen, die noch nicht in s sind, den kürzesten
Abstand.
Und jetzt berechne ich für alle Knoten v, also für irgendeinen, ich
kann jetzt hier also irgendeinen Knoten v noch hinmalen, für alle
Knoten v berechne ich das dv neu, das ist das Minimum der alten
Entfernung von u nach v, oder, das Minimum der alte Entfernung von u
nach v ist dv, das ist hier diese Distanz, dv plus cwv.
Das heißt, das w ist mit v direkt verbunden, das ist das cwv.
Ich gucke mir also an, alle Knoten, die mit w direkt verbunden sind,
und schaue also nach, welcher Wert ist kürzer, entweder der, den ich
bisher betrachtet habe, von u nach v, oder gibt es einen Weg von u
nach v, der über diesen Knoten w führt, den ich gerade dazu genommen
habe zu meiner Menge s, und mit einer Kante direkt mit v verbunden
ist.
Wenn der w kürzer ist als das, was ich bisher betrachtet hätte, was
dort hinführt, dann habe ich hier einen neuen Wert einzutragen.
Es kann eben sein, dass vorher bei dieser Operation, da hatte ich auch
einen Wert drinstehen, aber der war halt größer, und wenn er jetzt
über diese Kante von w nach v kleiner wird, habe ich hier eine
Veränderung einzutragen.
Also das wäre hier im Prinzip das dv gewesen.
Und diese Schritte wiederhole ich, bis ich alle Knoten dort drin habe,
bis also s gleich n-1 ist, dann ist nur ein Knoten übrig, und damit
ist es klar, welches die kürzesten Wege sind zu all diesen Knoten.
Der Aufwand dafür ist wie groß.
Ich muss zunächst mal hier dieses dv setzen für alle Knoten, das ist
natürlich ein linearer Aufwand.
Dann muss ich hier ein Minimum bestimmen, das ist auch ein linearer
Aufwand.
Diese Menge der Knoten wird zwar jedes Mal um eins kleiner, aber
trotzdem ist es jedes Mal ein Aufwand in der Größe der Menge v-s.
Und dann muss ich noch für alle Knoten das dv wieder neu berechnen,
für alle Knoten, die in der Menge v-s drin sind.
Und da ich das entsprechend oft wiederholen muss, habe ich insgesamt
einen Aufwand, der quadratisch ist.
Also das ist hier quadratischer Aufwand, um alle kürzesten Wege zu
bestimmen, von einem Knoten zu allen anderen.
Klassischer Algorithmus, kennen Sie.
Hier ist nochmal etwas zur Korrektheit, das nochmal dargestellt.
Ich wähle immer den Knoten, der den kürzesten Abstand von u hat, wobei
nur Wege über zuvor gewählte Knoten betrachtet werden.
s steht also für Menge der Selected Nodes, deswegen s.
Und ich mache im Prinzip, habe ich hier einen greedy Algorithmus, der
jeweils das nächstbeste hier betrachtet.
Und ich habe also immer, dieses w hier ist jeweils das lokale Optimum.
Um die Korrektheit zu zeigen, muss ich zeigen, dass die Entfernung dw
tatsächlich die Länge des kürzesten Weges von u nach w ist.
Um das zu zeigen, nehme ich einfach an, dass es irgendeinen kürzeren
Weg von u nach w geben könnte, über einen Knoten außerhalb von s.
Also, ich habe jetzt diesen, wie ist denn das, wenn ich von u nach w
laufe, dann, und ich behaupte, es gibt also irgendeinen kürzeren Weg,
als den, den ich jetzt hier betrachte, direkt von u nach w, das wäre
das dw.
Ich behaupte, es gibt einen kürzeren, also hier würde ich ja direkt
von einem Knoten aus s nach w laufen.
Wenn es einen kürzeren Weg gibt, über einen Knoten außerhalb von s,
dann wäre das dx kleiner als das dw.
Dann wäre aber das x vorher schon gewählt worden.
Also das dx muss dann, die Entfernung von u nach x, diese Entfernung
dx muss dann ja kleiner sein als das dw.
Weil ansonsten der Weg von u nach w über x nicht kürzer sein kann als
der Weg von u nach w, wo ich das x nicht mit drin hatte.
Also das ist ein einfacher Widerspruch, dass das x, dass also ein
Knoten geben könnte, der nicht in dem s drin ist, der also noch nicht
gewählt wurde, sodass ich trotzdem direkt zu dem, also einen kürzeren
Weg zu dem w gefunden hätte.
Es reicht sich immer, die Knoten zu nehmen, die in der Menge s drin
sind, um die Wege tatsächlich, um die Weglänge anzupassen.
Und also der Beweis für den Dijkstra-Algorithmus ist sehr naheliegend.
Im Prinzip habe ich Ihnen das hier schon erläutert, dass das so
korrekt läuft mit diesem Algorithmus.
Dass hier tatsächlich die Länge der kürzesten Wege bestimmt wird über
Knoten aus s, ist auch, da muss ich auch was zumalen, also hier wird
die Länge der kürzesten Wege von u nach v über Knoten aus s bestimmt,
genau.
Ich gehe ja zu dem w, also der Weg von u über w und x nach v.
Oder der Weg von,
also wenn ich betrachte, was ich hier mache in dem Schritt 5 des
Algorithmus, das war auf Folie 11.
Ich berechne für alle Knoten, ob die bisherige Distanz, die ich
betrachtet habe, aktualisiert werden muss, weil es einen Pfad oder
eine Kante gibt von w direkt nach v.
Also es gibt einen Pfad von u nach w und jetzt, das ist ja das, was
ich hier gemacht habe, da habe ich mir nur angeguckt, die Entfernungen
zu meinen,
also ich habe ja immer nur betrachtet oder aktualisiert, hier wird
aktualisiert die Entfernung zu dem Knoten v, dadurch, dass ich einen
neu hinzugenommenen Knoten w betrachte, der jetzt in der Menge s mit
drin ist.
Und ich gucke mir an, ob ich dadurch mit einer direkten Kante zu dem v
schneller hinkommen kann.
Wenn ich jetzt das hier betrachte, ich schaue mir also an diese Kante
und die Frage ist, gäbe es noch einen anderen Weg, der vielleicht
kürzer wäre, der über eine andere Kante aus dem x gelaufen wäre.
Also dieser Weg von u über w und noch irgendeine andere Kante in x.
Das heißt, es könnte es sein, dass ich das v über eine andere Kante
von einem anderen Knoten aus hätte kürzer erreichen können.
Und das kann nicht passieren, weil alle Gewichte größer gleich 0 sind.
Und das heißt, dieser Pfad hier, der kann nicht kürzer sein als das u
nach w zu dem v über w.
Wenn das ein kürzerer Weg wäre über x nach dem v, dann wäre das v
gewählt worden und nicht das w in dem Schritt 3.
Und auf die Art und Weise kann man sich also auch für diesen Schritt 5
überlegen, dass dort auf richtige Art und Weise die Distanzen
aktualisiert werden.
Und damit ist also die Korrektheit von dem Dijkstra-Algorithmus im
Prinzip nachgewiesen.
Ich habe das etwas intuitiv hier argumentiert.
Man kann das alles auch formal hinschreiben, das wollte ich Ihnen aber
ersparen.
Ich wollte aber noch eine Bemerkung machen zum Dijkstra-Algorithmus.
Das ist ein klassischer Algorithmus, braucht wie gesagt quadratische
Zeit und wird auch in ganz vielen Anwendungen eingesetzt.
Wenn ich also kürzten Weg haben will von einem Knoten zu irgendeinem
anderen, zum Beispiel bei Routingverfahren im Internet, wird genau der
Dijkstra -Algorithmus eingesetzt, um die kürzesten Verbindungen zu
finden.
Wenn Sie aber Routingverfahren machen, im Verkehr zum Beispiel, und
Sie haben hier ein großes Straßennetz, viele verschiedene Straßen, ein
riesiges Straßennetz mit riesengroß verbundenen Graphen, und jetzt
wollen Sie eine kürzeste Verbindung haben zwischen irgendwelchen
Knoten, Sie wollen Ihre Fahrtroute bestimmen.
Sie wollen von hier meinetwegen nach dort oben kommen.
Wenn Sie jetzt den Dijkstra-Algorithmus anwenden, dann werden alle
Knoten betrachtet.
Sie laufen im Prinzip so sukzessive von dem hier so rum in solchen
Fronten durch den ganzen Graphen durch, immer erst die Abstand 1 und
so weiter, wählen einen nächsten Knoten, wählen dessen direkte
Nachbarn, wählen dort wieder den kürzesten Weg, wählen wieder dessen
direkte Nachbarn, wählen immer den Knoten aus, der den kürzesten
Abstand hat und von dem aus wieder direkten Nachbarn.
Und das dauert sehr, sehr lange.
Aber das, was in diesem Bereich hier unten ist, wäre eigentlich gar
nicht relevant.
Eigentlich wollen Sie ja nur das betrachten, was eigentlich in einer
gewissen Nachbarschaft Ihres optimalen Pfades läuft.
Wenn Sie das machen könnten, dass Sie im Prinzip eine Art haben, wie
Sie identifizieren können, die relevanten Kanten in dem Graphen, die
Sie betrachten müssen, um den kürzesten Weg zu finden von A nach B,
dann hätten Sie hier linearen Aufwand, wenn Sie also diesen Korridor
schmal machen können.
Hätten Sie also nur alle Kanten in dem Korridor zu betrachten, Sie
hätten auf einmal linearen Aufwand in der Länge des Pfades.
Und man kann das tatsächlich machen.
Man kann also den kürzesten Weg finden.
Durch gewisse Vorbearbeitungen des Graphen kann man erreichen, dass
man deutlich schneller wird als der Dijkstra-Algorithmus.
Das sind Sachen, das haben hier die Kollegen Wagner und Sanders
herausgefunden, wie man das macht.
Die haben also für solche Anwendungen in großen Graphen den Aufwand um
sehr große Faktoren reduziert.
Und mittlerweile sind das also die Verfahren, die tatsächlich auch in
der Praxis eingesetzt werden.
Also Dijkstra ist ein guter Algorithmus, aber ich muss mir mal
anschauen, wo setze ich ihn ein.
Wenn ich in der Lage bin, das ein bisschen zu reduzieren, ist es noch
besser.
Also wenn ich eben den Bereich reduzieren oder einschränken kann.
Natürlich geht das nicht immer.
Wenn ich einen beliebigen Graphen habe, kann es natürlich sein, dass
der kürzeste Weg aus irgendeinem Grund gerade hier hinten drüber
läuft.
Das muss man dann entsprechend vorher ausgeschlossen haben, dass das
der Fall ist.
Man muss dann schon die richtigen wirklich betrachten.
Aber das kann man in solchen praktischen Straßennetzen, da kann man
solche Einschränkungen machen.
Und wenn Sie sich, also nur noch mal so zu den Problemen der kürzesten
Wege, wenn Sie sich anschauen, die typischen Navigationsverfahren, und
Sie sind hier meinetwegen auf dem kürzesten Pfad an irgendeinem Knoten
angekommen, dann stellt sich heraus, Sie haben hier ein Problem, da
ist eine Abweichung.
Was machen die Verfahren dann?
Dann nehmen Sie irgendeinen anderen Knoten, Sie fahren irgendwie ab
und dann versucht das Verfahren, sucht da den kürzesten Weg zurück zu
Ihrem alten optimalen Weg.
Das heißt, da wird nicht der Pfad ganz neu berechnet, sondern man geht
im Prinzip den kürzesten Weg zurück zu der alten Route.
Was natürlich schlecht sein kann.
Es kann sein, dass dadurch, dass Sie hier einen Umweg genommen haben
hierhin, dass vielleicht das hier besser gewesen wäre.
Das wird aber bei den üblichen Verfahren nicht gemacht.
Die meisten Anwendungen, die Sie in Ihren Navigationsgeräten haben,
die machen so eine einfache Umwegart, dass Sie, wenn Sie abgewichen
sind von der Route, dann werden Sie zurückgeführt zu Ihrer alten
Route.
Deswegen gibt es, wenn man sich nur noch auf den Navi verlässt, und
man hat irgendeinen Bereich, der gesperrt ist, Sie werden immer wieder
dahin geführt, wo es gesperrt war.
Ist also manchmal ein bisschen problematisch.
Diese Thematik ist eine interessante Thematik, kürzeste Wege zu
berechnen, in solchen Umgebungen, wo sich Dinge verändern können, dass
Sie mal auf einmal eine Kante nicht mehr da haben, das wird ein
Fehlerfall auftreten und so weiter.
Das ist eine interessante Thematik.
Also das wären so dynamische Probleme.
Und noch interessanter ist es, wenn Sie zeitlich unterschiedliche
Gewichte haben.
Sie haben Stauvorhersagen.
Sie wissen, zu bestimmten Zeiten während des Tages sind die Fahrzeiten
zwischen zwei Punkten anders, die verändern sich.
Und Sie wollen also einen Weg so planen, dass Sie unter
Berücksichtigung der zu erwartenden Staus dort gut ans Ziel kommen.
Dann müssen Sie zeitlich variable Gewichte auf den Kanten haben und je
nachdem, wann Sie losfahren, würden Sie zu anderen Zeitpunkten dorthin
kommen müssen, dann entsprechend andere Algorithmen anwenden.
Das sind Dinge, woran aktuell gearbeitet wird, wie man das dann auch
noch bestmöglich hinbekommt, wobei man sich eben über eines im Klaren
sein muss, wenn jetzt alle Leute dynamisch bestmögliche Pfade finden
würden, würden natürlich die Prognosen für die Staus, die man macht,
so nicht mehr zutreffen, weil sie ja diese Staus vermeiden.
Und dann muss man wieder dafür sorgen, dass durch diese Stauvermeidung
nicht woanders Staus auftauchen.
Das ist ein sehr dynamisches Problem, ein sehr interessantes
Optimierungsproblem, mit dem kann man sehr viele interessante
Forschungsarbeiten drauf machen.
Und jetzt möchte ich manchmal nicht nur die Verbindungen von einem
Knoten zu allen anderen haben, sondern ich möchte gerne alle kürzesten
Wege haben.
Von je zwei Punkten den kürzesten Weg.
Und ich kann das also so machen, dass ich für jeden Knoten einfach
Dijkstra's Algorithmus anwende, dann hätte ich kubischen Aufwand, n
hoch 3.
Ich kann aber auch den Floyd'schen Algorithmus anwenden.
Und bei dem Floyd'schen Algorithmus, wie sieht der aus?
Der läuft im Prinzip ähnlich, aber der hat hier eine einfache
Formulierung.
Sie haben also für je zwei Knoten, haben Sie zunächst mal das
Kantengewicht draufstehen, das kann also unendlich sein, wenn Sie dort
keine Verbindung haben.
Und dann haben Sie hier eine Schleifenformulierung für K gleich 1 bis
N, für IJ gleich 1 bis N.
Ist DIJ gleich dem Minimum von DIJ und dem DIK plus DKJ.
Und jetzt sehen Sie sofort eine Analogie zu dem Worschel-Algorithmus.
Kürzeste Verbindung zwischen je zwei Knoten.
Sie haben genau wieder diese Operation.
Wir hatten bei dem Worschel-Algorithmus hier nicht stehen, das Minimum
von DIJ und DIK plus DKJ, sondern wir hatten AIJ stehen oder AIK und
da stand also, das war AIJ gleich AIJ oder AIK und AKJ.
Die Indexpaare hier sind identisch.
Sie haben aber nicht oder und und, sondern Sie haben das Minimum von
zwei Werten und es ist offensichtlich, dass man genau diese Operation
hier natürlich dann ausführen kann in der Struktur, die wir Worschel
-Algorithmus genannt haben.
Das heißt, der Floyd'sche Algorithmus ist eigentlich der Worschel
-Algorithmus.
Das ist nichts anderes.
Das ist also nur hier unten die Operation leicht ersetzt und dadurch
haben Sie dann nicht nur die Erreichbarkeit, sondern Sie haben den
kürzesten Weg.
Die Frage ist, Sie haben hier zunächst mal nur die Längen der
kürzesten Wege.
Wenn ich jetzt weiß, das ist der kürzeste Pfad zwischen irgendwelchen
zwei Knoten, woher weiß ich, wenn ich hier irgendwo bin, über welchen
nächsten Knoten ich laufen muss?
Und die Frage ist, wie erreiche ich hier für jedes Paar den
vollständigen, kürzesten Weg?
Also erstmal ist das Entwurfsmuster Warschall, das ist klar.
Wenn ich wissen möchte, wie ich laufen muss, muss ich also von jedem
Knoten wissen, was ist mein nächster Knoten, über den ich laufen muss.
Also muss ich doch einfach nur wissen, wenn ich zwei Knoten habe, ich
muss wissen, welches ist der nächste Knoten, über den ich laufen muss,
um von A nach B zu kommen.
Das ist also mein Zwischenknoten K.
Das heißt, ich betrachte jetzt eine kleine Variante von dem
Floyd'schen Algorithmus, das ist ja alles so wie vorher.
Ich betrachte jetzt aber nicht nur die Abstände, sondern ich betrachte
auch noch jeweils eine Variable WIJ.
Und das WIJ setzt sich zu Anfang auf I.
Wenn das CIJ kleiner und endlich ist, wenn ich also einen Weg habe,
dann ist der Knoten, das ja zu Anfang heißt, ich habe eine Kante von I
nach J, das heißt, das WIJ gibt mir an, den Knoten, von dem aus ich
direkt das J erreichen kann, den Knoten J erreichen kann, was ist der
letzte Knoten auf dem Weg dorthin.
Und entsprechend mache ich das weiter.
Hier wird zunächst mal eine kleine Vereinfachung gemacht, das Ganze
macht ja nur Sinn, wenn ich durch die Summe, also wenn ich den Weg
über K tatsächlich eine Verbesserung habe.
Wenn das größer wäre, bräuchte ich hier gar nicht weiterzumachen.
Nur wenn das eine Verbesserung ist, dann setze ich das DIJ auf diesen
neuen Wert, DIK plus DKJ.
Und da ich jetzt weiß, ich habe, wenn wir uns das anschauen, nochmal I
und J und ich weiß, ich muss jetzt hier über den Knoten K laufen, das
sind jeweils hier Pfade, keine einzelnen Wege, und mein WIJ, sagte
ich, war der Knoten, über den ich das J als letztes erreichen kann.
Das heißt, ich habe hier ein WIJ, hier habe ich ein WIK und da habe
ich ein WKJ.
Und wenn jetzt der Weg über K, wenn dieser Weg hier kürzer ist, als
der Weg, den ich vorher hatte, dann erreiche ich doch den Knoten J
über den letzten Knoten auf dem Weg von K nach J.
Das heißt, ich setze einfach das WIJ auf den letzten Knoten, den ich
auf dem Weg von K nach J besucht hatte.
Ansonsten brauche ich nichts zu verändern.
Und damit habe ich immer in dem WIJ gespeichert den letzten Knoten auf
dem Weg, über den ich auf diesem kürzesten Weg das J erreicht hatte
und habe damit genau diese Pfadeinformation.
Und so kann ich sukzessive da durchlaufen.
Ich habe an jeder Position, für jede Position J oder für jedes, für
jede, ich habe also dort jeweils gespeichert genau diesen kürzesten
Pfad.
Ich weiß also, wenn ich dann zurückgelaufen bin, bei dem Knoten WIJ
bin, dann kann ich von dem aus betrachten, den kürzesten Pfad von I zu
diesem Knoten WIJ und habe dann wieder den Knoten, den ich dort als
letztes besucht habe usw.
Auf die Art und Weise bekomme ich also einfach mit dieser einfachen
Variable die Wege auch noch geliefert.
Ich muss nicht für jeden Pfad, für jeden einzelnen, also wenn ich den
kürzesten Weg vollständig abspeichern wollte, hätte ich einen hohen
Speicheraufwand.
Auch einen hohen Aufwand, um das immer zu aktualisieren.
Das kann ich mir hier mit sparen.
Man kann das also alles in einer Matrix abspeichern mit quadratischem
Aufwand.
Und jetzt sind wir im Prinzip schon mit diesem Algorithmen in Graphen
durch.
Es gibt eine ganze Reihe weiterer Probleme, die man sich anschauen
kann, die alle sehr interessant sind.
Ich möchte von einem Graphen die Zusammenhangskomponenten bestimmen.
Also das sind die verschiedenen Komponenten, wenn ein Graph in so
verschiedene Teile zerfällt.
Welche sind das?
Wie sieht das aus mit dem Grad des Zusammenhangs?
Was heißt das?
Ein Graph ist k-Knoten zusammenhängend.
Das heißt, ich kann irgendeinen beliebigen Knoten rausnehmen, oder ich
kann bis zu k-Knoten rausnehmen und er ist immer noch zusammenhängend.
Ich darf also bis zu k-Knoten rausnehmen, einfach zusammenhängend,
zweifach zusammenhängend usw.
Das gibt mir praktisch an, wie redundant die Verbindungsstruktur ist.
Und solche Informationen sind natürlich wichtig.
Sie wissen zum Beispiel, in Stromnetzen ist es so, dass wir eine N-1
Sicherheit haben.
Das heißt, wenn eine Komponente ausfällt, haben Sie immer noch die
volle Leistungsfähigkeit des Netzes garantiert.
Sie können also den Ausfall eines beliebigen Knotens tolerieren oder
auch den Ausfall einer beliebigen Kante.
Das macht natürlich Unterschiede, wenn hier ein Knoten wäre, der die
alle verbindet, und der Knoten würde ausfallen, wären die alle uns
zusammenhängend.
Wenn eine Kante ausfallen würde, dann wären die immer noch verbunden.
Also Knotenzusammenhang, Kantenzusammenhang sind leicht
unterschiedlich.
Was dann interessiert ist, wo sind die kritischen Bereiche eines
Graphen, wo sind also die Brücken.
Brücken wären so etwas oder so etwas oder so etwas und Zentren wäre so
ein Knoten.
Das heißt, Brücken wären Kanten, bei deren Ausfall ein Graph
unzusammenhängend wird oder ein Zentrum ist ein Knoten, bei dessen
Ausfall der Graph nicht mehr zusammenhängend ist.
Das sind also die kritischen Punkte eines Graphen.
Oder ich möchte vollständig verbundene Teilgrafen finden.
Vollständig verbundene Teilgrafen, das heißt, wenn ich mir die
transitive Hülle anschaue, dann wäre das in der transitiven Hülle,
wäre jeder mit jedem verbunden.
Das wäre ein Klicken in der transitiven Hülle des Graphen.
Kann von jedem zu jedem anderen kommen.
Oder ich möchte einen Graphen färben, keine gleich gefärbten Nachbarn.
Wie viele Farben brauche ich, um einen Graphen so zu färben, dass je
zwei Nachbarn unterschiedliche Farben haben?
Typisches Problem, wenn Sie Landkarten färben, Sie wollen Länder mit
unterschiedlichen Farben kennzeichnen, sodass Sie die direkt
unterscheiden können.
Keine zwei Länder, die aneinander grenzen, dürfen der gleichen Farbe
gefärbt sein.
Das kann man mit vier Farben erreichen.
Was ist der Durchmesser eines Graphen?
Der Durchmesser ist der maximale kürzeste Weg zwischen zwei Knoten
eines Graphen.
Sie haben also hier irgendwelche Knoten, Sie gucken sich an, alle
kürzesten Wege, der maximale kürzeste Weg zwischen irgendwelchen zwei
Knoten ist der Durchmesser.
Dann gibt es die Weite eines Graphen.
Noch ein Problem, das interessant ist.
Sie schauen sich irgendeinen Graphen an,
oder auch hier in diesem Graphen.
Sie schauen sich an, Sie schneiden den Graphen in zwei Teile, und zwar
so, dass etwa gleich viele Elemente links und rechts liegen.
Es ist die Frage, wie viele Kanten müssen Sie durchschneiden, um einen
Graphen in zwei Teile zu teilen.
Wenn ich Ihnen einen Baum aufmale, einen vollständig balancierten
Baum, dann bräuchten Sie nur eine Kante zu zerschneiden, und Sie
hätten eine vollständige Aufteilung.
Das Problem ist aber, wenn diese eine Kante wegfällt, oder wenn Sie
Informationen austauschen wollen zwischen diesem Bereich A und dem
Bereich B, dann hätten Sie hier einen Engpass.
Also die Anzahl der Kanten, die zwischen so zwei etwa gleich großen
Teilen eines Graphen liegen, sagen Ihnen etwas darüber, wie lange es
dauert, um Informationen zwischen diesen beiden Bereichen
auszutauschen.
Wenn die miteinander reden müssen, und Sie können das nur über diese
eine Kante hier oder diesen schmalen Weg da oben, dann dauert das sehr
lange.
Also möchten Sie gerne, dass Sie eine, also für
Kommunikationskomplexität zum Beispiel, wollen Sie gerne erreichen,
dass Sie eine einigermaßen große Weite eines Graphen haben, egal wie
Sie den aufteilen in zwei Teile, so dass Operationen auf einem solchen
Graphen relativ schnell bearbeitet werden können.
Ansonsten bekommen Sie einen Engpass dadurch, dass Sie über eine
solche, wie hier bei dem Baum, über einen solchen Engpass halt lange
brauchen, um Informationen auszutauschen.
Also Informationen über die Weite eines Graphen sind wichtig, um
untere Schranken anzugeben für die Ausführungszeit von bestimmten
Funktionen auf parallelen Rechnerstrukturen.
Andere Probleme.
Kürzester Hamilton'scher Kreis.
Das Problem kennen Sie unter einem anderen Namen.
Der Hamilton'scher Kreis ist ein Pfad, der alle Knoten eines Graphen
verbindet, ohne Knotenwiederholungen.
Kürzester ist praktisch das Travelling Salesperson Problem.
Anderes Problem ist, Sie wollen ein Layout eines Graphen zeichnen.
Wie zeichne ich das Layout eines Graphen?
Ich könnte einen Baum so aufmalen.
Das wäre ein Baum.
Ich kann den Baum auch so aufmalen.
Oder ich kann ihn auch noch anders aufmalen.
Ich kann ihn so aufmalen.
Wie male ich einen Baum bestmöglich auf?
Wie male ich einen beliebigen Graphen bestmöglich auf?
Also, wenn ich vier Knoten habe, ich habe die miteinander verbunden,
die und die, und ich habe die noch verbunden, und die verbunden, male
ich jetzt die Kante zwischen den beiden so hin?
Oder male ich sie hier direkt durch?
Möchte ich Kantenkreuzungen erlauben oder nicht?
Natürlich ein planarer Graph, ich kann das so hinmalen.
Ist das eine sinnvolle Art, den aufzumalen?
Also es gibt viele Überlegungen, wie man Graphen zeichnen kann.
Nehmen Sie sich ein, wenn der Graph der Streckennetz eines
öffentlichen Nahverkehrs ist.
Da wollen Sie, dass die geografischen Zuordnungen, dass das
einigermaßen passt.
Sie wollen aber auch eine schnelle Übersicht haben.
Der muss leicht überschaubar sein.
Also, Graphen zu zeichnen, ist ein sehr interessantes Problem.
Und da kann man also viele verschiedene Kriterien aufführen.
Kann sein, dass ich eine gleichmäßige Knotenkantenverteilung haben
möchte.
Das will ich bei einem Streckennetz einer U-Bahn nicht haben.
Nicht gleichmäßige Knotenkantenverteilung, sondern das soll der
Geografie der Stadt entsprechen.
Minimale Anzahl Kreuzungen, das sind andere, habe ich hier angedeutet.
Symmetrieeigenschaften können eine Rolle spielen.
Da gibt es viele verschiedene Probleme, die man betrachten kann.
Und das, was interessant ist, hatte ich schon gesagt vorhin, dass also
gerade die Probleme, die hier oben sind, im Prinzip alle entweder vom
Typ Matrixmultiplikation oder vom Typ Warschall sind.
Und man kann sie alle mit diesen beiden Mustern, die ich Ihnen
vorgestellt habe, im Prinzip bearbeiten.
Das sei für heute genug.
Ah ja, das ist noch was anderes.
Zum Mapping-Ansatz, ich kann natürlich den Warschall-Algorithmus auch
abbilden.
Wir haben diese Parallelisierung betrachtet, bei denen wir über den
Mapping -Ansatz das Ganze betrachtet haben.
Wenn Sie das hier machen, als Rekurrenzgleichung aufmalen, dann
stellen Sie fest, dass die Datenabhängigkeiten in diesen
Rekurrenzgleichungen alle unterschiedlich sind.
Das sind keine uniformen Rekurrenzgleichungen.
Und deswegen, wenn Sie den Warschall-Algorithmus modellieren im Sinne
dieses Mapping-Ansatzes, sehen Sie, dass Sie mit dem üblichen Ansatz
hier nicht zum Ziel kommen.
Da musste man eben diese andere Überlegung machen, die wir gemacht
haben mit der Wavefront, also mit dem wellenförmigen Abarbeiten von
Diagonalen.
Okay, das ist aber wirklich jetzt alles, was ich in dem Kapitel Ihnen
zeigen wollte.
Damit haben wir heute ein ganzes weiteres Kapitel geschafft.
Und nächste Woche bin ich nicht da, da wird Herr Schuklam mich
vertreten.
Nächste Woche haben wir Abschluss unseres Projektes EIZEUS und haben
dann eine Veranstaltung in Stuttgart.
Nächste Woche wird also Herr Schukla Ihnen etwas erzählen über ein
paar Probleme im Bereich algorithmische Geometrie.
Vielen Dank für die Aufmerksamkeit.