Definition Algorithmus
Unterschied Algorithmus, Programm
Defintion Datentyp, Datenstruktur
arithmetische Reihe
geometrische Reihe
harmonische Reihe
4 Logarithmengesetze
inkrementeller Algorithmus
Vier Sortieralgorithmen
Definition Schleifeninvariante
Bedingung, die
a) zu Beginn der Schleife immer erfüllt ist
b) bei Abbruch der Schleife Korrektheit liefert
Algorithmus: Korrektheit beweisen nach Schema F
Was ist n bei der Laufzeitanalyse?
Wovon hängt die Laufzeit ab?
Was ist das?
n ist die Eingabegröße (z.B. n unsortierte Karten)
Die Laufzeit hängt vom Rechenmodell ab.
Rechenmodell RAM (Abkürzung? Drei Bestandteile? Laufzeit?)
Laufzeit
worstcase Laufzeit
Groß-Oh von g
Groß-Omega von g
Groß-Theta von g
Klein-Oh von g
Klein-Omega von g
Rechenregeln Landau-Symbole (Addition? Multiplikation? Transitivität?)
Vergleich Laufzeiten 4 Algorithmen:
Teilen, herrschen, kombinieren
Beispiel:
Techniken Korrektheitsbeweise:
iterativer vs. rekursiver Algorithmus
Last changed9 days ago
