Ja, schönen guten Morgen.
Es ist die letzte Übung des Jahres.
Freut man sich.
Es geht wieder um Horker-Kühlen.
Dieses Mal habe ich eine ganze Vorführung.
Ich habe einen Algorithmus geschrieben.
Ich will jetzt sagen, das soll irgendwie was machen.
Wie kann ich das alles spezifizieren und dann nach und nach
systematisch zeigen, dieser Algorithmus ist auch korrekt.
Also ganz von Anfang bis Ende wird es nur um diesen Algorithmus hier
gehen.
Und damit es nicht wahnsinnig kompliziert ist, ist das eigentlich
etwas, was Sie vielleicht kennen.
Ich würde tippen, dass die meisten das kennen.
Ja, Fakultät.
Unten sehen Sie zum Beispiel die Definition.
Wenn Sie das nicht kennen, Y-Fakultät soll das Produkt von den Zahlen
von 1 bis Y sein.
Y ist irgendwie eine positive Zahl, vielleicht die Null.
Für die Null, die Null-Fakultät ist 1, dann ist das Produkt leer.
Man definiert das eben so.
Wie kann ich das berechnen?
Ich kann die Zahlen nehmen und dann nach und nach multiplizieren.
Und hier, also man kann das irgendwie von 1 bis Y aufzählen und dann
multiplizieren.
Man kann auch von hinten anfangen, also mit Y anfangen und dann mit Y
-1, Y-2 und so weiter multiplizieren.
Das ist, was hier eigentlich gemacht wird.
Ich habe gesagt, leeres Produkt, das ist die 1.
Also wenn Y gleich 0 ist, dann will das, dass das die 1 ist.
Deswegen mein Zwischenergebnis Z hier ist auf 1 initialisiert und in Y
speichere ich gerade, welche Zahl ich damit demnächst jetzt
multiplizieren will.
Und dann gehe ich in dieser Schleife so weiter, wie ich Zahlen zu
multiplizieren habe.
Also solange dieses Y jetzt nicht die Null ist, dann mache ich weiter,
multipliziere ich Z damit und Y wird integrimentiert.
Damit man sich sicher ist, Y wird nicht jetzt minus 1 oder so
komisches sein.
Das haben wir verboten, weil hier soll es nur um Variablen gehen, die
nicht negative ganze Zahlen sind.
Außer in Null.
Deswegen, damit man sicher ist, habe ich dieses Deck da.
Also Y wird garantiert nicht echt kleiner als Null sein.
Das können wir uns einig sein.
Das ist der Algorithmus vorgestellt.
Wenn man möchte zeigen, jetzt muss ich irgendwie eine Spezifikation
dafür schreiben, zu sagen, wann wird dieser Algorithmus korrekt sein,
was soll er denn tun, was soll am Ende doch gelten.
Am Ende will ich ja, dass in meinem Z Y-Fakultät gespeichert ist.
Das war immer der Zwischenwert und am Ende der Berechnung soll der
Zwischenwert gleich der Elementwert sein.
Das ist natürlich logisch.
Und das ist meine Nachbedingung.
Und ich brauche jetzt noch eine Vorbedingung beim Horker.
Was könnte sich an denen anbieten?
Ich würde normalerweise in der Vorbedingung was schreiben, was ich
jetzt annehme für meine ganze Berechnung.
Aber hier brauche ich eigentlich gar nichts anzunehmen.
Ich habe schon alles da.
Also diese Variablen sind schon aus diesem Wertebereich und das wird
immer funktionieren.
Deswegen brauche ich nicht zu fordern.
Und anstatt jetzt eine leere Vorbedingung zu haben, was man schreibt,
das würde jetzt nicht viel Sinn machen im Horker.
Ich brauche irgendwelche Formeln da, sonst kann ich nicht darüber
reden.
Deswegen muss man was schreiben, da schreibe ich irgendwas
Allgemeingültiges.
Also jetzt 0 gleich 0 oder so.
Ich könnte genauso Y ist gleich Y oder was auch immer geschrieben
haben.
Das würde jetzt keinen Unterschied ausmachen.
Das ist jetzt eine möglichst schwache Bedingung.
Schwacher als allgemeingültig geht gar nicht.
Das muss in jeder Interpretation gelten.
Also Schwache hätte ich jetzt nicht da.
Dann habe ich dieses Triple da.
Wie letztes Mal habe ich gesagt, man hat ein Triple.
Man hat ja einen Algorithmus, da hat man eine Spezifikation dafür
geschrieben.
Jetzt habe ich ein Hortriple und jetzt arbeite ich weiter nur im
Horker -Kühl.
Denke ich gar nicht mehr an Algorithmus oder so.
Und ich brauche irgendwie eine kleine Strategie, wie ich das jetzt
nach und nach arbeite.
Ich kann nicht irgendwie anfangen, muss irgendwo anfangen.
Und das erste, was ich merke hier, ich muss irgendwie diese
Weilschleife damit irgendwas machen im Horker-Kühl.
Und bei unserer Regel für die Weilschleife, da war es eben so, dass
wir diese Variante I brauchen.
Das müssen wir irgendwie festfinden.
Irgendwie muss das da sein, sonst würden wir die Regel für die
Weilschleife gar nicht anwenden.
Das ist eben so.
Die anderen Regeln sind natürlich einfacher.
Zum Beispiel, wenn man jetzt mit Zuweisungen anarbeitet, dann nehme
ich die Nachbedingungen, ersetze ich da weiter und weiter.
Da kann ich irgendwas machen.
Aber bei der Weilschleife, da habe ich keine andere Wahl, als diese
Variante zu finden.
Letztes Mal hatte ich auch ein Beispiel mit einem Algorithmus, wo eine
Schleifenvariante nötig war.
Da habe ich gesagt, das fällt einfach vom Himmel.
Deswegen, ja, Variante I.
Und man fragt sich, ja, muss man denn so kreativ sein, eine Variante
zu finden?
Gibt es nicht vielleicht, dass man systematisch vorgehen kann oder ein
Computerprogramm, da gebe ich die Schleife ein und da liefert mir, ja,
das ist die Variante, Schluss.
Könnte man sich vielleicht wünschen, ein Algorithmus oder so.
Das gibt es aber leider nicht.
Es gibt keinen Algorithmus, sodass, egal welche, für beliebige
Schleifen, für beliebige Algorithmen, dass sie da eingeben, dann auch
eine Schleifenvariante herausspucken wird, die für die Beweise gut
sind.
Also diese gute Variante ist auch wichtig.
Dazu kommt noch mehr in der nächsten Folie.
Aber dass es keinen solchen Algorithmus gibt, ist auch irgendwas ganz
überraschend vielleicht.
Was die eigentlichen Gründe dafür sind, das lernen Sie zum Beispiel in
TGE und Formalsystemen.
Am Ende der Vorlesung werden wir noch irgendwas dazu sagen.
Es gibt auch ein Forschungsgebiet, das arbeitet mit solchen Varianten
zu finden, obwohl das jetzt im Allgemeinen nicht geht.
Es kann aber auch sein, dass es für manche Schleifenstrukturen doch
geht.
Irgendwie kann ich irgendwas finden, das wäre vielleicht eine mögliche
Variante.
Das ist jetzt Forschung.
Genau, was heißt denn das Gute?
Man kann eigentlich immer eine Variante angeben.
Gibt es immer.
Zum Beispiel der allgemein gültige Formel.
Das wird vor der Schleife gelten, das ist allgemein gültig.
Das wird mitten in der Schleife nicht verändert werden.
Man kann jetzt nicht allgemein gültiges zerstören irgendwie.
Weil das gilt in jeder Interpretation.
Egal, was ich mit den Variablen mache, die Variablenbelegung ändere,
werde ich das nicht zerstören können.
Das ist immer noch allgemein gültig.
Deswegen gilt das immer noch.
Nach der Schleife ist das ganze Variant.
Was ist das Problem da?
Das kann ich jetzt nicht verwenden.
Ich will irgendwie zeigen, am Ende der Schleife gilt dieses I.
Und aus diesem I, und dass die Schleifebedingung für uns jetzt I
größer 0 nicht gilt, dann soll am Ende gelten, dass mein Algorithmus
korrekt ist.
Also ich brauche irgendwie, dieses I soll irgendwelche Informationen
kodieren, mit denen ich am Ende des Beweises noch schließen kann, dass
die Nachbedingung gilt.
Das klingt gut.
Aber man hat immer diesen Kompromiss.
Ich kann mehr und mehr beweisen, aber wann höre ich auf?
Also ich fange mit, falls es allgemein gültig ist, dann habe ich
stärkere und stärkere Implikationen.
Und dann irgendwann werde ich eine Schleifeinvariante haben, die
ausreicht.
Mehr brauche ich eigentlich nicht.
Ich kann jetzt beweisen, offene Probleme aus der Mathematik da
mittendrin beweisen, aber das brauche ich jetzt für meinen Horker-Kühl
-Beweis eben nicht in diesem Kontext.
Dann werde ich das auch nicht nutzen.
Also es lohnt sich nicht, jetzt möglichst starke Varianten zu fordern.
Die müssen immer irgendwie stark genug sein.
Deswegen ist es auch so schwer, Varianten zu finden.
Das muss irgendwie nicht trivial sein, aber das darf irgendwie nicht
so kompliziert sein.
Das muss irgendwie das richtige Maß an Komplexität haben.
Das ist, was ich dazu sagen wollte.
Ich habe gesagt, das geht nicht im Allgemeinen, aber vielleicht kann
man irgendwie was machen, damit man doch zu einem Variante kommt.
Und eben die Situation ist die, die Variante soll so sein, dass dieses
Drehpedal links gültig ist.
Und am Ende will ich noch zeigen aus i und nicht, i ist größer als 0,
dann folgt meine Korrektheit des Algorithmus.
Und man hat die Wahlregel, kann man anwenden.
Jetzt ist es schwer, diese Regel anzuwenden.
Ich stelle mir vor, ich habe dieses i schon, dann kann ich das schon
anwenden.
Dann kann ich jetzt mit diesem Rumpf arbeiten.
Jetzt habe ich nicht eine Steife mehr, sondern ich habe nur diesen
Rumpf stehen.
Und jetzt kann ich mir so vorstellen, ich habe den ganzen Algorithmus
fast bis zum Ende durchgeführt.
Bis zum letzten Durchlauf, steifen Durchlauf.
Und dann stelle ich mir vor, ich bin da, was muss denn da gelten?
Dann ist das, ich bin fast mit dem Schleife fertig.
Ja, dann muss das i eben gleich, also wenn ich das ausführe, das ist
der letzte Schleifendurchlauf.
Am Ende will ich ja, dass z mein Zwischenergebnis hat, das Ergebnis,
das war eben so, was wir wollen.
Am Ende des Algorithmus.
Und die Schleifenbedingung wird dann nicht mehr erfüllt.
Also das i wird gleich 0 sein.
Dann wird die Schleife nicht nochmal ausgeführt, weil das der letzte
Durchlauf ist.
Dann kann ich jetzt, und vorher muss i gleich 1 sein, das weiß ich
noch.
Weil i wird nur einmal dekrementiert hier.
Und jetzt kann ich mir, kann ich das Zuweisungssystem anwenden.
So wie letztes Mal, jetzt von unten nach oben irgendwie systematisch
vorgehen.
Das i durch neg von i ersetzen.
Und an dieser Stelle da in der Mitte, ich brauche irgendwie, dass das
i größer als 0 ist.
Sonst i dekrementiert, also wenn i gleich 0 ist, dann wird das immer
noch gleich 0 sein.
Das will ich jetzt nicht.
Und ich weiß, dass das nicht der Fall ist.
Weil ich weiß in meiner Vorbedingung, dass i gleich 1 ist.
Das weiß ich, weil das der letzte Schleifendurchlauf ist.
Dann kann ich das voraussetzen.
Dann verarbeite ich jetzt fort mit dem z.
Dann für z schreibe ich z multipliziert mit i.
Dann weiß ich, ja, es muss z mal 1 gleich y sein, y-Fakultät sein, das
i gleich 1.
Das hat mir nicht Willis gesagt, mit 1 multiplizieren.
Was soll das sein?
Aber das lasse ich einfach so stehen, weil ich kann dieses Spielchen
nochmal machen.
Ich kann mir jetzt vorstellen, ich habe nicht den letzten Durchlauf
gemacht, sondern ich habe noch einen Durchlauf davor.
Das i am Ende soll gleich 1 sein.
Dann kommt noch der letzte Durchlauf.
Und vorher ist i gleich 2, weil ich dann zwei Durchläufe mache.
Dann mache ich wieder diese ganze Geschichte von eben.
Mit dem Vorgehen und so weiter.
Dann finde ich jetzt heraus, vor diesem vorletzten Durchlauf, da muss
z mal 2 mal 1 gleich y-Fakultät sein.
Habe ich das herausgefunden?
Dann kann ich das wieder machen.
Wenn ich voraussetze, dass das 17 groß genug ist.
Das ist im Allgemeinen so.
Jetzt habe ich z mal 3 mal 2 mal 1 auf der linken Seite stehen.
Und jetzt merke ich, das wird immer größer und größer.
Und einer Weise, dass ich das voraussagen kann.
Das kann ich mir jetzt...
Auf der rechten Seite, wenn ich das y-Fakultät umschreibe, da habe
ich, also dieser letzte Teil, da habe ich im y-Fakultät stehen.
Und jetzt im Allgemeinen, ich habe das z da, das ist das vordere Teil.
Und dann auf der rechten, dann muss ich das mit noch welche Zahlen
multiplizieren und dann habe ich das y-Fakultät.
Und dann im Allgemeinen, was muss dieser rechte Wert sein, dass ich
mit z multipliziere, das ist eben y-Fakultät.
Jetzt fällt doch eigentlich vom Himmel, muss man sich doch mal
überlegen, dass das doch gilt.
Aber hier habe ich tatsächlich mehr Informationen, als wenn ich mir
einfach die Schleife anschaue und sage, was könnte denn ein Inverant
sein.
Hier habe ich damit gearbeitet, ich habe gesehen, was hat der
Algorithmus da gemacht, was macht die Schleife eigentlich, jeder
Durchlauf.
Und dann habe ich Informationen gefunden, jetzt kann ich denken,
wissen und dann habe ich mehr Informationen, mit denen ich jetzt zu
einem Inverant kommen kann.
Das ist so ein Tipp für Sie vielleicht.
So, dann haben wir das.
Und das verspreche ich jetzt, das war der schwierigste Teil.
Der Rest ist eigentlich nur automatisch irgendwie Heuker-Köhle
anwenden.
Weil dann habe ich meine Strategie von eben, ich will zeigen, wenn ich
diesen Inverant habe, dann muss ich zeigen, dass vor der Schleife das
alles noch klappt, bis zu meinen Vorbedingungen.
Das muss ich noch zeigen, dass für die Schleife das ein Inverant ist,
muss ich tatsächlich noch machen.
Und dann kann ich hintereinander Ausführungen anwenden, um das Ganze
jetzt zu verkürzen.
Um die zwei Hortribbel zu kombinieren.
Und am Ende muss ich noch zeigen, ja, aus dieser Inverant und aus den
Bedingungen, die nicht mehr gilt, dann wird folgen, dass der
Algorithmus korrekt ist.
Ja, so machen wir das.
Nach und nach vor der Schleife ist das gar nicht so schwierig.
Da habe ich wieder die Inverant, die unten stehen.
Und ich habe diese zwei Anweisungen am Anfang.
Dann brauche ich nur diese Zuweisungsaktion jetzt zweimal anzuwenden.
Wo das i steht, schreibe ich jetzt y.
Und wo das z steht, dann schreibe ich jetzt 1.
Und dann habe ich y-Fakultät ist gleich y-Fakultät.
Ja, das ist auch allgemeingültig.
Das ist das Äquivalent zu dem 0 gleich 0.
Dann habe ich das abgehakt.
Ich muss noch zeigen, das war eine Variante.
Ich brauche ein bisschen mehr Arbeit.
Jetzt schreibe ich das da, was ich zeigen muss.
Diese Variante schreibe ich vor der Schleife, nach der Schleife.
Nach der Schleife sollen auch die Bedingungen nicht gelten.
Dann habe ich diese Schleifenregel.
Fange ich einfach an.
Dann muss ich zeigen, dieses Triple da in der Mitte ist gültig.
Das wird ja nur eine Zuweisungsaktion mehr anwenden.
Dann fange ich unten an, wo das i steht, schreibe ich DEC von i.
Dann muss ich noch fordern, dass i echt größer 0 ist.
Das weiß ich, dass das gelten wird.
Ich kann immer mehr voraussetzen im Heukalkül, wenn ich von unten nach
oben gehe.
Das ist die Verstärkungsregel.
Das hatte ich letztes Mal auch davon erzählt.
Man kann immer mehr fordern.
Ich muss darauf aufpassen, dass ich nicht zu viel fordere, dass das
mit der Vorbedingung nicht mehr zu vereinen ist.
Das muss ich noch aufpassen.
Aber hier, das ist eben die Bedingung am Anfang der Schleife.
Da habe ich nicht viel gefordert, wenn ich jetzt sage, i soll echt
größer 0 sein.
Dann jetzt, wo z steht, schreibe ich z mal i.
Jetzt wird das i mit dem i-1-Fakultät zusammen.
Kann ich das anders schreiben?
Das ist die Fakultät und dann habe ich die Variante da.
Das ist auch nicht schwer.
Dann habe ich zwei Trippel.
Ich kann die zusammenbringen mit der Hintereinanderausführung.
Dann muss ich noch am Ende zeigen, wenn die Variante gilt und die
Bedingung für die Schleife nicht gilt, dann folgt diese Nachbedingung.
Mehr kann ich jetzt nicht zeigen.
Ich habe jetzt den ganzen Algorithmus durchgegangen und jetzt muss ich
nur diese Nachbedingungen zusammenbringen.
So, wie geht das?
Das arbeitet jetzt nicht mit einer Anweisung im Algorithmus, nur die
Bedingungen umzuformen.
Also wenn diese Bedingung nicht gilt, i ist echt größer 0, dann weiß
ich, i muss gleich 0 sein, weil das i war in 0.
Und das haben wir immer eingehalten.
Am Ende gibt es nur einen Wert, der möglich ist.
Wenn i gleich 0 ist, dann setze ich das auf der linken Seite ein.
Dann ist 0 Fakultät da.
0 Fakultät hatte ich am Anfang gesagt.
Das ist gleich 1, das ist so definiert.
Dann habe ich die Nachbedingung, die da stehen sollte, dann auch da
stehen.
Dann habe ich das abgehakt.
Das ist das Ende der Übung.
Vielen Dank für die Aufmerksamkeit.
Schöne Feiertage.
Alles Gute.
Wir sehen uns im nächsten Jahr.
Schönen guten Tag.
Herzlich willkommen zur letzten Vorlesung.
Grundbegriffe der Informatik im Jahr 2019.
Wir hatten das letzte Mal angefangen, uns für eine algorithmische
Aufgabenstellung in gerichteten Graphen anzugucken.
Nämlich Berechnung der Wegematrix.
Also herauszufinden, für jedes Knotenpaar, wenn ich einen gerichteten
Graphen gegeben habe, gibt es einen Pfad, welcher Länge auch immer,
von einem Knoten zu einem anderen.
Und das für alle Knotenpaare.
Die Idee war, was soll man sonst tun?
Die Erreichbarkeitsrelation, also E ist die Kantenmenge, das ist die
Relation, wo komme ich in einem Schritt hin, wo gibt es Kanten?
E-Stern war ja definiert als unendliche Vereinigung aller E hoch I.
Also von wo nach wo komme ich in I-Schritten.
Für alle I größer gleich Null.
Und wenn man jetzt daraus irgendwie einen Algorithmus machen will, das
erste, also eine Sache, worum man sich kümmern muss, ist unendliche
Vereinigung.
Das sieht jetzt erst mal nicht gut aus.
Wie mache ich das in endlich vielen Schritten?
Wo kriege ich die Matrizen hier für die Relationen E hoch I und was
bedeutet diese Vereinigung dann, wenn ich es mit Matrizen anstelle?
Also die Vorstellung immer, wir haben den Grafen gegeben, also die
Kantenrelation durch eine Matrix, quadratisch so viele Zeilen und
Spalten, wie es Knoten gibt.
Und in Zeile I Spalte J steht eine 1, genau dann, wenn es eine Kante
gibt von I nach J und eine 0 sonst.
Und analog will man das jetzt eben für die Matrizen, also letzten
Endes auch für die Wegematrix, die Matrix, die E-Sterne repräsentiert.
Die wesentliche Beobachtung war, also wenn man wissen will, kommt man
von I nach J, man muss nicht beliebig lange Pfade angucken, denn wenn
Pfade sehr lang sind, mindestens so viele Kanten benutzen, wie man
überhaupt nur Knoten hat, dann muss man bei einem Knoten zweimal
vorbeigekommen sein, da ist mal eine Schleife gegangen, die kann man
weglassen, man kommt immer noch vom Start zum Zielknoten.
Also für die Erreichbarkeit, es genügt, sich Pfade anzugucken mit
einer maximalen Länge, Anzahl Kanten minus 1.
Längere Pfade können Sie sich angucken, aber das wird Ihnen keine
neuen Erkenntnisse geben.
Das wussten Sie vorher auch schon, dass man von I nach J kommt, durch
einen kürzeren Pfad, aber es schadet jedenfalls nichts.
Dann hatten wir uns überlegt, also wenn Sie jetzt Potenzen der
Adjacenzmatrix ausrechnen, dann haben Sie in der Kartenpotenz, in A
hoch K in Zeile I Spalt J, genau dann einfach in der Potenz, der
Matrixpotenz, haben Sie die Anzahl der Pfade stehen, genau der Länge K
von I nach J.
Und wenn Sie nur wissen wollen, gibt es einen oder nicht, dann wenden
Sie doch die Signumfunktion drauf an, die aus allen Zahlengröße gleich
1, eine 1 macht.
Und dann war die erste plumpe Idee, wo steht es denn hier, so die
Wegematrix auszurechnen.
Also es läuft dann darauf hinaus, dass man alle A hoch I ausrechnet,
von I gleich 0 bis N minus 1.
Das ist die obere Schranke, weiter müssen Sie nicht gucken.
Sie rechnen diese ganzen Matrizen A hoch I aus, jedes Mal hier erstmal
ganz naiv, ganz dumpf hingeschrieben.
Da nimmt man die Einheitsmatrix und multipliziert I mal A dran, dann
habe ich A hoch I.
Und diese Matrizen, die addiert man alle auf.
Also nach der inneren Schleife hier in M steht immer das A hoch I, die
addiert man alle auf das W, was initialisiert ist als die Matrix, wo
überall 0 steht.
Und wenn Sie alle aufaddiert haben, dann am Ende steht in Zeile X
Spalte Y die Anzahl der Pfade der Länge höchstens N minus 1 von X nach
Y.
Und was einen in der Wegematrix so interessiert ist, gibt es
mindestens einen, also wenn Sie darauf noch Signum an und dann haben
Sie die Wegematrix.
Problem bei diesem völlig stumpfsinnigen Algorithmus ist, wenn Sie
jetzt zählen, wie viel Arbeit macht das denn?
Hier ist nochmal hingeschrieben links.
Da läuft also das I von 0 bis N minus 1 und jedes Mal haben Sie hier I
-Matrizenmultiplikationen.
Also insgesamt haben Sie Summe der I von 0 bis N minus 1 mal Aufwand
für eine Matrizenmultiplikation.
Da haben wir gesagt, also gut naiv, 2 mal N hoch 3 minus ein kleines
bisschen.
Das ist der Aufwand für eine Multiplikation.
Und dann kommen noch so ein bisschen was dazu für Matrizen addieren
und Signum ausrechnen.
Und weil diese Summe der I irgendwas Quadratisches ist, insgesamt,
wenn Sie es ausrechnen, kommt irgendwas raus mit N hoch 5 plus minus
irgendwelcher Krümelkram.
Also ich bezeichne das jedenfalls als Krümelkram und behaupte, das ist
nicht so wichtig.
Für große N ist es ausreichend, wenn Sie wissen wollen, was passiert,
wenn Sie auf das N hoch 5 starren.
Die Potenz mit dem größten Exponenten.
Und N hoch 5 ist nicht schön.
Also selbst wenn das nur 1.000 mal 1.000 Matrizen sind, 1.000 hoch 5
ist vielleicht ein bisschen viel Aufwand.
Das will man nicht haben.
Also Frage, geht es schneller?
Und jetzt sind wir ungefähr da, wo wir das letzte Mal aufgehört haben.
Wenn Sie sich das von vorhin nochmal angucken, wie rechnen wir die
Potenzen A hoch I aus?
Wir fangen an bei A hoch 0, also bei der Einheitsmatrix und dann jedes
Mal rechnen wir A hoch 1, 2, 3 bis A hoch I aus.
Dann haben wir A hoch I, werfen es weg und in jedem nächsten
Schleifendurchlauf für A hoch I plus 1, wir fangen wieder an bei A
hoch 0 und dann A hoch 1, 2, 3.
Und um A hoch I plus 1 auszurechnen, man rechnet nochmal A hoch I aus.
Das hat man gerade schon mal gemacht.
Wenn man sich das gemerkt hätte, müsste man es nicht nochmal machen.
Wenn man das gemerkt hat, dann kann man das etwas einfacher so
hinschreiben.
Also diese Matrix M wird initialisiert mit der Einheitsmatrix, das ist
A hoch 0.
Das können Sie dann gleich schon mal auf W drauf addieren und dann
multiplizieren Sie es mit A, dann haben Sie A hoch 1 in M stehen im
nächsten Schleifendurchlauf, addieren Sie das gleich auf W drauf,
multiplizieren Sie es mit A, haben Sie A hoch 2, addieren das im
nächsten Durchlauf drauf und dann A hoch 3, A hoch 4, A hoch 5 und
dann jedes Mal...
Sie haben nur eine Matrizenmultiplikation um die nächste Potenz
auszurechnen, nicht I Matrizenmultiplikationen.
Und dann hat man hier also nur noch eine Schleife und N mal den
Aufwand für eine Addition und eine Multiplikation.
Und dann haben Sie im Wesentlichen nur noch N mal 2, N hoch 3, nur
noch 2 mal N hoch 4 plus ein bisschen was und nicht mehr N hoch 5 plus
irgendwas.
Und setzen Sie irgendwelche kleine Zahlen ein, Sie werden schnell
merken, 2 mal N hoch 4 ist natürlich weniger als N hoch 5.
Das lohnt sich bestimmt.
2 mal N hoch 4 statt N mal N hoch 4 Operationen zu machen.
Also hier ist man schon mal ein bisschen schneller.
Frage, geht es noch schneller?
Und ja, also das ist einem vielleicht tatsächlich wirklich noch viel
zu langsam und es lohnt sich da irgendwie was Schnelleres zu machen.
Und dann habe ich gerade schon gesagt, erinnern Sie sich noch?
Ja, wenn Sie E-Stern ausrechnen wollen, also Sie müssen nur die
Potenzen bis I gleich N minus 1, da alle vereinigen, bis E hoch N
minus 1 reicht.
Aber mehr schadet nicht.
Ja, prima.
Aber wieso kann es helfen, wenn ich längere Pfade betrachte?
Warum kann ich da auf einmal Operationen sparen?
Ja, da kommt jetzt eben so ein kleiner Kniff.
Und dieser Kniff taucht aber an verschiedenen Stellen in verschiedenen
Verkleidungen immer wieder mal auf.
Deswegen zeige ich Ihnen den hier schon mal.
Wir nehmen jetzt mal als K hier oben, nicht als obere Schranke für die
Vereinigung von den ganzen E hoch I, nicht irgendwie das N minus 1,
sondern wir nehmen die kleinste Zweierpotenz.
Also wir nehmen jetzt als K das 2 hoch M, sodass das das erste Mal
Größe N ist.
Mit anderen Worten, M ist sowas wie Logarithmus von N zu Basis 2,
aufgerundet oder so, geschenkt.
Also M sei Logarithmus von N.
Und jetzt, also worauf wir hier hinaus wollen, ist das Einsparen von
Matrizen -Multiplikationen.
Das ist das Teure, jedes Mal N hoch 3 Operationen.
Je seltener, desto besser.
Und der Trick ist, jetzt eine Matrix zu finden.
Nennen wir die mal F.
Mit der Eigenschaft, dass F hoch 2 hoch M die gesuchte Wegematrix W
ist.
Das sieht jetzt nach 2 hoch M Matrizen-Multiplikationen aus im ersten
Moment, aber ist es ja nicht.
Denn F hoch 2 hoch M, wenn das eine echte Zweierpotenz ist, können Sie
ja so hinschreiben mit Pünktchen.
Ich darf das ausnahmsweise.
Sie nehmen F, Sie quadrieren die Matrix F.
Das Ergebnis quadrieren Sie wieder, das Ergebnis quadrieren Sie
wieder.
Da müssen Sie nur M mal eine Matrix quadrieren.
Also haben Sie nur noch M, also log N Matrizen-Multiplikationen.
Und wenn wir nur noch log N Matrizen-Multiplikationen haben statt N,
dann haben wir deutlich was eingespart.
Also Preisfrage, was ist diese Matrix F mit dieser Eigenschaft?
Wenn man sie hinreichend oft quadriert und quadriert, quadriert, kommt
die Wegematrix raus.
Ja, das muss man halt eben einmal gesehen haben.
Bei der Originalmatrix, Adjacenzmatrix A, wenn Sie da die Potenzen
ausrechnen, A hoch I, da sehen Sie, wie viele Pfade gibt es genau der
Länge I.
Und jetzt bei dieser Matrix F, was wir sehen wollen, da sehen wir
nicht Pfade genau einer Länge, sondern ob es einen Pfad höchstens
dieser Länge gibt.
Und dann hat man nämlich schon gewonnen.
Und das heißt also insbesondere in F hoch I wollen wir sehen, von
welchen Knoten zu welchen Knoten gibt es einen Pfad höchstens der
Länge I, also der Länge I oder der Länge 0.
Und deswegen nehmen wir mal für F diese Relation E hoch 0 vereinigt E
hoch 1.
Also da ist drin, sind alle Paare XY mit von X nach Y komme ich in
Nullschritten oder in einem Schritt.
Über Nullkanten oder über eine Kante, über Nullkanten heißt X gleich Y
oder über eine Kante, ich habe eine Kante von X nach Y.
Also Identität vereinigt mit E, E hoch 1 ist E, E hoch 0 per
Definition ist die Identität.
Und was ist, wenn man jetzt für diese Matrix F, also die zugehörige
Relation sei E hoch 0 vereinigt E hoch 1, wenn Sie da jetzt das
Quadrat ausrechnen, dann also für Relationen hingeschrieben ist das
also E hoch 0 vereinigt E hoch 1, Relationenprodukt E hoch 0 vereinigt
E hoch 1.
Und das heißt, Sie gucken, Sie hängen hintereinander einen Pfad
höchstens der Länge 1 und einen weiteren Pfad höchstens der Länge 1.
Und das gibt Ihnen alle Pfade höchstens der Länge 2.
Denn, also man darf so rechnen hier Distributivgesetz gilt, E hoch 0,
Kringel E hoch 0 ist E hoch 0, E hoch 0, Kringel E hoch 1 ist E hoch
1, E hoch 1, Kringel E hoch 0 ist E hoch 1 und E hoch 1, Kringel E
hoch 1 ist E hoch 2.
Und dann haben Sie das halt zweimal, das E hoch 1, das schadet nicht,
dann haben Sie E hoch 0, E hoch 1, E hoch 2.
Das ist R².
Und wenn Sie jetzt das wieder quadrieren, dann rechnen Sie R hoch 4
aus, dann ist also hier E hoch 0 vereinigt 1, vereinigt 2, Kringel,
das gleiche nochmal.
Da gucken Sie jetzt Pfade maximal der Länge 2 und dahinter angehängt
noch einen Pfad maximal der Länge 2, alle Möglichkeiten.
Da kriegen Sie gleich alle Pfade maximal der Länge 4.
Und wenn Sie das dann quadrieren, kriegen Sie alle Pfade maximal der
Länge 8 und dann alle maximal der Länge 16.
Die Längen werden sehr schnell sehr groß.
Und Induktion zeigt Ihnen dann ganz naheliegend, das funktioniert für
alle M.
Rf hoch 2 hoch M ist die Vereinigung der E hoch I von 0 bis 2 hoch M.
Und das heißt, wenn man das M eben so groß wählt, dass dieses 2 hoch M
mindestens N ist, dann hat man E-Stern.
Und das heißt, man kann jetzt ein neues Programm hinschreiben.
Als erstes, Sie rechnen diese Matrix F aus, die Ihnen sagt, alles über
Pfade der Länge 0 oder 1.
Das heißt, Sie nehmen die Adverzenzmatrix und zusätzlich die
Identität.
Also Pfade der Länge 0 nehmen Sie gleich mit dazu.
Und dann rechnen Sie noch Logarithmus N aus.
Da können Sie jetzt noch fragen, wie schwierig ist es, Logarithmus M N
auszurechnen.
Na gut, also wenn Sie pingelig sind und sagen, ich möchte elementare
Operationen zählen, dann nehmen Sie halt die 2 und multiplizieren so
lange 2 dran, bis Sie mindestens bei N sind.
Und Sie zählen, wie oft müssen Sie das tun.
Da haben Sie logarithmischen Aufwand, um das auszurechnen.
Und dann hier immer F ist F Quadrat, F ist F Quadrat, quadrieren,
quadrieren, quadrieren, nur noch Log N mal Signum und Sie sind fertig.
Und dann haben Sie eben nur noch Log N Matrizen, Multiplikationen, wo
jede N hoch 3 und ein bisschen kostet.
Und dann ist der Gesamtaufwand an arithmetischen Operationen Log N mal
2 mal N hoch 3.
Und das ist nochmal, ich hoffe, dass das auch Ihr Gefühl schon ist,
deutlich weniger als 2 mal N hoch 4.
Ist Ihnen klar, dass Logarithmus N deutlich langsamer wächst als N?
Log N ist im Allgemeinen viel kleiner und Sie haben hier nochmal,
statt eines Faktors N hier bei dem N hoch 4 hier nur einen Faktor Log
N.
Das ist besser.
Und dann noch so ein bisschen Kleinkram, von dem ich hier sage, müssen
wir nicht genau darüber reden, denn im nächsten Kapitel werden wir
sehen, wie man ungenau darüber redet, aber präzise ungenau, sodass
alles Hand und Fuß hat.
Ja, dann sind wir also bei Logarithmus N mal N hoch 3 und ein
konstanter Faktor, ein kleiner und noch so ein paar kleinere Terme.
Und dann will ich Ihnen jetzt...
Dann haben wir jetzt erstmal ein erstes Mal so ein bisschen genauer in
drei Varianten gezählt, wie viele arithmetische Operationen sind es
denn, mit der Idee, das gibt hoffentlich so ungefähr wieder sowas wie
Laufzeit des Algorithmus, in Abhängigkeit von Anzahl Knoten in dem
Graphen, in Abhängigkeit von Seitenlänge der Adjacenzmatrix.
Ab und zu, also wahrscheinlich öfter, als es gut tut, werden Sie davor
stehen, dass Sie sagen, jetzt möchte ich das aber gerne schneller
haben und vielleicht wollen Sie das am liebsten ganz von Anfang an,
alles möglichst schnell, ganz gleich von Anfang an das
schnellstmögliche hinschreiben.
Tun Sie das nicht.
Schreiben Sie erstmal irgendwas hin, was überhaupt funktioniert und
dann schauen Sie, wenn Ihnen das nicht schnell genug ist, wo wird denn
noch Zeit verschwendet, in Anführungszeichen.
Das wird nicht an allen Stellen sein, da können Sie vielleicht ein,
zwei, drei Stellen identifizieren und dann gucken Sie, dass Sie die
Stellen gezielt schneller kriegen.
Und manchmal ist halt dann das Schnellste nicht unbedingt das
Naheliegende, so wie hier gerade.
Wir gucken nicht nur Pfade bis Länge n, sondern bis Länge ein bisschen
mehr, bis zu einer Zweierpotenz, weil wir dann weniger arithmetische
Operationen haben.
Ja, da muss man halt drauf kommen.
Ja, und dann will ich Ihnen zum Abschluss dieses Kapitels nicht
vorenthalten, einen noch schnelleren Algorithmus, um die Wegematrix
auszurechnen, von einem Herrn, von dem ich ehrlich gesagt nicht genau
weiß, wie man ihn korrekterweise aussprechen sollte.
Ich sage mal einfach Warschall.
Und der spart diesen Faktor log n, den wir ja gerade noch hatten vor
dem n hoch 3 auch noch ein.
Und das ist der komplette Algorithmus, dass hier vorne, also es geht
um eine Matrix W.
Am Ende ist das die Wegematrix.
Und die wird hier initialisiert.
Und dann wird irgendetwas gemacht.
Und die Initialisierung ist so, wie wir das gerade schon auch bei uns
gemacht haben.
Also man schreibt in W in Zeile I Spalte J rein.
Erstens eine 1 auf der Diagonalen, wenn I gleich J ist.
Da hat man diese Identität gleich mit dabei.
Und außerhalb der Diagonalen das, was in der Adjacenzmatrix steht.
Also eine 1 genau dann, wenn es eine Kante gibt von I nach J.
Und dann kommt die eigentliche Arbeit.
Das sind hier drei Schleifen ineinander geschachtelt.
Das erinnert so grob von Ferne von der syntaktischen Struktur an
Matrizenmultiplikation, die naive Implementierung.
Aber Vorsicht.
Also hier geht man jetzt immer durch alle Zeilen und alle Spalten der
aktuellen Version von der Matrix W.
Aber Vorsicht, das sind die inneren beiden Schleifen.
Und dann gibt es also noch so ein K.
Da probiert man alle Werte der Reihe nach von 0 bis N minus 1 aus.
Und dann für jedes K, man guckt hier also für jedes K einmal alle
Einträge in W I J an.
Und von Anfang an stehen da nur Nullen und Einsen und dabei bleibt es
auch.
Und was man macht, ist das folgende.
Der neue Wert von W I J ist Maximum von altem Wert von W I J und W I K
mal W K J.
Das heißt, wenn in W I J schon eine 1 ist, dann bleibt das 1.
Egal, was da hinten bei dem Produkt rauskommt, egal, ob das 0 oder 1
ist, was anderes kann es ja auch nicht sein.
Also wenn man erst mal eine 1 hat, dann weiß man, ist gut.
Dann weiß man ganz sicher, man kommt von I nach J.
Und manchmal ist aber bisher da eine 0 und dann schreibt man aber dann
doch eine 1 rein, wenn nämlich W I K mal W K J 1 ist.
Und das heißt, W I K ist 1 und W K J ist 1.
Und das heißt, dass es irgendwelche gewisse speziellen Pfade von I
nach K und von K nach J gibt.
Und die können sich natürlich hintereinander setzen, haben sie einen
Pfad von I nach J, haben sie sich davon überzeugt, dass es einen Pfad
von I nach J gibt.
So und ich habe Ihnen in dem Kapitel zum Horkalkül ja gesagt, also bei
Schleifen, mir hat es immer geholfen, Schleifen in Varianten zu sehen.
Und hier ist das auch so, wenn Sie sich den Algorithmus so angucken,
dann können Sie ausprobieren, Sie werden feststellen, ja der
funktioniert prima, aber also solange ich behaupte, wenn Sie
verstanden haben, warum der funktioniert, dann haben Sie auch die
Schleifen in Variante gesehen.
Und die ist aber nicht komplett naheliegend, deswegen sage ich sie
Ihnen.
Und um das schöner zu sagen, geben wir, also hier in jedem Durchlauf
von dem K wird ja eine neue Matrix W ausgerechnet, geben wir der mal
noch einen dritten Index, den ich oben in eckigen Klammern
hinschreibe, also das sind keine Potenzen, einfach noch eine
Nummerierung.
Initialisierung ist das W oben 0 und dann entstehen eben aus W oben 0
entsteht Matrix W oben 1 und aus W oben 1 entsteht W oben 2 und so
weiter.
Und die Behauptung ist, man kann genau sagen, in W oben 3, wann steht
da in Zeile I Spalte J eine 1 und das geht so, also stellen Sie sich
vor, Sie haben irgendeinen Pfad von irgendeinem Knoten V0 zu
irgendeinem Knoten Vm, da steht also vorne V0, hinten Vm und wenn M
größer gleich 2 ist, stehen dazwischen auch noch irgendwelche Knoten
V1 bis Vm minus 1 und die Knoten, die hier zwischen V0 und Vm stehen,
nenne ich jetzt mal Überraschungen zwischen Knoten.
Wenn M kleiner gleich 1 ist, gibt es die halt nicht.
So und Behauptung in der Kartenversion von der Matrix W in W oben K
steht genau dann der 1, wenn es einen Pfad gibt von I nach J und die
Zwischenknoten haben alle Nummern, die echt kleiner als K sind.
Also Sie gucken sich an Pfade von I nach J, die zwischendurch nur
Knoten mit kleinen Nummern benutzen.
Warum ist das wohl grob gesagt eine Invariante?
Naja, also wenn Sie von I nach J kommen und benutzen nur Knoten
kleiner gleich einer Nummer K, wie kann das sein?
Entweder Sie benutzen sogar nur Zwischenknoten kleiner als K oder Sie
gehen von I nach K und von K nach J und dazwischen brauchen Sie nur
Knoten mit kleineren Nummern und deswegen funktioniert das.
Und wenn Sie jetzt am Ende fertig sind, ist K N minus 1 und dann steht
da in W oben N stehen Pfade von I nach J mit Zwischenknoten, deren
Nummern echt kleiner als N sind.
Ja und eine Nummer echt kleiner als N, das sind aber alle.
Alle haben eine Nummer kleiner als N.
Die sind von zwischen 0 und N minus 1 und deswegen, wenn Sie fertig
sind, haben Sie da die komplette Wegematrix.
Also das ist eine andere Art und Weise, so nach und nach sich davon zu
überzeugen, dass es ja von irgendwo nach irgendwo irgendwelche Pfade
gibt.
Und also genau die gleiche Idee wird Ihnen zum Beispiel in einem ganz
anderen Zusammenhang vermutlich in theoretische Grundlagen im dritten
Semester wieder über den Weg laufen, wenn Sie irgendwelche Dinge mit
endlichen Automaten anstellen.
Genauer gesagt, wenn Sie aus einem endlichen Akzeptor einen regulären
Ausdruck bauen mit gewissen Eigenschaften.
Da ist genau die gleiche Idee dahinter.
Das ist irgendwie was Allgemeineres noch.
Ja ach so und der Aufwand hier ist jetzt im Wesentlichen die
Initialisierung, da muss man also N Quadrat mal, weist man jedem
Element in W erstmal irgendwas zu und dann hier hat man drei Schleifen
ineinander geschachtelt, N mal die äußere und jedes Mal N mal die für
I und jedes Mal N mal die für J macht insgesamt N hoch drei
Kombinationen K, I, J, die betrachtet werden.
Drei.
Dann haben Sie eben N hoch dreimal hier dieses Maximum von irgendwas
und irgendwas und das ist jedes Mal jedenfalls konstant viel Aufwand.
Da machen Sie irgendwie ein bisschen was mit drei Bits und fertig.
Also der Gesamtaufwand ist irgendwie so was wie N hoch dreimal etwas.
Ungefähr irgendwie.
Und wie man das genau macht, das sehen wir jetzt dann gleich im
nächsten Kapitel.
Jetzt in diesem Kapitel haben wir erstmal gesehen, ein paar
Möglichkeiten, wie man Relationen, also dann auch gerichtete
Grafenrechner repräsentieren kann, wobei wir uns das bequemste
hergenommen haben, einfach so Adjacenzmatrix, mit der kann man gut
arbeiten, auch wenn sie manchmal groß wird.
Und dann haben wir halt so ein bisschen gezählt, wie viele Operationen
braucht man auf die ein oder andere Art und Weise, um die Wegematrix
auszurechnen.
Und dann habe ich immer schon so gerechnet, ja im Wesentlichen ist das
hier das N hoch 5 plus noch ein bisschen Kleinkram oder zweimal N hoch
4 ist der dominierende Summand.
Den Rest kann man vernachlässigen.
Und das wollen wir jetzt ein bisschen genauer angucken und so ein
bisschen redeweise einführen.
Die sogenannte Groß-O-Notation, das ist das, was Ihnen am häufigsten
über den Weg laufen wird.
Wenn wir da so ein bisschen was definiert haben, gucken wir uns auch
noch mal eine Methode an, um Matrizen zu multiplizieren, die
tatsächlich besser ist als diese naheliegende Standardschulmethode mit
N hoch 3 Operationen.
Das ist dann der Algorithmus von Herrn Strassen und der ist nicht
naheliegend, wenn man ihn zum ersten Mal sieht und der ist besser und
tatsächlich so viel besser, dass in Standard-Matte-Bibliotheken auf
dem Rechner, wenn Sie da eine benutzen für Matrizenmultiplikation,
also ziemlich sicher, wenn die Matrix nicht ganz klein ist, es wird
der Algorithmus von Herrn Strassen benutzt, weil er einfach schneller
ist, spürbar.
Das ist dann ein Beispiel für einen sogenannten Teile-und-Herrsche
-Algorithmus und dann dazu reden wir dann am Ende auch noch ein
bisschen was.
Erstmal, worum geht es uns?
Messen sozusagen, wie aufwendig sind irgendwelche Rechnungen.
Hier ist die Eingabe, eine Rechnung passiert, da ist die Ausgabe, wie
viel Aufwand macht das, wie viel kostet das in irgendeinem Sinne.
Wir haben gerade immer gezählt, so Anzahl elementarer arithmetischer
Operationen mit der Hoffnung, naja, eine Addition oder eine
Multiplikation von zwei Zahlen, die kostet halt konstant viel, einen
Takt des Prozessors oder zwei, was auch immer.
Und wenn man die zählt, dann hat man irgendwie jedenfalls eine
Näherung von Laufzeit des Algorithmus für eine Eingabe.
Das ist das, was man immer gerne als erstes anguckt, aber irgendwann
merkt man, oh Speicher ist ja auch endlich und manchmal interessiert
man sich auch dafür, bei einer Berechnung, wie viel Speicherplatz wird
denn benötigt und zwar insbesondere für die ganzen Zwischenergebnisse.
An der Eingabe kann man nichts ändern, die ist halt da, so viel Platz,
wie sie halt braucht.
Die Ausgabe muss man auch sowieso erzeugen, da kann man auch nichts
daran ändern, aber zwischendurch.
Und sowohl Laufzeit als auch Speicherplatzbedarf, das sind solche
Komplexitätsmaße, um den Aufwand bei Berechnungen irgendwie
auszudrücken und diese Sorte von Komplexitätstheorie heißt im
Englischen etwas genauer Computational Complexity, im Unterschied zu,
was ist denn das kürzeste Java-Programm, das eine Problemstellung
löst.
Das können Sie sich natürlich auch angucken, das sagt Ihnen aber gar
nichts über die Laufzeit aus, das sagt Ihnen nur, wie kurz oder lang
ist das Programm.
Das ist dann Beschreibungskomplexität, da gibt es auch sehr
verblüffende Ergebnisse, genau wie bei Computational Complexity, zum
Beispiel kann man beweisen, nur mal so am Rande, es gibt Probleme, für
die gibt es keinen besten Algorithmus, also keinen schnellsten, sagen
wir mal.
Da haben Sie das Problem, da gibt es einen Algorithmus, der löst das
Problem und egal, welchen Algorithmus Sie haben, also zum Beispiel
irgendeinen, den ich Ihnen jetzt gerade gebe, es wird immer einen
anderen Algorithmus geben, der schneller ist und zwar schneller, um
mehr als einen konstanten Faktor.
Dann haben Sie einen schnelleren Algorithmus, das wird auch nicht der
schnellste sein, es wird wieder noch einen geben, der noch schneller
ist, mehr als einen konstanten Faktor und noch einen und noch einen
und noch einen und noch einen.
Also es gibt Probleme ohne schnellsten Algorithmus, der das Problem
löst.
Es gibt immer noch schnellere Algorithmen.
Sehr kurios.
Gut und in irgendeinem Sinne, man ist immer daran interessiert, dass
es irgendwie schnell geht, aber nochmal, fangen Sie nicht zu früh an
mit Optimieren, hat Ihnen, glaube ich, Frau Kuziulek, habe ich auch
schon auf irgendwelchen Folien gesehen.
Erstmal ein Programm machen und dann gucken, wo geht viel Zeit
verloren, wenn es zu langsam ist und da dann gucken, ob man was
verbessern kann.
Jetzt hier ganz, ganz komplizierte Aufgabenstellung.
Sie haben eine Zahl, Dezimalzahl Darstellung, so K-Ziffern und Sie
wollen eins drauf addieren.
Frage, wie oft müssen Sie so elementare Operationen mit einzelnen
Ziffern machen?
Na ja, wenn Sie jetzt hier auf 3199 eins drauf addieren, neun und eins
gibt zehn und eins Übertrag, haben wir wieder neun und eins gibt zehn
und eins Übertrag, eins und eins gibt zwei.
Okay und dann hat man es, hat man also dreimal so elementar zwei
Ziffern addiert und dass das dreimal war, lag daran, dass man da
hinten zwei Neunen hat und jede Neun führt dazu, dass man irgendwie
beim drauf addieren eine Eins Übertrag kriegt und dann einmal muss man
noch den Übertrag richtig fertig abwickeln.
Also selbst wenn Sie Zahlen gleicher Länge haben, je nachdem wie viele
Neunen da am Ende stehen, haben Sie unterschiedlich viele so einzelne
Operationen.
Jetzt stellen Sie sich vor, Sie wollen auf diese Art und Weise von 0
bis 99.999 oder irgendwas bis 10 hoch K, irgendein 10 hoch K minus 1
hochzählen.
Also im Wesentlichen, Sie haben Zahlen, die K Ziffern lang sind.
Das Schlimmste, was Ihnen passieren kann, ist, naja, Sie müssen eben
durch alle Ziffern durch von so einer Zahl, bis der Übertrag ganz
vorne angekommen ist.
Das sind K so Operationen und im schlimmsten Fall müssen Sie das 10
hoch K mal machen.
Da haben Sie also so eine Gesamtzahl Operationen.
Jedenfalls erstmal irgendwie nach oben beschränkt durch im schlimmsten
Falle K Operationen für eine 1 addieren und das 10 hoch K mal.
Aber naja, also bis ganz vorne läuft der Übertrag ja nicht immer.
Genauer gesagt, nur sehr selten.
In den meisten Fällen, Sie haben gar keinen Übertrag und ansonsten
dann läuft er vielleicht mal eine Stelle oder zwei.
Aber das ist schon der Großteil der Fälle.
Also das K mal 10 hoch K ist zwar eine obere Schranke, aber keine
besonders tolle.
Nur so am Rande.
Wie man da eine bessere kriegt, das lernen Sie vielleicht mal irgendwo
im Zusammenhang mit sogenannter amortisierter Analyse.
Das wollen wir jetzt hier nicht machen.
Aber der Punkt ist, also selbst für Zahlen gleicher Länge ist es
unterschiedlich viel Arbeit.
Deswegen, wenn Sie jetzt sagen wollten, ganz genau wie lange dauert
das, bis ich eins drauf addiert habe, dann müssten Sie also für jede
Probleminstanz einzeln erstmal irgendwas sagen.
Das ist jetzt bei diesem Mickey Maus Beispiel noch nicht so schwierig,
weil Sie darüber reden können, wie viele Neunen stehen am Ende.
Das ist das, was dominiert.
Aber stellen Sie sich vor, Sie haben eine Liste von Zahlen und sind im
Sortier Algorithmus und Ihr Algorithmus funktioniert so, dass immer an
zwei Stellen Zahlen miteinander vertauscht werden nach irgendeinem
Verfahren.
Wie wollen Sie da beschreiben, für welche Listen von Zahlen Sie wie
viele Vertauschungen brauchen?
Also das kann man schon irgendwie machen, aber das ist kein Spaß.
Deswegen in den allermeisten Fällen, weil das so schwierig ist und so
aufwendig, für jede Probleminstanz einzeln zu sagen, wie viel Arbeit
macht die denn?
Man sagt, naja, da gucken wir ein bisschen ungenauer hin.
Wir sagen das nur in Abhängigkeit von der Größe der Eingabe.
Wie viele Stellen hat die Zahl, wo ich eins drauf addieren will?
Wie viele Zahlen sind in der Liste, die ich sortieren will?
Und wenn das N lang ist, dann ich brauche so und so viele Operationen.
Ja, aber wenn Sie nur die Länge wissen, nicht genau welche
Probleminstanz, dann kann das irgendwann variieren.
Und dann können Sie unterschiedliche Dinge machen.
Sie können sich angucken, im günstigsten Fall, wie schnell ist es
denn?
Ja, da kommt dann irgendwas raus, aber das sieht man dann auch
meistens schnell und das ist aber auch meistens das, was einen nicht
interessiert.
Also Sie wollen bei einer Liste von Zahlen nicht wissen, im
günstigsten Fall, wie wenig Operationen dauert es denn, die zu
sortieren, weil das sind die sortierten Listen.
Da gehen wir einmal durch, sehen, alles sortiert, fertig.
Das interessiert Sie nicht bei einem Sortieralgorithmus.
Dann könnte man auf die Idee kommen zu sagen, naja, dann gucke ich mir
halt für jede Probleminstanz einzeln an und rechne irgendwie den
Durchschnitt aus von allen Probleminstanzen gleicher Länge.
Also alle Listen mit gleich vielen Zahlen im Mittel.
Wie viele Vertauschungen muss ich denn machen, bis es sortiert ist?
Das kann einen interessieren, aber es ist leider typischerweise sehr
schwer auszurechnen.
Kein Spaß, überhaupt nicht.
Deswegen, das, was man meistens macht, ist, man guckt sich den
schlechtesten Fall an.
Das ist das, was Sie oft sehen werden bei Algorithmen.
Im schlimmsten Fall dieser Algorithmus für Probleminstanzen der Größe
n, Laufzeit n² oder was auch immer.
Aber das ist halt nur der schlimmste Fall.
Und Sie müssen immer gleich dazudenken, aha, vielleicht in ganz vielen
Fällen es geht schneller, vielleicht auch nicht.
Ja, weiß man nicht.
Muss man genauer hingucken.
Also passen Sie auf, aber Worst Case ist typischerweise interessanter
als Best Case und typischerweise viel einfacher als der Durchschnitt
auszurechnen.
Aber man verliert halt schon an Informationen.
Aber man kriegt die Mitteilung, ja, es gibt Probleminstanzen, da kann
es richtig dumm laufen.
Und so guckt man dann eben typischerweise bei Algorithmen, so wie ich
das vorhin auch immer gemacht habe, also da vorhin bei
Matrizenmultiplikation zum Beispiel oder Wegematrix ausrechnen, diese
ganzen Algorithmen, da ist es also völlig egal, was in der Matrix
drinsteht, da hängt es wirklich nur davon ab, wie groß die Matrix ist.
Da ist der Worst Case gleich dem Best Case, weil man immer gleich
viele Operationen macht.
Das ist ein schöner Spezialfall, der aber leider nicht immer vorliegt.
Ja, sowas macht man dann immer.
Und dann sagt man also irgendetwas darüber, wie lange der Algorithmus
so läuft, in Abhängigkeit von der Größe der Eingabe.
Aber man macht das nicht so ganz genau.
Weil man nicht will oder nicht kann oder nicht soll, nicht wollen
heißt vielleicht wirklich, man ist einfach zu faul.
Oder ja, eigentlich hätte man ja schon Lust, aber man weiß genau,
nächste Woche neue Hardware, alles ist auf einmal ganz anders.
Das lohnt sich überhaupt nicht.
Ich lasse es doch lieber gleich bleiben.
Oder es interessiert sie halt aus irgendwelchen Gründen gar nicht.
Also die fünfte Stelle hinterm Komma ist halt nicht so wichtig.
Ob ihr Algorithmus 27 Stunden oder 27 Stunden und fünf Sekunden läuft.
Wichtiger wäre Ihnen, dass es zwei Stunden statt 27 Stunden sind.
Fünf Sekunden hin oder her, egal.
Oder sie können es halt gar nicht ganz genau ausrechnen.
Und da gibt es sehr schöne Beispiele.
Ja, es gibt einen Aufsatz, da beweisen die Autoren hier für dieses
Problem.
Hier ist ein Algorithmus, der ist so schnell.
Einen schnelleren Algorithmus wird niemand finden, bis auf einen
konstanten Faktor.
Schade ist, wir können nicht analysieren, wie schnell der Algorithmus
ist.
Also die können beweisen, ihr Algorithmus ist optimal schnell, aber
sie wissen nicht, wie schnell.
So was gibt es selten, aber kommt vor.
Manchmal kann man es nicht so ganz genau, weil vielleicht gewisse
Dinge halt doch im Dunkeln sind in der Praxis.
Insbesondere womöglich sollen sie einen Algorithmus in
Anführungszeichen analysieren.
Da stehen halt gewisse Dinge so ein bisschen im Pseudocode, High Level
drin und man weiß gar nicht ganz genau, wie viel Aufwand verbirgt sich
denn dahinter.
Naja und manchmal, wie gesagt, soll man es nicht.
Also man will nicht für jede Probleminstanz einzeln was wissen oder
sie wollen unabhängig davon sein, ob sie gewisse Dinge bequem oder
unbequem hinschreiben können auf eine Art und Weise, sodass hinterher
effizienter oder nicht ganz so effizienter Code rauskommt.
Also manchmal, man will ungenau sein.
Wie ungenau?
Also zumindest, was man gerne ignoriert, sind zum Beispiel bei der
Laufzeit konstante Faktoren, ob der Algorithmus jetzt zweimal N hoch 3
Schritte macht oder zehnmal N hoch 3 Schritte.
Da sagt man dann, ja, das ist mir jetzt erstmal egal.
Hauptsache konstante mal N hoch 3 und nicht konstante mal N hoch 5.
So und also insbesondere ignorieren von konstanten Faktoren, ja, das
will man gerne, weil halt auch leicht durch Änderungen bei der
Hardware sie auch leichten konstanten Faktor unter Umständen rausholen
können.
Neuer Prozessor, schnellerer Speicher, was auch immer.
Schwupp, sind sie doppelt so schnell.
Und das andere ist, dass man manchmal halt noch weniger rauskriegt
oder wenn Sie über den Worst Case reden, Sie haben nur so obere
Schranken und es können auch was beliebig weiter unten sein bei der
Laufzeit und also manchmal können Sie nur obere oder untere Schranken
angeben und das will man dann auch ausdrücken können.
Und dafür gibt es dann die Groß-O-Notation, also das, was man
standardmäßig Groß-O-Notation nennt.
Dazu gehören typischerweise drei Symbole, nämlich, Überraschung, das
große U oder vielleicht ist es auch ein großes griechisches Omikron,
das weiß ich nicht so genau und ein großes griechisches Theta und ein
großes griechisches Omega.
Und wie die definiert sind, das gucken wir uns jetzt dann gleich mal
zumindest die ersten Dinge an.
Diese Symbole heißen manchmal auch Landauschesymbole, weil der das
jedenfalls bekannt gemacht hat, eingeführt, hat das schon vorher
mindestens ein Mathematiker namens Bachmann, jedenfalls für das Groß-O
und das Groß-Omega und das Groß-Theta hat dann Don Knuth irgendwie
weiter verbreitet.
Und bitte Achtung, nicht, dass Sie meinen, manche Leute schreiben
etwas unordentlich in ihren Aufsätzen.
Es gibt auch noch Klein-O und Klein-Omega, die bedeuten etwas anderes.
Glauben Sie nicht, wenn Sie ein Klein-O von n² sehen, dass das das
gleiche ist wie Groß-O von n², nur der Autor war zu blöd, das richtig
hinzuschreiben.
Klein -O, Klein-Omega sind andere Dinge und also falls Sie jemals in
die Situation kommen, dass Ihnen ein kleines Omega über den Weg läuft,
gucken Sie ganz genau nach, ob Sie herausfinden können, was der Autor
damit gemeint hat.
Es gibt mindestens zwei inhaltlich verschiedene Definitionen von Klein
-Omega, die verschiedene Autoren benutzen.
Das ist hässlich, passen Sie im Zweifelsfall auf, aber das machen wir
hier gar nicht.
Also jetzt hier erstmal ist alles gut.
So und das Erste ist jetzt, wir wollen irgendwie so reden können, dass
konstante Faktoren keine Rolle mehr spielen.
Dazu betrachten wir jetzt Funktionen f, die dann also sowas wie
Laufzeit beschreiben sollen von n0, das ist die Größe der Eingabe
nach, sagen wir mal, der Einfachheit halber, nicht negative, reelle
Zahlen.
Also wir erlauben uns sowas hinzuschreiben, wie die Laufzeit ist sowas
wie log n.
Und wir müssen nicht runden, weil wir als Werte irgendwie reelle
Zahlen zulassen.
Aber bitte, also damit wir es hier einfach haben, keine negativen,
reellen Zahlen als Funktionswert.
Solange man über Laufzeit und Speicherplatzbedarf redet, braucht man
sie auch nicht.
Also r und 0 oben plus sind die nicht negativen, reellen Zahlen bei
mir und wir betrachten jetzt so Funktionen n von n0 nach r.
Und jetzt wollen wir reden von etwas, was man asymptotisches Wachstum
einer Funktion f nennt oder auch größenordnungsmäßiges Wachstum.
Das Wort größenordnungsmäßig ist lustig, das steht nicht im Duden.
Also irgendwie gibt es das eigentlich gar nicht.
Aber Sie finden es in Wörterbüchern mit Übersetzungen ins Englische
und was weiß ich wohin.
Also vielleicht gibt es ja doch.
Also was ich meine, ist das, was wir gleich definieren werden.
So, nämlich wenn Sie eine Funktion f schon haben von n0 nach r0 plus,
dann sagen wir eine andere Funktion g von n0 nach r0 plus wächst
asymptotisch genauso schnell, wenn etwas gilt.
Und was soll dann gelten?
Also grob gesagt, die Funktionswerte g von n, die müssen etwas zu tun
haben mit den Funktionswerten f von n an der gleichen Stelle.
Und zwar soll das g von n kleinergleich irgendeinem konstanten c
-Strich mal f von n sein und größergleich einer anderen konstanten c
mal f von n.
Also bis auf einen konstanten Faktor immer die Funktionswerte für g
sind so in einem Bereich um Funktionswert von f.
Jetzt nach unten bitte, also nach oben das c-Strich soll positiv sein,
nach unten das c auch, damit die Aussage irgendwie einen Inhalt hat.
Für c gleich 0 ist das natürlich trivial immer wahr, aber das ist
nicht der Fall, der einen interessiert.
Also sowohl c als auch c-Strich sollen echt positive, reelle Zahlen
echt größer 0 sein, ja.
So und jetzt wäre natürlich das einfachste zu sagen, das g von n soll
immer in dem Bereich sein und dann merkt man aber sehr schnell, ja das
ist blöd irgendwie, so endlich viele Ausnahmen würde ich gerne
erlauben.
Dann gilt also dieses c mal f von n kleinergleich g kleinergleich c
-Strich mal f nicht ab 0, sondern da gibt es vielleicht Ausnahmen bei
n gleich 2, n gleich 5 und n gleich 641, aber ab n gleich 642, es gilt
immer.
Also was man verlangt ist, ups, Entschuldigung, es gibt ein n null,
sodass unterhalb, da können Sie so ein paar Ausnahmen haben, da muss
das nicht gelten, aber für alle n ab irgendeinem endlichen n null muss
das immer gelten.
Und wenn das immer gilt, dann wollen wir sowas hier schreiben, so f
und g und dazwischen so ein Gleichheitszeichen mit verbogenen
Strichen.
Und um die Notation übersichtlich zu halten, ich schreibe öfter mal
nicht f von n, g von n, sondern einfach nur f und g, die Namen der
Funktionen, ohne zu sagen, das Argument soll jetzt n oder x oder
irgendwas heißen, ist ja auch egal.
So zum besseren Verständnis, also stellen Sie sich vor, wir haben
irgendeine Funktion f von n und wir haben jetzt zwei Diagramme, da ist
in beiden als rote Linie, das soll rot sein, eine Funktion f
reingemalt und das ist beide Male die gleiche Funktion.
Also in beiden Diagrammen x läuft hier jetzt mal beispielhaft von 0
bis 10 und übrigens Vorsicht, also der Einfachheit halber, ich habe
einfach kontinuierliche reelle Funktionen reingemalt.
Eigentlich haben wir nur Funktionswerte an diskreten Stellen, aber
also interpretieren Sie da nicht zu viel rein.
Also wir haben hier zweimal f, x läuft in beiden Bildern von 0 bis 10,
nur die Y-Skala habe ich unterschiedlich hingemalt, im linken Bild ist
die auch linear 0, 100, 200, 300, im rechten Bild ist das
logarithmische Y-Skala, also da ein Zehntel, 1, 10, 100, so in
gleichen geometrischen Abständen.
Ich hoffe, sowas haben Sie schon mal gesehen.
Und dann habe ich für in beiden Bildern für die gleiche Konstante c, 1
,5 glaube ich war es, 1,5 mal f von n so als unterer Rand hingemalt
und für das gleiche c' 3 hier c' mal f von x und der Punkt bei der
logarithmischen Y-Skala ist, also was Sie da de facto ja plotten, ist
nicht mehr f von x, sondern Logarithmus von f von x und der
Logarithmus von c mal f von x ist ja einfach der Logarithmus von c
plus der Logarithmus von f von x.
Das heißt, wenn Sie logarithmische Y-Skala haben, so ein konstanter
Faktor führt einfach nur dazu, dass das Bild des Graphen um konstant
viel überall nach oben und unten geschoben wird.
Also der untere Rand und der obere Rand dieses blauen Bereiches, die
haben genau die gleiche Funktion, die gleiche Form wie hier das f von
x.
Also und deswegen sage ich, rede ich manchmal von so einem Schlauch um
f von x, also wenn man logarithmische Y-Skala hinmalt, dann sieht das
so ein bisschen aus wie ein Schlauch.
Im Allgemeinen ist das halt eben dieser Bereich zwischen c mal f von x
und c Strich mal f von x.
So und wenn Sie jetzt eine Funktion g haben, die ab irgendwo in diesem
blauen Bereich ist, dann sagt man g wächst asymptotisch genauso
schnell wie f.
Und ich habe jetzt hier also bewusst so ein g genommen, das sieht man
vor allem in dem rechten Bild deutlich, dass zwischendurch ist das mal
außerhalb von dem Bereich, also da gelten diese Ungleichungen größer
gleich c mal f und kleiner gleich c Strich mal f nicht.
Aber es gibt ein N0, was weiß ich, nehmen Sie sechs jenseits davon,
soll jedenfalls dieses Bild suggerieren, ist g immer in dem Bereich
hier, in dem blauen Bereich zwischen c mal f nach unten abgeschätzt
und c Strich mal f nach oben abgeschätzt.
Das bedeutet asymptotisch gleiches Wachstum.
Also Sie sehen auch die Funktion g, die kann schon irgendwie so ein
bisschen im Vergleich zu f so ein bisschen hin und her eiern.
Die muss nicht immer oberhalb, immer unterhalb oder irgendwas sein,
muss nicht die gleiche Form haben, aber es muss immer ab irgendwann in
diesem, in so einem Bereich sein.
Das ist asymptotisch genau so schnelles Wachstum.
Beispiel die Funktion f von n ist 3 mal n Quadrat und g von n ist 10
hoch 2 mal n Quadrat.
Behauptung, die wachsen asymptotisch gleich schnell.
Naja, also Sie müssen g, also das 10 hoch minus 2 mal n Quadrat nach
unten abschätzen durch Konstante mal 3 n Quadrat.
Also Konstante mal 3 n Quadrat soll kleiner sein als 10 hoch minus 2 n
Quadrat.
Da können Sie zum Beispiel Konstante 10 hoch minus 3 nehmen, wie man
sieht.
Und dann gilt das ab 0 gleich 0 direkt, ohne Ausnahme.
Und Abschätzung nach oben, naja 10 hoch minus 2 n Quadrat ist immer
kleiner als 3 n Quadrat, da das c stricht.
Das können Sie als 1 nehmen und das gilt auch für alle n, ohne
Ausnahme.
Also 3 n Quadrat wächst asymptotisch genauso schnell wie 10 hoch minus
2 n Quadrat und es ist kein Problem, sich das gleiche hin zu streiben
und statt 3 und 10 hoch minus 2 schreiben Sie irgendwelche positiven
Konstanten a und b hin.
Da werden Sie immer hier so Konstanten finden, dass die Abschätzungen
klappen.
Also Mitteilung, wenn Sie irgend so eine Funktion haben, zwei
beliebige Konstanten, positive Konstanten a und b, a mal die Funktion
f und b mal die Funktion f wachsen asymptotisch gleich schnell.
Wir können jetzt sagen, wir reden über die Funktion, die asymptotisch
ungefähr genauso schnell wachsen wie f und dann haben wir was gesagt,
was gilt unabhängig vom konstanten Faktor, den können wir jetzt
ignorieren, der ist jetzt weg.
Konstante Faktoren interessieren nicht mehr.
Bei dieser Schreib- und Redeweise in der Praxis natürlich schon, wenn
Sie einen Algorithmus haben, der 10 hoch minus 2 n Quadrat Laufzeit
hat, sind Sie wahrscheinlich viel glücklicher, als wenn Ihr
Algorithmus 10 hoch 10 hoch 10 hoch 10 mal n Quadrat Laufzeit hat.
Ganz bestimmt.
Aber manchmal will man halt konstante Faktoren ignorieren.
Es gibt auch Funktionen, die nicht asymptotisch gleich schnell
wachsen.
Also nehmen Sie zum Beispiel n Quadrat und n hoch 3.
Warum klappt das nicht?
Wenn das gelten würde, dann könnten Sie ja g von n, also das n hoch 3,
nach oben abschätzen durch positive konstante c Strich mal n Quadrat
ab irgendeinem n Null.
Naja und wenn n hinreichend groß ist, das f von n ist ja positiv,
können Sie dividieren und dann haben Sie also für alle hinreichend
großen n, müsste g von n durch f von n kleiner gleich c sein.
Kleiner gleich einer konstanten c Strich und g von n durch f von n ist
aber n hoch 3 durch n Quadrat.
Das ist n.
Es ist nicht für alle n größer irgendeiner Zahl n kleiner gleich c
Strich.
Nein, es wird beliebig groß, das n.
Also diese Abschätzung nach oben klappt nicht, egal welches c Strich
Sie nehmen und deswegen ist das halt, Entschuldigung, wächst g n hoch
3 nicht asymptotisch genauso schnell bzw.
genauer gesagt langsam wie n Quadrat.
Anderes Beispiel und das können Sie verallgemeinern.
Statt 2 und 3 irgendwelche konstanten a und b nehmen, n hoch a, n hoch
b.
Wenn b größer ist, dann das g wächst nicht asymptotisch genauso
schnell.
Und wenn Sie für g eine Exponentialfunktion nehmen, dann erst recht
sozusagen.
Dann müssten Sie auch wieder g von n durch f von n durch eine
Konstante abschätzen können.
Das ist dann also sowas wie 2 hoch n durch n Quadrat und also ich
hoffe mal jedenfalls ein Großteil von Ihnen hat in der Mathematik
irgendwie so ein bisschen Grenzwertbetrachtungen jetzt gemacht und es
ist klar, dass 2 hoch n durch n Quadrat, das wird beliebig groß.
Das können Sie nicht durch eine Konstante beschränken.
Und wenn es Ihnen nicht klar ist, dann kann man jedenfalls eine
Teilmenge von Werten für das n finden, wo man leicht durch Induktion
beweisen kann.
Der Quotient, das g von n durch f von n ist größer als 4 hoch i und
das i wird beliebig groß.
Der Quotient geht durch die Decke.
Also nicht asymptotisch gleich schnelles Wachstum.
Ja, dieses Zeichen überhaupt, dieses verbogene Gleichheitszeichen,
warum nimmt man das?
Naja, weil es wesentliche Eigenschaften hat wie auch Gleichheit,
nämlich es ist eine Äquivalenzrelation.
Sie erinnern sich an, wann war das letzte Vorlesung oder vorletzte?
Was ist eine Äquivalenzrelation?
Das ist eine Relation, die ist reflexiv, symmetrisch und transitiv.
Das heißt, was nochmal genau?
Reflexivität heißt, jedes Ding steht in Relation zu sich selbst.
Also hier jede Behauptung, eine Funktion wächst asymptotisch genauso
schnell wie sie selbst.
Also wenn die Formulierung halbwegs plausibel definiert ist, sollte
das gelten.
Naja, sie müssen f von n nach oben und unten abschätzen durch
Konstante mal f von n.
Ja, nehmen Sie Konstante 1.
Symmetrie, wenn g asymptotisch genauso schnell wächst wie f, dann soll
auch f asymptotisch genauso schnell wachsen wie g. Da zahlt es sich
jetzt aus, dass wir verlangt haben, dass diese Konstanten c und c'
echt größer Null sind.
Also stellen Sie sich vor, Sie haben c mal f von n kleiner gleich g
von n kleiner gleich c' mal f von n für alle hinreichend großen n, ab
irgendeinem n Null.
Was müssen wir beweisen?
Die umgekehrte Abschätzung f irgendwie eingeschachtelt zwischen
Vielfachen von g von n.
Hier, wenn c mal f von n kleiner gleich g von n ist und wenn c echt
größer Null ist, also erst mal, wenn es sich Null ist, können Sie
durch c dividieren und wenn es größer Null ist, bleibt das
Relationszeichen erhalten und dann steht da f von n ist kleiner gleich
1 durch c mal g von n und mit c ist auch 1 durch c positiv und dann
haben Sie f nach oben abgeschätzt und analog aus der Abschätzung von g
nach oben kriegen Sie eine Abschätzung von f nach unten, indem Sie
hier das c' auf die andere Seite bringen.
Und das dritte und das heißt, also man kann sozusagen die beiden
Seiten von diesem Wächst-Gleich-Schnell-Zeichen vertauschen und man
kann einfach symmetrisch formulieren f und g wachsen asymptotisch
gleich schnell und Transitivität auch ganz banal, wenn f und g
asymptotisch gleich schnell wachsen und g von g und h auch, dann auch
f und h.
Wenn Sie g einschachteln können zwischen Vielfache von f und h
einschachteln können zwischen Vielfache von g, dann nach unten das
Vielfache von g können Sie nach unten weiter abschätzen durch ein
Vielfaches von f und nach oben das Vielfache von g können Sie weiter
abschätzen durch ein Vielfaches von f und dann haben Sie h auch
zwischen Vielfachen von f eingeschachtelt.
Sie haben einen kleinen Schlauch um h und dieser kleine Schlauch ist
im großen Schlauch um f.
Also das ist eine Äquivalenzrelation.
Und jetzt die erste von diesen, das erste von diesen drei Symbolen,
die ich vorhin erwähnt habe, Groß-O, Groß-Theta, Groß-Omega, Groß
-Theta von f, wenn f so eine Funktion ist, das ist die Menge aller
Funktionen g, die asymptotisch genauso schnell wachsen wie f, also
Definition ausgeschrieben, das ist die Menge aller g mit der
Eigenschaft, es gibt c und c' positiv und n null, das heißt für alle n
größer, n null, das gilt, wovon wir die ganze Zeit reden.
Das ist Theta von f, die Funktionen, die asymptotisch genauso schnell
wachsen wie f, also im Wesentlichen, bis auf einen konstanten Faktor,
also ist das Händewedel, ungefähr das Gleiche.
Und wie gesagt, konstante positive, positive, ja, alles positiv, nicht
null, konstante Faktoren können Sie ignorieren, also Theta von dreimal
f und Theta von ein Hundertstel f, das ist alles das Gleiche.
Das sind die gleichen Funktionen, die asymptotisch so schnell wachsen.
Das ist schön, wenn man sowas weiß, dann hat man also diese Funktionen
g nach oben und nach unten durch Vielfache von f abgeschätzt.
Aber manchmal ist das halt nicht so, dass das nach oben und nach unten
durch Vielfache der gleichen Funktion f abgeschätzt ist, da kann man
nur nach oben oder nur nach unten abschätzen.
Und das führt dann zu diesen Notationen Groß O von f und Groß Omega
von f.
Nehmen wir erst mal Groß O von f, das sind alle Funktionen g mit der
Eigenschaft, g von n können Sie nach oben abschätzen durch positive
Konstante mal f von n für alle n größer gleich einem Konstanten n
null.
Also hier haben Sie die konstante Abschätzung nach, die Abschätzung
nach oben wie eben, aber keine Abschätzung mehr nach unten.
Ja, das kann auch viel langsamer sein.
Das f, das g kann auch viel langsamer wachsen als das f.
Und in so einem Fall jetzt hüpfe ich hier zum ersten von den beiden
Punkten hier schauen wir dann auch g so eine Art kleiner gleich mit so
einem geschwungenen kleiner Gleichzeichen.
Wenn g in O von f ist, ja, und dann sagt man g wächst asymptotisch
höchstens so schnell wie f, vielleicht auch schwächer.
Also dann bei O von f haben Sie alle Funktionen, für die f oder ein
Vielfaches von f jedenfalls obere Schranke ist.
Obere Schranke, alles ist drunter, was da in O von f ist.
Naja und das Umgekehrte auch, Omega von f, das sind die g, wo Sie die
Abschätzung nach unten haben durch ein Vielfaches von f und dann
schreiben wir auch g größer gleich f mit so einem geschwungenen größer
Zeichen und sagen g wächst asymptotisch mindestens so schnell wie f.
Das Wesentliche sind nicht mehr die konstanten Faktoren, sondern der
Rest sozusagen.
Also nehmen Sie als Funktion g 10 hoch 90 mal n hoch 7.
10 hoch 90 ist groß, das ist mehr als die geschätzte Anzahl
elementarer Teilchen im Universum oder irgendwie sowas.
Und f 10 hoch minus 90 mal n hoch 8, also die Konstante hier vorne
viel kleiner, aber dafür hier hinten n hoch 8 statt n hoch 7.
So, Behauptung g ist in O von f.
Und wenn Sie jetzt kleine Werte für n einsetzen, werden Sie merken, 10
hoch 90 mal n hoch 7 ist viel größer als 10 hoch minus 90 mal n hoch
8.
Sie müssen schon verdammt große Werte für n einsetzen, damit das nicht
mehr der Fall ist.
Also Sie müssen Größen, Problemgrößen, wenn Sie das interpretieren als
Größe von Probleminstanzen, Sie brauchen Probleminstanzen, die größer
sind als Anzahl elementarer Teilchen im Universum.
Das werden Sie nur selten haben.
Aber trotzdem, Behauptung 10 hoch 90 mal n hoch 7 wächst asymptotisch
höchstens so schnell wie 10 hoch minus 90 mal n hoch 8.
Was müssen Sie tun?
Sie müssen 10 hoch 90 mal n hoch 7 abschätzen nach oben durch eine
positive Konstante c mal 10 hoch minus 90 n hoch 8.
Naja, da nehmen Sie halt als c den 180.
Da haben Sie gewonnen.
Das sind absurd große Konstanten, ja.
Also deswegen in der Praxis, also irgendwann redet man, erstmal redet
man über Groß O und sagt und konstante Faktoren interessieren mich
nicht, aber irgendwann interessieren sie dann halt doch, ja.
Wenn sie absurd groß werden, kann man sie halt in der Praxis nicht
mehr ignorieren.
Und deswegen, wenn dann irgendjemand so eine Abschätzung mit Groß O
hinschreibt, die interessante Frage ist dann schon auch immer noch, ja
und wie groß ist der konstante Faktor denn?
Ist das 2 oder ist das 2 Milliarden oder noch mehr?
Manchmal sehen Sie, werden Sie vielleicht noch sehen, O von 1.
Was soll das sein?
Ja, mit 1 ist hier gemeint die Funktion, die Konstantin Wert 1 hat.
Und was ist dann O von 1?
Das sind also alle Funktionen g mit der Eigenschaft, Sie können g von
n abschätzen nach oben durch Konstante mal die Funktion, die
Konstantin Wert 1 hat.
Das ist also Konstante c und das heißt in O von 1 sind alle
Funktionen, die Sie nach oben durch eine Konstante beschränken können.
1 oder 1000 oder 3 Milliarden, was auch immer.
Und das sind natürlich alle Funktionen, die sowieso durch Konstanz
sind, aber auch was, was so ein bisschen hin und her wackelt, 3 plus
Sinus n, können Sie nach oben durch die Konstante 4 beschränken, ist
auch in O von 1.
Ja und jetzt hier noch mal ein bisschen allgemeiner, das, was ich
vorhin schon gesagt habe und jetzt mit Groß-O-Notation statt
asymptotisches Wachstum.
Wir haben uns vorhin schon angeguckt, so was, was hat man verglichen
n² und n³.
Wenn Sie n² und n vergleichen zum Beispiel, dann stellen Sie fest, der
Quotient wird beliebig groß.
Das heißt, Sie können n² nicht durch irgendeine Konstante mal n nach
oben abschätzen.
Das heißt, n² ist nicht in O von n, aber die Umkehrung gilt.
Daran sieht man schon mal, dass dieses kleine gleich nicht symmetrisch
ist.
Und die Beobachtung ist, wenn Sie zwei positive Konstanten a und b
haben, die voneinander verschieden sind, bitte, damit die rechte Seite
auch stimmt und sagen wir mal a ist echt kleiner als b, dann ganz
allgemein n hoch a wächst asymptotisch höchstens so schnell wie n hoch
b, aber n hoch b, wenn das b echt größer ist als a, wächst nicht
asymptotisch höchstens so schnell wie n hoch a.
Also n hoch a ist in O von n hoch b, aber nicht umgekehrt.
Und n hoch b sind Groß-Omega von n hoch a, aber nicht umgekehrt.
Egal, was die Exponenten sind, ob das jetzt der Exponent 3 oder 7,8
oder Pi oder E oder irgendwas ist.
Es kommt nur auf die Zahlen da an.
Naja und für Exponentialfunktionen erst recht.
Und da müssen Sie jetzt nicht mehr gucken, wenn Sie Konstanten a hoch
b haben, die beide echt größer 1 sind.
Das ist jetzt hier mal bitte wichtig, sicherheitshalber.
Dann egal, wie groß a ist, n hoch a wächst asymptotisch höchstens so
schnell wie b hoch n, selbst wenn die Konstante b kleiner ist als die
Konstante a.
n hoch 10 wächst asymptotisch höchstens so schnell wie 1,0001 hoch n.
Also Exponentialfunktionen, salopp gesagt, wachsen schneller,
asymptotisch schneller als Polynomialfunktionen.
Gut, dann denke ich, machen wir bis hierher.
Dann wünsche ich Ihnen schöne Weihnachten, alles Gute für das neue
Jahr.
Bleiben Sie gesund.
Das ist keine Floskel, es ist nicht selbstverständlich und ich hoffe,
wir sehen uns dann alle nächstes Jahr hier wieder.
Dankeschön.