Eine Ansage vorweg hinsichtlich Übungsblattabgabe.

Wie angekündigt ändern wir die Regelung von Übung zu Übung.

Allerdings noch nicht auf diesem Zettel.

Auf diesem Zettel, der aktuell raus ist, werden Sie feststellen, haben Sie ersatzweise eine

Woche länger Zeit als sonst mit Rücksicht auf den Berg.

War ein Gorinsidee.

Ja, gut, wir hatten uns zuletzt also angeguckt, zum einen unser Berechnungsmodell, die Random

Access Machine und zum anderen ein paar grundsätzliche Aspekte von Pseudocode, auf die wir uns geeinigt

haben, den wir also verwenden, um Programme in dieser Random Access Machine zu beschreiben.

Wir wollen jetzt im üblichen Falle nicht hingehen und also jetzt diesen Pseudocode

tatsächlich uns kompiliert vorstellen in die RAM und dann einzeln dieser Anweisungen

zählen.

Das ist nicht so grammdösig bei, sondern was man tut ist, man hat eben ja jetzt sich

diese O-Notation verschafft, man interessiert sich nur für asymptotisches Verhalten und

macht deswegen die Analyse direkt auf dem Pseudocode.

Das ist also wesentlich weniger anstrengend als einzelne Anweisungen der Random Access

Machine zu zählen.

Anstrengend genug ist es trotzdem noch.

Um jetzt mal Neil Jones zu zitieren, dessen Buch wir ja in diesem Semester nicht verwenden,

Programme Analysis isn't easy.

Aber man hat da Methoden, die man verwenden kann und diese Methoden, die sehen wir uns

heute an.

Die greifen nicht immer, aber die greifen oft.

Als größere Überschrift schreibe ich heute mal Zeitanalyse darüber.

Der zweite Teil ist streng genommen auch auf völlig andere Dinge anwendbar.

Wir teilen das in zwei Teile.

Ein einfacherer, sehr schnell abgehandelter am Anfang für nicht-rekursive Programme, die

also rein über Iteration laufen, die also Schleifen verwenden.

Die sind so ein bisschen leichter zu analysieren als rekursive Programme.

Anschließend wenden wir uns den rekursiven Programmen zu und unser Hauptwerkzeug zur Analyse

rekursiver Programme ist das sogenannte Master Theorem.

Also einmal ohne Rekursion können wir einfach so ein paar arithmetische Grundregeln verwenden,

die uns durch die meisten Programmanalysen so einigermaßen durchhelfen.

Und zwar sind das Analysen der Kontrollstrukturen oder Gesetze über das Zeitverhalten von Kontrollstrukturen.

Ich habe nur gar nicht gesagt, was die Kontrollstrukturen sind, die wir zulassen und ich lege mich da

auch absichtlich nicht fest, aber die wesentlichen Kontrollstrukturen, die man immer hat, sind

typischerweise dreierlei.

Erstens hat man sequenzielle Kompositionen von Programmen, also man kann Anweisungen

hintereinander schreiben.

Zweitens hat man Verzweigung, man hat sowas wie if-then-else.

Und drittens hat man Schleifen.

Gut, gucken wir uns das an.

Erster und einfachster Fall, ich führe zwei Programmteile hintereinander aus, sequenzielle

Kompositionen.

Wie lange dauert das?

Na ja, offensichtlich dauert es so lange, wie es dauert, erst den ersten Teil auszuführen

und dann den zweiten auszuführen, also Addition.

Und weil die Random Access Maschine ja schon ein ähnliches Konstrukt mitbringt, die Random

Access Maschine gestattet ist, mir Anweisungen einfach in Liste hintereinander zu schreiben

und ich zwei solche Listen habe, hänge ich die einfach hintereinander, hat das auch