Analyse

Korrektheit, Laufzeit, Speicherplatz, Kommunikationszeit, Güte u.a

idealisierte Rechenmodelle -> Registermaschine -> festgelegter Befehlssatz

Die Laufzeit ist dann die Anzahl ausgeführter RAM-Befehle

Ermittlung charakteristische Parameter wie Schlüsselvergleich, mem swaps & arithmetik

Siehe Laufzeit 2^n bei Moore's law nützt das nicht, weil eine z.B bri nur +7 angenommen Laufzeit 1s => 1m …

da 2 · 2^n = 2^n+1 (eine Verdopplung bei +1 n ergo für jeden weiter Wert min 2 Jahre warten :(

O(g) = {f | ∃c ∈ R+ ∃n0 ∈ N ∀n ≥ n0 : 0 ≤ f (n) ≤ c · g(n)}. Dabei betrachten

wir nur Funktionen mit natürlichen Funktionswerten, also f, g : N → N, weil wir die Anzahl

von Schritten oder benutzten Speicherzellen angeben. Konstante Faktoren c werden bei Aufwandsabschätzungen vernachlässigt; es wird nur das asymptotische Wachstum der Funktionen betrachtet, also das Verhalten bei großen Werten von n.

Nein. Es können auch obere Schranken für Average- oder Best-Case-Abschätzungen

angegeben werden. Groß-O heißt nicht automatisch Worst-Case, es beschreibt lediglich obere

Schranken

Divide-and-conquer

Dynamische Programmierung

Greedy

Backtracking

Branch-and-Bound

Lokale-Suche

Divide the problem into subproblems.

Conquer the subproblems by solving them recursively

Combine subproblem solutions

Bei Divide-And-Conquer entstehen in den rekursiven Aufrufen Teillösungen, die wir

im Combine-Schritt zusammen fügen müssen. Damit wir nicht dieselben Teilprobleme immer

wieder rekursiv lösen, werden bereits berechnete Teillösungen in Tabellen gespeichert. Diesen Ansatz nennt man memorieren.

Anstatt die Teillösungen rekursiv zu berechnen, kann man aber auch einen Bottom-Up-Ansatz

wählen: Aus Rekursion wird Iteration, indem wir aus kleinen Teillösungen größere Lösungen

zusammensetzen. Da wir nicht von vorneherein wissen, welche Teillösungen wir benötigen,

berechnen wir einfach alle. Dieses Verfahren wird oft bei Optimierungsproblemen eingesetzt

und heißt dynamische Programmierung

Unter anderem beim 0/1-Rucksack-Problem, beim Wechselgeld-Problem, bei der

Levenshtein-Distanz und bei einigen Grafalgorithmen wie z.B. die transitive Hülle oder all-

pairs-shortest-path.

Das Optimalitätsprinzip von Bellman: Eine optimale Lösung kann aus optimalen Teillösungen zusammengesetzt werden; dies gilt z.B. bei kürzesten Wegen: jeder Teilweg

(vi, . . . , vj ) eines kürzesten Weges (v1, . . . , vi, . . . , vj , . . . , vk) ist ebenfalls ein kürzester Weg