Welche Eigenschaften interessieren uns bei Algorithmen?
Korrektheit, Laufzeit, Speicherplatz, Kommunikationszeit, Güte u.a
Wie bewerten bzw. vergleichen wir Algorithmen?
idealisierte Rechenmodelle -> Registermaschine -> festgelegter Befehlssatz
Die Laufzeit ist dann die Anzahl ausgeführter RAM-Befehle
Ermittlung charakteristische Parameter wie Schlüsselvergleich, mem swaps & arithmetik
Warum ist die Komplexität der Algorithmen interessant? Sind heutige Rechner nicht
für alle Probleme ausreichend schnell?
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 :(
Wir haben zur asymptotischen Aufwandsabschätzung die Klasse Groß-O definiert. Geben Sie diese Definition an und erklären Sie die einzelnen Teile.
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.
Wird die Groß-O-Notation nur für die Angabe von Worst-Case-Abschätzungen genutzt?
Mit Erläuterung
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
Wie ist die Worst-Case-Laufzeitkomplexität definiert?
Welche grundlegenden Entwurfsmethoden für Algorithmen kennen Sie?
Divide-and-conquer
Dynamische Programmierung
Greedy
Backtracking
Branch-and-Bound
Lokale-Suche
Wie funktioniert ”divide and conquer“?
Divide the problem into subproblems.
Conquer the subproblems by solving them recursively
Combine subproblem solutions
Als Beispiel für einen Divide-And-Conquer-Algorithmus hatten wir Strassens Matrix-
multiplikation kennengelernt. Wodurch unterscheidet sich der vom naiven Algorithmus?
Welche Idee liegt der ”dynamischen Programmierung“ zugrunde?
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
Bei welchen Problemen haben wir dynamische Programmierung eingesetzt?
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.
Welche allgemeine Bedingung muss erfüllt sein, damit dynamische Programmierung
eingesetzt werden kann? (mit Erklärung)
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
Geben Sie die zu optimierende Funktion beim 0/1-Rucksack-Problem an.
Welche Idee liegt der Greedy-Methode zugrunde und welche Probleme haben wir mit
Greedy-Algorithmen gelöst?
dee des Greedy-Algorithmus für das Rucksack-Problem?
Idee des Greedy-Algorithmus für das Wechselgeld-Problem?
Wie kann mittels dynamischer Programmierung das Wechselgeld-Problem gelöst wer-
den?
Was ist das Master-Theorem und auf welche Probleme lässt es sich anwenden
Nennen Sie ein Problem, bei dem die Laufzeit mit Hilfe des Master-Theorems berechnet
werden kann. Geben Sie die Rekursionsgleichung an und erklären Sie die einzelnen Terme
Geben Sie einen Algorithmus zur Multiplikation von zwei Matrizen der Größe n × n an.
Welche Komplexität hat der Algorithmus? (mit Erklärung)
Zuletzt geändertvor 2 Monaten
