Schönen guten Tag.
Ich begrüße Sie zur Fortsetzung der Vorlesung Grundlagen der
Informatik.
Quatsch, nicht Grundlagen der Informatik.
Manchmal hat man so Sätze einfach im Kopf.
Nein.
Ich begrüße Sie zur Vorlesung effizienter Algorithmen.
Das sind auch Grundlagen von Algorithmen, aber wir machen hier nicht
Grundlagen der Informatik 2.
Also, effiziente Algorithmen.
Wir waren letztes Mal bei Suchen und Sortieren und haben da schon
viele Dinge uns angeschaut gehabt.
Wir waren ziemlich weit gewesen.
Wir hatten alle möglichen Sortierverfahren angeguckt.
Die einfachen Bekannten, die ein bisschen weniger Bekannten.
Paralleles Verfahren, sehr parallel.
Ich habe Ihnen das 01-Prinzip vorgestellt.
Wir haben gesehen, wie man das benutzen kann, um Korrektheit zu
beweisen.
Wir haben das bei TonicMerge kennengelernt.
Ich habe Ihnen dann letztes Mal das LS3-Sort nochmal vorgeführt,
beziehungsweise bewiesen.
Laufzeit analysiert, bewiesen, dass das so korrekt ist.
Dieses Vierwegmischen in zwei Dimensionen.
Wir hatten gesehen, dass das also relativ gut ist.
Asymptotisch auf jeden Fall optimal.
Mit Bezug auf die Konstante noch nicht ganz, aber man kommt eben schon
ziemlich weit ran.
Wir hatten eben gesehen, dass es eine untere Schranke gibt.
Das war dann hier diese Sache mit der unteren Schranke, bei der man
das Prinzip der Joker-Zone ausgenutzt hat.
Wichtiges Beweisprinzip für untere Schranken.
Das heißt, ich erzeuge damit schlechte Fälle, also schwierige
Situationen für einen beliebigen Algorithmus.
Und dadurch kann ich untere Schranken zeigen.
Und das brachte eben in diesem Beispiel dann eine untere Schranke von
3N.
Und dafür gibt es eben sogar auch ein optimales Verfahren, das von
Thomson -Kung.
S-Quadratwegmischen, also noch deutlich größer, also nicht nur 2 oder
4, sondern eben S-Quadrat, wobei S die Wurzel aus der Anzahl der
Zeilen und Spalten ist in dem Fall.
Und dann kam noch das Mesh-of-Three-Sort.
Ich habe Ihnen dann noch diese untere Schranke vorgestellt für das
Sortieren mit allgemeinen Sortierverfahren, bei dem man eben nichts
weiß, außer dass man weiß, dass man die Elemente vergleichen kann.
Und dann kam noch als Kontrapunkt dagegen, wenn wir eben mehr wissen,
das Bin-Sort, bei dem wir einfach nur die Zahlen anschauen, die wir
sortieren und wissen, in welche Dose wir sie werfen.
Und wenn das nicht zu viele Dosen sind, wenn das genau N Dosen wären,
dann hätte ich ja Aufwand, Block N jeweils festzustellen, in welche
Dose ich das Ganze reinwerfen soll.
Und dann wäre das wieder etwas mehr Aufwand.
Also insofern muss man hier aufpassen, wie man wirklich analysiert.
Und dann kam als letztes, letztes Mal das Selektionsverfahren.
Ich habe Ihnen den naiven Ansatz vorgestellt, der natürlich
quadratisch ist im schlechtesten Fall.
Also das Selektionsverfahren für die Medien insbesondere.
Dann kam kurz der Algorithmus Quick-Select, eine Variante von Quick
-Sort, bei der wir eben nur noch auf einer Seite verzweigen müssen und
deswegen im Mittel auf O von N kommen, im schlechtesten Fall, aber
immer noch leiden müssen unter dem schlechten Fall, bei dem wir die
Folge, die wir angucken, nur um eins reduzieren jeweils, sodass wir
dann quadratisches Verhalten haben.
Und jetzt kommt heute als Neues das Verfahren, mit dem ich Ihnen
zeige, wie man tatsächlich in linearer Zeit ein beliebiges Element,
also das Karte-Element auswählen kann, insbesondere eben den Medien in
linearer Zeit.
Das war das Problem bei den anderen Verfahren, die ich Ihnen
vorgestellt hatte.
Wie sieht dieser Algorithmus aus?
Im Prinzip ist das auch ein Quick-Select-Verfahren.
Das ist eigentlich nur eine Variante von Quick-Select, aber man passt
hier auf, welches Element man aussucht, um diese Partitionierung zu
machen.
Man sorgt dafür, dass diese Partitionierung, die beim Quick-Select ja
im schlechtesten Fall zum quadratischen Verhalten führt, so gemacht
wird, dass ich jeweils einen festen Anteil der Folge, aus der ich
etwas raussuchen soll, abschneiden kann.
Wenn ich einen festen Bruchteil jeweils abschneiden kann, dann
verringert sich die Größe der Folge, die ich anschauen muss jedes Mal,
um eben genau diesen Bruchteil mindestens.
Und damit habe ich dann die Möglichkeit, tatsächlich hier auch im
schlechtesten Fall auf lineare Zeit zu kommen.
Und das schauen wir uns genauer an.
Also wir haben nach wie vor hier eine Menge von n Elementen und für
kleines n bestimmen wir das kartgrößte Element einfach durch irgendein
Verfahren.
Das ist uns egal, wie lange das dauert, das ist kleiner Aufwand.
Daran können Sie schon sehen, die Konstante, die man hier hat bei dem
linearen Verfahren, die wird relativ groß.
Wenn man sagt, hier spielt es keine Rolle, dann ist das schon ein
Verfahren mit einer großen Konstante.
Und jetzt kommt die Art, wie ich dafür sorgen möchte, dass ich einen
gewissen Anteil meiner Folge rauswerfen kann.
Das mache ich so, dass ich zunächst mal sage, ich teile meine Liste S
in Teillisten auf, die jeweils fünf Elemente haben.
Die sind hier angedeutet, also jeweils solche Teillisten.
Jetzt habe ich also n Fünftel solcher Teillisten.
Und jetzt bestimme ich die Mediane dieser Teillisten.
Das ist n Fünftel mal ein konstanter Aufwand, um die Mediane zu
bestimmen.
Die habe ich jetzt einfach so getan, als wenn die tatsächlich hier
jeweils in der Mitte liegen.
Also hier habe ich n Zehntel, n Zehntel plus eins und so weiter bis
die Folge n Fünftel, jeweils die Mediane.
Und jetzt nehme ich einfach an, in dieser Anordnung seien die kleinen
Elemente oben, die großen unten.
Also alle, die hier oben drüber sind, diese hier, die sind alle
kleiner gleich dem Median hier, die sind größer gleich dem Median da
unten.
Und jetzt mache ich folgendes, ich bestimme den Median dieser n
Fünftel Elemente durch einen Aufruf von Select.
Das heißt, hier ist ein rekursiver Aufruf.
Ich nehme mir diese kleine Folge hier von n Fünftel Elementen und
suche dort rekursiv den Median.
Welchen Aufwand das macht, werden wir später sehen.
Also n Fünftel der Elemente.
Dann habe ich ein Median anschließend und ich nehme einfach an, dass
das hier unser Median ist.
Alles geschickt angeordnet, sodass man sehen kann, was passiert.
Und die größeren Mediane seien links, die kleineren rechts.
Und jetzt kann ich daran gehen zu sagen, wie ich jetzt mein Quick
Select mache.
Das mache ich im Prinzip bezogen auf dieses Element M.
Damit bin ich eigentlich schon fertig.
Ich mache jetzt ein Quick Select M und bin noch nicht ganz fertig.
Ich suche ja das cardgrößte Element.
Ich brauche nicht Quick Select M.
Das stimmt nicht.
Also Quick Select, das cardgrößte.
Ich suche ja ein Pivot-Element.
So muss ich anfangen.
Ich suche ein Pivot-Element bei Quick Select.
Und dieses Pivot-Element nehme ich, das M.
Dieses M, also das Pivot-Element war ja so, wir haben hier
normalerweise unsere Folge.
Wir nehmen bei dem Standard-Quick Select das erste Element und
transformieren das Ganze so, dass wir anschließend eben dieses Element
C hier irgendwo hinpacken können an die richtige Position.
Und wir wissen alles, was hier ist.
In dem Fall, das ist größer gleich und diese hier sind kleiner als
dieses Element C.
So, das war die Partitionierung der Folge.
Und jetzt nehmen wir als Pivot-Element das M.
Das Problem beim schlechtesten Fall von Quick Select war, dass bei
einer unglücklichen Wahl des Pivot-Elements dieses C ganz am linken
Rand endet, sodass wir nichts gewonnen haben und die Folge nur um eins
kleiner wird.
Jetzt nehmen wir hier diesen Median, diesen Fünftel-Median und schauen
uns an, was wir jetzt für Ergebnisse haben bezüglich dieser weiteren
Folgen, die wir betrachten müssen.
Also ich definiere jetzt meine Mengen S-Strich und S-Zweistrich, so
wie vorher bei Quick Select.
Dieses S-Strich, das ist die Menge aller Elemente, die größer gleich M
sind.
Und S-Zweistrich, das sind alle, die kleiner als M sind.
So, was heißt das?
Also ich möchte gerne hier dafür sorgen, dass ich einen festen
Bruchteil rauslassen kann.
Wenn ich mir anschaue, die Elemente, die garantiert größer gleich
sind, das sind Elemente, naja, also schaue ich mir mal diese beiden
Mengen A und B an, das wollte ich im Prinzip machen.
Die Menge A enthält Elemente, die liegen in dem Bereich, wo sie hier
unten alle größer sind, als diese Mediane M1 bis Mn-Zehntel.
Die Mediane M1, M2 und so weiter sind alle größer gleich diesem M.
Das heißt, alle Elemente, die in A drin liegen, die sind alle größer
gleich M.
So, wenn die alle größer gleich M sind, dann weiß ich doch, dass S
-Zweistrich, geschnitten A, gleich leer ist.
Da sind nämlich alle drin, die kleiner als M sind.
Kein Element aus A kann in S-Zweistrich sein.
Wenn ich mir die Menge B anschaue, dann sind alle Mediane, die ich
hier habe, die Mn-Zehntel plus 1 bis Mn-Fünftel, sind kleiner als das
Mn -Zehntel.
Also kleiner als M.
Und alle Elemente, die hier oben drüber liegen, sind kleiner als die
jeweiligen Mediane.
Das heißt, dass alle Elemente in B kleiner sind als M.
Und das heißt, dass S-Zweistrich, geschnitten B,
auch gleich leer ist.
So, das heißt, ich habe, egal ob ich jetzt in S-Strich oder S
-Zweistrich weitersuchen muss, eine Folge, die um mindestens die
Elemente, die in A liegen, oder mindestens die in B liegen, kleiner
geworden ist.
Und man sieht, das sieht hier so aus, naja, das sind etwa so ein
Viertel der Elemente.
Ja, das ist eine reine Visualisierung.
Das muss ich ja gar nicht machen.
Ich habe das nur so angeordnet, um darstellen zu können, also das, was
ich mache, ist nur das hier.
Ich habe meine Folge, ich habe die eingeteilt in so, also erstmal, ich
kann das auch so sagen, ich habe meine Folge ursprünglich, dann teile
ich die eben in so viele kleine Teilfolgen ein, der Länge 5, bestimme
dort jeweils hier das Medianelement und so weiter, dann wähle ich
daraus, dann kommt daraus das Element M und ich mache dann diesen
Schritt, dass ich jetzt bezüglich M die Partitionierung mache.
Und die Partitionierung, also ich brauche nichts anzuordnen.
Die Anordnung ist nur aufgrund der Visualisierung da, dass man sich
klar macht, was hat das für eine Bedeutung bezüglich der Größe der
Menge S' und S''.
Aber im Prinzip ist das nach wie vor Quick Select, das ist nur eine
schöne oder eine andere Art, wie ich dieses Pivot-Element aussuche.
So, da schauen wir uns jetzt nochmal genauer auf der, achso, jetzt
geht das Verfahren noch weiter.
Falls das S' gleich K ist, also die Anzahl der Elemente in S', wenn
das genau gleich K ist, das ist ja hier, S' ist ja gerade dieser Teil
bis M, dann weiß ich, dass M ist das K-größte Element.
Das ist praktisch genau wie bei Quick Select.
Wenn ich mehr Elemente habe als K, führe ich auf der Menge S', die
gleiche Suche nochmal durch und ich hätte auch das so machen können
wie bei dem Quick Select.
Da habe ich gesagt, ich ziehe erstmal das M noch ab aus dem S', ich
streiche das da raus und wenn ich dann kleiner als K bin in der Anzahl
der Elemente, dann weiß ich, dass das M auch das K-größte Element ist.
Aber ich kann es auch so machen.
Und andernfalls gehe ich auf die Menge S2' und suche dort das Element
K an der Position K minus Anzahl der Elemente von S'.
Das ist also genau wie bei Quick Select, nichts anderes.
Und das sind eben die beiden Mengen S', S2'.
Jetzt schauen wir uns an, wie man das jetzt weiter analysiert.
Also das sind nochmal die Eigenschaften.
Das A ist natürlich enthalten in S'.
Das sind alle Elemente in dem A hier in diesem Bereich, die sind alle
größer gleich M.
Alle Elemente, die hier drin sind, sind alle kleiner als M.
Und die beiden sind also jeweils nicht in der anderen Menge drin.
So, wie viele Elemente sind dort drin?
Zählen wir mal genau durch.
Ich habe doch in dem A dreimal in Zehntel Elemente drin.
Ich hatte ja fünf als Größe der Teilfolgen.
Also habe ich diesen jeweiligen Median plus die anderen beiden, die
größer gleich sind, die habe ich hier noch mit drin.
Also hat sowohl A als auch B drei Zehntel Elemente.
Bisschen mehr als ein Viertel.
Also 30% der Folge.
Also können in S' und S'', maximal sieben Zehntel der Elemente drin
sein.
Kann ja auch sein, dass es noch deutlich kleiner ist, aber es sind
maximal so viele Elemente drin.
Das geht natürlich nur so schön, wenn ich sage, das N ist ein
Vielfaches von 10.
Wenn es das nicht ist, dann muss ich es ein bisschen anders
abschätzen, kann ich immer noch zeigen, wenn es nicht ein Vielfaches
von 10 ist, dann sind hier meine Folgen nicht alle voll und dann
stimmt das nicht ganz.
Aber dann ist immer noch die Größe von A und B mindestens 3 Elftel N
groß.
Und entsprechend, wenn ich das abziehe, ist dann S' und S' maximal 8
Elftel N groß.
Also so etwa drei Viertel der Elemente, wie man ja im Bild sieht, sind
dann maximal in S' und S'.
Und es ist schon völlig klar, wenn ich in der Lage bin, ein Viertel
der Elemente rauszustreichen, dann habe ich, wenn ich das jetzt
rekursiv weitermachen kann, habe ich natürlich insgesamt, weil ich nur
eine Folge anschauen muss, ich verzweige nur auf eine weitere Folge,
habe ich dann auch im schlechtesten Fall ein lineares Verhalten.
Das ist also so anzunehmen, also da in jedem Rekursionsschritt die
Liste meinen festen Bruchteil kürzer wird, ist die zu erwartende
Rekursion eben so etwas, dass das T-Select von N, das ist das kleiner
gleich T-Select, auf einer Folge der Größe A mal N ist, wobei A
kleiner als 1 ist, das ist der wesentliche Punkt.
Und dann kommt noch was Lineares dazu, hoffen wir mal, dass das linear
ist.
Da war ja noch ein bisschen mehr, das bisschen mehr müssen wir gleich
noch anschauen.
Und wenn also hier das T-Select N, also 4N kleiner gleich 100, ist das
irgendeine Konstante.
Und wenn also das hier unsere Formel wäre schon, wären wir fertig.
Ein Punkt, den wir noch nicht wirklich nachgewiesen haben, ist, dass
wir hier tatsächlich mit linearer Zeit auskommen für den Teil.
Also für den Teil, den wir in den ersten Schritten machen, auf das
Suchen der Mediane dieser kleinen Teilfolgen plus den Medianbestimmen
dieser N-Fünftel-Mediane, das muss dann insgesamt linear sein.
Das ist aber auch wieder rekursiv.
Also da müssen wir ein bisschen aufpassen.
Das machen wir jetzt auf der nächsten Folie nochmal ein bisschen
genauer.
Das sind hier unsere Schritte.
Der erste Schritt war der Aufwand um, jetzt habe ich hier geschrieben,
Aufwand kleiner gleich a, auf der vorigen Folie stand Aufwand kleiner
gleich c, ist egal.
Also irgendeine Konstante ist unser Aufwand für Folgen, die klein
genug sind.
Der zweite Schritt, das Aufteilen der Folge in Teilfolgen der Länge 5,
ist überhaupt kein Aufwand.
Ich suche ja nur jeweils den Median dieser 5 Elemente, das kann ich
einmal durchrauschen.
Nein, ich suche noch nicht den Median.
Schritt 3 sucht den Median.
Ich habe also 9, oder man kann sich überlegen, wie man den Median in
der Folge von 5 Elementen bestimmt.
Das geht mit 9 Vergleichen und man kann sich leicht überlegen, wie man
das mittlere Element herausfinden kann.
Dann müssen wir 2 finden, die größer sind, 2 die kleiner sind und dann
haben Sie den Median.
Und wenn ich 9 Vergleiche pro 5 Elementen habe, habe ich also
insgesamt das n-Fünftel mal zu machen.
Und das heißt, das sind weniger als 2 n-Vergleiche.
Das ist also in linearer Zeit, das ist gar kein Problem.
Schritt 4 lasse ich jetzt nochmal draußen.
Schritt 5,
Schritt 5 war Partitionieren.
Das kennen wir von Quicksort und Quickselect, das sind die n-plus-1
-Vergleiche.
Der Schritt 4, der hier fehlt, das ist der rekursive Aufruf auf der
Menge der n-Fünftel Mediane.
Und dann haben wir noch den Schritt 6, das ist eigentlich nur diese
Abschätzung, wie viele Elemente habe ich in S-Strich und S-Zweistrich
drin.
Und Schritt 7 ist dann, also Schritt 6 war einfach nur festzustellen,
wenn ich genau k-Elemente habe, bin ich fertig.
Schritt 7 ist der Schritt, wo wir daran gehen, jetzt rekursiv auf der
Folge S-Strich oder S-Zweistrich weiterzumachen.
Ich gehe mal hier ganz durch.
Wieso taucht hier Schritt 4 nicht auf?
Okay, also, brauchen wir wahrscheinlich auch nicht.
Genau, das kommt jetzt hier unten, im Prinzip ist das hier drin.
Also, wie ist die Anzahl der Vergleiche, die ich machen muss?
Für n kleiner gleich 100 ist es kleiner gleich A, das haben wir so
gesagt.
Ansonsten habe ich hier 3n plus 1.
Warum?
Ich habe 2n plus n plus 1, das ist 3n plus 1.
Dann habe ich hier, das ist jetzt der Schritt Nummer 4.
Sag mal Schritt 4.
21n Hundertstel, das ist n Fünftel.
Das ist 21n, weil das nicht unbedingt aufgehen muss.
Muss kein Vierfaches von 5 sein, das Ganze.
So, und das ist also dieser rekursive Aufruf, um den Median zu
bestimmen.
Und dieses hier, das ist der Schritt 7.
Das ist unsere Rekursion für die Anzahl der Vergleiche, beim Suchen
des kartgrößten Elements in einer Folge von n Elementen.
Und wenn man sich das anschaut, also nur so über den Daumen, dieses
21n Hundertstel plus 8n Elftel, das ist insgesamt immer noch weniger
als n.
Um einen festen Bruchteil weniger als n.
Und trotz dieser zwei Aufrufe hier auf diesen kleinen Folgen, also
wenn die Summe dieser beiden Teilfolgen, die ich hier anschaue, wenn
die Länge insgesamt größer gleich n wäre, dann wäre ich beim gleichen
Problem wie vorher, da wäre ich nicht unbedingt linear, da könnte es
sein, dass ich ein bisschen Schwierigkeiten kriege, dass ich Richtung
n log n komme.
Aber im Prinzip kann man so über den Daumen kurz sagen, die
Gesamtlänge ist kleiner als n, festen Bruchteil kleiner als n.
Und daran liegt es, dass wir hier mit linearer Zeit auskommen.
Hier passen unsere typischen Rekurrenzgleichungen nicht, weil wir hier
zwei rekursive Aufrufe haben.
Deswegen muss man sich das hier genauer angucken.
Dieses genauere Angucken spare ich mir jetzt.
Aber ich muss zeigen, es gibt eine Konstante.
Also ich muss zeigen, dass es ein O von n ist.
Ich muss also zeigen, es gibt ab einer gewissen Größe von n, gibt es
eine Konstante, sodass der Aufwand für Vselect von n kleiner gleich
diese Konstante mal n ist.
Und das kann man nachweisen.
Da muss man einfach diese Rekursion ein bisschen auflösen.
Und dann bekommt man die Konstante, die ist allerdings relativ groß.
Die liegt so in der Größenordnung 40-50.
Das heißt, für die Praxis ist das zunächst mal nicht so sehr relevant,
denn ich könnte ja in Zeit n log n das grad größte Element bestimmen.
Und wenn die Konstante bei 40-50 liegt, da brauchen Sie schon sehr,
sehr große Folgen, damit Sie tatsächlich einen Vorteil haben gegenüber
dem üblichen Verfahren.
Trotzdem kann man versuchen sowas...
Das sind ja Abstelzungen im schlechtesten Fall.
Und man kann versuchen, das einfach mal zu implementieren und zu
sehen, wie weit das in der Praxis tatsächlich sich jetzt auswirkt.
Ja, noch eine Frage?
Ich mache ja hier nicht Quicksort, ich mache Quickselect.
Ja, aber das ist ja etwas...
Das ist aber genau das, was man hier eigentlich macht.
Man nimmt hier ja den Median so raus...
Ich suche ja nicht genau die Mitte raus für diese Aufteilung, sondern
ich suche mir ja...
Ich will nur gewährleisten, dass ich sage, ich kann mindestens diese
etwa ein Viertel Elemente rauswerfen.
Und damit bin ich ja schon relativ nahe dran.
Und ich habe hier insgesamt dadurch ein im schlechtesten Fall lineares
Verhalten.
Ich könnte auch daran gehen, dass bei dem...
Also jetzt dieses Verfahren einzusetzen bei Quicksort, ob sich das
lohnt, weiß ich nicht.
Da wird das wahrscheinlich greifen, was Herr Sanders da erzählt hat.
Aber bei Quickselect ist es so, dass wir eben wirklich im
schlechtesten Fall einen linearen Aufwand haben.
Und allgemein ist es eben so, wenn ich nur sortieren möchte, dann ist
eigentlich das Bottom-up Heapsort das schnellste Verfahren.
Okay, das Interessante ist aber, wenn Sie sich das hier nochmal
anschauen, unser Bild, also diese Aufteilung in so Teilfolgen, in
denen ich etwas mache, so jeweils diese Mediane bestimme, und dann den
Median daraus nehme, um weiterzuarbeiten, das riecht ganz stark nach
guten Parallelisierungsmöglichkeiten.
Das ist auch genau der Fall, dass man eben hier im Prinzip, wenn ich
so und so viele K-parallele Prozessoren habe, dann teile ich die Folge
einfach auf in K-Teilfolgen und bestimme dort jeweils auf diese Art
und Weise die Mediane und kann dann sehr schnell weitergehen.
Wir bekommen dadurch sehr gute Verfahren, um parallel den Median zu
bestimmen.
Ist völlig egal.
Muss nur irgendwie dafür sorgen, dass ich diese in Zehntel-Elemente
kriege.
Man hätte auch eine andere Konstante nehmen können.
Ich hätte auch sieben nehmen können.
Wäre auch möglich gewesen.
Der wesentliche Punkt ist, man erreicht damit, dass der schlechteste
Fall, der hier auftreten kann, immer noch gut genug ist, um nicht zu
einem quadratischen Verhalten zu führen.
Dadurch habe ich insgesamt das lineare Verhalten, das ich ja im Mittel
sowieso schon habe.
Also wahrscheinlich, wenn man sich mittleres Verhalten nur anschaut,
ist das einfache QuickSelect auch schon nicht schlecht, aber hiermit
kann man das eben noch verbessern.
Damit kommen wir jetzt zu Suchverfahren.
Wir haben das Sortierverfahren angeschaut.
Wir haben Medianbestimmung gemacht, also eine Rangposition
festzustellen.
Jetzt schauen wir ohne Rangposition einfach nur nach irgendwelchen
Elementen aus der Menge.
Ich nehme an, dass die Elemente alle verschieden sind.
Aber das muss nicht unbedingt sein.
Wir wissen, man kann die durchaus unterscheiden, wenn man will.
Aber hier werden wir Beispiele haben, wo wir auch gleiche Elemente
haben.
Wenn ich Suchverfahren betrachte, auch eine klassische Anwendung oder
klassische Aufgabe in der Informationsverarbeitung, dann will ich
wissen, ist ein bestimmtes Element in der Menge?
Es kann sein, dass ich nach dem Element suche.
Das ist ein Unterschied.
Das eine ist, ist die Menge drin?
Also ist ein Schlagwort tatsächlich in einem Dictionary drin?
Oder bei Search sage ich, ich möchte gerne den Eintrag haben, der zu
diesem A gehört.
Da möchte ich wirklich mehr haben, möchte ich das Element auch
wirklich haben.
Dann haben wir Insert und Delete, das ist klar.
Ich muss Elemente einfügen können oder auch löschen können.
Und das, was eben hier üblicherweise dahinter steckt, das sind nicht
einfach nur Folgen von einzelnen Zahlen, sondern in der Regel habe ich
hier irgendwelche Objekte mit irgendeinem speziellen Schlüsselfeld,
irgendeinem Suchschlüssel, nach dem ich suche oder wie das Ganze
angeordnet ist.
Und das kann man als Lexikon auffassen, als Dictionary oder irgendeine
große Datenmenge.
Und ich suche da drin jetzt irgendwelche speziellen Elemente.
Also das sind hier die üblichen Lexikon-Operationen, so nennt man die.
Und wie gesagt, manchmal gibt es noch diese Operation Xmin, dass man
sagt, ich möchte das minimale Element raushaben.
Oder ich habe die Aufgabe, ich möchte das nächstliegende Element
haben.
Wobei der Schlüssel, nachdem ich suche, also das Element, das ich
ausgebe, hat den geringsten Abstand von diesem Schlüssel A, der hier
angegeben ist.
Gut, Suchverfahren kennen Sie zum Teil, nehme ich an.
Es gibt einfache Sachen, lineare Suche.
Ich habe hier meine Folge und gehe einfach von links nach rechts
durch.
Die muss ja nicht geordnet sein.
Das ist irgendeine Folge von Elementen.
Da habe ich keine andere Chance zunächst mal, als wenn das
irgendwelche Elemente sind.
Da muss ich halt von links nach rechts durchlaufen.
Wenn ich die sortiert angeordnet habe, dann kann ich halt meine
übliche binäre Suche machen.
Ich kann erst mal das mittlere Element anschauen und dann kann ich
verzweigen nach links oder nach rechts und dann entsprechend wieder an
der mittleren Position so weitermachen.
Das ist die übliche binäre Suche, die Sie von den ersten Semestern aus
der Schule kennen.
Entsprechend ergeben sich binäre Suchbäume, auch ganz einfach.
Und dann kann man auch eine interpolierende Suche machen, dass ich mir
die Größe anschaue und sage, wenn ich nach einem großen Element suche,
ich weiß, da sind Zahlen in einem bestimmten Bereich drin, dann kann
ich die Kenntnis über die Größe des suchenden Elementes ausnutzen, um
in einen vielversprechenden Bereich meiner Folge hineinzugehen und
dort konkret zu suchen.
Da muss ich aber mehr wissen, als nur, das Element ist dort drin oder
nicht.
Es gibt Standardbäume dafür, das muss ich mal schauen, das habe ich
jetzt dummerweise nicht.
Da wollte ich eigentlich noch kontrollieren, ob diese App noch
funktioniert.
Das ist falsch, ich muss hier rauf gehen.
Feiloptionen, das wollte ich eigentlich mittlerweile wissen.
AVL-Bäume, AVL-Bäume heißen so nach Adelson, Velsky und Landis.
Funktioniert noch, sehr schön, das ist ein AVL-Baum.
Was ist hier das Wesentliche?
Das ist ein höhenbalancierter Baum.
Höhenbalanciert heißt, es sind alle Pfade von der Wurzel zu den
Blättern maximal um 1 unterschiedlich in ihrer Länge.
Wir können hier zum Beispiel, wenn ich jetzt hier sage, ich füge jetzt
ein neues Element zu, nehmen wir mal hier das Element 51 und ich sage,
ich füge das hinzu, dann sehen Sie, das kommt jetzt da hin, das passt
da noch rein.
Das ist jetzt darunter gelaufen, man kann also einfügen, indem man
hier einfach sukzessive verzweigt und beim Suchbaum habe ich halt die
Eigenschaft, wenn ich an einer Wurzel, an einem Knoten bin, vergleiche
ich das Element, das eingefügt werden muss, mit diesem Element und
wenn es kleiner ist, gehe ich nach links, wenn es größer ist, gehe ich
nach rechts.
Auf die Art und Weise habe ich halt hier das alles schön eingefügt.
Jetzt mache ich mal folgendes, ich lösche mal die 7.
Schauen wir, was dann passiert.
Dann geht er hier runter, findet die 7, löscht die 7, geht wieder
zurück und stellt fest, hier war es nicht mehr höhenbalanciert.
Und jetzt müssen wir ein bisschen mehr machen, jetzt muss die Höhe
wieder ausbalanciert werden.
Es war auf einmal der rechte Teilbaum um 2 höher als der linke
Teilbaum.
Das hat man, wie Sie sehen hier, einfach wieder so ausgeglichen.
Wir haben jetzt wieder eine Situation, wo mehr gemacht wird.
Und ich sage, auch der Aufwand, den wir gerade gesehen haben, ist
nicht größer als konstante mal Pfadlänge in dem Baum.
Und da die Pfadlängen sich maximal um 1 unterscheiden, ich habe einen
binären Baum, habe ich hier Log N bei N Elementen als Pfadlänge.
Das heißt, ich habe einen Aufwand von Log N maximal.
Für das Einfügen war es klar, wenn wir nicht umordnen müssen.
Aber auch dieses Umordnen geht sehr schnell.
Wir können den Aufwand insgesamt auf Log N reduzieren.
Das ist ein wichtiger Punkt, dass wir Aufwand Log N haben.
Geht zurück zur Vorlesung oder zur Folie.
Also können Sie gerne selbst mit rumspielen.
Es gibt auch...
Habe ich hier auch eine App?
Das war mir gar nicht klar.
Muss ich mal kurz reingucken.
Das müsste eigentlich auch sein.
Da habe ich nichts.
Da habe ich keine App.
B-Bäume, da gehen wir gleich nochmal selbst drauf ein.
Das ist externes Suchen.
Das hat eigentlich mehr Anwendungen im Bereich Datenbankanwendungen.
Und wir machen jetzt genauer die 2-3-4-Bäume und die Rot-Schwarz
-Bäume.
2 -3-4-Bäume sind sowas ähnliches wie B-Bäume.
B steht hier für Bayer.
Das ist ein Professor von der TU München, ein früherer.
Und der hat diese B-Bäume sich ausgedacht, wo also die Knoten sehr
dick sind.
Und die Idee da ist, dass man in den Knoten jeweils dort so viele
Elemente drin hat, wie etwa auf eine Seite im Speicher passen.
Oder halbe Seitengröße normalerweise.
Oder Blockgröße in so einem B-Baum.
Ich will jetzt Ihnen in weiteren die 2-3-4-Bäume vorstellen.
Auch da kann man in die Applets reingehen.
Auch da haben wir... kann ich ja dann doch mal kurz machen.
Ich hoffe, dass das auch funktioniert.
Okay, da muss ich irgendwas machen, das habe ich nicht vorbereitet.
Schauen Sie sich das selber an.
Ich mache das auf jeden Fall jetzt an Beispielen hier auf den Folien.
Fangen wir also an mit, nochmal ganz kurz, binärer Suchbaum.
Ist also einfach ein binärer Baum, bei dem ich sicherstelle, dass
jeder Knoten zwei Nachfolger hat oder keinen.
Kein Nachfolger heißt, ich habe ein Blatt.
Wenn ich keinen Vorgänger habe, ist es eine Wurzel.
Die anderen sind innere Knoten.
Und das Wesentliche ist also der binäre Suchbaum.
Bei dem enthalten alle inneren Knoten einen Schlüssel.
Das ist keineswegs immer so.
Da gibt es auch Varianten, bei denen die Schlüssel nur in den Blättern
hängen und die anderen nur Navigationsknoten sind.
Die Schlüssel im linken Unterbaum sind kleiner, alle im rechten
Unterbaum sind größer oder gleich dem Schlüssel im Knoten.
Also wenn sie alle verschieden sind, sind sie dann entsprechend alle
größer.
Das ist einfach genau das, was man macht, wenn man eine binäre Suche
macht.
Ich gehe auf das mittlere Element in einer Folge, wenn die schön
angeordnet ist, das mittlere Element, die sieben, und dann gehe ich
entweder nach links oder rechts, da auch wieder das mittlere Element
und kann so schön durchsuchen und ich brauche maximal Log-N
-Vergleiche, wenn ich hier suchen möchte.
Das ist also hier sofort offensichtlich.
In den Blättern sind keine Elemente.
Die hängen dann nur so unten dran.
Das Problem ist natürlich, wenn ich so einen Suchbaum habe, ich habe
hier gesagt, naja, Log-N-Vergleiche, aber wenn ich diesen Baum hier
anschaue, der ist auch ein binärer Suchbaum, der erfüllt die
Eigenschaften, die hier stehen, alle Elemente links und rechts haben
genau die Eigenschaften, die wir hier postuliert haben, aber hier hat
man vielleicht die Elemente A, B, C und D in der Reihenfolge eingefügt
und keine Umordnung gemacht, sodass hier jeweils das größere Element
nach rechts gewandert ist und dann habe ich einen linearen Baum.
Sehr ungünstig, wenn wir dort suchen, machen wir im Prinzip eine
sequentielle Suche, haben lineares Verhalten.
Das wollen wir also nicht.
Da hätten wir einen linearen Suchaufwand, den wir natürlich vermeiden
wollen, wir wollen einen logarithmischen Suchaufwand haben.
Das eine sind die höhenbalancierten Bäume, das sind genau diese AVL
-Bäume, die Sie vielleicht aus Grundvorlesungen kennen.
Das habe ich gerade eben auf der Animation schon gezeigt gehabt.
Der andere Ausweg hier sind also leicht abgewandelte Bäume, bei denen
ich keine Verzweigung mehr von 2 habe, keinen binären Baum, sondern
einen 2-3-4-Baum.
Das heißt, ich habe nicht nur 2 Nachfolger, sondern ich habe 2, 3 oder
4 Bäume.
Es gibt übrigens eine Vielfalt von Varianten von Suchbäumen, nicht nur
diese höhenbalancierten, es gibt auch andere, es gibt auch sogenannte
Bruderbäume und es gibt zig verschiedene Varianten.
Ich beschränke mich jetzt hier auf die 2-3-4-Bäume zunächst mal und
nachher kommt dann als eine Implementierungsvariante die Rot-Schwarz
-Bäume dazu, die eigentlich die effizienteste Datenstruktur sind für
Suchen.
Es gibt noch andere, es gibt noch ein bisschen welche mit
randomisierten Eigenschaften drin, Splash-Trees und solche Dinge, auf
die ich aber hier jetzt auch nicht eingehe, das würde ich jetzt zu
weit führen.
So, also 2-3-4-Bäume.
Ich sagte, wir haben bis zu 4 Nachfolger.
Ein Blatt hat natürlich keinen Nachfolger, das ist klar.
Und dann kann es sein, dass hier in den Knoten ein Schlüssel drin ist,
oder ein 1-Knoten.
Da haben wir alle 0 bis 3 Schlüssel dort jeweils drin, hier
angedeutet, S1 bis SK.
Und ich habe natürlich immer gerade K plus 1 Nachfolger, es sei denn,
das sind Blätter.
Da habe ich auch 0 Knoten, 0 Schlüssel drin.
Und ich muss ja jeweils nach links und rechts verzweigen können, je
nachdem ob ein Element, das ich suche, kleiner oder größer als der
jeweilige Schlüssel ist.
Und ich suche, gehe eben hier, wenn ich ein Element hier einfügen
möchte, so weit durch, bis ich eben irgendwann die Position gefunden
habe, wo ich runterlaufen muss.
Das heißt, die Position zwischen zwei Schlüsseln ist dann die
Verzweigung, die da gewählt wird.
Zunächst mal, ich nehme an, dass die Schlüssel da drin geordnet sind,
sonst macht das Durchlaufen von links nach rechts keinen Sinn.
Und für die Unterbäume ist es eben so, dass die genau die
Eigenschaften haben, wie vorher bei dem binären Suchbaum.
Also alle Schlüssel in diesem Teilbaum T1 sind kleiner als S1.
Und dann für alle anderen Schlüssel sind die in Ti größer gleich Si-1
und kleiner als Si.
Und dieser Tk-plus-1 hier, da sind alle Schlüssel drin, die größer
gleich dem Schlüssel Sk sind.
Und alle Unterbäume haben die gleiche Höhe.
Das ist auch eine wichtige Eigenschaft.
Das hatten wir bei den AVL-Bäumen nicht, da hatten wir nur
Höhenbalanciert gesagt.
Das heißt, die haben eine Höhe, die sich um maximal 1 unterscheidet.
Hier sagen wir, alle Pfade in diesem Baum haben die gleiche Länge.
Wenn das so ist, wenn die alle die gleiche Länge haben, dann ist der
Suchaufwand, also wenn ich mir anschaue, die Anzahl der Elemente, die
drin sein können, ich muss ja nur die Pfade durchlaufen von oben nach
unten, dann ist der Suchaufwand naheliegend kleiner gleich log n, weil
die Pfadlänge, selbst wenn das immer zwei Nachfolger sind, ist die ja
maximal log n.
So, und jetzt schauen wir uns an, wie wir solche Bäume aufbauen
können.
Wir haben einen ganz einfachen Baum mit einem Element.
Wir wollen ein Element A einfügen.
Ich mache einfach eine Reihe von Beispielen, füge Ihnen vor, wie man
hier Elemente einfügen kann.
Also, das A wird eingefügt, ich habe im Knoten da der eine Schlüssel
drin, packe ich einfach den zweiten Schlüssel dazu.
Und dann habe ich halt ein weiteres Blatt da unten dranhängen.
Wenn ich da schon zwei Elemente drin habe, packe ich das A an die
richtige Position in den Knoten und dann habe ich vier Nachfolger.
Und jetzt wird es kompliziert.
Jetzt habe ich ja die Situation, dass ich ein Element A einfügen will.
Und wir nehmen mal an, wir sind irgendwo in dem Baum schon drin.
Wir sind also hier an dem X vorbeigelaufen, meinetwegen hier an diesen
Teilbaum hinein.
Das heißt, das X ist kleiner als B, C und D.
Und wir haben hier also dort B, C und D drin.
Wenn wir jetzt das A einfügen, ich tue mal so, als würden wir das A
einfügen, dann würde ja ein Knoten entstehen, bei dem ich jetzt, wenn
das A kleiner gleich B ist, A, B, C, D hier stehen hätte in dem
Knoten.
Das sind vier Schlüssel, der Knoten wird zu groß, der muss verkleinert
werden.
Das heißt, jetzt ziehe ich das dritte Element nach oben.
Das ist der Median.
Ziehe einfach den Median dieser Folge nach oben, das ist das C.
Und damit, wenn ich das nach oben ziehe, in den Knoten oben drüber,
habe ich dort jetzt einen Schlüssel mehr.
Hoffen wir mal, dass das auch geht, dass da genügend Platz ist.
Wenn nicht, müsste ich noch weiter nach oben laufen.
Wenn dort Platz genug ist, packe ich das C da rein.
Dann habe ich jetzt einen Knoten, in dem das A und B drin ist.
Und ich habe einen Knoten, in dem das D drin ist.
Und das sind gerade die neuen zwei Teilbäume, die aus dem Knoten oben
drüber verzweigen.
Entsprechend, wenn das in einer anderen Reihenfolge ist, ich nehme
also immer den Median da raus, also hier wäre es eine Reihenfolge,
dass das A größer als B, C und D ist.
Dann müsste ich halt das D rausnehmen, das A würde rechts wandern.
Das sind einfach nur einfache Beispiele.
So könnte man das machen.
Und jetzt habe ich hier noch, ich komme gleich noch mal darauf zurück,
hier mit dem Knoten oben drüber.
Wenn ich jetzt diese Situation hätte, ich habe einen Baum, bei dem ich
in der Wurzel bereits drei Schlüssel drin habe, und ich füge ein A
dazu.
Dann geht auch hier das Median nach oben, nach oben ist aber gar
nichts.
Das heißt, ich füge einen neuen Wurzel dazu.
Und dann habe ich hier diese beiden Knoten mit A, B und D drin.
Das heißt, ich habe natürlich auch wieder gleiche Pfadlängen.
Links und rechts habe ich gleiche Pfadlängen.
Die Pfadlängen an den anderen Situationen haben sich nicht verändert.
Das heißt, die Eigenschaft, dass ich gleiche Pfadlängen habe, die ist
durch diese Einfügeoperation nicht modifiziert worden.
Also es geht immer der Median nach oben.
Situation drei und vier habe ich nicht zu Ende angeschaut.
Kann man aber leicht im Prinzip genauso wieder machen.
Da geht der Median nach oben, der muss in den Knoten oben drüber
eingefügt werden.
Und auch dort ist es so, wenn ich dadurch einen zu großen Knoten
bekomme, muss entsprechend wieder der Median der vier Schlüssel nach
oben wandern in die nächste Ebene.
Irgendwann komme ich dann hier zu dem Wurzelknoten.
Und wenn auch der zu voll ist, dann muss ich eben eine neue Wurzel
erzeugen.
Dann verändert sich die Pfadlänge im gesamten Baum um eins.
Also das ist etwas, was man hier sehr einfach machen kann.
Solange ich also immer noch etwas einfügen kann nach unten, mache ich
das auf diese Art und Weise.
Wenn ich etwas nach oben schieben muss, muss ich nochmal zurücklaufen
nach oben.
Aber der Aufwand hält sich ja auch in Grenzen.
Ich muss ja nur den Pfad einmal, also wenn ich hier meinen gesamten
Baum habe, laufe ich einmal runter bis zu einer Position, wo ich halt
einfügen kann.
Und wenn ich da eben dann wieder zurücklaufen muss, dann ist aber die
Anzahl der Knoten, die ich besuche, kleiner als Log N.
Das heißt, ich habe hier insgesamt logarithmischen Aufwand.
Ich kann jetzt das mit diesen vier Knoten, was ich gerade gesagt
hatte, ein bisschen reduzieren, das Problem.
Ich möchte nicht gerne wieder nach oben zurücklaufen, ich möchte nur
noch runterlaufen beim Einfügen.
Man kann das so machen, dass man sagt, ich schaue mir beim Durchlaufen
durch meinen Baum die Knoten genauer an.
Wenn ich also jetzt an einem Vierknoten vorbeikomme, der bereits drei
Schlüssel hat, dann weiß ich, wenn ich dort etwas einfügen muss, dann
kann die Situation auftreten, dass ich eben eventuell wieder den
ganzen Weg nach oben zurücklaufen muss.
Das möchte ich nicht.
Deswegen sage ich, der ist schon relativ groß.
Wenn ich jetzt dabei bin, etwas einzufügen, möchte ich vermeiden, dass
ich wieder nach oben laufen muss.
Das heißt, ich muss dafür sorgen, dass oben drüber genügend Platz ist,
wenn ich an der Position angelangt bin, zu der mein Schlüssel gehört.
Also dann tritt Situation drei oder vier auf von der vorigen Folie.
Deswegen verändere ich einfach beim Durchlaufen diesen Knoten hier in
diese drei Knoten.
Und habe dadurch also zwei Knoten draus gemacht aus diesem einen
Vierknoten.
Dadurch verändert sich natürlich hier in diesem Beispiel die Größe
oder die Höhe des Baumes, weil ich eine neue Wurzel dazufüge.
Wenn ich das beim Durchlaufen mache, auf diese Art und Weise, ich bin
also jetzt mitten im Baum, was war bei der Wurzel?
Wenn ich jetzt mitten im Baum bin und habe einen solchen Knoten
erwischt, dann teile ich ihn auch auf, schiebe den mittleren Knoten
nach oben, also das B kommt nach oben.
Und da ich ja beim Durchlaufen dafür gesorgt habe, dass oben nur
kleine Knoten sind, kann ich diesen mittleren Knoten problemlos nach
oben schieben.
Dadurch entsteht maximal ein Dreiknoten, bei dem ich also drei
Nachfolger habe.
Und das heißt, oben drüber ist garantiert Platz.
Ich muss garantiert nicht wieder nach oben durchlaufen, wenn ich die
Einfügeposition für das zu einzufügende Element gefunden habe.
Und entsprechend andere Situation, wenn ich also hier irgendwo bin,
das B füge ich nach oben.
Das ist nur leicht anders aufgezeichnet, aber eigentlich kein großes
Problem.
Und hier nochmal irgendwo in der Mitte, das ist einfach keine große
Tat, sich die Situation hier aufzumalen.
Gibt es eine Frage da hinten?
Sie dürfen gerne Fragen stellen, Sie wissen, dass ich das eigentlich
liebe, wenn Fragen gestellt werden.
Okay, oder ist das zu einfach?
Eigenschaften.
Das, was wir gerade gemacht haben, nennen wir Top-Down-Teilen.
Das heißt, da entstehen jeweils zwei neue Zweiknoten und höchstens ein
neuer Vierknoten.
Warum ein neuer Vierknoten?
Weil es sein kann, dass oben drüber ein Dreiknoten war, den ich nicht
aufgeteilt habe.
Dadurch, dass ich jetzt einen Vierknoten aufteile, geht der mittlere
Knoten nach oben, dann kann oben drüber ein neuer Vierknoten
entstehen.
Aber ich habe eben da unten drunter dann auf jeden Fall Knoten, die
zwei oder drei Knoten sind.
Und diese Suche endet an einem neuen Zweiknoten oder einem alten Zwei-
oder Dreiknoten.
Und dann kann ich dort problemlos einfügen, ohne nochmal neu aufteilen
zu müssen.
Das heißt, dann bin ich fertig.
Jetzt könnte man sagen, ich mache jetzt noch einen extra Aufwand.
Vorher bin ich durchgelaufen von oben nach unten an die richtige
Position, habe dort eingefügt und musste dann eventuell nach oben
laufen.
Jetzt laufe ich von oben nach unten durch und mache an jeder Stelle,
wo ich einen Vierknoten finde, gleich diese Operation.
Das ist ja eigentlich kein Gewinn.
Aber es ist tatsächlich so...
Es ist so, dass dieses Top-Down-Teilen dazu führt, dass auf diesem
Faden von oben nach unten am Ende maximal ein Vierknoten ist.
Und das heißt, dass ich eigentlich einen relativ geringen Aufwand
habe, das zu machen.
Und es zeigt sich, dass das im Schnitt effizienter ist, als wenn man
das ohne Top-Down-Teilen macht.
Jetzt habe ich hier ein kurzes Beispiel.
Wir gehen aus von einem leeren 2-3-4-Baum und bauen daraus einen
vollständigen 2-3-4-Baum, wo wir mal davon ausgehen, dass das alles
hier Buchstaben sind, die irgendwie eingefügt werden sollen.
Und dann gehe ich also los mit dem...
Hier steht nur das E, dann habe ich hier nur zwei Blätter, dann kommt
das I dazu, dann kommt das N dazu und dann muss ich entsprechend
aufteilen.
Und dann ergibt sich durch diese Operation, die ich angegeben habe, am
Ende dann genau dieser Baum hier.
Und wenn wir das mit einem binären Suchbaum machen würden, dann würde
der so aussehen.
Ich muss ja nicht abbrechen, ich suche ja keine Viererknoten, sondern
ich suche die Position für das einzufügende Element.
Das heißt nur, der Aufwand, den ich habe, der ist eben nicht groß.
Ich habe nur das maximal einmal zu machen und ansonsten kann ich da
einfach so durchlaufen.
Dadurch reduziere ich also die Anzahl der Einfügeoperationen, die ich
machen muss.
Ich erkaufe mir das dadurch, dass der Baum nicht ganz so eng gepackt
ist, das heißt die Pfadlänge ist etwas größer, als wenn ich die
kompakt gelassen hätte, dann hätte ich eventuell mehrere dicke Knoten
auf so einem Pfad und müsste dann von unten nach oben beim Einfügen
wieder nach oben laufen, das würde dann den Aufwand dort erhöhen.
Aber es zeigt sich, dass das insgesamt dann doch ein Gewinn ist.
Also die Eigenschaften sind eben, dass die die gleiche Länge kleiner
gleicht Log N haben, das ist klar.
Ich muss maximal Log N vier Knoten teilen.
Wenn man stets Top-Down-Teilen anwendet, ist es im Mittel weniger als
einer.
Und das ist halt dann wichtig und das hatten wir gerade eben
diskutiert.
Also insofern habe ich hier eine Struktur, bei der ich einen Baum habe
mit gleichen Pfadlängen, Einfügeaufwand kleiner gleicht Log N,
Suchaufwand natürlich auch.
Frage, wie löscht man in diesem Fall?
Das ist natürlich ganz symmetrisch.
Schauen wir uns das doch nochmal genauer an.
Wir haben einen 2-3-4-Baum und wollen in dem ein Element löschen.
Dann kann es sein, dass dieses Element gar nicht drin ist.
Also ich möchte das erste Element A aus dem 2-3-4-Baum löschen.
Das Ergebnis muss wieder ein 2-3-4-Baum sein.
Wenn das gar nicht drin ist, das A in dem S, dann läuft die Suche nach
unten durch, stellt fest, ich bin am Blatt angekommen.
Wenn ich am Blatt angekommen bin, dann heißt das, das Element war
nicht drin.
Ich brauche gar nichts zu löschen.
Dann bin ich fertig.
Wenn es drin ist, dann habe ich so eine Situation.
Dann habe ich ein Knoten A.
Bei diesem Knoten ist Element A drin in irgendeiner Position.
Also in zwei, drei oder vier Knoten.
Und das A muss ich löschen.
Wenn ich das lösche, muss ich den Baum natürlich etwas umbauen.
Jetzt geht natürlich nach links und nach rechts von diesem A ein
Teilbaum raus.
Und der rechte Teilbaum, der hat irgendwo ein Element B.
Das ist das kleinste Element in dem Teilbaum, der ja nur Elemente
enthält, die größer gleich A sind.
Also ist das B größer gleich A.
Und alle Elemente in dem Teilbaum, da ist noch ein weiteres Element,
C, dann sind alle Elemente da drin kleiner als das C.
Das heißt, ich brauche ja nur, das A von hier rauszunehmen und dort
hinzuschieben.
Ich habe hier schon wieder diesen komischen Strich.
Also das B wird da oben hingeschoben.
Aber dann verschwindet das B natürlich da unten.
Und dann kann da auf einmal meine Struktur durcheinander kommen.
Jetzt müssen wir uns anschauen, was passiert.
Das B ist unten in irgendeinem 2, 3 oder 4 Knoten drin.
Wenn es in einem 3 oder 4 Knoten drin ist, ist es gar kein Problem.
Dann sind ja noch mehr Schlüssel dort drin.
Mindestens ein weiteres ist dann vorhanden.
Dann brauche ich nur das B da rauszunehmen.
Das B ist ganz links, ich brauche also nur das eine Blatt hier zu
streichen.
Und die restlichen Schlüssel bilden immer noch einen vollständigen
Knoten.
Ich bin fertig.
Das Problem ist, wenn dieses ein Zweiknoten ist.
Dann war das der einzige Schlüssel.
Und das muss ich dafür sorgen, dass...
Also ich kann jetzt nicht einfach hier ein Blatt da oben ranhängen.
Also wenn ich sagen würde, okay, das wird einfach reduziert.
Ich hänge da jetzt ein Blatt ran, das geht ja nicht, weil ich dann
unterschiedliche Pfadlängen hätte.
Das darf ich nicht machen.
Also das geht nicht.
Ich muss also dafür sorgen, dass ich wieder gleiche Pfadlängen habe.
Und das heißt, da dieser Teilbaum der Höhe 1 jetzt wegfällt, muss ich
mir anschauen, was ist rechts daneben und was ist oben drüber.
Also oben drüber ist ein C.
Das B war also kleiner als das C.
Und dann geht von hier aus ein Teilbaum runter.
Das D ist hier das nächstgrößere Element.
Und dann schiebe ich einfach das um 1 rum.
Das heißt, das C kommt nach unten, das D wird nach oben geholt.
Und dann habe ich hier noch irgendein E stehen.
Also irgendwelche weiteren.
Könnte natürlich sein, dass hier neben auch nur ein Element ist.
Wenn das D das einzige gewesen wäre, dann hätte ich hier jetzt auch zu
wenig gehabt.
Dann müsste ich also noch weiter laufen, also die weiteren hier noch
durchlaufen, bis ich, das sind ja maximal noch drei weitere, muss ich
dann durchlaufen, um dafür zu sorgen, dass das richtige Element nach
oben wandert.
Und wenn da eben nur zwei Knoten dran waren, dann ist halt einfach ein
Knoten da unten weggefallen.
Und dann habe ich hier das dann oben entsprechend, also insgesamt habe
ich dann das aber auch richtig behandelt.
Es muss ja mindestens hier, ich habe hier auf jeden Fall mindestens
diese zwei Elemente.
Wenn ich jetzt da hier von oben ein Element wegnehme, kann es sein,
dass ich hier jetzt insgesamt noch weiter nach oben laufen muss.
Dieses Verfahren ist ein bisschen aufwendiger als das Löschen in den
anderen Bäumen, aber es geht auch mit einem Aufwand, der logarithmisch
ist insgesamt, also im Schnitt konstanter Aufwand pro Knoten auf dem
Pfad.
Also zunächst mal hier runterlaufen, das A finden, dann durch B
ersetzen und dafür sorgen, dass ich jetzt hier insgesamt meine
Struktur beibehalte, die Eigenschaften beibehalte, indem ich eben
richtig die Schlüssel rumschiebe.
Gut, das ist hier nochmal, genau, das war noch eine Situation, wenn
der rechte hier eben auch ein, genau, das ist der Fall, dass ich jetzt
rechts auch nur zwei Knoten habe, dann würde ich C und D
zusammennehmen und ich lösche das C praktisch hier oben raus, in der
nächsten Ebene.
Dadurch, dass ich das C jetzt in der nächsten Ebene hier oben
rauslösche, muss ich hier oben im Prinzip die gleiche Operation
nochmal machen, oben drüber und dort Knoten oder Schlüssel rumschieben
und das kann dann wieder bis nach oben durchwandern, das kann ich
nicht vermeiden.
Das ist das, was ich gerade eben schon angedeutet habe.
Entsprechend macht man halt weiter auf den nächsten höheren Ebenen und
wenn ich bis nach oben gelaufen bin, kann es sein, dass dadurch die
Wurzel gelöscht wird und dann bin ich fertig, habe also dann die
gesamte Höhe des Baumes um eins reduziert.
Das ist also das, was beim Löschen passiert.
Da muss man eben ein bisschen durchlaufen.
Also der schlechteste Fall ist, dass ich nur zwei Knoten habe auf dem
Weg von B, von diesem Element, durch das ich das A ersetzt habe, von
dort bis zur Wurzel, wenn dort nur zwei Knoten liegen und auch jeweils
rechte oder linke Nachbarn jeweils zwei Knoten nur sind, dann endet
das Ersetzen in der Wurzel und dann verringert sich die Höhe des
Baumes entsprechend.
Okay, das ist also hier dieser Punkt, wenn das hier oben die Wurzel
wäre, würde ich das da rausnehmen und wenn das auch nur zwei Knoten
ist, wäre der Knoten dann weg.
Aufwand insgesamt bleibt weiterhin bei Log N, also nicht so schlimm.
Und damit haben wir eine Struktur, bei der wir einfügen und löschen
können mit Aufwand Log N.
Das Suchen ist sowieso ein Aufwand Log N.
Die anderen Operationen ist klar, kann man auch jeweils über die
Suchoperationen hinbekommen.
Das geht also relativ schnell.
Jetzt ist die Frage, wie implementiert man das?
Ich habe jetzt drei verschiedene Knoten plus Blatt, also das ist etwas
aufwendigere Datenstruktur.
Drei unterschiedliche Knotentypen, abgesehen von dem Blatt.
Das Teilen der vier Knoten sah relativ aufwendig aus.
Das heißt, dieser Vorteil der zwei, drei, vier Bäume, dass ich so eine
ganz klare Struktur habe, mit gleichen Fahrtlängen, der geht bei einer
direkten Implementierung so ein bisschen verloren, weil ich aufwendige
Datenstrukturen und Operationen habe.
Also die sind zwar asymptotisch alle in der schönen Log N, aber
trotzdem die Konstante, die ist relativ hoch hier.
Und jetzt ist die Idee, dass man eine sehr viel einfachere
Datenstruktur nimmt.
Und zwar eine Datenstruktur, die man Rot-Schwarz-Bäume nennt.
Und die Idee hier ist, ich stelle einfach einen zwei, drei, vier Baum
dar, durch binäre Bäume mit roten und schwarzen Kanten.
Und die roten Kanten sind Kanten, die ich praktisch nicht zähle.
Das sind im Prinzip Kanten innerhalb eines zwei, drei, vier Knotens.
Und die schwarzen Kanten sind die Kanten, die ich auch im zwei, drei,
vier Baum hätte.
Also wenn ich einen einfachen Zweiknoten habe, da ändert sich gar
nichts.
Wenn ich einen Dreiknoten habe, zwei Schlüssel da drin, dann habe ich
also immer noch hier meinen Knoten.
Ich verändere einfach diesen Knoten mit zwei Schlüsseln in zwei binäre
Knoten, die jeweils Schlüssel A oder B enthalten, sodass die bezüglich
der üblichen Suchbaumstruktur richtig angeordnet sind.
Aber die Kante dazwischen, die färbe ich rot.
Jetzt könnte man sagen, das muss ich also rote und schwarze Kanten
auch noch abspeichern.
Ich kann es aber so machen, dass ich sage, naja, ein Knoten ist rot,
der bekommt einfach nur ein Bit dazu.
Und dieses Bit sagt einfach nur, geht dort eine rote oder schwarze
Kante rein.
Wenn eine rote Kante reingeht, ist das ein Knoten, der eigentlich
innerhalb so eines Drei- oder Vierknotens wäre.
Und wenn eine schwarze Kante reingeht, wäre das auch eine Kante, die
in einem 2-3-4 Baum ist.
Also ich brauche nur ein Bit, um zu unterscheiden, ist das ein Knoten,
auf dem eine rote Kante zeigt, oder ein Knoten, auf dem eine schwarze
Kante zeigt.
Und wie man sieht, habe ich hier zwei verschiedene Möglichkeiten, das
zu machen.
Ich kann das nach links oder nach rechts so runterhängen lassen.
Wenn ich einen Vierknoten habe, ist der ganz einfach zu einem binären
Baum zu machen.
Das war genau das, was wir bei den Top-Down-Teilen gemacht haben, da
haben wir die Vierknoten aufgeteilt.
Aber hier sind jetzt die beiden inneren Kanten, die sind halt rot.
Das heißt, ich habe jetzt zwei rote Knoten, einen schwarzen Knoten.
Die bauen insgesamt jetzt meinen Vierknoten in der Implementierung.
Und damit habe ich jetzt also einen binären Suchbaum, den ich sehr
einfach darstellen kann.
Ich habe einfach nur bei der üblichen Darstellung eines binären
Suchbaums jetzt dazu zu fügen, die Unterscheidung, ist das ein roter
oder schwarzer Knoten.
Beziehungsweise geht eine rote oder schwarze Kante rein.
Das heißt, der Darstellungsaufwand ist hier wirklich sehr gering.
Die Frage ist, wie kann ich jetzt die Operationen ausführen?
Und Sie sehen schon an diesem einen Bild, wenn ich das hier anschaue,
das Top-Down-Teilen, das wir gemacht haben.
Ja, wenn ich Top-Down-Teilen machen möchte, wie mache ich das denn
hier?
Dann bräuchte ich ja nur die beiden Bits zu verändern in diesen beiden
Knoten von rot auf schwarz.
Und ich hätte aus den vier Knoten drei Zweiknoten gemacht.
Das heißt, das ist hier etwas, was mit ganz wenig Aufwand zu machen
ist.
Also, ich habe niemals zwei rote Kanten nacheinander.
Die wechseln sich immer ab.
Ich habe nur maximal drei Schlüssel in so einen Knoten drin.
Das heißt, ich brauche maximal diese Struktur hier unten.
Und ich brauche eben nur einen Bit pro Knoten, um ihn als rot oder
schwarz zu kennzeichnen.
Wenn ich Operationen mache, suchen ist klar, kleiner gleich zwei log
n, weil ich ja maximal abwechselnd rote und schwarze Kanten habe.
Und wir wussten, dass im 2-3-4-Baum die Höhe maximal log n ist.
Das heißt, das kann nicht größer sein.
Also ist sogar maximal log n hier die Länge.
So, gemäß dem Top-Down-Verfahren für 2-3-4-Bäume, das heißt, jeder
vier Knoten wird dann aufgeteilt, beziehungsweise jeder Knoten mit
zwei roten Nachfolger.
Also ich kann feststellen, ob ein Knoten zwei rote Nachfolger hat und
kann das dann aufteilen.
So, und ich habe also hier das Aufteilen, wie funktioniert das.
Das hier wäre jetzt ja im Prinzip mein Vierknoten.
Und jetzt will ich den aufteilen, daraus drei Zweiknoten machen.
Das kann ich einfach machen, indem ich, wie gesagt, hier unten die
beiden zu vollen Knoten mache.
Das müssten hier übrigens schwarze Kanten sein, da unten.
Und hier oben verändere ich einfach die Farbe bei den Knoten.
Ich mache den Knoten hier oben.
Wir hatten bei den 2-3-4- oder beim Top-Down-Teilen gesehen, wir
müssen das mittlere Element dieses Vierknotens nach oben schieben.
Das nach oben schieben beschränkt sich jetzt darauf, diesen Knoten
hier oben rot zu machen.
Dadurch wird er ein interner Nachfolger von dem Knoten da oben.
Die Kante wird rot.
Und das Reinschieben in die nächste Ebene geschieht nur durch diesen
einfachen Farbwechsel.
Und hier unten drunter, ob da also rot oder schwarz ist, ist völlig
egal.
Also hier konnte natürlich nur schwarz sein, ist nicht völlig egal.
Hier konnte nur schwarz sein, deswegen bleibt das da unten auch
schwarz.
Das will ich dann auch kurz hier richtig kennzeichnen.
Das sind also schwarze Kanten da unten.
Denn da unten ändere ich ja nichts durch dieses Aufteilen.
So, das ist also eine ganz einfache Operation.
Man muss, wenn man das Ganze macht, schon eine Reihe Sonderfälle
betrachten.
Insbesondere wenn es eben um diese Dreiknoten geht.
Aber das kann man alles machen.
Der Aufwand insgesamt, also der Implementierungsaufwand ist geringer
als bei den 2-3-4-Bäumen.
Und der Aufwand bleibt relativ klein.
Beim Löschen wird das wieder etwas komplizierter, aber man kriegt das
auch alles hin.
Und damit sind wir durch diesen Teilsuchen in irgendwelchen Listen
auch schon durch.
Wir haben eine Datenstruktur kennengelernt, die sich als eine sehr
günstige Datenstruktur herausgestellt hat.
Die wird eigentlich sehr weit verbreitet verwendet.
Wobei, wenn es um große Datenmengen geht, in denen ich suchen muss,
dann werden wieder ganz andere Verfahren eingesetzt.
Aber wenn es jetzt um Big Data geht, wie Herr Sandler es vorhin
erwähnt hat, der macht vor allen Dingen Algorithmen auf sehr, sehr
großen Datenmengen.
Auf die Problematik gehe ich jetzt nicht ein.
Ich gehe davon aus, die Datenstrukturen, die wir hier haben, liegen so
alle im Hauptspeicher.
Und wir haben keine Problematik mit wirklich sehr großen Datenmengen.
Okay, damit sind wir schon am Ende dieses Teils angekommen bezüglich
der Suchverfahren.
Das war der Hinweis vom vorigen Mal.
Wer Interesse hat an australischen Stipendien, kann das machen.
Was ich heute noch dazufügen sollte, wäre die Prüfungsanmeldung
bis 11.07.
Sollte eigentlich stimmen.
Das ist Montag auf jeden Fall.
Bis zu dem Montag müssen Sie sich spätestens angemeldet haben.
Und das sollten Sie auch möglichst bald tun.
Okay, also die Prüfungsanmeldung ist geöffnet.
Ich hoffe, dass das alles funktioniert.
Wir haben leider die dumme Situation, dass unser Campus-Management
-System nicht so stabil funktioniert, wie man das erwartet von einem
neu gebauten System.
Aber ich glaube, für unsere Vorlesungen funktioniert das einigermaßen.
Haben Sie es gefunden?
Die Prüfungsanmeldung finden Sie auf der AfB-Webseite unter Studien-
und Lehreprüfungen.
Und da finden Sie auch den Termin.
Das müsste da draufstehen.
Sollte eigentlich jetzt schon geöffnet sein.
Okay, das zu diesem Teil Suchen und Sortieren.
Ich will hier natürlich alles beibehalten.
Und gehe dann auf das nächste Kapitel.
Kapitel 6.
Genau, hier steht es nochmal drauf.
Bitte anmelden für die Klausur bis zum 11.
Juli 2016.
Ja, nochmal eingerahmt.
Das sollten Sie machen.
Und dann geht es jetzt um Graph-Algorithmen.
Algorithmen auf Graphen.
Wir haben jetzt Suchen gemacht, wir haben Algebraische Probleme
betrachtet.
Graph -Algorithmen sind auch ein ganz wichtiges Gebiet.
Wir haben sehr viele Strukturen in der Welt, die Graphen darstellen.
Und man kann da sehr viel Interessantes drauf machen.
Ihre Navi-Systeme sind Graphen-Algorithmen.
Also die Navigationsalgorithmen sind Graphen-Algorithmen.
Da werden kürzeste Wege gesucht.
Wenn Sie Fahrplanauskunft machen, sind das Graphen-Algorithmen.
Wenn man Lastflussberechnungen macht, sind das Graphen-Algorithmen.
Es gibt also vielfältige Anwendungen für Graphen.
Die Datenstruktur eines Graphen tritt an sehr vielen verschiedenen
Stellen auf.
Und ich werde hier nur einen kleinen Ausschnitt machen von Graph
-Algorithmen.
Einfach nur, um dieses Problemfeld auch einmal anzusprechen.
Schauen wir mal, was wir da an Themen haben.
Was ist ein Graph?
Ein Graph ist so eine Knoten- und Kantenmenge.
Wir haben Knoten, Kanten.
Nehmen wir an, dass wir N Kanten haben, nummeriert von 1 bis N.
N Knoten.
Und die Kantenmenge ist entsprechend eine Teilmenge des Kreuzproduktes
der Knoten.
Das heißt, wir haben gerichtete Kanten.
Das kann also alles Mögliche modellieren.
Kennen Sie alles aus den OR-Vorlesungen oder sonstigen Vorlesungen.
Also das gibt es an sehr vielen Stellen.
Und die Frage ist, wie modelliert man das?
Was ist die Datenstruktur?
Wie ist die Problemgröße?
Ich habe einmal die Anzahl der Knoten.
Das sind N Knoten.
Ich habe die Anzahl der Kanten.
Wenn ich zwischen je zwei Knoten eine Kante habe, habe ich N Quadrat
halbe Kanten.
Wenn die in beide Richtungen unterschiedlich sind, wenn ich aus beiden
Richtungen angeben muss, habe ich sogar N Quadrat Kanten.
Das heißt, das ist eine quadratische Anzahl.
Wenn Sie einen Planarengrafen haben, haben Sie maximal 6 N Kanten.
Bei Planarengrafen ist die Anzahl der Kanten immer linear in der
Anzahl der Knoten.
Aber bei beliebigen Grafen kann die Anzahl der Knoten deutlich größer
sein.
Man stellt einen Grafen da zum Beispiel durch eine Adjacenzmatrix,
Nachbarschaftsmatrix.
Das ist ja eine Sache.
Oder durch Adjacenzlisten.
Also ich habe hier meinen Knoten, wenn ich eine Kante habe, von Knoten
I nach Knoten J.
Dann steht entsprechend hier an dieser Stelle eine 1.
Sonst steht da eine 0.
Das wäre eine Adjacenzmatrix.
Genau dort an der Position steht eine 1.
Und der Platzbedarf ist natürlich quadratisch.
Wenn ich mir also hier eine Zeile anschaue, sehe ich, wie viele Kanten
dort rausgehen.
Wenn ich mir eine Spalte anschaue, sehe ich, wie viele Kanten auf das
J zulaufen.
Das Ganze kann ich reduzieren.
Wenn ich weiß, es kann sein, dass der Graf nur eine lineare Anzahl von
Kanten hat, dann werde ich keine Matrix nehmen, um die darzustellen,
sondern dann mache ich das mit Listen.
Und dann könnte ich also für jeden Knoten eine Liste führen über die
Anzahl der Knoten, die dort mit dem verbunden sind, die dort
rausgehen.
Und dann hätte ich also entsprechend einen Aufwand, der, wenn ich
Glück habe, kleiner ist.
Aber dann muss ich eben diese Listenstruktur dort entsprechend
bearbeiten.
Also das sind die beiden Möglichkeiten bei dünn besetzten Grafen auf
jeden Fall vorteilhaft.
Ein Algorithmus kennen Sie alle relativ gut, denke ich, der Dijkstra
-Algorithmus.
Das will ich hier noch einmal kurz darstellen.
Was machen wir beim Dijkstra-Algorithmus?
Wir wollen kürzeste Wege bestimmen.
Also wir wollen von irgendeinem Knoten, von einem Knoten U, die
kürzesten Wege finden zu allen anderen Knoten.
Ich möchte also für irgendeinen Knoten von den Grafen wissen, wie ist
der kürzeste Pfad von U nach diesem Knoten V.
Zu allen anderen Knoten V.
Und kürzeste Wege heißt also Wege mit kürzester Gewichtssumme.
Wir gehen davon aus, dass die Gewichte der Kanten alle größer gleich
Null sind.
Also die C, I, J sind alle größer gleich Null.
Wenn Sie negative Kantengewichte hätten, dann würden Sie die
Fahrtlänge reduzieren, wenn Sie da mehrfach rüberlaufen.
Das heißt, da könnten Sie Schleifen rentieren.
Das macht natürlich gar keinen Sinn.
Der kürzeste Pfad soll ja nicht länger werden können, nur weil ich
negative Kanten habe.
Negativ bewertete Kanten.
Also alle Kanten sind mit Zahlen größer gleich Null bewertet.
Ich habe da nicht nur eine 1 dran stehen, sondern irgendwelche Kosten,
Entfernungen oder ähnliches.
Und wenn ich keine Verbindung habe, steht da unendlich.
Der Dijkstra-Algorithmus ist also ein Greedy-Verfahren, eine
Heuristik, bei dem man wie folgt vorgeht.
Ich fange hier mit dem U an, mit dem Knoten, von dem aus ich gerne
wissen möchte, wie sehen die Fahrtlängen aus.
Und zunächst mal setze ich für alle Knoten V die Distanz von U nach V
auf das Kantengewicht UV.
Das Kantengewicht UV ist größer gleich Null natürlich.
Es ist kleiner als unendlich, wenn eine Kante existiert.
Wenn keine existiert, steht da unendlich.
Das heißt, ich weiß erst mal nichts.
Nur von den Knoten, die direkt verbunden sind, von denen weiß ich
etwas.
Dann wähle ich aus der Menge V minus S, also diese S ist meine Menge,
in der ich schon viel weiß, das ist hier angedeutet durch das S, das
ist meine Menge, der Knoten, bei denen ich genaue Informationen
darüber habe, wie weit sie von U weg sind.
Jetzt nehme ich irgendeinen, das habe ich für alle Knoten hier diese
Entfernung gesetzt, jetzt wähle ich aus den Knoten, die nicht in S
drin sind, den Knoten aus, der die minimale Distanz hat, von U.
Also, ich suche mir einen Knoten W.
Der ist nicht in S.
Und ich sage, dass dW soll der minimale Wert dV sein, sodass V aus V
minus S ist.
Zu Anfang ist ja nur das U da drin.
Das heißt, jetzt würde ich mir die nächsten Knoten, die Entfernungen
kenne ich ja, zu den nächsten Knoten, ich würde mir als nächstes den
hernehmen, der die kürzeste Distanz hat, kürzeste Kantengewicht.
Ich füge diesen Knoten zu dem S hinzu und berechne jetzt für alle,
also das ist hier mein Knoten W, der war irgendwie mit einem Knoten
hier drin verbunden, das ist der, der hat die geringste Distanz zu dem
U.
Ich schaue mir jetzt an, die Distanz zu einem, hier habe ich einen
Knoten V, und ich möchte die Distanz zu dem Knoten V jetzt
aktualisieren, dadurch, dass ich mir den alten Wert von V anschaue.
Kann ja sein, dass der irgendwo hier verbunden war schon.
Die Entfernung kann nicht kleiner sein, als die Entfernung von W zu
dem U, weil ansonsten das V gewählt worden wäre.
Jetzt schaue ich mir an, die Entfernung, hier muss ja irgendeine
Verbindung existiert haben.
Ich habe eine alte Entfernung und jetzt eine neue Entfernung, dadurch,
dass ich über den Knoten W gehe.
Das heißt hier, wenn die direkt verbunden sind, habe ich hier ein CWV
stehen, das ist das hier, und ich habe die Entfernung von W zum Knoten
U, und damit habe ich hier für diesen Knoten V einen neuen Wert für
die Distanz.
Kann sein, dass der Wert kleiner wird, wenn er nicht kleiner wird,
bleibt das halt gleich.
Ich muss jetzt noch das Kantengewicht der Kante von W nach V
dazufügen.
Und jetzt ist natürlich, das W hatte ich ja zugefügt zu dem S, das
heißt, das gehört jetzt mit dazu zu dem S.
Und entsprechend mache ich dann weiter, dann suche ich wieder
außerhalb nach dem kleinsten Knoten, oder nach dem mit der kürzesten
Distanz.
Und hier mache ich also immer so eine Xmin-Operation auf der Menge der
Knoten, die noch da sind.
Ich muss immer das kleinste Element raussuchen können, oder ich habe
eine Prioritätswartenschlange, brauche immer nur das kleinste Element
rauszusuchen.
Ich mache das so lange, bis die Anzahl der Elemente in der Menge S
gleich L-1 ist, oder bis das V-S im Prinzip nur noch ein Element hat,
danach bin ich fertig.
Der Aufwand, den ich hier treibe, ist quadratisch, weil ich N-mal eine
Operation machen muss, wo ich Minimum-Operation wähle.
Hier habe ich eine Minimum-Operation, da habe ich auch eine Minimum
-Operation.
Das heißt, hier habe ich jedes Mal einen linearen Aufwand.
Ich muss für alle Knoten die Entfernungen aktualisieren, wobei sich ja
nur für die etwas ändern kann, die direkt mit den Knoten W verbunden
waren.
Für keine weiteren, das wird nicht zu groß sein.
Also der Aufwand ist allerdings insgesamt jeweils linear und wir haben
dann insgesamt einen Aufwand von N² dafür.
Was ist denn jetzt?
Wieso ist die Folie eigentlich hier reingerutscht?
Ich wundere mich schon, dass gleich der Dijkstra-Algorithmus kommt,
aber irgendwie ist das hier reingerutscht, das habe ich Ihnen jetzt
schon erklärt.
Es kommt nämlich jetzt erst die Folie, da muss sich gestern irgendwas
verschoben haben, es kommt jetzt erstmal nochmal eine Einführungsfolie
über Begriffe, über die wir gerade schon geredet haben, nämlich der
Begriff eines Weges, also eine Folge von Kanten, das ist klar.
Das da unten ist also ein einfacher Weg ohne Knotenwiederholungen,
eine Folge von Kanten, ich habe eine Quelle, das ist mein U1, ich habe
ein Ziel, das ist mein VN und die Länge des Weges ist die Anzahl der
Kanten.
Wenn ich einen Knoten habe mit Knotenwiederholungen, dann ist es ein
Kreis und ein Kreis ist eben ein Pfad mit Knotenwiederholungen, der
durch Entfernen einer Kante ein einfacher Weg wird.
Und ein Graph ist a-zyklisch, wenn der Graph keine Kreise enthält.
Und jetzt kommen hier noch die ungerichteten Graphen, also das sind
noch ein paar Einführungssachen.
Ich habe vorher die gerichteten Graphen nur betrachtet.
Wenn ich sage, ich habe jeweils IJ und JI da drin, dann male ich das
eben nicht so wie hier, da habe ich beide Kanten drin, sondern ich
male da einfach nur einen ungerichteten Strich zwischen die beiden
Knoten.
Und für ungerichtete Graphen ist eben das E dann nicht eine Menge von
Paaren, sondern es sind das ein bis zwei elementige Teilmengen, weil
ich ja keine Ordnung da drin habe.
Es ist egal, ob ich erst I oder J schreibe oder das ist immer die
gleiche Kante.
Und dann ist noch ein Begriff, der wichtig ist, das ist der Begriff
des Zusammenhangs.
Ganz wichtiger Begriff, weil ein Graph häufig eben irgendein
Versorgungsgraph ist, Versorgungsstruktur.
Und wenn Sie durch Hinausnehmen einer Kante auf einmal dafür sorgen,
dass die nicht mehr zusammenhängend sind, das heißt, dass ich nicht
mehr einen Weg habe zwischen beliebigen zwei Knoten in meinem Graphen,
dann wäre er nicht zusammenhängend.
Das heißt, er ist zusammenhängend, wenn es jeweils einen Weg von I
nach J gibt, wobei ich hier einen ungerichteten Graphen voraussetze.
Wenn ich einen gerichteten Graphen hätte, wenn ich dann erwarte, dass
ich von jedem Knoten zu jedem anderen gehen kann durch gerichtete
Kanten, dann hätte ich einen stark zusammenhängenden Graphen, bei dem
ich also auch über gerichtete Kanten von jedem Knoten zu jedem anderen
kommen kann.
Und ein Baum, haben wir vorhin gerade betrachtet, ein Baum wäre dann
ein Graph, der zusammenhängend ist und a-zyklisch.
Also wenn Sie einen Baum haben,
offensichtlich zusammenhängend und a-zyklisch, also zusammenhängend,
sofern die Kanten immer schön an die Knoten rangehen.
Und in dem Augenblick, wo Sie hier irgendeine weitere Kante dazufügen,
dann hätten Sie einen Zyklus drin.
Und das wäre eben dann etwas, was wir nicht haben, dann wäre es kein
Baum mehr.
Und dabei muss man natürlich sagen, das hier oben, was ich da gemalt
habe, ist ja eigentlich auch ein Kreis.
Nur den zählen wir nicht als Kreis.
Das ist eine Kante und kein trivialer Kreis.
Also solche trivialen Kreise, die werden hier nicht berücksichtigt.
Wenn wir sagen, ein ungerichteter Graph ist a-zyklisch, wenn keine
solchen, wenn also nicht mindestens drei Knoten an den Kreisen
beteiligt sind.
So, jetzt kommen wir hier zu den typischen Graph-Problemen.
Ich weiß nicht, wieso die Folie mit Dijkstraben wieder nach oben
gerutscht ist.
Ich muss irgendeine Operation drauf gemacht haben.
Aber es macht ja nichts, dann haben wir schon mal gesehen, wie das
Problem in den kürzesten Wege hier gemacht wird.
Also, die typischen Graph-Probleme, die ich ja eigentlich betrachten
wollte, oder auch betrachte.
Ein typisches Graph-Problem ist die Erreichbarkeitsbestimmung.
Das heißt, ich habe irgendeinen Graphen und ich möchte wissen, kann
ich die alle voneinander erreichen.
Das heißt, wenn ich die Erreichbarkeitsmatrix habe, weiß ich, gibt es
von irgendeinem, wenn ich hier einen Knoten I und J habe, wenn hier
irgendein Wert drinsteht, wenn da eine Eins drinsteht, dann gibt es
einen Weg von I nach J.
Und diese Erreichbarkeitsmatrix, oder auch die transitive Hülle des
Graphen, ich kann ja einen Graphen als eine Relation auffassen, das
ist die transitive Hülle der Relation, definiere ich einfach für alle
R aus N, Tg hoch R, also die transitive Hülle des Graphen G,
beziehungsweise hier, bezogen auf Pfade der Länge R.
Das Tijr ist gleich 1, wenn es einen Weg der Länge kleiner gleich R
von I nach J gibt.
Die Pfadlänge in einem Graphen ist natürlich maximal N, also N-1 ist
die maximale Pfadlänge.
Die längsten sind dort aber maximal N Elemente drin.
Ich kann also auf die Art und Weise jetzt hier meine Tij berechnen.
Das Tijn ist dann auf jeden Fall ein Eintrag in der
Erreichbarkeitsmatrix, weil ich dann weiß, es gibt ein Pfad, wenn das
Tijn gleich 1 ist, dann sind die entweder die IJ bereits verbunden,
oder es gibt einen Knoten K, der mit einem Pfad der Länge N-1 mit dem
Knoten J verbunden ist, und dann gibt es einen Pfad von I nach J.
Also wenn das AIJ nicht 1 ist, d.h.
ich habe dort keine Kante von I nach J, dann kann es sein, dass ich
über einen anderen Pfad dort laufe.
Also hier Knoten I, Knoten J, dann habe ich hier den anderen Knoten.
Es gibt also entweder hier direkt eine Kante, oder es gibt eine Kante
von I nach K und einen Pfad von K nach J, und die muss ich jetzt
entsprechend berechnen.
Das kann ich machen, indem ich einfach Matrixmultiplikation mache.
Wenn Sie sich nämlich das hier anschauen, diese Gleichungen, die hier
stehen, dann ist es genau das, was wir bei der Matrixmultiplikation
gemacht haben.
Da haben wir ein Produkt gebildet, und das addiert zu einem Wert.
Und wir machen hier von der Struktur her nichts anderes.
Das kann ich genauso durchlaufen lassen.
D.h.
um eine Iteration hier zu machen, mache ich eine Matrixmultiplikation.
Meine Erreichbarkeitsmatrix, oder die Adjacenzmatrix, multipliziere
ich mit sich selbst.
Zu Anfang habe ich ja hier die Adjacenzmatrix reingenommen.
Und ich muss also nur alle Produkte bis A hoch N im Prinzip berechnen.
Dann habe ich meine Erreichbarkeitsmatrix.
Wenn ich das machen würde, N-Multiplikation machen.
Wir wissen, Matrixmultiplikation brauchen, wenn wir naive Verfahren
nehmen, Zeit N hoch 3, hätten wir Aufwand N hoch 4.
Jetzt kann man sagen, ich will ja alle Potenzen berechnen.
Wenn ich alle Potenzen berechnen will, dann geht das auch mit N hoch 3
log N, indem ich sukzessives Quadrieren mache und entsprechend dann
die entsprechenden Potenzen, die Zweierpotenzen sind, jeweils
miteinander multipliziere.
Und dann habe ich alle mit Aufwand N hoch 3 mal log N hinbekommen.
Also das ist problemlos machbar, aber es ist noch nicht optimal.
Und den klugen Ansatz, den Wortschreißalgorithmus, machen wir nächstes
Mal.
Vielen Dank, das war es für heute.