Herzlich willkommen zur Vorlesung. Schönen guten Tag alle zusammen. Ja, sie kann auch gerne kommen,

selbstverständlich. Wir schließen hier keine aus. So, wo befinden wir uns eigentlich? Wir

befinden uns hier in der Vorlesung Einführung in die Algorithmik. Wir hatten gestern Abend schon

das schöne Vergnügen und haben angefangen, uns mit Laufzeitanalysen zu beschäftigen. Wir haben ja

die Frage gestellt, jetzt habe ich so einen Algorithmus und ist der eigentlich gut, was

bedeutet gut? Eine Möglichkeit des Messens der Güte ist natürlich die Laufzeit. Wir wollen immer

schneller sein. Andere Metriken, die wir auch kurz besprochen haben, waren zum Beispiel der

Speicherbedarf. Wie viel Speicher brauche ich, um eine gewisse Aufgabe auszuführen? Das heißt,

wir befinden uns immer noch in dem Abschnitt über Aufwandsanalyse. Dazu haben wir ein neues

Berechnungsmodell eingeführt und wir hatten wunderschöne Notationen eingeführt, im wesentlichen

theta, O und groß omega. Und diese Notationen dienen insbesondere dazu, die Laufzeit des

Algorithmuses abzuschätzen. Und was wir auch gesagt haben, war es ist im wesentlichen eine

asymptotische Betrachtung. Das heißt, der Anfang hier für kleine Eingabewerte ist meistens nicht

so interessant, weil die Rechenleistung auch immer schneller wird. Deswegen ist das hier eigentlich,

man könnte sagen, fast egal. Wir sind vielmehr daran interessiert, naja, was passiert, wenn wir

das Verfahren auf riesigen Daten ausführen. Und was wir hier sehen, ist im Wesentlichen die

Beschreibung von groß theta. Das heißt, wir haben eine bestimmte Laufzeit, die wir gerne von f

verstehen möchten, die wir abschätzen möchten. Und das Tolle daran ist, dass f im Wesentlichen sich

verhält wie eine Funktion g von n. Und was heißt im Wesentlichen? Naja, das heißt, dass zwei

Konstanten c1 und c2 die Laufzeit einmal nach oben beschränken und einmal nach unten beschränken.

Danach hatten wir auch noch die Groß-O-Notation, das ist eigentlich das, was wir, denke ich,

am meisten nutzen werden. Kann man sich im Wesentlichen diese lila Linie hier wegdenken,

das heißt, wir sind im Wesentlichen daran interessiert, naja, was beschränkt meine Laufzeit,

wie kann ich meine Laufzeit nach oben beschränken? Und das letzte, was wir hatten,

ups, war Groß-O-, hallo, Moment, war Groß-O- und da denken wir uns die rote Linie weg und

beschränken im Wesentlichen die Laufzeit nach unten. So, das war ein guter Ansatz,

um erstmal warm zu werden mit den Themen. Was wollen wir heute machen? Nein, wir wollen nicht

lesen in 3.1, 3.2 oder 3.3, das sind die Referenzen für die Abschnitte im Common. Wir wollen uns

insbesondere damit beschäftigen, wie können wir eigentlich mit diesen Funktionen arbeiten und

rechnen? Im nächsten Abschnitt werden wir die Frage stellen, okay, wir wollen jetzt mal eine

konkrete Laufzeit analysieren, wie machen wir das? Und da fangen wir mit dem Bereich der wunderschönen

Rekursionen an. Also insbesondere hier natürlich als Beispiel, die Weit an Konka haben. Und weil

wir, jetzt hätte ich fast gesagt, ein bisschen faul sind, nein, wir sind natürlich nicht faul,

sondern wir sind effizient, schauen wir uns im letzten Abschnitt das Mastertheorien an,

das berühmte Mastertheorien, was uns bei der Analyse ein Großteil der Arbeit abnehmen wird.

Okay, also wir fangen hier an, im Wesentlichen im zweiten Teil der Vorlesung und wollen gerne

die Laufzeit von Rekursionen analysieren und dann merken wir, oh, das ist gar nicht so einfach,

und relativ aufwendig. Und glücklicherweise gibt es ein wunderschönes Theorien, das uns das in

vielen Fällen, das Leben in vielen Fällen erleichtert. So, dann legen wir los an diesem

wunderschönen Freitag. Gut, hier sieht man es nicht drin, aber. Also wir wiederholen noch mal die

Notation, mit der wir uns ganz zum Schluss beschäftigt haben. Und wir wollen auch ein

Gefühl dafür bekommen, was bedeutet das überhaupt? Was ist denn der Unterschied

zwischen linearer Laufzeit oder logarithmischer Laufzeit? Was heißt quadratischer Laufzeit? Also

zunächst wiederholen wir die einzelnen Definitionen. Was wir gerade schon besprochen haben,

war im Wesentlichen die Täternotation. Nach der Vorlesung hat mich einer von Ihnen angesprochen,

sehe ich gerade nicht, und hat gesagt, naja, das ist ja irgendwie alles hier ein bisschen komisch

definiert. Vollkommen richtig. Gehen wir, gehe ich gleich noch mal drauf ein. Also wie ist die

Notation definiert? Wir fangen an, indem wir eine Funktion betrachten, nämlich g von n,

und wir bezeichnen mit Großtäter von g von n die Menge an Funktionen für die Folgen des Geld.

Also zunächst haben wir gerade gelernt, dass es sich um Mengen handelt, das ist richtig,