Herzlich willkommen zur Übung Algorithm 1.
Mein Name ist Björn Keidel.
Ich bin einer von drei Übungsleitern dieses Semester.
Und wir machen heute ausnahmsweise nur Übungen.
Letzte Woche waren zwei Vorlesungen aufgrund des Feiertags.
Deswegen machen wir heute einen kompletten Baum Übung, damit ihr genug
geübt habt, um die zwei Übungsleiter zu machen.
Machen wir zuerst mal kurz ein paar Orga-Sachen.
Also was machen wir heute?
Ich möchte erst mal kurz mit euch über zwei, drei organozytorische
Dinge sprechen.
Und dann der Stoff, den wir heute machen.
Da geht es um die Effizienz von Algorithmen.
Um die Korrektheit von diesen.
Und wir reden über Teilen und Herrsche und das Master-Theorem.
Also alles Stoff, den ihr schon hattet in der Vorlesung.
Und dieser Stoff ist auch thematisiert auf dem ersten und zweiten
Übungsblatt.
Gut.
Orga.
Der erste Punkt.
Wo finde ich was?
Wir haben eine Homepage für die Vorlesung.
Auf dieser Homepage findet ihr das ganze Vorlesungsmaterial.
Wenn ihr euch diesen kryptischen Link nicht aufschreiben wollt, dann
könnt ihr auch einfach nach Algorithmen suchen.
Bei Google oder sowas, dann findet ihr das sicherlich auch.
Und zusätzlich zu unserer Homepage haben wir ein Ilias-Forum.
Und dieses Ilias-Forum könnt ihr verwenden.
Manche von euch haben es schon getan.
Wenn ihr Dinge diskutieren wollt.
Stoff, Vorlesung oder wenn ihr Orga-Fragen habt oder sowas.
Dann postet es doch einfach ins Forum.
Dann schaue ich da rein oder meine Übungsleiter-Kollegen und auch die
Tutoren.
Und sie versuchen eure Fragen schnellstmöglich zu beantworten.
Das ganze Material zur Vorlesung, das veröffentlichen wir aber nicht
auf dem Ilias.
Weil erfahrungsgemäß doch die meisten Leute nicht ins Ilias schauen.
Also deswegen, die Vorlesungsfolien und Übungsblätter findet ihr auf
der Homepage.
Und diskutieren könnt ihr im Ilias.
Zusätzlich dazu haben wir eine Mailing-Liste.
Die Mailing-Liste soll dazu dienen, dass wir als Übungsleiter einen
Kanal haben, mit dem wir euch erreichen können.
Und deswegen würde ich euch bitten, dass ihr euch alle bei der Mailing
-Liste anmeldet.
Den Link dazu findet ihr auf der Webseite.
Damit wenn mal eine Raumänderung ansteht oder wenn man eine Vorlesung
ausfahren sollte oder sowas.
Damit wir euch rechtzeitig Bescheid sagen könnten.
Zusätzlich haben wir auf der Webseite noch so einen Feedback-Kasten.
Und ein Feedback-Kasten ist einfach so ein Textfeld mit einem Absenden
-Button.
Und den könnt ihr verwenden, wenn ihr uns anonym Feedback schicken
wollt.
Wenn ihr uns sagen wollt, was gut lief, was schlecht lief und damit
nicht warten möchtet bis zur Evaluation, könnt ihr diesen Feedback
-Kasten verwenden.
Der Kasten eignet sich aber nicht dazu, dass ihr uns Fragen stellt.
Dadurch, dass er anonym ist, können wir euch nicht darauf antworten.
Also wenn ihr Fragen habt und ihr möchtet gerne eine Antwort, dann
postet ihr besser ins Forum oder schreibt eine E-Mail.
Wenn ihr eine Frage habt und keine Antwort möchtet, dann könnt ihr
auch den Feedback-Kasten verwenden.
Aber Sinn und Unsinn?
Na gut.
Ich habe es so angedeutet, es gibt dieses Jahr drei Übungsleiter.
Mein Name ist Björn Keitel und ihr erreicht mich unter dieser E-Mail.
Es gibt einen zweiten Übungsleiter, das ist Sascha Witt.
Der sitzt hier vorne links in der Ecke.
Bleibt mal kurz winken.
Und es gibt einen dritten Übungsleiter, der ist jetzt gerade nicht
anwesend.
Und der soll auch eher im Hintergrund agieren.
Der übernimmt vielleicht mal eine Vorlesung oder sowas.
Aber eure beiden Hauptansprechpartner sind Sascha und ich.
Und wenn ihr nichts dagegen habt, würden wir euch gerne duzen.
Ihr könnt uns auch gerne dann zurück duzen.
Wenn ihr was dagegen habt, dann fragt uns das, aber ich finde es
angenehmer, wenn ich einfach du sagen kann.
Und ihr bestimmt auch.
Dann zwei kurze Punkte zum Tutorium.
Das WebInscribe System, das lief jetzt schon.
Ihr solltet euch alle angemeldet haben zum Tutorium.
Und einen Tutorienplatz zugewiesen bekommen haben.
Wenn das aus irgendeinem Grund nicht funktioniert hat, dann meldet
euch bitte bei mir.
Dann gucke ich, dass ihr noch einen Tutorienplatz kriegt.
Wenn ihr jetzt vom WebInscribe ein Montagstutorium zugewiesen bekommen
habt, dann geht diese Woche bitte einfach in irgendein anderes
Tutorium.
Weil es ist ja ausgefallen, Montag war Feiertag.
Für die restlichen Feiertage dieses Semester werden wir
Ausweichtermine für die ausfallenden Tutorien besorgen.
Trotz dieses Mal war es halt schwierig einen Ausweichtermin zu finden,
weil wir ja gar nicht wussten, wer von euch ist in welchem Tutorium.
Dann drei Wörter zum Übungsblatt.
Das Übungsblatt kommt montags raus, spätestens nach der Vorlesung,
vermutlich eher früher.
Und abgeben könnt ihr das auf den darauffolgenden Dienstag, aber nicht
den Dienstag einen Tag danach, sondern den Dienstag eine Woche später
bis 12.45 Uhr im Informatikgebäude, in diesen Briefkästen, die ihr
bestimmt schon aus dem ersten Semester kennt.
Und das erste Übungsblatt, das ist schon online.
Uns ist aufgefallen, dass es einen kleinen Fehler gab, der ist schon
beseitigt.
Den zeige ich euch kurz, damit ihr alle Bescheid wisst.
Nämlich bei Aufgabe 2, an dieser Stelle hier, in der Weilschleife, da
stand ein Größer, da muss aber ein Größer gleich stehen.
Das Übungsblatt auf der Webseite ist schon aktualisiert, also wenn ihr
es noch nicht runtergeladen habt, dann kümmert euch das gar nicht.
Falls ihr schon angefangen habt mit dem Übungsblatt, würde ich euch
bitten, nochmal den Neuweißen runterzuladen.
Gut.
Das wäre es soweit zum Organisatorischen und wenn es dazu keine Fragen
mehr gibt, würde ich jetzt mit dem Stoff anfangen.
Gibt es denn Fragen noch dazu?
Ich sehe keine Fragen.
Gut.
Also wir machen hier die Übungen zu Algorithmen und ein essentieller
Punkt für Algorithmen ist deren Effizienz.
Also wir sind daran interessiert, möglichst effiziente Algorithmen zu
entwickeln.
Was heißt effizient?
Naja, so ein Algorithmus, der benutzt im Prinzip zwei Ressourcen.
Der benutzt einmal die Rechenzeit von dem Rechner, auf dem er läuft
und der benutzt den Speicherplatz.
Und wir möchten natürlich, dass einerseits der Algorithmus so schnell
ist wie möglich und auch so wenig Speicherplatz wie möglich verwendet.
In dieser Vorlesung Algorithmen 1 sprechen wir aber hauptsächlich um
die Laufzeit und nicht um den Speicherplatz.
In fortgeschrittenen Vorlesungen, da spricht man auch mal über den
Speicherplatz.
Aber hier, Algorithmen 1, soll es erstmal vorrangig um die Laufzeit
der Algorithmen gehen.
Unser Ziel ist wie gesagt, dass wir Algorithmen entwerfen, die
möglichst schnell sind und damit auch möglichst effizient.
Denn wir wollen ja irgendwelche Probleme lösen und je schneller wir
das Problem gelöst haben, desto besser.
Wenn ihr euch jetzt zurück erinnert an das Web-Instructions-System,
weil das System jetzt 5 Monate bräuchte, um zu berechnen, in welches
Tutorium ihr kommt, dann werdet ihr wahrscheinlich unzufrieden,
deswegen gibt es da zum Glück einen Algorithmus, der das ein bisschen
schneller macht.
Oder wenn ihr irgendwas mit Excel macht und eure Excel-Daten da
sortieren wollt, dann wollt ihr ja auch, dass die Daten möglichst
schnell sortiert werden und ihr müsst nicht erstmal eine halbe Stunde
warten, bis Excel fertig ist, um 5 Daten zu sortieren.
Deswegen möchten wir gerne schneller Algorithmen.
Aber jetzt natürlich die Frage, was heißt eigentlich schnell?
Was bedeutet für uns schnell?
Das ist ja erstmal so ein oberflächliches Wort.
Wenn ich verschiedene Leute frage, was schnell bedeutet, sagt der eine
Ferrari, der andere sagt TGW oder was.
Und das wollen wir formalisieren, was wir bei Algorithmen unter
schnell verstehen.
Und dazu müssen wir uns auch klar werden, wie man überhaupt die
Laufzeit von einem Algorithmus bestimmt und wie man die dann im
Endeffekt misst.
Bevor wir jetzt damit anfangen, erstmal so ein kurzer Überblick, warum
sich so Effizienzbetrachtungen wirklich lohnen.
Nämlich die Effizienz von verschiedenen Algorithmen, die kann sich
stark unterscheiden.
Ein ganz typisches Algorithmenproblem ist das Entwerfen von
Sortieralgorithmen.
Also ihr habt irgendeine Liste gegeben von verschiedenen Dingen,
meinetwegen N verschiedene Zahlen.
Und diese Zahlen wollt ihr aufsteigend oder absteigend sortieren.
Das Sortierproblem, das dreht überall auf, in allen möglichen
Anwendungen auch, wo man es vielleicht gar nicht vermutet.
Deswegen ist es auch ein zentraler Teil dieser Vorlesung.
Und da gibt es verschiedene Algorithmen, die dieses Problem lösen.
Bekannte Algorithmen dafür sind einmal das Sortieren durch Einfügen
oder Englisch Insertion Sort.
Und Sortieren durch Mischen, Merge Sort auf Englisch.
Die beiden Algorithmen lernt ihr noch im Laufe der Vorlesung kennen.
Aber jetzt müsst ihr euch mal damit begnügen, es gibt diese
Algorithmen und diese Algorithmen haben diese Laufzeit.
Das Sortieren durch Einfügen, das braucht in Abhängigkeit der Anzahl
von Zahlen, also wir wollen N Zahlen sortieren.
Braucht dann irgendwie N Quadratschritte, multipliziert mit irgend so
einer Konstanten.
Und das Sortieren durch Mischen, das braucht N mal Log N Schritte,
auch wieder mit irgend so einer Konstanten.
Jetzt kann man denken, N Quadrat und N Log N, das ist gar nicht so
weit auseinander.
Und zusätzlich, wenn man sich die Algorithmen genau anschaut und ihre
genaue Laufzeit bestimmt, kann man auch feststellen, dass diese
Konstante hier vorne, dass die kleiner ist als die Konstante hier.
Kann man denken, dass Sortieren durch Einfügen vielleicht doch die
bessere Wahl ist als Sortieren durch Mischen, obwohl es erstmal formal
eine schlechtere Laufzeit hat.
Aber, wenn man das denkt, dann hat man sich geirrt und das möchte ich
kurz argumentieren.
Nämlich, gehen wir mal davon aus, wir wollen 10 hoch 6 Zahlen
sortieren oder 10 hoch 6 Datenbankeinträge, 10 hoch 6 Freunde bei
Facebook oder was auch immer.
Und mal so vereinfacht, hat das Sortieren durch Einfügen die Konstante
2, also es braucht 2 mal N Quadrat, Dritte, und das Sortieren durch
Mischen hat die Konstante 50.
Also es braucht 50 mal die Anzahl der Elemente, mal Log N, also Log
die Anzahl der Elemente, Dritte bis es fertig ist.
Um das Ganze jetzt noch ein bisschen unfairer zu machen, lassen wir
das auf verschiedene Recher laufen.
Das Sortieren durch Einfügen kriegt den schnelleren Rechner mit 2
Gigahertz und das Sortieren durch Mischen kriegt so einen Rechner aus
der Steinzeit mit 500 Megahertz.
Und dann, was denkt ihr, welcher Algorithmus ist schneller?
Das Sortieren durch Mischen ist wesentlich schneller, obwohl der
Rechner viel, viel schlechter ist.
Das kann man dann so einsehen, der Sortieren durch Einfügen, der
braucht 2 mal 10 auf 6 zum Quadrat Rechenschritte.
Das war vorausgesetzt.
Und der Rechner, der hat 2 Gigahertz, also er kann 2 mal 10 auf 9
Anbindungen pro Sekunde verarbeiten.
Dann braucht er dafür insgesamt ungefähr 1000 Sekunden.
So ganz stark vereinfacht.
Das Sortieren durch Mischen, das braucht 50 mal N log N Schritte und
der Rechner, der gibt uns 500 mal 10 auf 6 Schritte pro Sekunde.
Und dann braucht der zum Sortieren mit Mischen nur 0,6 Sekunden.
Also ein ganz krasser Unterschied, obwohl gefühlt der Unterschied
vielleicht gar nicht so groß war am Anfang.
Den wir jetzt, dass der Sortieren durch Mischen wesentlich schneller
ist, obwohl er die viel schlechteren Voraussetzungen hat.
Einen viel schlechteren Rechner und er hat einen schlechteren
Konstante.
Aber, er hat halt hier nur N log N, statt N Quadrat Schritte zu
berechnen.
Und damit ist er viel schneller fertig.
Wenn wir jetzt natürlich die Anzahl an Elementen hochschrauben, dann
wird es auch nicht besser.
Also wenn wir statt 10 auf 6 Zahlen jetzt 10 auf 7 Zahlen sortieren
wollen, dann braucht das Sortieren durch Einfügen schon über einen
ganzen Tag.
Während das Sortieren durch Mischen immer noch nur 7 Sekunden braucht.
Also ich denke das spricht ganz klar für Sortieren durch Mischen, so
oberflächlich gesehen.
Und formal betrachten wir das auch noch im Laufe der Vorlesung.
Bei der nächsten Folie hier jetzt, da steht so eine Tabelle, die
braucht ihr euch jetzt nicht im Detail anzuschauen.
Aber diese Tabelle, die soll euch nochmal so ein Gefühl dafür geben,
was heißen denn so verschiedene Laufzeiten.
Insbesondere mag ich euch auf dieses 2 hoch N hinweisen.
Denn wir werden in der Vorlesung immer sagen, exponentielle Laufzeit,
also sowas wie 2 hoch N, 3 hoch N, 5 hoch N.
Das ist völlig irrelevant für die Praxis.
Das kann man hier schon sehen, wenn ich eine Probleminstanz habe, mit
100 Elementen, also beispielsweise ich möchte 100 Zahlen sortieren.
Und der Algorithmus, der würde 2 hoch N Schritte brauchen bis er
fertig ist.
Dann können wir ja schon 10 auf 13 Jahre warten.
Während so ein realistischer Algorithmus, wie der Merkle Algorithmus
halt vielleicht nur irgendwas im Mikrosekundenbereich braucht.
Aber auch hier zwischen den beiden Spalten seht ihr, dass N² auch
wieder viel schlechter ist als NlogN.
Zum Beispiel hier unten, hier noch 8 Elemente, braucht dieser
Algorithmus nur so knapp 4 Minuten, äh 4,5 Minuten oder 4,4 Minuten.
Und der N² Algorithmus, der braucht schon wieder mehrere Jahre.
Also es lohnt sich Algorithmen zu entwickeln, die eine möglichst
kleine Laufzeit haben.
Und in der Praxis kann man eigentlich schon sagen, alles was so über N
hoch 3 ist, ist eigentlich schon viel zu langsam.
Auch wenn wir vereinfacht in der Informatik immer sagen, ein
Algorithmus mit Polylaufzeit, also Laufzeit polymer, irgendwie eng
verdreht, N hoch 3, N hoch 4, N hoch 5.
Da sagen wir, das ist schnell.
In der Praxis muss das nicht unbedingt zutreffen.
Aber in der Theorie teilt man das so auf zwischen Polynomen und
exponentieller Laufzeit.
Nach dieser Einführung, warum es sich lohnt, sich damit zu
beschäftigen, gehen wir jetzt ein bisschen mehr ins Detail.
Nämlich einmal müssen wir uns darüber klar werden, von was abhängig
wir die Laufzeit des Algorithmuses messen.
Und wir messen die Laufzeit von einem Algorithmus immer abhängig in
der Länge der Eingabe.
Also wenn ich zum Beispiel Zahlen oder irgendwelche Datensätze
sortieren möchte, dann messe ich die Laufzeit in der Anzahl der
Datensätze.
Also wenn ich 5 Millionen Zahlen sortieren möchte, dann muss ich meine
Laufzeit irgendwie ausdrücken als Theorem, wo diese 5 Millionen Zahlen
vorkommen.
Wenn ich mich mit Multiplikation beschäftige, so wie Karazuba Ofman,
das ihr aus der Vorlesung kennt und über das wir heute auch noch
reden, dann muss ich mir erstmal Gedanken darüber machen, wie tut der
Rechner die Zahlen darstellen.
Und das ist Bits.
Und dann bin ich bei Multiplikation vielleicht daran interessiert, die
Laufzeit zu messen in der Anzahl der Bits, die ich als Eingabe
bekomme.
Oder Grafen, kennt ihr vielleicht schon aus anderen Vorlesungen, da
tut man üblicherweise die Laufzeit betrachten in der Menge der Knoten
und Kanten.
Also was die Eingabegröße bedeutet, hängt immer ab vom Problem, ist
aber eigentlich auch meistens relativ natürlich.
Und wenn ihr das ein paar Mal gesehen habt, dann ist das kein Problem
mehr, das einzuschätzen, in was wir jetzt die Laufzeit messen.
Und jetzt die Laufzeit, wie bestimme ich die?
Das mache ich typischerweise folgendermaßen, ich schaue mir den
Algorithmus an und ich zähle, wie viele Schritte er braucht, bis er
fertig ist.
Dazu macht man üblicherweise die Annahme, dass jeder Schritt im Total
Code oder im Algorithmus, dass er einen Schritt braucht und dann
summiere ich auf, wie viele Schritte macht der Algorithmus insgesamt
und das ist dann seine Laufzeit.
Da müsst ihr aber aufpassen, nämlich wenn ihr innerhalb eines
Algorithmus einen anderen Algorithmus aufruft, dann könnt ihr
natürlich nicht sagen, dass er jetzt nur Laufzeit 1 braucht.
Der braucht natürlich ein bisschen länger, aber das werden wir auch
noch thematisieren.
Jetzt, in diesem Moment, können wir mal davon ausgehen, wir bestimmen
die Laufzeit, indem wir uns den Algorithmus gut angucken und wir
zählen, wie viele Rechenschritte er macht.
Wir machen dazu gleich auch noch ein paar Beispiele, also wenn euch
das jetzt noch ein bisschen rätselhaft ist, einfach kurz warten.
Gut, wenn wir jetzt wissen, wie wir die Eingabekurse bestimmen oder
was das überhaupt ist und wir jetzt wissen, wie wir die Laufzeit
bestimmen, dann müssen wir noch uns überlegen, wie drücken wir die
Laufzeit aus.
Beziehungsweise, was wir uns auch noch überlegen müssen ist, wir
müssen uns überlegen, an was für einer Laufzeit sind wir überhaupt
interessiert.
Und da gibt es drei verschiedene Typen.
Einmal gibt es die Laufzeit im besten Fall oder hier steht im
günstigsten Fall, also das ist der Fall, in dem der Algorithmus am
besten läuft.
Zum Beispiel beim Sortieren, wenn die Liste schon sortiert ist, dann
muss ich nichts mehr machen.
Wenn der Algorithmus gut ist, braucht er da nicht lange, ist gleich
fertig.
Dann gibt es den mittleren Fall, da hat man auch Average Case,
Complexity dazu und es gibt den schlechtesten Fall.
Und der schlechteste Fall ist der Fall, der für uns eigentlich am
interessantesten ist.
Denn üblicherweise möchte man wissen, wie lange brauche ich im
schlimmsten Fall, bis der Algorithmus fertig ist.
Wenn ihr euch zum Beispiel vorstellt, ihr entwickelt irgendwie
Algorithmen für einen Bordcomputer von einem Auto oder einem Flugzeug
oder sowas, wo es auch wirklich darauf ankommt, dass der Algorithmus
schnell fertig ist.
Und ihr habt jetzt einen Algorithmus, da wisst ihr, in den meisten
Fällen braucht er fünf Schritte, aber es gibt so ein paar Fälle, da
braucht er fünf Jahre.
Dann kann diese fünf Jahre aber halt bedeuten, dass das Auto gegen die
Wand fährt oder das Flugzeug abstürzt.
Und deswegen ist es wichtig, dass ihr euch vorher überlegt habt, was
ist der schlechteste Fall für diesen Algorithmus und was ist seine
Laufzeit in diesem schlechtesten Fall.
Den besten Fall zu wissen ist natürlich auch interessant, weil dann
weiß ich, wie schnell der Algorithmus überhaupt sein kann.
Und der mittlere Fall ist eigentlich auch sehr spannend, insbesondere
wenn es mal darum geht, wenn man sich mit dem Thema Sicherheit
beschäftigt oder Kryptografie.
Aber mittlerer Fall ist sehr schwer zu bestimmen und man müsste auch
erstmal definieren, was heißt überhaupt mittlerer Fall, was ist
überhaupt ein durchschnittlicher Fall für meine Anwendung.
Deswegen hat sich eigentlich durchgesetzt, dass man den schlechtesten
Fall betrachtet und das machen wir in dieser Vorlesung auch meistens.
Weil auch noch zwei Gründe dafür, ein Grund ist noch, dass der
schlechteste Fall auch meistens häufig auftritt.
Das heißt zum Beispiel bei einem Sortieralgorithmus ist das wieder
schlechtester Fall sein, dass die Liste irgendwie völlig zufällig ist,
also die Zahlen sind irgendwie zufällig verteilt.
Und das wird auch häufig auftreten, weil sonst müsste man nicht
sortieren.
Wenn die Daten schon vorsortiert sind, dann kann ich vielleicht was
besseres machen als so einen generischen Sortieralgorithmus.
Und zusätzlich muss man sich auch überlegen, dass es so böse Instanzen
geben kann.
Damit ist zum Beispiel gemeint, angenommen ihr entwickelt irgendeinen
Algorithmus und der Algorithmus läuft auf einem Webserver.
Und jetzt möchte jemand von euch den Webserver lahmlegen, irgendwie
mit einem DDoS-Angriff oder sowas.
Also möglichst viele Daten an den Server schicken und den Server dazu
bringen, dass er möglichst lange rechnet, damit niemand mehr eure
Website aufrufen kann oder euren Webserver wisst.
Und da ist natürlich gut zu wissen, was sind die Fälle, die meinen
Server lahmlegen, damit ich meinen Server irgendwie dagegen schützen
kann, dass jemand von außen nicht den Server bombardiert mit solchen
Eingaben und dann meinen Server abschießt.
Also es gibt gute Argumente dafür, dass wir den schlechtesten Fall
betrachten.
Und wir betrachten das asymptotisch, also wir sind nicht daran
interessiert, ach, Listen mit mehr als 50 Zahlen werde ich eh wie
sortieren.
Ich schau mir nur an, was macht der Algorithmus für bis zu 50 Zahlen.
Das ist einfach unrealistisch, weil wie ihr auch wisst, die Technik
schreitet immer weiter voran.
Wir haben immer mehr Anwendungen, wo wir die Informatik brauchen und
so eine Einschränkung hier vornherein zu treffen, ist einfach
unrealistisch.
Deswegen machen wir die Annahme, dass die Eingabengröße potenziell bis
ins Unendliche gehen kann.
Und wir sind daran interessiert, den Laufzeitsalgorithmus zu bestimmen
für alle Pälle.
Und jetzt müssen wir uns noch darüber klar werden, wie wir so eine
Laufzeit ausdrücken und dazu gibt es diese schöne Notation.
Diese Notation wird O-Notation genannt und das sind Klassen, die
Funktionen charakterisieren.
Also wir geben die Laufzeit von Algorithmen an in Funktionen.
Also haben wir gerade eben schon gesehen, der eine Sortieralgorithmus
hat n log n Schritte gebraucht, der andere n Quadrat.
Und jetzt sind wir aber daran interessiert, verschiedene Algorithmen
auch theoretisch vergleichen zu können.
Und dazu gibt es diese O-Notation, die diese verschiedenen Typen von
Polynomen charakterisiert in verschiedene Klassen.
Und die erste Klasse ist dieses Groß O von g von n steht jetzt hier.
Und eine Funktion f von n, die ist in Groß O von n, wenn das
folgende...
Achtung, jetzt wird es ein bisschen schwurbelig, aber ich mache es
gleich intuitiv.
Von der Funktion f von n, wir sagen, die liegt in Groß O von g von n,
wenn das folgende gilt.
Es existieren zwei positive Konstanten, c und n0, sodass f von n für
alle n größer als diese Konstante n0, einmal größer als 0 und immer
kleiner gleich diese Konstante c mal g von n.
Was bedeutet das?
Schauen wir uns mal ein anschauliches Beispiel an.
Wir haben jetzt hier eine Funktion f1 von n.
Die macht jetzt hier so einen lustigen Schlenker und dann wächst sie
hier.
Und wir gehen jetzt mal davon aus, sie wächst bis ins Endliche immer
weiter so linear.
Also ein bisschen eine komische Funktion und wir möchten jetzt
feststellen, in welcher Klasse O von irgendwas liegt die denn?
Dann schauen wir mal an, liegt das vielleicht in O von n?
Und wenn ich jetzt O von n betrachte, also n heißt, es ist eine
lineare, einfach so eine Gerade, dann liegt diese Gerade für die
Konstante c1 jetzt unten drunter unter dieser Funktion.
Und zwar ab hier die ganze Zeit.
Bringt auch nix.
Aber jetzt kann ich eine zweite Konstante nehmen, Also eine c2.
Und jetzt ist dieses Rote, diese Gerade, auf einmal über dem Blauen.
Und nämlich ab diesem Punkt.
Und dann haben wir einmal hier so eine Konstante c2 gefunden.
Das ist dann im Prinzip das hier, dieses c.
Und wir haben so einen Punkt gefunden, ab dem ist die rote Funktion
immer über der blauen.
Also diese rote Funktion, die deckelt dann die blaue Funktion von
oben.
Und wir wissen, der Algorithmus wird nie mehr Schritte brauchen, als
diese Funktion c2 mal n.
Und dann sagt man, dass die Funktion f1 von n, die liegt in O von n.
Denn wir haben zwei Konstanten gefunden, dieses c2, dass die Funktion
irgendwann oben drüber liegt.
Und irgendwann ist gegeben durch das n0, hier bei 48 oder sowas, ab da
ist das Rote immer über dem Blauen.
Und dann liegt das in O von n.
Das ist jetzt eine anschauliche Erklärung, was das bedeuten soll.
Das ist natürlich kein Beweis, aber dazu, wenn man sowas beweist,
kommen wir auch gleich noch.
So, jetzt haben wir eine Funktion gefunden, die liegt in O von n.
Und eine andere Funktion, hier dieses Lilerne, das ist f2 von n.
Das hier liegt aber nicht in O von n.
So anschaulich erklärt, könnt ihr euch vorstellen, egal mit welchem
Wert wir diese lineare Gerade multiplizieren, das hier wächst
exponentiell.
Und ab irgendeinem Punkt wird so eine Gerade, egal wie steil sie geht,
immer unter diesem Lilerne sein.
Und damit kann das Lilerne nicht in O von n sein.
Es gibt soweit Fragen.
Dieses Konzept ist am Anfang ein bisschen befremdlich, aber wenn ihr
ein bisschen rumgespielt habt, was ihr da machen könnt, auf dem
Übungsblatt, dann wird es eigentlich meistens relativ schnell klar.
So, wir haben uns jetzt gerade eben dafür interessiert, dieses Blaue
von oben abzudeckeln.
Damit bestimmen wir quasi eine Funktion, die sagt uns, der Algorithmus
braucht im schlechtesten Fall so viele Schritte.
Und wir haben von oben gedeckelt.
Wir wollen aber vielleicht manchmal auch von unten deckeln, dass wir
wissen, der Algorithmus braucht im schnellsten Fall, oder sowas auch
höchstens sowas hier.
Und dafür gibt es diese Komplexitätsklasse Omega von n.
Und Omega von n, die beschäftigt sich, wie gesagt, mit unteren
Schranken.
Also dieses Rote ist irgendwann immer unter dem hier.
Und warum machen wir das?
Wir schauen uns das an, weil wenn ich jetzt hier sowas bestimmt habe,
dass diese rote Funktion die blaue immer von oben deckelt, dann bin
ich vielleicht nicht wirklich optimal.
Dann weiß ich zwar, der Algorithmus braucht höchstens so viele
Schritte, aber vielleicht bin ich auch ganz weit weg von der richtigen
Laufzeit.
Und das Rote, das könnte ja auch hier oben irgendwo rumlaufen.
Und das Blaue ist aber hier unten.
Dann bin ich ziemlich weit weg.
Und wenn ich jetzt so eine Schranke von unten beweisen kann, dann weiß
ich, so ein Bereich, in dem sich der Algorithmus bewegt, und je enger
ich diesen Bereich schätzen kann, desto klarer wird mir, wie schnell
der Algorithmus wirklich ist.
Also hier nochmal die formale Definition von diesem Omega.
Das Omega unterscheidet sich jetzt hier.
An dieser Stelle stand hier noch f von n kleiner als g von n.
Jetzt ist es umgekehrt.
Also g von n liegt immer unter f von n.
Jetzt haben wir zwei Klassen.
Einmal diese O-Kompliziertklasse und einmal dieses Omega.
Das eine deckelt von oben, das andere deckelt von unten.
Und wir können das auch kombinieren.
Oder hier nochmal ein kurzes Beispiel.
Dieses Blaue.
Das Blaue hier liegt in Omega von n, weil das geht hier so
exponentiell nach oben weg.
Und hier habe ich schon eine Konstante gefunden, dass es unten drunter
liegt.
Und da passt es auch.
Wir können das auch kombinieren.
Wir haben einmal dieses O und einmal dieses Omega.
Das können wir kombinieren zu einer Klasse namens Theta.
Und Theta macht beides gleichzeitig.
Also Theta gibt an, ich kann für diese Funktion eine Konstante
angeben, die einmal oben drüber ist und einmal unten drunter.
Und damit kann ich sehr genau angeben, in welcher Laufzeit sich der
Algorithmus bewegt.
In den meisten Fällen in der Vorlesung werden wir uns mit diesem O von
irgendwas begnügen.
Weil das kann man meistens relativ gut festlegen oder bestimmen.
Wohingegen diese untere Laufzeit ist nicht immer so einfach zu
bestimmen.
Und dieses Theta, das mit einer einzigen Funktion von oben und von
unten deckelt, das geht in manchen Fällen vielleicht sogar gar nicht.
Aber es ist alles relevant und alles wichtig, also bitte anschauen.
Jetzt haben wir jetzt schon drei solcher Klassen kennengelernt, aber
drei reicht auch nicht, wir brauchen noch zwei weitere.
Es gibt nämlich noch dieses kleine O und dieses kleine Omega.
Und die unterscheiden sich vom vorherigen so.
Beim vorherigen steht hier, es existieren positive Konstanten.
Hier steht es für alle Konstanten.
Also hier machen wir eine wesentlich stärkere Aussage.
Dieses kleine O und kleine Omega werdet ihr wahrscheinlich in der
Vorlesung auch eher weniger sehen, aber ist auch wichtig, dass ihr das
mal gesehen habt.
Und diesen ganzen Komplex von Notationen nennt man O-Notation oder
auch Landau-Notation.
Um dieses kleine O und kleine Omega auch noch ein bisschen zu
motivieren, hier nochmal so ein paar Beispiele.
Also wir haben hier zwei Funktionen, f1 und f2, die sind in Groß-Omega
von n.
Denn es gibt so eine Konstante c1, dass das n unten drunter liegt.
Ihr seht hier auf dem Bild, das Rote ist immer unter dem Blauen und
immer unter dem Linernen, also ist es in Groß-Omega.
Aber es gibt eine Konstante, nämlich c2, dass das Rote über dem Blauen
liegt.
Und daraus wissen wir jetzt, dass f von n nicht in Klein-Omega liegen
kann.
Denn Klein-Omega spricht über alle Konstanten und wir haben hier eine
Konstante gefunden, sodass diese Bedingung nicht erfüllt ist.
Und damit kann das Blaue, das ist f1, nicht in Klein-Omega von n sein.
Wohingegen bei dem Linernen wissen wir es noch nicht, ob es da eine
Konstante gibt.
Aber unter uns gesagt, so wie das hier aussieht, vermutlich wird das
in Klein-Omega sein von n.
Gibt es zu dieser Anschauung Fragen?
Ich glaube nicht.
Jetzt haben wir uns anschaulich mal angeguckt, wie diese Notation
funktioniert.
Jetzt ist natürlich die Frage, wie beweise ich, dass eine Funktion in
so einer Klasse liegt.
Und das kann man zum Beispiel über Grenzwertbetrachtung machen.
Nämlich es gibt ein paar interessante oder ein paar nützliche
Zusammenhänge.
Die sind hier mal aufgelistet.
Nämlich, wenn ich zeigen will, dass eine Funktion f von n in Klein-O
von g von n liegt, dann kann ich f von n teilen durch g von n und dann
den Limit betrachten für n gegen unendlich.
Und wenn das n gegen unendlich geht und dieser Bruch hat dann Gliedern
gegen 0, dann ist f von n in Klein-O von g von n.
Und das hier ist eine Äquivalenz.
Also wenn das hier gilt, dann liegt f von n in Klein-O von g von n.
Und wenn f von n in Klein-O von g von n liegt, dann gilt auch diese
Beziehung mit dem Grenzwert.
So eine Beziehung mit dem Grenzwert, die existiert auch für das kleine
Omega.
Bloß betrachtet man hier den Limit Superior, den ihr hoffentlich alle
schon in HM gesehen habt.
Wenn nicht, dann könnt ihr den im Kopf mal durch den Limit ersetzen.
In den meisten Fällen wird das zutreffen im Algorithmanumfeld, im
Allgemeinen natürlich nicht.
Und hier ist es jetzt nicht gleich 0, nachdem wir schauen, sondern wir
schauen, dass es gegen unendlich geht.
Das Ganze kann man sich auch irgendwie anschaulich klar machen.
Nämlich, wenn das f von n in Klein-O von g von n liegt, dann haben wir
gesagt, dann liegt das g von n immer über dem f von n.
Das heißt, das g von n, das dominiert dieses f von n irgendwie.
Und wenn ich diesen Bruch betrachte, dann wird der immer kleiner und
immer kleiner.
Während bei diesem Omega ist es genau umgekehrt, dann wird der Bruch
immer größer und immer größer.
Und dann geht es dagegen um unendlich.
Also das ist jetzt komplett Handwavy und kein Beweis oder so.
Aber nur damit ihr euch irgendwie klar machen könnt, wo kommen diese
Beziehungen her.
Und für dieses Theta von irgendwas, da gibt es auch so eine Beziehung.
Hier wieder mit einem Limit.
Und der Limit muss einmal größer sein als 0.
Und er muss einen konstanten Wert annehmen, der kleiner ist als
unendlich.
Aber Achtung, das hier ist keine Äquivalenz, sondern es ist nur eine,
aus dem hier folgt das hier, Beziehung.
Nämlich, wenn das hier gilt, dann liegt f von n in Theta von g von n.
Aber umgekehrt, wenn f von n in Theta von g von n liegt, dann muss
dieser Limit noch lange nicht diese Form annehmen.
Da muss man ein bisschen aufpassen.
Und für das O und das Omega, Groß-O und Groß-Omega, gibt es auch noch
solche Äquivalenzen.
Und die sind im Prinzip das gleiche wie gerade eben, bloß auch wieder
mit dem Lime-Superior.
Und das sind jetzt wieder Äquivalenzen.
In den meisten Fällen, in fast allen Fällen jetzt für die
Übungsaufgaben und sowas, könnt ihr das hier benutzen.
Oder das hier.
Gut.
Was bringt uns das jetzt?
Das haben wir hier so komische Limisse und irgendwelche Grenzwerte.
Machen wir mal ein Beispiel.
Wir haben hier dieses 5n und wir möchten gerne wissen, ob die Funktion
5 mal n, ob die in der Klasse Groß-O von n² liegt.
Jetzt schaue ich kurz zurück in diese Formeln.
Aha, ich muss irgendwie f von n durch g von n betrachten.
f von n war 5 mal n und g von n ist n².
Also tue ich mal f von n durch g von n berechnen.
Dann berechne ich 5n durch n².
Und 5n durch n² ist gleich 5 durch n.
Und dann schaue ich mir davon den Limiss an für das x gegen unendlich,
das sollte n gegen unendlich stehen.
Und das wisst ihr hoffentlich aus HM1, dass dieser Limiss, dieser
Grenzwert, der geht halt gegen 0.
Damit existiert er, damit ist er gleich zum Limiss Superior.
Und damit können wir auch das hier verwenden.
Das f von n ist jetzt aus kleinen O.
Also wir haben jetzt im Prinzip mehr gezeigt als wir müssten.
Wir haben jetzt gezeigt, f von n ist aus kleinen O von n².
Und wenn etwas aus kleinen O ist, dann ist es natürlich auch etwas aus
Groß -O.
Das kann man sich ganz schnell klar machen.
Bei dem kleinen O steht für alle Konstanten, bei dem Groß-O steht für
eine Konstante.
Wenn es für alle Konstanten gilt, dann gilt es natürlich auch für eine
Konstante.
Okay.
Und damit haben wir jetzt gezeigt, dass 5 mal n aus O von n² ist.
Man muss das nicht unbedingt so machen.
Man kann das auch Schritt für Schritt machen, indem man sich die
Formeln der Klassen genau anschaut und dann solche Konstanten angibt
und beweist, dass die Konstanten das gewünschte tun.
In manchen Fällen ist das einfacher als die Grenzerbetrachtung.
In anderen Fällen ist die Grenzerbetrachtung einfacher.
Auf dem Übungsblatt oder in Klausuren, wenn ihr irgendwelche
Funktionen einsortieren sollt in solche Klassen, dann ist es im
Prinzip egal, was ihr verwendet.
Es kam auch schon im Forum die Frage auf, darf ich diese
Grenzerbetrachtung.
Natürlich dürft ihr das.
Also ihr könnt das verwenden.
Aber bei manchen Aufgaben ist es einfacher als direkt zu beweisen.
Aber es ist auch Geschmackssache.
Naja, die Folie ist sinnlos.
Jetzt haben wir hier ein Beispiel, das ist ein bisschen griffiger.
Wir haben die Funktion Sinus von x plus 2.
Und jetzt möchte ich gerne wissen, liegt der Sinus in Theta von 1?
So intuitiv würde man mal sagen, ja.
Denn der Sinus von x, der wird maximal 1.
Nämlich immer an diesen Stellen hier.
Und wenn ich die 2 drauf addiere, wird er halt maximal 3.
Also wenn ich die Funktion 4 mal 1 anschaue, dann liegt die immer oben
drüber.
Genauso wird der Sinus, wenn man ihn betrachtet ohne diese plus 2,
höchstens, also minimal, minus 1.
Und dann hier in diesem Fall, wo ich jetzt 2 drauf addiere, wird er
höchstens, also minimal, zu 1.
Und dann kann ich es auch von unten deckeln durch 1 halb mal 1.
Habe ich im Prinzip zwei Funktionen angegeben, oder zwei Konstanten,
die so intuitiv klar machen, dieser Sinus, der liegt in Theta von 1.
Jetzt war das aber nur eine anschauliche Erklärung und kein Beweis.
Also damit würdet ihr in einer Übungsaufgabe oder in der Klausur
höchstens ein paar Punkte kriegen, denn es ist kein wirklicher Beweis.
Aber jetzt kann man sich fragen, wie beweise ich denn richtig, dass
dieses Sinus von x plus 2 in Theta von 1 liegt.
Und da kann man jetzt erstmal denken, wir haben doch diese schöne
Beziehungen mit den Grenzwerten, schaue ich mal an, ob die
funktionieren.
Und die funktioniert hier leider nicht so gut, denn wir müssten jetzt
folgendes zeigen, wir müssten zeigen, dass f von n durch g von n, wenn
wir davon den Limit betrachten, das sei einmal größer als 0 und einmal
gleich ist es zu einer Konstanten, die kleiner ist als unendlich.
f von n ist in diesem Fall das Sinus von x plus 2 und g von n ist in
diesem Fall die 1.
Also hier steht, der Limus von n gegen unendlich von Sinus x plus 2.
Was kommt da raus?
Was ist der Limus von Sinus von x plus 2 für n gegen unendlich?
Hat da jemand eine Ahnung?
Ja.
Bitte?
Genau.
Der Limus von Sinus von x plus 2, der ist nicht existent.
Denn ihr seht ja, der Sinus, der schlingt immer hin und her, der hat
nur Räufungspunkte, aber der hat keinen Grenzwert.
Also können wir diese Beziehung nicht ausnutzen.
Denn dieser Limus, den wir betrachten müssen, der existiert einfach
gar nicht.
Aber hier ist es gut für uns, dass das keine Äquivalenz ist, sondern
nur eine Folgerung und wir können das Ganze um zwei Ecken betrachten.
Wir betrachten einmal diesen Limus für diese Klasse Groß O.
Also wir zeigen erstmal, dass f von n in Groß O von 1 liegt.
Das kann ich jetzt machen mit dem Limus Superior.
Und der Limus Superior wird hier einfach 3 sein.
Dann ist diese Bedingung erfüllt und damit habe ich gezeigt, Sinus von
x plus 2 ist in O von 1.
Genauso mache ich es mit dem Omega.
Beim Omega habe ich es mit dem Limus Inferior.
Der Limus Inferior von dieser Funktion hier, der ist die 1.
1 ist größer als die 0 und kleiner als ein Endlich.
Dann habe ich damit gezeigt, Sinus von x plus 2 liegt in Omega von g
von n.
Habe ich zwei Sachen gezeigt.
Sinus von x plus 2 liegt in Groß O von 1 und in Groß Omega von 1.
Damit habe ich es von oben gedeckelt mit der 1 und von unten gedeckelt
mit der 1.
Und daraus kann man jetzt das gewünschte folgern.
Nämlich, dass es in Theta von 1 liegt.
Nämlich, das Theta von 1 sagt ja bloß, ich kann es von oben deckeln
und von unten deckeln mit der gleichen Funktion, aber verschiedenen
Konstanten.
Und wenn ich das beweise, es liegt in Groß O und es liegt in Omega von
der gleichen Funktion, dann liegt es auch in Theta von dieser
Funktion.
Das ist hoffentlich intuitiv euch allen klar.
Ansonsten schaut euch kurz nochmal die Definitionen an von diesen
Klassen und dann kann man sich das auch herleiten.
Ein Hinweis zum Logarithmus.
Wenn wir jetzt so Laufzeiten betrachten, dann wird sehr häufig der
Logarithmus eine Rolle spielen.
Und wenn wir so einen Logarithmus hinschreiben in so einer Klasse,
dann lassen wir meistens die Basis weg.
Warum lassen wir die Basis weg?
Naja, einerseits weil die Basis in der Informatik meistens die 2 ist.
Also beschäftigen wir uns meistens mit Bits.
Das kennt ihr alle.
Und zusätzlich ist es innerhalb der O-Notation auf gewisser Weise
egal, welche Basis wir betrachten, denn man kann so einen Logarithmus
von der einen Basis ja umwandeln zum Logarithmus von einer anderen
Basis.
Und dann gilt diese Beziehung.
Also, ich habe hier mal so Groß O von Logarithmus von der N zur Basis
B.
Und jetzt kann ich dieses kleine B immer hinschreiben oder ich lasse
es einfach weg, denn es ist im Prinzip egal was da steht.
Warum ist es egal?
Naja, ich kann dieses Logarithmus von B umwandeln zu einer anderen
Basis.
Dieser Basiswechsel von Logarithmus ist euch hoffentlich allen auch
bekannt aus HM.
Und dann habe ich jetzt hier einmal was stehen.
Logarithmus zur Basis A von N geteilt durch irgendeinen konstanten
Wert.
Aber dieser konstante Wert, durch die Art und Weise wie diese O
-Notation definiert ist, der wird einfach verschluckt von der O
-Notation.
Denn die O-Notation interessiert sich nur für Dinge die nicht konstant
sind.
Zum Beispiel die Funktionen 5n², 6n², 7n², die sind alle in O von n².
Diese Konstanten vorne dran, die fallen einfach weg, die werden durch
diese O-Notation, wenn man sich die Definition mal genau anschaut,
einfach verschluckt.
Und genauso wird hier dieses, ich sag jetzt mal,
Basiswechselhilfsmittel von der O-Notation auch verschluckt.
Und dann können wir hier einsehen, dass Groß O von Logarithmus von N
zur Basis B das gleiche ist wie Groß O von Logarithmus zur Basis A von
N.
Für völlig beliebige a und b.
Deswegen lassen wir in den Notationen meistens die Basis weg, weil es
einfach nicht relevant ist, wenn wir Laufzeitbetrachtungen machen.
Zumindest asymptotisch gesehen.
Soviel soweit zum Thema Laufzeiten von Algorithmen.
Jetzt als nächstes wollen wir über die Korrektheit von Algorithmen
sprechen.
Wir kommen am Ende der Übung nochmal auf Laufzeit zu sprechen, aber
jetzt wollen wir erstmal über Korrektheit von Algorithmen reden.
Wir haben jetzt gerade eben argumentiert, dass es für uns wichtig
wäre, dass der Algorithmus irgendwie schnell ist.
Weil wir wollen keinen langsamen Algorithmen.
Genauso wichtig wie zu wissen, wie schnell ist ein Algorithmus, ist
für uns aber auch, dass der Algorithmus das Richtige tut.
Aber wenn ich irgendeinen Algorithmus entwickle, dann möchte ich
hinterher auch wirklich wissen, dass er das tut, was ich vorhabe.
Also wenn ich einen Sortieralgorithmus entwickle, dann will ich mir
hinterher auch sicher sein, dass er wirklich die Zahlen aussortiert
und nicht irgendwie die Zahlen löscht oder sowas.
Und deswegen möchten wir gerne die Korrektheit beweisen.
Also wir möchten beweisen, dass ein Algorithmus das tut, was wir von
ihm verlangen.
Beim Sortieralgorithmus möchte ich beweisen, dass der Algorithmus auch
sortiert.
Das wäre aber auch cool, wenn wir das könnten.
Da aber gleich mal eine schlechte Nachricht.
Wir können das nicht unbedingt immer.
Also in vielen Fällen, auch in ziemlich abgedrehten Fällen, wo der
Beweis extrem kompliziert ist, kriegt man das hin.
Aber es gibt auch Algorithmen, wo man das vielleicht nicht unbedingt
hinbekommt.
In solchen Fällen, oder generell überhaupt zum Beweis von Korrektheit
von Algorithmen, ist es interessant, sich einzelne Schleifen zu
betrachten.
Also Schleifen sind Grundbausteine von Algorithmen.
Und da kann man sich ja anschauen, dass zumindest die einzelnen
Schleifen das Richtige tun.
Und sowas macht man über sogenannte Schleifeninvarianten.
Also eine Bedingung, die invariant bleibt, also unverändert, während
die Schleife berechnet.
Also wir haben eine Bedingung für eine Schleife.
Die Schleife läuft und wir wissen, vor der Schleife gilt die
Bedingung.
Innerhalb der Schleife gilt die Bedingung immer.
Und nach der Schleife gilt die Bedingung auch.
Wenn wir so einen Zusammenhang haben, kann uns das helfen, die
Korrektheit zu beweisen.
Also machen wir folgendes.
Wir finden so eine Bedingung, wir finden so eine Invariante.
Und wir beweisen diese Invariante.
Und das machen wir meistens induktiv, also durch vollständige
Induktion.
Das grobe, allgemeine Vorgehen besteht aus drei Schritten.
Wir haben so eine Initialisierung.
Also bevor wir in die Schleife gehen, da müssen wir zeigen, dass
unsere Invariante auch schon gilt.
Das ist der erste Schritt.
Der zweite Schritt ist, dass wir zeigen müssen, dass während die
Schleife berechnet, dass die Invariante auch gilt.
Das machen wir, indem wir uns irgendeinen Schleifendurchlauf, den
Schleifendurchlauf I oder die Iteration I anschauen.
Und wir zeigen, wenn wir zur Iteration I plus 1 gehen, dann ist die
Invariante immer noch erhalten.
Und im dritten Schritt zeigen wir, dass die Schleife irgendwann
terminiert.
Also dass sie abbricht.
Also dass diese Abbruchbedingung erfüllt ist.
Und wir zeigen, dass die Invariante auch nach der Schleife gilt.
Und dann kann man daraus häufig, nicht unbedingt immer, aber häufig
folgern, dass die Schleife das Richtige tut.
Wir haben dann nämlich bewiesen, diese Invariante gilt vor der
Schleife, in der Schleife und nach der Schleife.
Und zusätzlich terminiert die Schleife auch irgendwann.
Und daraus können wir hoffentlich folgern, dass das richtige Ergebnis
rauskommt.
Oder zumindest so eine Nachbedingung erfüllt ist, die uns dabei hilft,
zu beweisen, dass der Algorithmus das Richtige tut.
Dieses grobe allgemeine Vorgehen, das wollen wir uns mal an Beispielen
anschauen.
Hier nochmal kurz hingeschrieben, das erste und zweite.
Das machen wir im Prinzip wie so eine Art mathematische Induktion.
Aber der Unterschied zu der normalen vollständigen Induktion ist jetzt
der dritte Punkt.
Nämlich, wir sind daran interessiert, dass die Iteration irgendwann
abbricht.
Wohingegen die vollständige Induktion läuft immer bis zum Endlich.
Hier sind wir jetzt in der Informatik und wir wollen keine
Algorithmen, die bis zum Endlich laufen.
Wir wollen die Algorithmen auch irgendwann hoffentlich terminieren.
Und deswegen interessieren wir uns bei so Invarianten dann auch dafür,
dass diese Iteration abbricht.
Und müssen das im Beweis entsprechend auch betrachten.
Gut, jetzt erstmal bevor wir an ein richtiges Beispiel gehen, machen
wir mal so ein Spielzeugbeispiel.
Wir brauchen drei Dinge.
Wir brauchen so eine Vorbedingung, wir brauchen so eine
Schleifeninvariante und wir brauchen so eine Nachbedingung.
Und jetzt stellt euch mal vor, wir haben hier so ein Algorithmus
-Grundgerüst.
Der Algorithmus, der kriegt irgendeine Eingabe.
Und diese Eingabe, mit der macht er irgendwie was und am Ende gibt er
irgendwas aus.
Jetzt tue ich den Algorithmus versehen mit so einer Vorbedingung.
Und diese Vorbedingung, die schränkt die Eingabe irgendwie ein.
Vielleicht will ich, dass der Algorithmus nur funktioniert, wenn die
Zahlen größer als 0 sind.
Vielleicht will ich, dass der Algorithmus nur mit Zahlen funktioniert,
die ungerade sind oder sowas.
Und das schreibe ich in die Vorbedingung rein.
Und dann kann ich mich für den Rest vom Beweis darauf beziehen.
Ich rede nur über solche Fälle, wo diese Vorbedingung gilt.
Auch dazu kommt gleich ein Beispiel.
Lasst das hoffentlich klar machen, was das soll.
Und dann haben wir jetzt hier so eine Weisschleife.
Die Weisschleife macht irgendwas und am Ende, wenn die Weisschleife
fertig ist, wollen wir, dass irgendeine Nachbedingung erfüllt ist.
Die Nachbedingung hilft uns dann, die Korrektheit zu beweisen.
Oder die Nachbedingung ist schon die Korrektheit von dem Algorithmus.
Und jetzt innerhalb der Schleife, da kommt die Schleife in die
Variante hin, von der ich gerade eben gesprochen habe.
Wir haben drei Dinge.
Wir haben so eine Vorbedingung, die gerade am Anfang gilt.
Wir haben so eine Schleife in der Variante, von der müssen wir zeigen,
dass sie am Anfang der Schleife gilt und bei jedem Schleifendurchlauf
auch.
Und wir müssen zeigen, dass sie nach der Schleife immer noch gilt.
Und wir müssen die Nachbedingung beweisen.
Nämlich wenn hier die Schleifenbedingung am Ende immer noch erfüllt
ist, dann wollen wir daraus folgern, dass die Nachbedingung auch
erfüllt ist.
Also insofern die Schleife überhaupt terminiert.
Gut.
Also das Vorgehen im Allgemeinen ist es, finde so eine
Schleifeninvariante, beweise oder zeige diese Schleifeninvariante und
dann mit Hilfe dieser Schleifeninvariante und irgendwelchen sonstigen
Wissen, können wir dann die Korrektheit der Algorithmus beweisen.
Als einfaches Beispiel schaut euch mal diesen Algorithmus hier an.
Der Algorithmus kriegt als Eingabe ein Array und er soll das maximale
Element in diesem Array bestimmen.
Hier jetzt ein relativ sinnvolles Beispiel für eine Vorbedingung.
Wenn ich innerhalb eines Arrays die maximale Zahl bestimmen möchte,
dann brauche ich eigentlich nur Arrays angucken, die auch Zahlen
enthalten.
Wenn das Array leer ist, dann braucht der Algorithmus nichts zu tun,
ist für uns uninteressant.
Wenn ich jetzt ein Algorithmus programmiere, dann muss ich diesen
Sonderfall abfangen.
Aber jetzt für diesen Korrektheitsbeweis können wir mal davon
ausgehen, dass das Array zumindest mal irgendwelche Elemente enthält.
Dann gibt es hier zwei Indizes, das ist das I und das J.
Und in diesem I werden wir den Index speichern des maximalen Elements.
Und dieses J ist so ein Hilfszähler.
Dann haben wir hier eine Schleife, die erkläre ich gleich.
Und am Ende haben wir so eine Nachbedingung, nämlich wir haben die
Nachbedingung, dass am Ende des Algorithmuses innerhalb des Index I
uns den Index angibt vom größten Element innerhalb des Arrays.
Also dieses argmax sagt einfach, dass was hier steht, ist der Index,
sodass dieser Wert a von L maximal wird.
Also a von I ist das maximale Element im Array.
Dieses argmax ist eigentlich eine Bezeichnung für Funktionen.
Also wir machen jetzt mal so ein bisschen Abuse of Notation.
Dass wir hier was verwenden, was eigentlich über Funktionen redet und
wenden das auf Arrays an.
Man kann ja so ein Array auch als eine Art Funktion betrachten.
Und dann ist die Nachbedingung also, dass hier drin der Index steht
vom maximalen Element.
Also wir haben die Vorbedingung und wir haben die Nachbedingung.
Und ihr seht schon, die Nachbedingung für dieses einfache Beispiel,
das ist im Prinzip sofort die Korrektheit.
Wenn ich die Nachbedingung beweisen kann, dass der Algorithmus, wenn
er durchgelaufen ist, diese Nachbedingung erfüllt, dann habe ich auch
bewiesen, dass er das Maximum bestimmt in dem Array.
So, und jetzt kommt unsere Pfeifen im Variante.
Wir haben hier diese Schleife.
Diese Schleife, die nimmt dieses J und die inkrementiert es immer bis
ans Ende vom Array.
Also wir haben hier angefangen mit Index 0 bis N-1 und wir
inkrementieren immer dieses J.
Und was wir machen ist, wir merken uns hier im I das größte Element.
Und zwar am Anfang sagen wir mal ganz hypothetisch, das größte Element
steht an Index 0.
Wenn ich jetzt einen anderen Index gefunden habe, sodass das Element
größer ist als das aktuelle, dann setze ich natürlich den Index auf
diesen neuen Index.
Und ich zähle es immer hoch.
Wenn es kleiner ist oder gleich, mache ich nichts.
Ich hoffe der Algorithmus ist soweit klar, ist relativ grundlegend
oder auch relativ einfach.
Diese Schleifen im Variante, bzw.
wie sieht die Schleifen im Variante überhaupt aus?
Die sieht so aus.
Wir haben als Invariante wieder diese Argmax, aber wohingegen hier
diese Argmax steht bis zu N, betrachten wir in der Invariante nur das
Argmax bis zu J.
Also was hier steht ist, dass in dem Index I, der Index I gibt das
größte Element an in dem Bereich von 0 bis J.
Also wir haben das maximale Element in dem Bereich von 0 bis J in A
von I gegeben.
Also die Invariante ist hier mal zufällig, fast genauso wie die
Nachbedingung, bloß die Nachbedingung beschäftigt sich mit dem ganzen
Array.
Die Invariante beschäftigt sich nur mit dem Array bis zu dem Punkt, an
dem wir es jetzt schon betrachtet haben.
Jetzt wollen wir diese Invariante beweisen und das machen wir, wie
gesagt, mit so einer Art Induktion.
Und die Induktion fängt an mit Schritt 1.
Also der erste Schritt ist die 1 und das ist im Prinzip klar.
Wenn J gleich 1 ist, dann betrachte ich nur das Element A0.
Denn wir haben ja dann hier diese kleineren Beziehungen und dann ist
ja eigentlich ganz klar, da wird alles passen.
Im A0 steht aktuell der richtige Wert.
Also diese Invariante, die bezieht sich ja nur auf die Zahlen von 0
bis dein Alles kleiner als J.
J ist 1, also bezieht sich hier nur auf die 0, deswegen passt das.
Das ist hoffentlich klar.
Für alles, was größer ist als 1, also wir machen jetzt den
Induktionsschritt von J zu J plus 1.
Da wissen wir folgendes.
Wir wissen, es gilt, dass im I der Index steht, sodass das hier
erfüllt ist.
Also das ist der A-Max von L bis J plus 1.
Also wir wissen, dass A von I ist das maximale Element bis zu J plus
1.
Wenn wir beweisen, nach der Schleife ist es auch noch erfüllt, dann
machen wir folgendermaßen.
Im ersten Fall, also wir wollen jetzt diesen A-Max, der aktuell nur
bis kleiner J plus 1 geht, wollen wir erweitern auf kleiner J plus 2,
mehr oder weniger.
Und das müssen wir erweitern, weil wir innerhalb dieser Schleife das J
immer wieder hochzählen und dann hier das neue betrachten.
Und im ersten Fall ist das J plus 1 Element größer als das I.
Das heißt, wir hätten im Prinzip ein neues Maximum gefunden, also muss
der Algorithmus den Wert I anpassen.
Das macht der Algorithmus auch, er passt das an.
Wenn das größer ist, passt das an.
Also ist es in dem Fall immer noch gültig, wie in der Invariante.
Im zweiten Fall ist dieses neu betrachte Element kleiner gleich, also
kein neues Maximum.
Wenn das der Fall ist, dann macht die Schleife nichts anderes, als
dass ihr hier hochzählt, dieses If ist nicht erfüllt, hier wird nichts
getan, also wird kein Update ausgeführt und diese A-Max Beziehung ist
immer noch erhalten.
Und damit haben wir diese einfache Schleifeninvariante bewiesen.
Also müssen wir uns einfach klar machen, dass der Algorithmus bis zu
einer bestimmten Grenze die Elemente hat und wenn das nächste Element,
wenn das größer ist, dann tun wir das natürlich updaten und damit
steht in diesem Index immer wieder das Richtige.
Jetzt haben wir die Invariante gezeigt, jetzt wollen wir noch zeigen,
dass auch die Nachbedingung erfüllt ist.
Dazu müssen wir zeigen, dass die Schleife irgendwann terminiert.
Das ist hier relativ einsichtig, weil wir haben hier eine ganz
einfache kleine Beziehung und das j wird einfach immer hochgezählt.
Also die Schleife terminiert irgendwann, irgendwann hat j den Wert n
erreicht, dann bricht die Schleife ab.
Und wir haben gerade eben gezeigt, dass die Schleifeninvariante nach
jedem Durchlauf von der Schleife gilt.
Also gilt sie auch ganz am Ende.
Ganz am Ende ist das j aber das n und wir hatten gezeigt, dass im i
immer das argmax steht bis zum Wert j.
Also steht im i das argmax bis zum n, genau das ist die Nachbedingung
und damit liefert der Algorithmus das korrekte Ergebnis.
Das wäre ein Beispiel für eine Schleifeninvariante, wie man die findet
und wie man die beweist.
Ich habe noch einen zweiten Algorithmus als Beispiel.
Der Algorithmus, der hat den tollen Namen FunWithAlgorithms und der
macht folgendes.
Er kriegt als Eingabe eine natürliche Zahl n.
Dann schaut er sich die Menge an von Zahlen von 1 bis n.
Also ihr könnt euch das vorstellen, es gibt so ein Array z, das
enthält alle Zahlen von 1 bis n.
Und dann macht er folgendes, er nimmt diese Menge oder dieses Array
her, geht in diese Schleife rein und solange mehr als ein Element drin
ist in dieser Menge, nimmt er einfach irgendwelche Elemente raus, zwei
verschiedene Elemente, vollkommen egal welche.
Er löscht die aus dieser Menge und er fügt die Multiplikation dieser
zwei Elemente wieder hinzu.
Und das Ganze macht er bis nur noch ein Element drin ist.
Jetzt ist eine natürliche Nachbedingung, dass am Ende diese Menge auch
wirklich nur noch ein Element enthält.
Das ist relativ klar, weil die Schleife bricht halt genau dann ab,
wenn es nur noch ein Element enthält.
Und die Menge wird in jedem Schritt kleiner.
Es werden immer zwei Elemente rausgenommen und ein Element
hinzugefügt.
Also die Menge wird in jedem Schritt um 1 kleiner.
Jetzt wollen wir beweisen, dass der Algorithmus das Richtige tut.
Gleicherweise müssen wir aber erstmal wissen, was macht der
Algorithmus überhaupt.
Hat da irgendjemand eine Idee?
Der Algorithmus multipliziert alle Zahlen von 1 bis n.
Also er berechnet im Prinzip n Fakultät.
Das ist jetzt natürlich ein bisschen ein Quatsch-Algorithmus, aber
einfach um euch nochmal das Vorgehen klar zu machen, wie das
funktioniert.
Wir haben jetzt die Behauptung, der Algorithmus berechnet n Fakultät.
Und das wollen wir beweisen.
Also erstmal werden wir die Nachbedingungen aktualisieren.
Wir sagen, am Ende steht im 0.
Element das n Fakultät.
Und dann müssen wir uns eine Invariante ausdenken und die beweisen.
Und die Invariante, die ist jetzt hier einfach, wenn ich alle Elemente
nehme aus der Menge z und ich multipliziere sie, dann kriege ich
wieder n Fakultät.
Im Prinzip sagt diese Invariante jetzt hier nichts anderes aus, als
dass der Algorithmus während diese Schleife läuft, keine Zahlen in
Anführungszeichen vergisst.
Diese Invariante wollen wir beweisen.
Und der Induktionsanfang, der ist eigentlich auch wieder relativ klar,
denke ich.
Am Anfang, bevor die Schleife startet, da steht in Set einfach alle
Zahlen von 1 bis n.
Also ist das S, S nenne ich jetzt hier das Produkt der Zahlen, die in
der Menge drin sind, ist einfach das Produkt von allen i von 1 bis n.
Also von 1 bis n, das ist n Fakultät.
Da ist noch nichts groß passiert.
Jetzt der Induktionsschritt.
Da nehme ich an, dass das hier erfüllt ist für die bisherige Menge z.
Und jetzt verändert der Algorithmus ja das z.
Also ich muss zeigen, dass diese Veränderung im Algorithmus, also der
Algorithmus nimmt hier zwei Zahlen raus und er tut eine neue Zahl
rein.
Das schreibe ich hier so hin.
Wir müssen zeigen, dass das immer noch gleich n Fakultät ist.
Wie mache ich das?
Naja, ich schaue mir diesen Wert S' mal an.
Also S' ist jetzt der Wert nach dem Schleifendurchlauf.
Und das beweise ich so.
Ich nehme das S' her.
Und dann kann ich feststellen, S' ist das gleiche wie das S.
Aber geteilt durch das A, weil das A nehme ich raus.
Und geteilt durch das B, weil das B nehme ich raus.
Und multipliziert mit dem A mal B, weil das A mal B nehme ich hier mit
rein.
Dann kürzt sich hier das weg.
Und dann haben wir genau S stehen.
Und S war n Fakultät.
Und damit habe ich auch bewiesen, dass diese Schleife nichts vergisst.
Also die Schleife vergisst keine von den Zahlen.
Und sie macht genau das Richtige.
Damit haben wir also bewiesen, dass auch nach dem Schleifendurchlauf,
immer noch, wenn ich alle Zahlen aufmultipliziere innerhalb dieser
Menge Z, das n Fakultät rauskommt.
Damit habe ich die Invariante bewiesen.
Jetzt bleibt mir nur noch zu beweisen, dass die Nachbedingung erfüllt
ist.
Und das ist eigentlich auch relativ easy.
Die Schleife bricht genau dann ab, wenn nur ein Element drin ist.
Wir haben gezeigt, nach der Schleife ist auch diese Invariante
erfüllt.
Und damit gilt auch nach der Schleife diese Bedingung, dass wenn ich
die Elemente, die noch drin sind, aufmultipliziere, was jetzt nur noch
ein Element ist, dann ist es n Fakultät.
Also muss im Null-Element n Fakultät stehen.
Und damit macht der Algorithmus das, was er tun soll.
Ich kann mir gut vorstellen, dass das jetzt alles ein bisschen schnell
ist und nicht ganz so einfach.
Und vielleicht auch nicht ganz so eingängig.
Aber wenn ihr euch die Folien nochmal anschaut, dann wird es euch
bestimmt klar.
Und in den Tutorien werden eure Tutoren auch nochmal das Thema
Schleifende Invariante mit euch thematisieren.
Also wie gesagt, die Nachbedingung gilt.
Also gibt der Algorithmus hier am Ende genau n Fakultät aus.
Und damit liefert er das korrekte Ergebnis.
Unsere Behauptung, dass der Algorithmus n Fakultät ausgibt, haben wir
damit bewiesen.
Und damit wären wir fertig mit dem Thema Schleifende Invariante.
Und wir kommen zum anderen wichtigen Thema.
Nämlich zu dem Thema Teile und Herrsche.
Dieses Thema, Teile und Herrsche, ist sehr wichtig für die komplette
Informatik.
Was meine ich mit diesem Teile und Herrsche?
Wenn wir Algorithmen entwickeln, dann sollten Algorithmen ja immer
irgendwelche Probleme lösen.
Und diese Probleme, die sind vielleicht ziemlich groß.
Also irgendwelche gigantischen Listen von Zahlen.
Und diese gigantischen Listen von Zahlen will ich sortieren.
Also ich nehme jetzt gerade mal mehr das Beispiel des
Zahlensortierens.
Oder stellt euch vor, in eurer WG kommt man wieder nach Hause und euer
Mitbewohner hat die Küche immer mehr dreckig hinterlassen.
Und jetzt habt ihr keine Lust mehr auf eine dreckige Küche und ihr
wollt die Küche aufräumen.
Wie macht ihr das?
Ihr guckt euch an, welche Teile in der Küche sind dreckig.
Also ihr tut das Problem des Kücheaufräumens in mehrere kleine
Probleme.
In Spüler aufräumen, den Tisch abwischen, die Teller abwischen oder
sowas.
Diese Probleme sind vielleicht immer noch zu groß.
Was heißt Spüler aufräumen?
Spüler aufräumen kann sich nochmal zu Teilen in die dreckigen Teller
abwaschen, die Teller einräumen und so weiter und so fort.
Also in so ganz kleine Probleme, die ganz greifbar sind.
Und dann löse ich diese einfachen Probleme.
Also ich spüle die Teller, ich räume die Teller ein.
Oder wenn ich zu einem eher Informatikbeispiel komme.
Wenn ich eine Liste habe aus zwei Zahlen und ich will die sortieren,
dann ist das kein Problem mehr.
Oder wenn ich eine Liste habe aus einer Zahl und ich will die
sortieren, dann ist das kein Problem mehr.
Also ich nehme ein großes Problem her und ich zerbreche das große
Problem nach und nach in kleinere Probleme.
So lange, bis das Problem so klein und so einfach ist, dass es schon
regelrecht trivial ist, dieses Problem zu lösen.
Und wenn ich dann diese kleinen Probleme gelöst habe, dann setze ich
auf geschickte Art und Weise, also dieses Problemlösen nennt man
beherrschen die kleinen Probleme, dann setze ich diese kleinen
Lösungen zusammen.
Also ich habe jetzt meinen Teller abgespült, ich habe meinen Teller
eingeräumt und wenn ich alles das gemacht habe, dann ist die Küche
halt sauber in meiner WG und ich kann wieder in Ruhe kochen.
Oder wenn ich meine Listen sortiert habe, die nur aus zwei Elementen
bestehen, dann muss ich mir einfach nur die sortierten Listen
anschauen und in richtiger Reihenfolge zusammenkleben und dann habe
ich auch das große Problem gelöst.
Also ich nehme das Problem her, ich mache es immer kleiner, bis es
ganz einfach ist, ich löse die einfachen Probleme und dann baue ich
die einfachen Problemlösungen zusammen zu der Problemlösung von dem
großen Problem.
Das bringt uns jetzt zu einer wichtigen Frage, nämlich wenn ich das so
mache, wie berechne ich dann die Laufzeit von so einem Algorithmus?
Denn so ein Algorithmus, der wird typischerweise rekursiv sein.
Das heißt, der Algorithmus, der wird sich irgendwie selbst aufrufen.
Er kriegt als Eingabe irgendwie eine Probleminstanz, jetzt hier nur
eine natürliche Zahl, und dann ruft er sich selbst auf mit einer
kleineren Zahl.
Ganz am Anfang von der Vorlesung habe ich gesagt, so oberflächlich
könnt ihr bei der Laufzeitbestimmung einfach zählen, wie viele
Rechenschritte mache ich, aber wie viele Rechenschritte mache ich denn
jetzt, wenn ich mich selbst aufrufe?
Das ist nicht unbedingt einfach einzusehen und deswegen müssen wir
hier die Laufzeit anders betrachten.
Das macht man typischerweise durch so eine Rekurrenzgleichung.
Also wir drücken diese Rekursion in eine Gleichung aus, die genau
dieses Aufteilen erfasst.
In diesem Beispiel, also wir haben jetzt einen Algorithmus, der
rekursiv das Teilwort des Problems zerlegt in zwei kleinere Probleme,
nämlich immerhin genau die gleiche Hälfte, und der betrachtet nur eine
Hälfte von den Problemen.
Dann kann ich die Laufzeit von meinem Algorithmus darstellen, als die
Laufzeit von meinem Algorithmus in dem Fall, dass ich nur die Hälfte
von den Elementen betrachte, plus die Zeit, die ich hier oben zum
Aufteilen und hier unten zum Zusammensetzen brauche.
Und dann habe ich hier so eine Gleichung, so eine Rekurrenzgleichung,
die mir die Laufzeit angibt von meinem Algorithmus und dann muss ich
noch bestimmen, was diese Gleichung eigentlich genau darstellt.
Wenn man das macht, wollen wir gleich thematisieren, aber kurz vorher
mal ein Beispiel, nämlich diese Karatsuba-Offmann-Multiplikation.
Die kennt ihr aus der Vorlesung.
Da ging es darum, wir wollen zwei lange Zahlen geschickt miteinander
multiplizieren, sodass es ganz schnell geht.
Aufgrund der vorgeschrittenen Uhrzeit werde ich das Beispiel ein
bisschen knapper halten.
Und in diesem Algorithmus, da wird der Multiplikationsalgorithmus
selbst wieder dreimal aufgerufen.
Jetzt habe ich hier so ein Beispiel vorbereitet, wie der Algorithmus
funktioniert.
Aufgrund der vorgeschrittenen Uhrzeit muss ich das jetzt leider
durchklicken, weil der Rest ist mir wichtiger, als jetzt hier so ein
Zahlenbeispiel zu machen.
Aber das könnt ihr zu Hause nachvollziehen, wie der Algorithmus
funktioniert.
Das ist nicht schwierig.
Ihr braucht übrigens, weil ich es mehrmals gesehen habe, die Folie
nicht zu fotografieren.
Die Folien kommen online.
Wir haben jetzt hier diesen Algorithmus.
Und der Algorithmus, der zerlegt das Problem in drei Teilprobleme und
ruft sich dann selbst wieder auf mit dem kleineren Teilproblem.
Und das wollen wir darstellen in so einer Rekurrenzgleichung.
Und die Rekurrenzgleichung ist einfach für den Fall, dass ich zwei
Zahlen habe, die nur aus einer Stelle bestehen.
Da sagen wir, das ist der Basisfall.
Da ist Multiplizierung ganz einfach.
Da gebe ich dem Algorithmus mal jetzt die Laufzeit 1.
Und ansonsten tue ich es zerlegen in Probleminstanzen, die so groß
sind wie die Hälfte des Originalproblems.
Und das mache ich dreimal.
Und dann muss ich das noch irgendwie zusammenrechnen, was da
rauskommt.
Also ich zerlege es in dreimal die Hälfte und rufe mich dann selbst
auf.
Und mache am Ende noch irgendwas.
Damit komme ich zu meiner Rekurrenzgleichung.
Und jetzt muss ich irgendwie angeben, in welcher Klasse O von
irgendwas diese Rekurrenzgleichung liegt.
Also wie bestimme ich jetzt die Laufzeit davon im OK-Kühl?
Das mache ich mit dem Mastertheorem.
Das kennt ihr aus der Vorlesung in einer einfachen Variante.
Das Mastertheorem sagt, wenn man eine Rekurrenz diese vor mir hat,
dann muss ich betrachten, was hier vorne steht und was hier steht bei
dem Aufteilen.
Und solange hinten nur so ein linearer Term steht, dann bat mir das
Mastertheorem, in welcher Komplexitätsklasse das liegt.
Bei dem Karatsubo Hoffmann gerade eben, da stand hier eine 3 und hier
eine 2.
Jetzt gucke ich, 3 ist größer als 2.
Okay, hier steht im Fall, dass D größer ist als B, kommt das hier
raus.
Also kommt hier raus bei Karatsubo Hoffmann, dass die Laufzeit in
Theta von N hoch Nog 2 von 3 ist.
Ihr müsst aufpassen, dieses Mastertheorem könnt ihr nur anwenden, wenn
hier hinten so ein linearer Term steht.
Es gibt das Mastertheorem auch noch in komplizierteren Varianten, die
auch damit umgehen können, dass hier hinten was anderes steht, aber
die betrachten wir in der Vorlesung hier nicht.
Deswegen noch kurze Hinweise, was mache ich denn, wenn hier hinten
irgendwas steht, was nicht linear ist.
Also zum Beispiel hier hinten steht nicht 5 mal N oder so, sondern
hier hinten steht N plus Log N.
Dieses plus Log N, das passt nicht in die Form von diesem
Mastertheorem.
Also kann ich es nicht einfach draufschmeißen und gucken was da
rauskommt, sondern ich muss mir ein bisschen mehr Gedanken machen.
Und dann kann ich aber diese Rekurrenz schachteln, einmal von unten
und einmal von oben.
Also Mastertheorem ist nicht anwendbar, aber ich schachtel jetzt von
unten und von oben.
Nämlich einmal ich mache eine neue Rekurrenz, wo ich dieses Log N
einfach weglasse.
Und dann steht hier nur plus N und kein Log N mehr.
Und dann passt diese Rekurrenz genau in dieses Schema von
Mastertheorem.
Dann kann ich das Mastertheorem draufschmeißen und ich finde raus, das
Tier 1 von N ist aus Theta von N.
Damit habe ich es von unten betrachtet.
Weil diese Rekurrenz, die wird immer kleiner sein als das hier, weil
ich einfach das Log N weglasse.
Genau das gleiche kann ich von oben her machen.
Indem ich das Log N einfach ersetze durch nochmal ein N.
Also hier steht dann N plus N, also einfach zweimal N.
Und jetzt passt es auch wieder aufs Mastertheorem.
Dann kann ich auf diese Rekurrenz auch das Mastertheorem
draufschmeißen.
Und kriege auch raus, dass diese Rekurrenz aus Theta von N ist.
Weil ich jetzt zwei Rekurrenzen angegeben habe, die entweder immer
kleiner sind oder immer größer, als die Rekurrenz, für die ich mich
eigentlich interessiere und ich für beide feststellen konnte, dass sie
in Theta von N liegen, dann muss auch hier dieses T von N in Theta von
N liegen.
Das ist neben dem Mastertheorem eine wichtige Möglichkeit, wie man so
Rekurrenzgleichungen lösen kann.
Diese Möglichkeit werden auch eure Tutoren im Tutorium nochmal genau
mit euch besprechen.
Manchmal funktioniert aber auch das nicht.
Zum Beispiel in so einem Fall, wenn ich hier schon so einen N² habe.
Beim Mastertheorem kann ich aber nur anwenden, wenn hier hinten
irgendwas mit N steht.
Das Log N konnte ich gerade eben wegkriegen, weil es mit Plus da
stand, aber ich zitiere einen N² und das Mastertheorem kann mit diesem
N² nicht umgehen.
Und jetzt kann ich nur noch eins machen, nämlich vollständige
Induktion und dazu muss ich irgendwie durch geschicktes Nachdenken
oder geschicktes Raten eine obere Schranke ausdenken und dann durch
vollständige Induktion beweisen, dass diese obere Schranke gilt.
Also Mastertheorem ist in so einem Fall, wo hier ein N² steht, oder N³
oder N mal Log N oder Plus Wurzeln oder sowas, nicht unbedingt
anwendbar.
Und dann muss ich eine obere und untere Schranke finden.
Wie finde ich so eine obere und untere Schranke?
Eine gute Möglichkeit ist es, wenn man einfach mal ein paar Zahlen
einsetzt und dann so ein Gefühl dafür kriegt, wie sich diese
Rekkurrenz entwickelt.
Je größer die Zahlen werden, man kann sich auch vielleicht mal ein
einfaches Skript mit Python oder so schreiben, das die Rekkurrenz kurz
ausrechnet für 100 Zahlen und dann so ein Gefühl dafür kriegen.
Und dann beweise ich meine geratene Schranke durch vollständige
Induktion.
In dem Fall kann ich zum Beispiel beweisen, dass dieses T von N immer
größer ist als N³ und immer kleiner ist als 2N³-N².
Diese beiden Behauptungen muss ich mit vollständiger Induktion
beweisen und dann habe ich bewiesen, dass T von N eben Heter von N³
ist.
Ich werde euch auch noch eine Datei hochladen, wo drinsteht, wie das
funktioniert.
Und eure Tutoren sollen auch solche Aufgaben mit uns vorrechnen.
Damit wären wir für heute am Ende der Vorlesung.