So, jetzt haben wir auch das Bild zur heutigen Vorlesung, Algorithmen
1.
Wie üblich kurzer Rückblick, was haben wir letztes Mal in der
Vorlesung gemacht?
Das war letzte Woche im anderen Hörsaal.
Sie erinnern sich vielleicht daran, wir hatten uns mit dem sogenannten
minimalen Spannenbaum-Problem beschäftigt.
Das ist auch ein Problem auf Graphen.
Und wir haben uns dazu zwei Algorithmen angeschaut.
Einen untersetzt den Jarnik-Priem-Algorithmus und einen untersetzt den
Kruskal -Algorithmus.
Und dann ging Ende der Vorlesung noch eine spezielle Datenstruktur,
die hilfreich war in dem Kruskal-Algorithmus.
Und das war die sogenannte Union-Find-Datenstruktur.
Gut, Sie haben das bestimmt alle noch im Kopf von letzter Woche, um
was es da ging.
Oder vielleicht auch nicht, deshalb schauen wir uns vielleicht nochmal
ganz kurz an, was das Problem war.
Oder vielleicht kann auch jemand von Ihnen das kurz erklären.
Hier hätten Sie auch die Folie dazu.
Worum geht es bei dem minimalen Spannenbaum-Problem?
Wichtige Eigenschaft, alle Knoten sollen erreicht werden und das
Kantengewicht über diese verbindenden Kanten soll minimal sein.
Dann kann man sich überlegen, wieso heißt das jetzt minimaler
Spannenbaum?
Weil eben diese Struktur an Kanten, die dabei entsteht, dabei auch
noch einen Baum bilden soll.
Jetzt hätte ich noch eine Frage an Sie, muss das immer ein Baum sein?
Also wenn ich jetzt nur die Eigenschaft hernehme und sage, das soll
eine Menge von Kanten sein, die alle Knoten abdecken und ein minimales
Gewicht haben, ist das zwangsläufig ein Baum?
Sie waren schon dran, dann nehmen wir etwas anderes.
Genau, also wenn man eine zusammenhängende Menge auswählt, dann wird
das wohl ein Baum sein, nehme ich auch an.
Aber ist es so, dass es immer zusammenhängend sein muss?
Nein, ist nicht der Fall.
Also es kann sein, dass man wirklich eine Menge von Kanten mit
kleinerem Kantengewicht findet, die eben keinen Baum bildet.
Aber das ist eben nicht das, was hier gesucht ist, sondern hier geht
es darum, dass wir einen Baum finden wollen mit dieser Eigenschaft.
Okay, also alle Knoten abdecken, minimales Kantengewicht und das soll
eben zusammenhängend sein oder ein Baum bilden.
Das sind diese minimalen Spannbäume.
Genau, dazu haben wir uns zwei Algorithmen angeschaut.
Oder zuerst mal zwei Eigenschaften, die möchte ich auch nochmal ganz
kurz wiederholen.
Das war die Schnitteigenschaft und das zweite war die
Kreiseigenschaft.
Und da würde ich jetzt vielleicht auch kurz darum bitten, ob jemand
ganz kurz erklären kann, was diese Schnitteigenschaft war oder ist.
Also das war eigentlich ein ganz interessantes Phänomen, dass die
ganzen Algorithmen auf zwei einfachen Eigenschaften von minimalen
Spannbäumen basieren.
Also man muss sich gar nicht sehr viele komplexe Dinge anschauen.
Wenn man einmal diese beiden Grundideen hat, die reichen einem aus, um
daraus Algorithmen zu bauen.
Gut, wer von Ihnen kann und möchte die Schnitteigenschaft kurz
erläutern?
Wollen Sie es mal versuchen?
Nein, eher nicht.
Dann haben wir jemand anderes, der sich daran wagt.
Ja, hier oben, sehr schön.
Darf ich ganz kurz noch brechen?
Können Sie das verstehen oder ist es zu leise?
Sie können es nicht verstehen.
Ich bringe Ihnen schnell ein Mikrofon.
Dann dürfen Sie.
Die mit kleinstem Gewicht im minimalen Spannbaum.
Genau, richtig.
Das ist eigentlich eine relativ einfache Eigenschaft.
Irgendwie den Graphen umschneiden, in zwei Knotenmengen zu legen.
Sie könnten die von der einen Menge in die andere gehen betrachten.
Da gehe ich hin mit dem kleinsten Gewicht und die kann dann in einem
minimalen Spannbaum auftreten.
Okay, dann haben wir noch die zweite Eigenschaft, die ist noch ein
bisschen einfacher.
Vielleicht können Sie einfach das Mikrofon eins weitergeben, in eine
beliebige Richtung.
Und dann ein Kollege von Ihnen, womit wir uns schnell erklären können,
was diese Kreiseigenschaft war.
Also die schwerste Kante kann man aus einem Kreis immer streichen,
weil man ja mit allen anderen verbunden ist schon.
Genau, das war kurz und bündig und das ist eigentlich auch schon die
Idee.
Man sieht es hier auch nochmal in der Darstellung.
Also wenn wir in so einem Kreis eine Kante weglassen, sind immer noch
alle Knoten zu erreichen.
Die sind noch miteinander verbunden.
Wir haben auch einen Baum dann durch das Entfernen der Kante.
Und welche Kante entfernen wir?
Die schwerste Kante, weil die eben garantiert nicht zu dem minimalen
Spannbaum, dem Baum mit dem geringsten Gewicht dazugehört.
Okay, und da haben wir uns dann die zwei Algorithmen eben angeschaut.
Einerseits den Jarnik Prim Algorithmus, der auf dieser ersten
Eigenschaft, diesem Cut Property beruht.
Also wir können das auch nochmal, wenn jemand von Ihnen das erklären
möchte, dann darf er das auch nochmal schnell hier.
Ansonsten würde ich einfach entweder es kurz selber machen oder
schnell drüberspringen.
Ich möchte mit ganz kurz den Algorithmus erklären.
Ja, sehr schön.
Also wir fangen an mit einem Knoten und schauen uns dann die
Teilgrafen an, die entstehen, wenn man praktisch den einen Knoten
nimmt und dann die disjunkte Menge dazu, die zusammen die komplette
Knotenmenge gibt.
Wir schauen uns an, welche Kanten von dem einen Teilgraf zum anderen
führen, also auf dieser Schnittkante liegen und wählen dann praktisch
die mit dem geringsten Kantengewicht aus.
Und das machen wir so lange sukzessive, bis wir einmal durch die
kompletten Grafen durchgelaufen sind.
Genau, und wie viele Schritte benötigen wir dazu?
N-1 Genau, wie es auch hier bei der Steife eben dran steht.
Und nach N-1 Schritten haben wir eben wirklich dann, weil jedes Mal
ein neuer Knoten dazukommt, haben wir alle Knoten dann erreicht.
Oh ja, genau, Sie möchten es schon weitergeben, das können Sie gleich
machen.
Wir haben ja noch einen zweiten Algorithmus, den Kruskal-Algorithmus.
Wollen Sie den erklären, kurz?
Nein, nicht wirklich.
Nicht wirklich?
Gibt es hier etwas anderes in der Gegend hier oben, das machen wir ja
auch möglich?
Ja, also dieser Algorithmus sucht einfach die nächst kleinere Kante
und guckt, ob die noch zu keinem Kreis dazugehört und nimmt die dann
dazu.
Und daraus bildet er sich dann den minimalen Spannraum zusammen.
Okay, ja, auch kurz und bündig sind die wichtigsten Eigenschaften
drin.
Was heißt die nächst kleinere Kante?
Also wie fangen wir da an?
Ja, man nimmt einfach die nächste, die den kleinsten Wert hat, die
noch nicht verwendet wird oder schon ausgeschlossen ist.
Genau, ja, und das macht man eben hier in so einem
Vorverarbeitungsschritt, dass man die Kanten erstmal sortiert, ihrem
Gewicht nach, und dann können wir einfach da immer die nächst kleinere
Kante mit dem Gewicht rausnehmen.
Was für eine Datenstruktur würden Sie da verwenden oder was haben wir
da verwendet?
Ich glaube, ich habe jetzt keine Folie dazu.
Aber wenn man daran interessiert, ist das kleinste Element immer zu
finden.
Klar, man kann sortieren, aber um das kleinste Element zu finden, gibt
es noch eine andere Datenstruktur.
Die Delete-Min-Funktion auf der Datenstruktur.
Wenn es jemand anders weiß, hier oben.
Ein Heap.
Ja, genau, Heap oder Priority Queues können wir dazu verwenden.
Die erlauben eben, das kleinste Element immer zu finden.
Wir brauchen nicht alle auf einmal, wir müssen also nicht die
komplette Menge sortiert haben, sondern haben damit Zugriff auf das
kleinste Element.
Gut, genau, Intimarbeit dann gelöst.
Gut, das ist der zweite Algorithmus, der Kuhskern-Algorithmus.
Wir werden uns anschauen, was sind die Teile, die Laufzeit benötigen.
Einerseits eben das Sortieren oder die Handhabung von der Priority
Queue, um diese kleinsten Knoten immer finden zu können.
Und dann haben wir noch das, was jetzt hier in rot-violett markiert
ist, dass wir herausfinden müssen, ob zwei Knoten U und V in
unterschiedlichen Teilbäumen sind.
Also wir bauen ja unseren Baum so schrittweise auf, indem wir einfach
Kanten schrittweise hinzufügen.
Und die Frage ist, also die können auch dann erstmal getrennt sein,
das muss nicht alles zu einem Baum schon dazugehören.
Und die Frage ist dann eben, die wir hier immer wieder beantworten
müssen, ob zwei gegebene Knoten im selben oder in unterschiedlichen
Teilbäumen liegen.
Und dazu haben wir uns auch noch eine spezielle Datenstruktur
angeschaut.
Sie haben gerade das Mikrofon, wissen Sie noch, wie die hieß?
Die Union Find Datenstruktur.
Genau, Union Find.
Und was gab es da für Tricks dazu, um die effizient zu machen?
Oder vielleicht, wenn Sie es mal grob im Kopf haben, was waren so die
Elemente oder die Ideen bei dieser Datenstruktur?
Ich habe gesagt, geben Sie einfach das Mikrofon weiter.
Also die Idee war, dass man versucht hat, in jeder...
Also wir haben uns das allgemeinere Problem angeschaut, wenn wir eine
Menge haben, die wir partitionieren in Teilmengen.
Und jede Teilmenge entspricht einem solchen teilaufgebauten Baum.
Und wir wollen dann herausfinden, ob zwei beliebig vorgegebene
Elemente jetzt eben in derselben Teilmenge oder im selben Block in
dieser Partition liegen oder nicht.
Und dann haben wir uns überlegt, das reicht ja aus, wenn wir für jedes
Element uns einen Repräsentanten raussuchen in jeder Teilmenge und
indem wir dann einfach direkt vergleichen können über diesen
Repräsentanten, ob das eben dieselbe Teilmenge ist.
Und das heißt, wir haben dann das Problem, dass wir eben einen
Repräsentanten finden müssen für jede Teilmenge und den irgendwie
abspeichern.
Und dazu hat man so eine verzeigerte Struktur dann gedacht, dass wir
zu jedem Knoten eben immer so einen Pointer abspeichern zu dem
Repräsentanten.
Und das war über diese Parent-Datenstruktur gemacht.
Schauen wir mal kurz...
Also, noch ein paar Folien habe ich noch vom letzten Mal dabei.
Genau diese Feind-Datenstruktur mit den verschiedenen Mengen.
Und wir hatten eben einerseits diese Parent-Datenstruktur, die uns
eben angibt, wie wir zu dem Repräsentanten finden.
Das war eben über so eine Kette von Parent-Kanten.
Also, wenn wir hier einen Knoten haben, dann kommen wir über mehrere
Parent -Kanten irgendwann mal zu einem letzten Element, wo wir dann
eben hier stehenbleiben und nur noch im Kreisraum laufen können.
Und dann dieses Element ist schon der Repräsentant für unser Element
hier unten in der Menge.
Und wenn wir jetzt zwei solche Elemente eben hernehmen und berechnen,
verbreitet den Repräsentant, der ist eben in jeder Menge eindeutig,
was der Repräsentant ist.
Und die können wir dann direkt vergleichen.
Vielleicht entfernt so, wenn Sie jetzt irgendwelche Objekte
vergleichen wollen, in Java zum Beispiel, dann können Sie erst mal die
Adresse von den Objekten vergleichen und haben damit so einen
schnellen Vergleich schon mal vorab,
um zumindest im positiven Fall, wenn Sie gleich sind, eine Antwort zu
erhalten.
Also hier einfach die Idee, wir speichern uns einen Repräsentant für
jede Teilmenge ab.
Also hier, wenn wir diese Zerlegung haben in M1, M2, Mk, in jeder
Teilmenge gibt es einen Repräsentant und alle anderen Elemente haben
dann eben über diese Parent-Datenstruktur solche Zeiger, die uns unter
Umständen über mehrere Schritte bis zu diesem Repräsentant führen.
Okay, also das war diese Union-Find-Datenstruktur.
Und die Find-Operation ist relativ einfach.
Also die Find-Operation soll uns diesen eindeutigen Repräsentanten
zurückgeben.
Also das, was wir hier unten sehen, Find bringt als Eingabe den Index
von einem Element in unserer partitionierten Menge M und liefert uns
dann den Repräsentanten zurück für den Block I oder für das Element,
das wir eingegeben haben.
Was macht die Union-Funktion dann?
Wo ist das Mikrofon gerade?
Hat jemand von Ihnen noch...
Sie dürfen es einfach auch nochmal weitergeben, wenn Sie wollen.
Was macht diese Union-Funktion, war die Frage.
Ja, die Union-Funktion fügt eben so zwei Blöcke zusammen, indem sie
den Parent von der einen Funktion da nochmal den Parent von der
anderen Block zusammen macht.
Genau, ja.
Also letztendlich sollte einfach eine Mengenvereinigung gemacht werden
und die ist hier relativ einfach möglich.
Also was soll nach der Mengenvereinigung möglich sein, dass man eben
wieder diese Find-Operation ausführen kann und die uns einen
eindeutigen Repräsentanten liefert.
Und wenn wir dann eben zwei Mengen zusammenführen, müssen eben die
Repräsentanten für beide Mengen dieselben sein und das erreichen wir
eben, indem wir so eine Parent-Kante einfach nochmal von einem alten
Parent zu dem Parent im anderen Block einfügen.
Okay, also das war diese Union-Find-Datenstruktur.
Hier sehen wir auch nochmal schon eine Optimierung und dann noch eine
zweite Optimierung.
Und die erste Optimierung, das war diese sogenannte Pfadkompression
und die zweite Optimierung war dieses Union-by-Rank.
Und genau, soweit waren wir in der Vorlesung.
Ja, wenn wir jetzt gerade schon dabei sind, dass wir hier die Fragen
beantworten, möchte jemand die Pfadkompression kurz erklären?
Naja, im Grunde ist es so, dass man allen Kindern von einem Knoten den
Elternknoten den gleichen zuweist.
Also nimmt man von einem den Elternknoten und nimmt dann alle Kinder
von dem auf den gleichen Elternknoten.
Ja, genau.
Können Sie vielleicht rechts hier noch an dieser Abbildung hier
kurz...
Ja, da gibt es ganz oben den Elternknoten und alle anderen sind Kinder
oder Enkel oder so weiter von dem Elternknoten und wenn man all diesen
Knoten als Parent den Elternknoten zuweist, also direkt drauf zeigen
lässt, dann ist man fertig.
Genau, und die Idee dabei ist eben diese Pfade von jedem beliebigen
Element in so einem Block zu dem Repräsentanten möglichst kurz zu
halten.
Also links hat man eben einen Pfad, der maximal die Länge O von N
haben kann und auf der rechten Seite ist es immer nur noch ein
Schritt, den man benötigt, um zum Repräsentanten zu kommen.
Und diese Feind-Operation, die läuft ja eben diese Parent-Relation
oder diese Parent-Tenten ab und wenn es eben in einem Schritt geht,
dann ist es natürlich besser, als wenn man da jetzt bis zu maximal N
-Schritten benötigt.
Okay, also das erlaubt uns dann, den Repräsentanten schnell zu finden.
Im Gegensatz zu N-Schritten können wir den dann eben immer in einem
Schritt finden.
Und dann haben wir noch eine zweite Optimierung für das Union Find und
das war diese Einführung von einem Run oder Rank für jedes Element in
einem Menu.
Wenn mich das fragt, kann das auch jemand schnell noch erklären.
Was kann dabei passieren?
Über diese Parent-Relation bauen wir ja praktisch einen Baum auf.
Einen Baum, der uns eben von beliebigen Elementen bis zu dem
Repräsentanten führt, der eben oben in dem Baum steht.
Und wenn wir jetzt eine Union-Operation durchführen...
Im Prinzip sorgt man dafür, dass der Bau möglichst balanciert ist,
sodass man eben möglichst schnell von jedem Element zum Elternelement
kommt.
Genau, also wo ist das Problem?
Was kann bei der Union-Operation passieren?
Dass ein sehr unbalancierter Baum entsteht, dann ein sehr langer Pfad
von einem Element zum Elternelement entsteht, von dem man quasi immer
sich merkt, wie viele Stufen der Baum hat, kann man dann jeweils die
Union -Operation so ausführen, dass immer quasi der kleinere Baum so
an den größeren dran gehängt wird, dass am Ende ein balancierter Baum
entsteht.
Genau, das ist die Idee hier, wir wollen balancierte Bäume bekommen.
Und bei der Union-Operation hat man ja immer jeweils die Wahl, möchte
ich den einen Baum als teilbar vom anderen definieren oder so eben
andersrum.
Und das wählt man dann eben anhand von dem Rang so aus, dass man einen
möglichst balancierten Baum enthält.
Gut, dann, ja, vielen Dank für die Antworten.
Und soweit waren wir auch letztes Mal in der Vorlesung.
Dann dreht uns hier mal kurz zurück, dass wir nochmal schnell schauen,
was wir uns heute anschauen.
Aber wir werden noch ein bisschen weiter bei der Union-Find
-Datenstruktur bleiben, uns noch ein paar Eigenschaften anschauen und
gehen dann über zu einem anderen Thema, zu generischen
Optimierungsansätzen, Optimierungsverfahren.
Und da schauen wir uns ein Rucksackproblem an oder generell eine große
Problemklasse, die sich lineare Programmierung nennt.
Okay, gut, also jetzt nochmal zu dem Union-Find.
Also, wir hatten ja gesagt, es lässt sich mit zwei Techniken
optimieren.
Eben einerseits mit der Part-Kompression und zum anderen mit dieser
Rank -Funktion, die wir einführen, die dafür sorgt, dass es
ausbalanciert ist.
Und jetzt können wir uns wieder anschauen, was die Laufzeit von diesem
Verfahren ist.
Und es ist hier so, dass die Laufzeit eben auch schwankt.
Also, wenn wir bei dem Find eben viele Updates durchführen müssen und
die ganzen Pointer eben, statt dass die Endschritte brauchen, auf
einen Schritt abkürzen, das ist etwas, was wir eben einmal machen
müssen, da benötigen wir Rechenzeit und danach gehen alle Abfragen
dann sehr schnell.
Gut, und das heißt, wir betrachten jetzt deshalb eben auch die
amortisierte Komplexität über eine ganze Reihe von Aufrufen.
Und eben, wie sieht das genau aus?
Wir haben M mal die Find-Operation, also M mal wollen wir so einen
Repräsentanten finden, um feststellen zu können, ob im Zwei-Limit in
derselben Partition sind.
Und N mal haben wir diese Link-Operation und die Link-Up-Operation,
die berechnet ja unsere Updates von diesen Pointer-Könten.
Und dann schauen wir uns an, was dann eben die amortisierte Laufzeit
ist.
Und was man beweisen kann, ist, dass die Laufzeit von M Find und N
Link, also Sie können sich grob auch Union-Operationen darunter
vorstellen, da kommt sonst auch nochmal ein Find jeweils dazu,
benötigt die Zeit O von M mal Alpha von T.
Und Alpha T ist eine Funktion, die auch wieder von M und von N
abhängt.
Also haben wir eine Laufzeit von M mal irgendwas.
Und dieses Irgendwas ist eine Funktion, die extrem langsam wächst,
also noch langsamer als der Logarithmus.
Also wenn es jetzt nicht der Logarithmus wäre, dann wäre das so eine
amortisierte Laufzeit O von M mal Logarithmus M, aber es ist eben was,
was noch kleiner Werte zurückliefert die Funktion als der Logarithmus.
Und was haben wir da an Funktionen zur Verfügung, die langsamer
wachsen als der Logarithmus?
Und was vielleicht ein bisschen überraschend ist, ist, dass man hier
zeigen kann, dass das mit einer Funktion zusammenhängt und sich die
Laufzeit beschreiben lässt, die auf den ersten Blick vielleicht gar
nichts direkt zu tun hat mit diesen beiden Algorithmen, Komponenten
wie Pfadkompression und diese Rangfolgeeinführung.
Und zwar ist es so, dass die Ackermann-Funktion hier wieder eine Rolle
spielt.
Und zwar in der Weise, dass dieses Alpha von T die inverse Ackermann
-Funktion ist.
Also Ackermann-Funktion eine Funktion, die extrem schnell wächst und
das inverse der Ackermann-Funktion ist eben eine Funktion, die dann
extrem langsam wächst.
Und Ackermann-Funktion, die haben Sie, habe ich glaube ich letztes Mal
auch schon gefragt, ich glaube in Grundbegriffe der Informatik war das
schon enthalten.
Also wenn Sie schauen, die Ackermann-Funktion, die ist leider nicht
ganz eindeutig.
Also da gibt es verschiedene Varianten, wie man die definieren kann.
Und Sie hatten wahrscheinlich eine klein bisschen andere Version der
Ackermann -Funktion in Ihrer Vorlesung.
Aber letztendlich ging es bei dieser Ackermann-Funktion, als die
vorgestellt wurde, um ein theoretisches Ergebnis, was mit
Berechenbarkeit oder mit Komplexität zu tun hat.
Und zwar gibt es zwei verschiedene Modelle, Sie haben vielleicht noch
im Kopf, dass es eben die sogenannten rekursiven Funktionen gibt und
es gibt primitiv-rekursive Funktionen.
Und die Frage war eben, was kann man mit diesen Funktionsklassen
jeweils berechnen?
Also die Begriffe rekursive oder primitiv-rekursive Funktionen, die
sind Ihnen wahrscheinlich auch bekannt in den Ausgrundbegriffen der
Informatik.
Ist das richtig?
Okay, also letztendlich geht es darum.
Oder haben Sie diese Begriffe noch nicht gehört?
Ah, sind nicht bekannt, okay.
Gut, da müsste ich jetzt vielleicht ein bisschen weiter dazu ausholen.
Also das war schon weit zurückliegend, eigentlich Anfang des
Jahrhunderts, die Frage, was bedeutet denn Berechenbarkeit?
Also was sind Modelle, mit denen man eben angeben kann, was eine
Rechnung ausmacht?
Und ein Modell war eben die Turing-Maschinen, das ist Ihnen bestimmt
ein Begriff, die haben Sie schon gesehen.
Und dann gab es eben auch andere Berechnungsmodelle.
Und die Frage war, wie die im Verhältnis zueinander stehen.
Also eine andere Variante war zum Beispiel das Lambda-Kalkül, wo sich
die Frage stellt, was eben auch einen bestimmten
Berechnungsformalismus ausdrückt.
Und das andere, eine dritte Variante, sind eben diese rekursiven
Funktionen.
Und da gab es verschiedene Abstufungen, es gibt kleinere
Funktionsklassen, das sind einfach die rekursiven Funktionen, und auch
primitiv -rekursive Funktionen.
Und die größere Klasse, die sogenannten my-rekursiven Funktionen.
Und die my-rekursiven Funktionen haben sich eben herausgestellt, dass
die auch wieder genauso viel berechnen können, wie mit der Turing
-Maschine oder eben auch mit diesem Lambda-Kalkül.
Und wie gesagt, eine Teilmenge davon, die man sich auch zuerst
angeschaut hatte, und wo die Hoffnung war, dass die vielleicht schon
ausreichen, waren die sogenannten primitiv-rekursiven Funktionen.
Und das wurde damals alles sehr mathematisch aufgeschrieben, aber aus
heutiger Sicht kann man sich das eigentlich so vorstellen, dass sich
mit diesen primitiv-rekursiven Funktionen, also nicht-rekursiven
Programme, ausdrücken lassen, die Schleifen enthalten.
Also alles, was eine Vorschleife enthält, lässt sich mit primitiv
-rekursiven Funktionen ausdrücken.
Und dann wäre jetzt die Frage, lässt sich mit Vorschleifen, wenn Sie
jetzt also nur Vorschleifen zur Verfügung haben, lässt sich da eine
beliebig komplexe Funktion oder lässt sich ja beliebige Funktionen
berechnen.
Also dabei geht es immer um Funktionen von natürlichen Zahlen auf
natürliche Zahlen.
Und wenn Sie jetzt einmal ein Programm schreiben müssten, in der
Programmiersprache, jawohl, Sie dürfen keine Rekursion verwenden, ein
bisschen komischen Begriffen ja, aber das ist die Übertragung dann.
Keine Rekursion, sondern nur Vorschleifen.
Lassen sich damit alle Programme realisieren.
Und Sie werden es vielleicht schon vermuten, oder sollten sich sagen,
das geht nicht.
Also es gibt bestimmte Funktionen, die sich eben nicht nur mit
Vorschleifen ausdrücken lassen.
Oder mit Verschachtelungen von Vorschleifen.
Sondern man benötigt eben in manchen Fällen auch eine Weilschleife.
Die hat eben noch mehr Möglichkeiten, auch länger laufende Prozesse,
die eben jetzt nicht nur polynomiell, wenn Sie sie verschachteln,
viele Iterationen dann durchführen können, ausdrücken können.
Und eben eine solche Funktion, die jetzt gezeigt hat, dass diese
Klasse der primitiv-rekursiven Funktionen, also aus heutiger Sicht die
Programme, die eben nur Vorschleifen enthalten können, dass die nicht
ausreichend sind, war eben diese Ackermann-Funktion.
Also Ackermann-Funktion, eine Funktion, die nicht in diese Klasse der
primitiv -rekursiven und schneller berechenbaren Funktionen fällt,
sondern die eben sehr so schnell wächst, dass sie sich nicht mehr mit
diesem einfacheren Formalismus oder Vertragen eben nur mit
Vorschleifen darstellen lässt.
Genau, und die Funktion, die ist jetzt hier auch nochmal
aufgeschrieben.
Was macht die?
Im Normalfall hat die zwei Parameter, eben dieses m und n oder hier
mit i und j bezeichnet.
Und letztendlich ist die Idee, die dahinter steckt, dass man in der
Arithmetik ja auch eine gewisse Hierarchie hat von Funktionen, die
immer schneller wachsen.
Also Sie können mit der Addition anfangen, die wächst relativ langsam,
die Multiplikation wächst schon schneller, wenn Sie da eben größere
natürliche Zahlen reinstecken.
Wenn Sie dann exponieren, also wenn Sie n hoch m berechnen, das wächst
nochmal schneller und daraus können Sie eben so eine Hierarchie
aufbauen, dass Sie dann eben über Exponentiation nochmal drüber gehen
und zum Beispiel eben die nächste Stufe sagen, das gibt einem, wie oft
Sie exponieren sollen.
Also Sie praktisch so eine aufsteigende Kette haben von Exponentiation
und das machen Sie eben n mal und n ist dann der Parameter Ihrer
Funktion.
Also das ist die Idee, die hinter dieser Ackermann-Funktion steckt, um
da eben schrittweise zu immer schneller wachsenden Funktionen für
einen Parameter zu kommen.
Und das lässt sich dann eben zum Beispiel so dann ausdrücken, wie hier
das jetzt der Fall ist.
Okay, also letztendlich was wichtig ist, ist die Ackermann-Funktion
wächst extrem schnell und die inverse Ackermann-Funktion, das hat eben
extrem langsam und wenn man sich mal anschaut, wie die sich für
praktikable Werte von m und n verhält, dann ist es so, dass die
praktisch fast als Konstante betrachtet werden kann und die Werte
eigentlich auch in allen fünftigen Fällen zum Beispiel unter 5
bleiben.
Jetzt schauen wir uns kurz mal ein Beispiel an.
Also hier oben sind die ersten drei Zeiten nochmal die Definitionen
wiederholt.
Also wo sich die Definitionen leicht unterscheiden, ist zum Beispiel
hier in dem Basisfall, dass man hier a von 1j ist einfach 2 hoch j in
dem Fall, das kann man auch anders definieren.
Aber letztendlich geht es um diese Grundeigenschaft des schnellen
Wachstums, die für die Ackermann-Funktion eben eine Rolle spielt.
Und dann ist eben hier definiert, dass a i 1 ist eben dasselbe wie,
also hier haben wir den rekursiven Aufruf a i minus 1 und der zweite
Parameter geht 1 hoch auf 2.
Wenn Sie für beliebiges a j das betrachten, dann wird es nach dieser
Eigenschaft berechnet, also wenn das j weiger oder größer ist.
Und wenn wir uns dann anschauen, a 2 1, das wäre diese Zeitdefinition
hier, das ist gleiche wie a 1 2, das ist dann 2 hoch 2.
a 2 2 wäre dann schon 2 hoch 2 hoch 2.
a 2 3 wäre eben dieser Turm von Exponentiation 1 höher noch.
Und eben entsprechend hier, wenn man den ersten Parameter auf 2 lässt
und mit dem zweiten hoch geht, gibt es hier diesen Turm von
Exponentiationen.
Wenn Sie den ersten Parameter größer werden lassen, dann wächst das
Ganze noch extrem viel schneller.
Also dann ist schon das a 3 1 schon 2 hoch 2 hoch 2.
Und a 3 2, also wenn Sie hier bei der 3 bleiben und hier den zweiten
Parameter 1 höher machen, dann sind Sie schon bei a 2 16.
Also das wäre so ein Zweier-Exponentiationsturm, wo Sie 16 mal hoch 2
rechnen.
Also da sieht man schon, dass die eben extrem schnell wächst.
Und bei a 4 1, da kann man es dann fast schon nicht mehr vernünftig
aufschreiben, was der Funktionswert hier wäre.
Also das können Sie gerne noch mal programmieren, oder wahrscheinlich
findet man auch Werte von der argument-Funktion für kleine Werte im
Index.
Okay, also die Laufzeit von Union Find ist extrem gut.
Das ist eben nicht ganz linear, aber fast linear, was man da in der
Laufzeit benötigt.
Und das Einbauen in den Großkarl-Algorithmus, das war unser
Ausgangspunkt.
Wir hatten einen Großkarl-Algorithmus, wo wir eben einerseits die
Sortieroperationen haben, andererseits also hier dieses Sortieren der
Kanten in aufsteigender Ordnung.
Andererseits hatten wir diese Union-Repräsentanten-Vergleichs
-Operation, also gehören zwei Knoten, u und v, zum selben Teilbaum,
den man bis dahin aufgebaut hat.
Und das können wir dann eben mit dieser Union Find-Datenspritz
durchführen, indem wir hier einfach diese Find-Operationen aufführen.
Und wenn sie noch nicht in derselben Komponente sind, dann wird eben
die Kante zugenommen und die beiden Heilmengen vereinigt.
Okay, und hier steht noch dran, dass auch die Link-Funktion reichen
würde.
Also wir haben diese Union-Funktion, die hat noch eine Vorbedingung
gehabt, das können Sie nochmal nachschauen auf den früheren Folien,
dass eben diese Find unterschiedlich sein müssen und das ist hier
natürlich schon erfüllt.
Das heißt, hier könnte man sogar diese vereinfachte Version von der
Union verwenden.
Okay, und die Gesamtzeit für diesen Algorithmus ist jetzt O von M log
M.
Und warum ist es O von M log M?
Das werden ja gerade irgendwie die Ackermann-Funktionen gesehen, dass
die doch irgendwie sogar so aussieht, als ob das noch besser wäre als
M log M.
Sonst hätten wir das M mal inverse Ackermann-Funktion nur hätten.
Wo kommt hier denn die Laufzeit her?
Sie haben gerade das Mikrofon auch noch in der Hand, da können Sie das
auch gleich noch verwenden.
Wegen dem Sortieren ganz am Anfang, wir brauchen die ja in der
absteigenden Ordnung und dann in der aufsteigenden Ordnung und
deswegen muss es ja sortiert werden und dafür laufen wir das halt an.
Genau, also hier haben wir diese Sortier-Version einmal drin, die eben
O von M log M benötigt.
Wir hatten uns am Anfang der Voraussetzung auch schon angeschaut,
Sortierverfahren, die eben jetzt auf ganzen Zahlen basieren.
Denken Sie nochmal zurück vielleicht an diese Lochkarten-Maschinen,
diese CL-Maschinen, die sortiert haben, wo Sie einfach mehrfach diese
Lochkarten durchgeschickt haben.
Dieses Sortierverfahren, das haben wir auch gesehen, das arbeitet noch
schneller als M log M.
Das heißt, wenn wir jetzt hier nur ganzzahlige Gewichte haben, dann
können wir auch schnellere Verfahren noch verwenden, die eben diese
zusätzliche Eigenschaft von den Gewichten mit berücksichtigt und dann
kann man auch noch etwas besser werden als M log M.
Was wir uns auch noch überlegen können, wie muss der Graph
repräsentiert sein?
Wir hatten ja auch eine ganze Reihe von Graph-Repräsentationen
angeschaut mit Adjacenz-Matrix oder über Inzidenz-Arrays oder Listen.
Und hier ist es sogar so, dass die einfachste Variante, die wir uns
betrachtet hatten, wenn wir einfach eine lineare Kantenliste uns
abspeichern, dass das schon ausreicht.
Das Einzige, was wir machen müssen, wir müssen irgendwie diese Kanten
hier durchlaufen können oder die Kantenliste sortieren können und dazu
reicht uns eben diese ganz einfache Graph-Repräsentation.
Also wir müssen nicht jetzt einen bestimmten Pfad durch den Graph zum
Beispiel finden, sondern einfach nur die Kanten in einer bestimmten
Reihenfolge haben.
Also sehr einfache Graph-Repräsentation reicht aus und die Laufzeit
ist auch relativ schnell.
Auch noch mal eine kleine Anmerkung dazu, wir haben jetzt dann mit
diesem Algorithmus zwei verschiedene Arten von Bäumen.
Einerseits eben unseren Ergebnisbaum, den wir berechnen, diesen
Minimal Spanning Tree oder wenn der Graph zerfällt, haben wir so einen
Minimal Spanning Forest, der aus mehreren Bäumen besteht und die
entsprechen dann eben auch den Partitionen von unserem Graph und
gleichzeitig haben wir dann zusätzlich noch Partitionen innerhalb
jeden Graphs, während der läuft und in diesem Graph haben wir dann
wieder auch noch mal eine Darstellung über diese Parent-Knoten, die
uns eben für diese Union-Find-Datenstruktur angeben, wie wir zu dem
Repräsentanten kommen und es gibt uns dann noch einen zweiten Baum,
eben diese sogenannten Rooted Trees.
Jeder dieser Bäume hat eben eine einzelne Wurzel und das heißt, wir
haben dann eigentlich immer zwei Bäume, mit denen wir hier dann zu tun
haben.
Einerseits diesen Minimal Spanning Tree oder Forest, den wir aufbauen
und andererseits eben noch mal einen Baum, der über diese Parent
-Relation im Union-Find-Algorithmus vorhanden ist.
Aber das ist eher so eine Randbemerkung, dass wir eben hier zweimal
ähnliche Dinge haben.
Okay, jetzt schauen wir uns noch kurz an, wie das in einem Beispiel
jetzt aussieht.
Also hier oben von links nach rechts haben wir unseren Booskal
-Algorithmus, der uns den Baum, den Minimal Spanning Tree aufbaut und
hier unten haben wir die entsprechenden Datenstrukturen dazu.
Also hier oben soll dieser Rank angegeben sein für jedes Element und
hier unten dann diese entsprechenden Parent-Pointer.
Und die Initialisierung war ja so, dass wir die Ranks alle auf null
gesetzt haben und die Parent-Pointer immer auf das eigene Element
jeweils gezeigt haben.
Und das heißt, wenn wir hier jetzt anfangen, den Algorithmus ablaufen
zu lassen, dann haben wir eben hier diese eine Kante mit geringstem
Gewicht, die von 2 nach 4 geht.
Das heißt, wir haben jetzt diese zwei Teil-Minimal-Spanning-Trees, die
aus einem Knotenbestand haben, verbunden.
Da müssen wir jetzt den Rank eben entsprechend anpassen.
Wenn beide Rank 0 hatten und wir zwei Bäume verbinden, dann bekommt
das einen größeren Rank, Rang 1.
Und wir tragen auch den Repräsentanten-Link entsprechend ein, also
Knoten 2 enthält einen Link auf Knoten 4.
Und wir sehen dann jetzt eben hier damit, dass 4 und 2 in derselben
Partition liegen oder im selben Teilbaum.
Wenn wir eine weitere Kante einfügen, die zwischen 1 und 3, die hat
dann ja jetzt als nächstes das geringste Gewicht, dann machen wir von
1 eben auch eine Kante von 3 nach 1.
Und der Rank wird hier entsprechend 1 hochgezählt in den Parent
-Knoten.
Also haben wir jetzt hier auch etwas 1.
Dann im nächsten Schritt verbinden wir 3 und 4.
Das heißt, wir haben jetzt die Vereinigung von diesen beiden Teil
-Mingen, 3 und 4.
Und dazu müssen wir jetzt eben eine Kante eintragen, die 3 und 4
verbindet.
Oder auf den Repräsentanten jeweils von dem entsprechenden Element
geht.
Also da müssen wir schauen, was ist der Repräsentant von 3.
Also hier von 3 der Repräsentant wäre 1.
Von 4 der Repräsentant ist 4.
Also fallen jetzt 1 und 4 auch in den selben Teilbaum und wir müssen
diese Teilbäume verbinden.
Und wir haben jetzt hier entschieden, dass wir von 1 nach 4 verbinden
in diese Richtung.
Beide haben ja hier den gleichen Rang, also können wir das in
beliebige Richtungen machen.
Und dann bekommt, wenn wir den von 1 nach 4 herum eintragen, ist hier
praktisch dieser Knoten 4 unser neuer Wurzelknoten in unserem Parent
-Baum.
Und deshalb wird hier eben der Rank 1 hochgezählt.
Gut.
Und das ist jetzt zum ersten Mal auch, wo dann dieser Kompress-Schritt
ausgeführt wird.
Davor wurde er noch nicht benötigt.
Wenn wir jetzt eben bestimmte Pfade haben, also wenn wir jetzt einen
Repräsentanten suchen wollen, zum Beispiel von Element 3, sehen wir,
der Repräsentant wird berechnet, indem wir feststellen, ja, erstmal
geht es zu 1 und dann von 1 geht es nach 4.
Und das geht in zwei Schritten, das heißt hier macht dann die
Kompression das aus, dass die eben aus diesen zwei Schritten nur noch
einen macht.
Und wir würden dann halt stattdessen direkt den Link, der von 3 über 1
nach 4 geht, direkt von 3 nach 4 eintragen, also hier diesen Link
hier.
Und bei 2 ist es schon so, dass der Link, der direkt nach 4 geht, für
1 auch so.
Das heißt, bei denen ändert sich nichts.
Und hier rechts hätten wir dann die Datenstruktur, die entstanden ist
mit den entsprechenden Ranks und eben auch den entsprechenden Parent
-Kanten, die jetzt durch diese Pfade-Kompression entstanden sind.
Okay, gibt es da gerade noch Fragen dazu?
Gut, scheint nicht der Fall zu sein.
Dann überlegen wir uns mal kurz, wir haben jetzt zwei Algorithmen
gesehen, die uns diesem Minimal Spanning Tree Problem lösen.
Einerseits den Jarnik-Priem-Algorithmus, das war der erste, den wir
uns letztens mal angeschaut hatten.
Der war der, der auf dieser Schnitteigenschaft beruht hat.
Das heißt, wir haben immer wieder Schnitte durch unseren Graph gemacht
und die Kante mit kleinstem Gewicht dann eben dazugenommen.
Der Algorithmus, der ist besonders asymptotisch gut für alle Werte von
m und m und ist besonders schnell, wenn m, also die Anzahl der Kanten
in dem Graph, sehr groß ist.
Also wenn wir viele Kanten haben, dann ist der Algorithmus gut.
Aber weil er eben nur n-1 Iteration benötigt.
Wenn wir uns hier bei Gruskal das anschauen, bei Gruskal müssen wir z
.B.
erstmal die Kanten sortieren.
Das heißt, wenn wir sehr viele Kanten haben, müssen wir erstmal viel
Arbeit mit den Kanten machen.
Und hier oben wäre es so, dass wir uns...
Also wenn wir sehr viele Kanten haben, trotzdem nur n-1 die Schleife
durchlaufen und wenn der Knotengrad dann auch noch gering ist, müssen
wir uns in jedem Schritt auch nur sehr wenige Nachbarn anschauen, um
da das Minimum zu finden.
Also deshalb der obere Algorithmus, der ist auch nicht gut, wenn wir
viele Kanten haben.
Und Gruskal ist gut, wenn wir relativ wenige Kanten haben.
Ausnahmevorteil ist hier, dass man nur die Kantenliste benötigt und
man kann auch spezielle Sortierverfahren einsetzen.
Und es gibt auch Varianten von Gruskal-Algorithmus, der dann auch für
große Werte von M durch N gut ist.
Wir haben uns ja das Routenplanungsproblem auch angeschaut.
Haben Sie noch im Kopf, was war denn da so?
Was war da so die Relation zwischen Kanten und Knoten beim
Routenplanungsproblem?
Sind wir da eher in dem oberen Fall, dass wir sehr viel mehr Kanten
haben oder ist es eher so, dass die ganze Zeit eine Kante so grob O
von N ist?
Was würden Sie sagen bei Routenplanung für Straßen?
Ja, vielleicht weiß doch jemand anders.
Eher O von N.
Ja, genau.
Wenn Sie sich anschauen, welche Straßenzüge es gibt, dann sind das nur
relativ wenige.
Wenn Sie sich jeden beliebigen Kreuzungspunkt innerhalb von
Deutschland anschauen, dann sind eben nicht beliebige Punkte
miteinander verbunden, sondern eher nur wenige in der Umgebung.
Also da ist man in dem Fall in dem unteren und da funktioniert das
Gruskal ganz gut.
Dann schauen wir ein bisschen noch, was es an weiteren Dingen gab.
Es gibt viele Varianten von dem Problem oder von der Lösung dieses
Problems der minimalen Spannbäume.
Es gibt zum Beispiel einen Algorithmus, der auch schon relativ alt
ist, von 1926, der das Problem in Zeit M log N löst.
Es gibt auch einen Algorithmus, der relativ neu von 1995 ist, der in
erwarteter Zeit O von M das Problem löst, der auch noch zusätzlich die
Eigenschaft hat, dass er parallelisierbar ist und auch noch
externalisierbar.
Jetzt ist die Frage, was bedeutet externalisierbar?
Hat den Begriff in dem Zusammenhang jemand schon mal gehört?
Nein, also da geht es darum, wenn man mit sehr, sehr großen Graphen
arbeitet, dass dann irgendwann mal der Hauptspeicher eben ausgeht und
dann muss man das eben auf irgendwelchen Sekundärspeicher auslagern,
also auf Festplatten oder SSDs eben, und die haben im Normalfall eine
deutlich längere Zugriffszeit als der Hauptspeicher.
Und es geht jetzt dann hier darum, dass man eben Algorithmen entwerfen
möchte, die auch in den Fällen noch schnell arbeiten, auch wenn man
Teile des Algorithmus immer wieder auslagern muss auf eine Festplatte
oder auf einen externen Speicher.
Und das sind dann natürlich nochmal zusätzliche Anforderungen.
Also Sie können dann eben nicht mehr auf ganz beliebig oder auf
beliebige Elemente schnell zugreifen, sondern Sie haben typischerweise
eben Blöcke, innerhalb von denen Sie relativ schnell zugreifen müssen
und können, also ähnlich wie so ein Cache und andere Bereiche, also
wenn Sie sehr viel hin- und herspringen, wo Sie eben nur langsam
darauf zugreifen können.
Also Sie müssen da sich dann, wenn Sie so einen externalisierbaren
Algorithmus haben wollen, dann müssen Sie darauf achten, dass Sie
möglichst lokale Zugriffe haben und nicht beliebig im Speicher hin-
und herspringen.
Und dieser Algorithmus von 1995 ist eben einer, der sich sehr gut
parallelisieren lässt und auch für solche externalisierbaren oder
externen Algorithmen auch geeignet ist.
Gut, dann gab es einen Algorithmus im Jahr 2000, der eben
deterministisch zeigt, O von M von alfaft benötigt, also nicht nur
amortisiert.
Und dann wurde gezeigt, dass es sowas wie einen optimalen
deterministischen Algorithmus gibt, der im Jahr 2000.
Und dann gab es noch eine ganze Reihe von Arbeiten auch hier am KIT
von der Algorithmengruppe von Herr Sanders zu diesem Thema, wobei auch
hier externe Algorithmen eine relativ große Rolle gespielt haben.
Also eben die, die auch auf extrem großen Datenmengen, die man nicht
mehr im Hauptspeicher halten kann, arbeiten können.
Also das sind Varianten, die im Laufe der Zeit noch entstanden sind
aus diesen Basis-Algorithmen.
Also eine kleine Anmerkung noch zu den externen Algorithmen.
Mit Datenbanken hat man ein ähnliches Problem, dass die eben auch,
solange sie im Hauptspeicher auf ihre Daten zugreifen können, sehr
schnell sind.
Also wenn man jetzt z.B.
ein Datenbank-Join, also ein Relationsprodukt berechnen möchte, das
ist etwas, was im Hauptspeicher deutlich schneller geht, als wenn man
es auf Festplatte macht.
Und da gab es dann eben auch vor ca.
10 Jahren den Trend, dass man versucht hat, möglichst alle Daten einer
Datenbank im Hauptspeicher zu halten.
Und da sind dann auch sehr große Maschinen zum Einsatz gekommen.
Es gab dann auch von SAP spezielle Varianten, die mit extrem großem
Speicher umgehen konnten.
Anfangs waren es vielleicht 500 GB Speicher.
Heute ist es so, dass sie eben auch Rechner mit einem oder mehreren
Terabyte an RAM bekommen können.
Und das hängt mit den Datenbanken zusammen, die man eben versucht,
komplett im Speicher zu halten.
Also auch Datenbanken, die eben wirklich mehrere Terabyte benötigen,
sollen im Hauptspeicher gehalten werden können, um eben nicht diese
Verlangsamung von Festplatten z.B.
zu benötigen.
Aber irgendwann mal, wenn die Daten noch größer werden, muss man dann
doch den Schritt machen und da geht es dann eben nur mit externen
Algorithmen.
Big Data ist ja auch ein Stichwort dazu, wenn Sie sich anschauen, was
in physikalischen Experimenten z.B.
an Daten anfällt.
Also solche Einrichtungen wie das CERN in der Schweiz mit dem Large
Hadron Collider.
Ich habe jetzt nicht genau die Datenmengen im Kopf, die da sekündlich
anfallen, aber das sind wirklich Festplatten, die da pro Sekunde
vollgeschrieben werden und die Daten auch zum Auswerten eben erstmal
irgendwo vorgehalten und über einen gewissen Zeitraum abgespeichert
werden müssen.
Und es sind da jetzt schon Experimente auch in Vorbereitung, wo die
Datenmengen nochmal um Größenordnung oder ein oder zwei
Größenordnungen größer noch anfallen werden.
Das heißt, die haben 10- oder 100-mal mehr Speicherplatzbedarf für
zukünftige Anwendungen aus solchen physikalischen Großgeräten.
Also da geht es häufig darum, dass die Auflösungen besser werden.
Sie haben so etwas wie Fotos praktisch mit höherer Auflösung oder
höhere Auflösung in Experimenten und brauchen eben noch mehr Daten.
Und das lässt man dann schnell in Bereichen, die sich auch von
Rechnern mit mehreren Terabyte Rahmen eben nicht mehr behandeln
lassen.
Gut, also soviel für diese minimalen Spannbäume.
Also Zusammenfassung nochmal.
Was spielt eine Rolle bei diesen Algorithmen?
Sehr interessant.
Man hat nur zwei Eigenschaften, nämlich diese Schnitt- und
Kreiseigenschaft.
Und die beiden sind die Basis von allen Algorithmen, die wir uns hier
angeschaut hatten.
Also die Kernalgorithmen basieren alle auf zwei sehr einfachen
Beobachtungen.
Und das ist etwas, was auch, wenn Sie neue Algorithmen entwerfen, eine
Vorgehensweise sein kann.
Dass Sie sich erstmal anschauen, gibt es irgendwelche Eigenschaften,
die sich kompakt ausdrücken lassen und die möglicherweise als Basis
für einen Algorithmus dienen können.
Also man kann das auch als Entwurfsprinzip dann verstehen, indem Sie
eben sich erstmal nach abstrakten Programmeigenschaften oder
Problemeigenschaften versuchen, die daraus zu finden.
Okay, dann haben wir uns genau die Beweise für diese beiden
Eigenschaften angeschaut, warum die korrekten Algorithmen ergeben.
Und wir haben uns eben diese eine sehr spezielle, effiziente
Datenstruktur angeschaut, diese Union-Find-Datenstruktur.
Also auch hier haben wir gesehen, wir hatten jetzt aus dem Algorithmus
heraus eine ganz spezielle Problemstellung, eben diese Partitionierung
von Mengen und hatten das Problem, dass wir schnell feststellen
wollten, ob eben zwei Elemente in derselben Partition sind und haben
dazu dann eine eigene Datenstruktur uns überlegt, eben diese Union
-Find -Datenstruktur.
Gut,
dann noch ein paar kleine Randbemerkungen.
Also Dijkstra, also der Algorithmus um die kürzesten Fahnen zu
berechnen, ist etwas ähnlich zu unserem ersten Algorithmus für
minimale Spannbäume.
Da werden wir nachher noch sehen, dass es da auch ein bisschen
Überbegriff gibt für diese Art von Algorithmen.
Also das sind die sogenannten Greedy-Algorithmen, die eben immer
versuchen im nächsten Schritt, den sie betrachten, den besten nächsten
Schritt auszuführen.
Bei Union-Find hatten wir uns eben diese beiden Tricks angeschaut
noch, Fahrtkompression in Union bei Rank, und genau, hatten
festgestellt, dass da diese Akkumentfunktion dann, oder die inverse
Akkumentfunktion auftaucht.
Wir haben uns nicht im Detail jetzt angeschaut, wie das zustande
kommt, oder wie der Beweis aussieht, dass die Laufzeit genau so ist,
aber genau, das wäre dann auch etwas komplexer.
Okay, damit sind wir am Ende dieses Kapitels über minimale Spannbäume
angekommen.
Und zwar geht es hier um ganz allgemein und in sehr breitem
Verständnis um Optimierungsprobleme.
Und eben um Lösungsverfahren, die sich jetzt nicht mit einem
speziellen Problem beschäftigen, also zum Beispiel irgendwelche
Fahrtoptimierungen auf Grafen, sondern Lösungsverfahren, die so
allgemein sein sollen, dass sie auf eine ganz, ganz breite Menge von
Problemen angewendet werden können.
Und das sind dann häufig sogenannte Blackbox-Solver oder Blackbox
-Löser.
Also das heißt, Sie als Anwender, der ein Problem lösen möchte, der
muss gar nicht genau wissen, wie dieses Verfahren jetzt intern
arbeitet, sondern Sie haben einfach einen gewissen Formalismus, wie
Sie Probleme beschreiben können, die eben spezifisch für diesen Solver
sind, und auf diese Art beschreiben Sie dann Ihre Probleme und der
Solver liefert Ihnen dann ein Ergebnis zu Ihrem Problem.
Also das ist schon ein deklarativer Ansatz.
Sie geben nicht an, wie das berechnet werden soll, das Ergebnis,
sondern das ist das, was in diesem Blackbox-Solver dann drinsteckt.
Der hat da eben verschiedene Verfahrenheuristiken, die den Anwender
nicht, oder zumindest grob nicht interessieren müssen.
Sie beschreiben das Problem in einer passenden Sprache und der Solver
kann dann alle Probleme, die sich in dieser Sprache lösen lassen, oder
möglichst viele davon, dann möglichst effizient lösen.
Und genau, das wäre eine sehr große Problemklasse.
Man kann das dann aber doch auch wieder, wenn man sich jetzt für
bestimmte Algorithmen interessiert, die dann auch in diesen Solvern
realisiert sind, auf bestimmte Algorithmen-Klassen nochmal dann
festlegen, oder die unterscheiden hier.
Und da gibt es dann eben Verfahren wie diese Greedy-Algorithmen, also
die ligierigen Algorithmen, die versuchen eben immer, lokal den
nächsten Schritt möglichst gut zu machen.
Dann gibt es diese Technik der dynamischen Programmierung und eben
noch weitere Verfahren wie systematische Suche oder lokale Suche und
evolutionäre Algorithmen.
Also das sind alles Verfahren, die eigentlich erstmals nicht auf eine
bestimmte Anwendung zugeschnitten sind, sondern die für sehr viele
verschiedene Probleme geeignet sein sollen.
Und diese generischen Optimierungsansätze, die wollen wir uns jetzt im
Laufenden etwas genauer anschauen.
Und als Beispiel, wie so ein Optimierungsproblem aussehen kann, also
ein solches Problem aus dieser großen Menge, die eben von so einem
generischen Solver gelöst werden können, wäre jetzt dieses Rucksack
-Problem.
Und was ist das Rucksack-Problem?
Also Sie haben einen Rucksack, der soll hier rechts angegeben sein,
durch diesen, ja, sieht eher wie so ein Eimer aus, aber genau, das ist
der Rucksack und der hat eben eine bestimmte Füllmenge.
Das heißt, Sie haben hier zum Beispiel fünf Einheiten, die Sie in
Ihren Rucksack reinpacken können, fünf Liter zum Beispiel.
Und jetzt haben Sie eine Reihe von Gegenständen, die Sie in diesen
Rucksack reinpacken wollen.
Und jeder dieser Gegenstände hat ein bestimmtes Gewicht.
Also die Größe vom Rucksack, die wollen wir auch eben in solchen
Gewichtseinheiten angeben.
Also der kann dann eben nicht fünf Liter, sondern fünf Kilogramm zum
Beispiel fassen.
Und die Gegenstände, die Sie reinpacken wollen, die haben eben ein
bestimmtes Gewicht.
Das soll jetzt hier durch die Höhe der Blöcke angedeutet sein.
Also hier dieser rechte Gegenstand, mit diesem rot-braunen Farbe, der
hat jetzt eben ein Gewicht von drei, dieser Gegenstand ein Gewicht von
zwei und so weiter.
Und jeder Gegenstand hat auch einen Nutzen.
Und dieser Nutzen ist durch die Zahl angedeutet, die eben auf den
Gegenständen hier draufsteht.
Und Sie wollen jetzt eben Ihren Rucksack möglichst optimal packen.
Das heißt, Sie müssen die Kapazitätsgrenze des Rucksacks einhalten und
wollen aber möglichst viel reinpacken, sodass eben der Nutzen
maximiert wird von dem, was Sie dabei haben.
Also wenn Sie aufsummieren, wenn Sie zum Beispiel jetzt die beiden
gelben Gegenstände einpacken, hätten Sie einen Nutzen von 25 und die
würden auch gemeinsam reinpassen.
Aber die Frage ist eben, geht es besser?
Also wie packen Sie optimal?
Also das ist jetzt vielleicht so eine bestimmte abstrakte Fassung von
dem, was Sie, wenn Sie jetzt demnächst in den Urlaub fahren,
vielleicht auch auf ähnliche Art lösen müssen.
Aber, also ein bisschen abstrakter, ein Gegenstände, die jeweils mit
Gewicht und einem Nutzen oder einem Profit versehen sind.
Und es geht darum, jetzt eben eine Teilmenge von diesen Gegenständen
auszuwählen oder zu finden, sodass die Summe dieser Gewichte unter dem
M bleibt, also in den Rucksack reinpasst und gleichzeitig soll der
Profit maximiert werden.
Das heißt, wenn wir über alle Elemente, die in dieser Teilmenge X
enthalten sind, aufsummieren, dann soll dieser Profit maximiert
werden.
Das wäre so ein typisches Problem.
Wo man sich jetzt eben ein Lösungsverfahren überlegen könnte, speziell
für dieses Problem, oder eben man versucht einen allgemeineren Ansatz
zu finden, mit dem sich eben dieses Problem, aber vielleicht noch ganz
andere, die eben ähnliche Charakteristika aufweisen, also wie eben,
dass man mehrere Gegenstände mit mehreren Eigenschaften hat und da
eben über bestimmte Eigenschaften optimieren möchte.
Also eher dieser allgemeinere Ansatz soll verfolgt werden.
Okay, und wenn man das versucht zu verallgemeinern, dann kommen wir
letztendlich bei sowas, oder können wir an der Stelle aufhören zu
sagen, wir wollen eben solche Optimierungsprobleme lösen, dann haben
wir genug abstrahiert.
Unser Optimierungsproblem sieht dann so aus, dass wir erstmal einfach
so eine Menge U von potenziellen Lösungen haben.
Also in unserem Rucksackbeispiel wären das dann alle Teilmengen von
Gegenständen.
Also entweder gar kein Gegenstand oder der erste oder dritte eben, das
wäre unser Lösungsraum.
Also das sind potenzielle Lösungen, das ist die Menge U.
Und dann haben wir die Menge L, die eben die zulässigen Lösungen
ausdrückt.
Und zulässig würde beim Rucksackproblem bedeuten, dass das eben das
Gewicht unter der Kapazität des Rucksacks sein muss, wenn Sie das
aufsummieren.
Also wir haben von allen denkbaren oder möglichen Lösungen, dann die
wirklichen Lösungen und dann haben wir diese Zielfunktion noch.
Und diese Zielfunktion gibt uns eben für jedes Element, das eben eine
wirkliche Lösung ist, eine reelle Zahl zurück, die wir versuchen
wollen zu optimieren.
Also wir suchen ein X-Stamm aus unserer Lösungsmenge L und dieses X
-Stamm soll eine optimale Lösung sein.
Und das ist eben dann der Fall, wir versuchen jetzt das zu maximieren,
also so wie wir im Rucksackproblem versuchen den Profit zu maximieren.
Das ist also dann der Fall, wenn dieses F von X-Stamm größer, gleich
ist als alle F von X für sämtliche anderen Lösungen, die möglich
wären.
Also unter den Lösungen muss das X-Stamm die Lösung sein, die eben den
größten Wert unserer Zielfunktion F ergibt.
So lässt sich das beschreiben und die Frage ist jetzt natürlich, das
ist alles noch sehr abstrakt, wir haben jetzt noch gar nicht gesagt,
wie sollen zum Beispiel unsere zulässigen Lösungen charakterisiert
werden.
Irgendwie brauchen wir da auch noch einen Mechanismus dazu und auch
nicht genau, wie wir diese Zielfunktion beschreiben wollen.
Minimierungsprobleme kann man natürlich genauso machen, indem man
einfach die Zielfunktion oder die optimale Lösung entsprechend
andersherum definiert.
Und es gibt eben viele Möglichkeiten, wie man das jetzt konkret
umsetzen kann oder auch was es an Einschränkungen noch gibt.
Also bei unserem Rucksackproblem ist es so, dass wir sagen, wir wollen
unsere Gegenstände, die wir reinpacken, oder die sind nicht
aufteilbar.
Wir können für jeden Gegenstand entweder den komplett reinnehmen oder
nicht reinnehmen.
Das ist jetzt eine Annahme, die wir bisher da reingesteckt haben.
Könnte natürlich auch sein, dass Sie sagen, ja dieser Gegenstand ist
aufteilbar, also der besteht vielleicht jetzt aus, sagen wir eine
Packung Kekse, wenn Sie vielleicht nur drei davon mitnehmen würden,
Ihnen das auch reichen.
Das ist eine Stelle, wo dieses Problem eben auch noch verschiedene
Varianten haben kann.
Indem man zum Beispiel sagt, die Lösungen enthalten eher so
ganzzahlige Lösungsanteile oder sie dürfen auch beliebige Bruchteile
enthalten.
Und das Interessante ist, wenn es sich um ganzzahlige Lösungen
handelt, dann sind es meistens sehr schwere Probleme.
Das ist meistens in dieser Problemklasse NP schwer, das heißt, die
sich von allen bekannten Algorithmen nur in Exponentialzeit lösen
lassen.
Okay, also sehr allgemeine Formulierung von Problemen haben wir jetzt,
zulässige Lösungen und Zielfunktionen.
Und dafür könnten Sie jetzt versuchen, so einen Blackbox-Solver zu
schreiben, also ein Lösungsverfahren, was Ihnen eben zumindest für
eine bestimmte, möglichst große Teilklasse dieser Probleme versucht,
diese zu lösen.
Und es gibt eben auch eine ganze Reihe von solchen Werkzeugen, wenn
Sie sich umschauen im Internet, dann finden Sie Löser, die eben
Probleme zu der sogenannten linearen Programmierung lösen.
Und sehen wir gleich noch, was es damit auf sich hat.
Oder solche Blackbox-Solver, die das nach Aussagenlogik kodieren.
Das ist auch ein Forschungsthema von mir, sich mit solchen effizienten
Verfahren zur Lösung von aussagenlogischen Problemen zu beschäftigen.
Also das ist auch eine Möglichkeit, alles nach Aussagenlogik kodieren
und dann das Problem zu lösen.
Oder eine Verallgemeinerung ist die sogenannte Constraint
-Programmierung, wo Sie eben Restriktionen in einem bestimmten
Formalismus angeben können und dann Lösungen suchen, die entweder nur
die Constraints anhalten oder zusätzlich auch noch eine bestimmte
Zielgröße optimieren.
Und solche Constraint-Solver, die finden Sie auch im Internet oder
werden auch kommerziell angeboten.
Es gab zum Beispiel eine französische Firma, ILOC hieß die, die sehr
stark und führend war, die dann von IBM auch aufgekauft worden ist.
Aber das wäre zum Beispiel ein solches Tool oder ein solcher Blackbox
-Solver, den es da gibt in dem Bereich.
Okay, bevor wir zu den Constraints kommen, schauen wir uns jetzt diese
eine Variante an, die lineare Programmierung.
Also lineare Programmierung ist vielleicht ein bisschen ein komischer
Begriff, weil da dieser Begriff Programmierung drin steckt.
Aber letztendlich ist es eigentlich nur ein bestimmter Formalismus,
mit dem Sie eben solche Nebenbedingungen oder diese Kostenfunktionen
und diesen Lösungsraum beschreiben können.
Also es hat eigentlich nichts mit Programmierung zu tun, aber hat sich
eben eingebürgert, dass für diese Probleme, also für lineare Probleme
mit einer Optimierungsfunktion, dass die eben lineare
Programmierungsprobleme genannt werden.
Und entsprechend heißt dann eben auch diese Formalisierung eines
Problems ein lineares Programm.
Das enthält eine Menge von Variablen, also zum Beispiel eben sowas wie
das Gewicht, was wir haben können.
Und es enthält eine Reihe von Constraints oder Nebenbedingungen.
Und diese Constraints, die schränken eben den Lösungsraum ein.
Und dann hat man eben ein Minimierungs- oder Maximierungsproblem.
Man hat eine Kostenfunktion, die sich eben berechnet, indem man hier
einen Vektor hat, der für die Variablen steht.
Also was wollen wir haben?
Wir haben eben unsere Lösungen sollen so aussehen, dass die eben
diesen Variablen aus dem Vektor X bestimmte Werte zuweisen.
Und dieser Lösungsvektor soll dann eben diese Nebenbedingungen
einhalten und zusätzlich die Kostenfunktion optimieren.
Und also die Kostenfunktion ist eine lineare Funktion.
Also das sieht so aus, als wenn wir den Vektor jetzt hier ausschreiben
würden.
C0X0, C0 mal X0 plus C1 mal X1 und so weiter.
Das heißt, Sie haben eine Linearkombination von den einzelnen
Variablen Ihres Lösungsraums.
Und die wird eben über diese Kostenfunktion ausgedrückt.
Und C ist eben so ein Konstantenvektor.
Also da stehen dann eben Werte drin wie 2, 3, 5 oder auch vielleicht
auch negative.
Das ist der sogenannte Kostenvektor.
Also dass Sie am Schluss eben was dastehen haben, wie die
Kostenfunktion, die Sie optimieren möchten, ist 2 mal X0 plus 3 mal X1
minus 5 mal X2 und so weiter.
Und die Constraints, die sollen auch in der Form von linearen
Gleichungen und Ungleichungen angegeben sein.
Also das heißt, Ihren Lösungsraum beschreiben Sie über lineare
Gleichungen und Ungleichungen.
Also zum Beispiel können Sie sagen, dass ich einfach mal X1 gleich X0
oder X1 muss größer als X0 sein.
Oder 2 mal X0 plus X1 muss größer als 3 mal X3 sein oder ähnliche
Dinge.
Und wenn man das auch wieder versucht, ein bisschen knapper
hinzuschreiben, dann haben wir einfach hier das Produkt von zwei
Vektoren.
Also AI wäre unser Constraintvektor, X unser Variablenvektor und das
soll eben gleich einer Konstante sein.
Das ist jetzt hier dann wieder kein Vektor, sondern einfach eine
reelle Zahl.
Und dieses komische Symbol hier in der Mitte, das soll einfach von
einer Relation stehen, wie kleiner gleich, größer gleich oder gleich.
Also so ein Constraint könnte dann eben so aussehen, genau 2 mal X1
minus 3 mal X5 und kleiner gleich 7.
Und dann haben wir eben einerseits hier diesen Konstantenvektor
wieder, wo die AIs drin stehen, die eben die Konstanten in unserer
Ungleichung ausdrücken.
Und das wäre unser Lösungsvektor X wieder.
Okay.
Und Lösungen betrachten wir hier erstmal über den reellen Zahlen.
Also das heißt, oder Sie könnten auch rationale Zahlen, dann reichen
natürlich auch aus, wenn es um lineare Gleichung geht.
Aber das heißt, Sie können auch beliebig halt mit, also nicht nur mit
ganzen Zahlen, sondern auch mit, was ich gebe, Komazahlen, also 2,5
mal X0 oder sowas arbeiten dann.
Und die Lösungen dürfen eben auch entsprechend dann, müssen nicht
ganzteilig sein, sondern dürfen auch rationale oder reell sein.
Okay.
Und dann, was ist dann unser Lösungsraum L?
Das ist einfach das, was uns sämtliche, die Werte von den Variablen X,
die uns sämtliche Ungleichungen eben oder Gleichungen einhalten.
Also all die Punkte aus A hoch N, also für jede Variable eben eine
reelle Zahl, wenn wir N haben.
Und für all diese Variablen muss eben gelten, dass, also zum einen
wird das häufig verlangt, dass die Lösungen positiv sein müssen.
Also wenn Sie eben verlegen, irgendwelche Dinge einzupacken, dann
dürfen Sie eben nicht negative Dinge in Ihren Rucksack einpacken.
Also das ist was, was häufig verlangt wird als Zusatzbedingungen, aber
auch nicht immer.
Und dann eben, dass diese Ungleichungen eingehalten sein sollen.
Okay.
Also hier haben wir jetzt Vector mal Vector.
Wenn wir jetzt natürlich eine Menge von solchen Gleichungen haben,
also hier haben wir gesagt, dass es geht, wir haben M solche
Constraints, kann man das natürlich auch als eine Matrix-Operation
darstellen.
Dann hätten wir hier so eine Matrix, die uns eben alle M Constraints
gleichzeitig ausdrückt.
Und ganz normal wieder unseren Lösungsvektor x, der bleibt.
Und hier auf der rechten Seite eben auch ein Vektor.
Das wäre dann einfach eine Matrix-Operation hier zum Beispiel.
Was wir uns auch noch überlegen können, hier bei den Relationen haben
wir hier kleine, kleine, gleich, größer, gleich, unter gleich
zugelassen.
Das können wir auch noch reduzieren.
Das reicht aus, wenn wir eines dieser Symbole haben.
Wie können wir die Gleichheit ausdrücken?
Also wenn wir Gleichheit loswerden wollen und das einfach durch die
anderen ausdrücken wollen, was machen wir dann?
Ja, die haben schon so viel gesagt, aber wenn sich jemand anderes
meldet, dann tut sie es trotzdem.
Genau, also man nimmt einfach zwei Constraints dazu.
Einmal größer gleich, einmal kleiner gleich.
Und wenn alle Constraints erfüllt sein müssen, ergibt es die
Gleichheit.
Also Gleichheit können wir auch loswerden bei den Relationen, indem
wir es einfach durch zwei Ungleichungen ersetzen.
Dann haben wir noch kleiner gleich und größer gleich übrig.
Da können wir auch noch einen davon loswerden.
Wie machen wir das?
Ja, Negation einfach.
Wir drehen überall bei den Konstanten das Vorzeichen herum.
Also alle a i hier kommen, wird das Vorzeichen vertauscht.
Bei dem b wird das Vorzeichen vertauscht.
Und dann haben wir, wird aus dem kleineren gleich immer ein größerer
gleich.
Einfach Rechenregeln für Ungleichungen.
Okay, sodass wir letztendlich uns mit einer Relation eben auch
auskommen können.
Das heißt, wir können zum Beispiel nur mit kleiner gleich alles
formulieren.
Und dann wird zum Beispiel auch hier diese Darstellung des
Lösungsraums besonders übersichtlich.
Dann haben wir nämlich hier einfach nur noch so ein System Matrix mal
Lösungsvektor gleich unseren Konstantenvektor.
Also a mal x kleiner gleich b.
Und dieses kleiner gleich ist eben die einzige Relation, die wir
benötigen.
Also das heißt, in diesem Formalismus der linearen Programmierung
können wir das auch aufschreiben dann als a mal x kleiner gleich b.
Also dann haben wir eigentlich nur noch die Matrix und diesen Vektor
auf der rechten Seite.
Und ansonsten eben dieses eine Ungleichung Symbol.
Also das wäre noch eine Variante, eine vereinfachende.
Und es wird auch häufig gemacht, dass man den Lösungsraum oder die
Constraints entsprechend einschränkt.
Oder womit diese Blackboxer umgehen können.
Okay, dann um es ein bisschen konkreter zu machen, ein Beispiel.
Wie können die Constraints aussehen?
Hier nehmen wir einfach mal an, es gibt zwei Variablen, x und y.
Und dann, genau das heißt, unser Lösungsraum wäre jetzt so, dass wir
eben einen Vektor haben, der aus zwei Elementen besteht.
Also wir sind in einem 2 in 2 Raum.
Und die heißen jetzt hier eben x und y.
Oder im Relationform wäre es halt dann x0 und x1.
Und wir haben solche Constraints wie zum Beispiel x plus y kleiner
gleich 8.
Also das ist schon eine lineare Ungleichung.
Und die würde eben hier, wenn man es geometrisch darstellt, genau
dieser Fläche unterhalb dieser Linie entsprechen.
Also alles, was hier links von dieser Linie liegt, erfüllt die
Ungleichung x plus y kleiner gleich 8.
Dann haben wir vielleicht noch einen anderen Constraint, dass 2x minus
y auch kleiner gleich 8 sein soll.
Ja, das könnte diese Gleichung hier sein.
Dann haben wir noch eine Einschränkung, dass y kleiner gleich 6 sein
soll.
Das wäre dann dieser Schnitt hier nach oben.
Sodass man eben letztendlich dann zum Beispiel an so einer grauen
Fläche hier landet.
Das wären dann eben die Lösungen des Problems.
Zusätzlich haben wir noch gesagt, wir sind zumindest in unserem
Formulismus jetzt hier nur an positiven Lösungen interessiert.
Also müssen wir uns nicht anschauen, was hier links oder weiter nach
unten passiert.
Also suchen wir in diesem grauen zugeschnittenen Raum jetzt nach einer
optimalen Lösung.
Und Optimalität heißt eben auch wieder, dass wir eine lineare
Ungleichung haben und versuchen, eine lineare Gleichung haben und
diese lineare Gleichung zu optimieren.
Also den möglichst großen Wert für diese Linie zu bekommen.
Also es könnte zum Beispiel sein, dass wir hier eine Gleichung haben,
die uns eben in diese Richtung anwächst.
Also das wäre jetzt ein bestimmter Wert, den wir haben können.
Und je weiter wir die Linie nach oben verschieben, desto höher wäre
unsere Zielfunktion.
Und das heißt, wir wären dann jetzt eben interessiert an einem Wert
innerhalb dieses grauen Bereichs, der uns eben entlang oder parallel
zu dieser Linie hier den größten Wert ermöglicht.
Und das wäre dann jetzt eben zum Beispiel dieser Wert hier oben, der
hier rauskommt, der dann diese Zielfunktion maximieren würde.
Okay, also um diese Art von Problemen geht es, die wir lösen können
mithilfe dieser linearen Programmierung.
Also lineare Ungleichungen plus, die uns den Lösungsrahmen
einschränken, auf das Graue hier zum Beispiel, plus eine Zielfunktion,
die wir optimieren wollen.
Okay, also auf die Lösungsverfahren möchte ich jetzt erst mal gar
nicht eingehen, sondern stattdessen noch zeigen, was man damit alles
an Problemen formalisieren kann.
Und zum Beispiel das kürzeste Wegeproblem in Grafen, was wir uns ja
vor ein paar Stunden angeschaut hatten.
Auch dieses Problem lässt sich eben in diesem Formalismus lineare
Programmierung ausdrücken.
Wenn wir uns mal anschauen, was hatten wir?
Das mit der Maximierung, das überlegen wir uns vielleicht im zweiten
Schritt.
Überlegen wir uns erst mal die Gleichungen.
Wir haben die Distanz, die wir jetzt eben hier in variablen ds für
jeden Knoten ablegen wollen.
Und wir haben dann einerseits eben die Gleichung ds gleich 0, also
Startknoten hat die Distanz 0 vom Startknoten.
Und für alle weiteren Knoten haben wir diese Ungleichung, dass wenn
wir schon die Distanz für den Knoten v haben, unter eine Kante von v
nach w, dass dann eben die Distanz zu dw auf jeden Fall kleiner gleich
sein muss als dieser Wert.
Das kann nicht größer sein, weil sonst könnten wir einfach diese Kante
von v nach w nehmen.
Jetzt haben wir es so als kleiner gleich formuliert.
Und das heißt, damit ist es so, dass wir jetzt praktisch erstmal hier,
um die alle einzuhalten, können wir überall 0 wählen für diese
Distanzen.
Und was man deshalb eben machen muss, um zu dem kürzesten Pfad zu
kommen, ist, dass wir jetzt eben diese Werte, die eben gerade noch
diese Optimalitätsbedingungen für den kürzesten Pfad einhalten, dass
wir die maximieren.
Also deshalb versuchen wir praktisch jeden von diesen Werten dv zu
maximieren.
Und das können wir dann zum Beispiel so ausdrücken, indem wir einfach
die Summe von den Werten nehmen.
Und indem wir die Summe eben maximieren, optimieren wir auch jeden
einzelnen Wert.
Okay, also das wäre dann eine Formalisierung dieses kürzesten Wege
-Problems.
Dann ein anderes Beispiel, was vielleicht mehr der Realität oder mehr
oder weniger der Realität entspricht oder zumindest in Varianten
ähnlich vorkommt.
Also Sie wollen zum Beispiel das Tierfutter optimieren für Ihre
Kanarienvögel.
Und Sie haben N Futtersorten, für jedes Futter haben Sie einen
bestimmten Preis gegeben.
Und Sie haben auch noch dann irgendwelche zusätzlichen Anforderungen,
dass die bestimmte Werte einhalten sollen, damit Sie dann eine gesunde
Ernährung von Ihren Vögeln haben.
Also zum Beispiel Kalorien, Proteine, Vitamine und sonstige Sachen.
Und damit enthalten es dann eben auch lineare Gleichungen oder
Ungleichungen.
Also zum Beispiel könnte es sein, auch so etwas wie Sorte I von Ihrer,
oder Ihre Futtersorte I enthält, so und so viel Prozent des täglichen
Bedarfs für diese Anforderung J.
Also zum Beispiel ein Vitamin C.
Okay, und genau damit kann man dann eben auch so ein
Ungleichungssystem aufstellen und dann wieder versuchen, es zu
optimieren.
Und hier sieht man, es gibt jetzt eben hier eine ganze Reihe von
Größen, die einfließen.
Also außer den Futtersorten oder den kostenden Futtersorten, eben noch
diese Eigenschaften jeder Futtersorte, die eben aus einer ganzen Reihe
von Komponenten besteht.
Also eben diese Dinge wie Kalorien oder Vitamine oder sonstige Dinge.
Und was Sie dann jetzt versuchen können zu optimieren, wäre eben der
Preis für eine gesunde Ernährung der Vögel.
Und das lässt sich dann auch wieder als so ein lineares
Programmierungsproblem beschreiben.
Also das ist jetzt vielleicht ein bisschen ein künstliches Beispiel.
Wahrscheinlich wird niemand jetzt mit einem linearen
Programmierungsholder versuchen, die Optimierung seiner Haustiere oder
die Ernährung seiner Haustiere zu optimieren.
Aber es gibt natürlich zum Beispiel in der industriellen Produktion
eine ganze Reihe von Problemen, die auch sehr ähnliche Eigenschaften
aufweisen.
Also das sind dann eben nicht die Kosten für Futter, sondern um ein
bestimmtes Produkt herzustellen.
Und die Anforderungen sind dann eben auch nicht die Kalorien oder
Proteine, sondern vielleicht der Materialeinsatz, der erforderlich
ist, oder die Arbeitszeit, die erforderlich ist.
Und Sie können sich jetzt auch vorstellen, es gibt wirklich sehr viele
Probleme, die in diese Klasse reinfallen.
Und deshalb sind diese Solver auch sehr wichtig.
Und es gibt im Grunde genommen auch in dem ganzen Bereich, der auch in
der Wirtschaftsinformatik eine Rolle spielt, wie dieses Operations
Research, was sich auch mit solchen Verfahren beschäftigt.
Gut, an der Stelle machen wir Schluss für heute.
Am Mittwoch sind dann wieder Saalübungen und wir sehen uns dann
nächste Woche Montag wieder.
Dankeschön.