Flashcards Algorithmen - Tabellenblatt1
Was sind die Eigenschaften eines Algorithmus?
Korrektheit, Vollständigkeit, Eindeutigkeit/Ausführbarkeit, statische Endlichkeit, dynamische Endlichkeit, Effizienz
Definition Schleifeninvariante
Eine Schleifeninvariante ist eine Aussage über eine Variable, die stets gültig ist, wenn die Wiederholbedingung geprüft wird.
Eigenschaften einer Schleifeninvariante
1.Die Invariante ist vor der ersten Iteration der Schleife wahr 2.Wenn sie vor der Iteration wahr ist, bleibt sie auch zum Beginn der nächsten Iteration wahr (Invariante bleibt erhalten) 3.Wenn die Schleife terminiert, liefert die Invariante eine zweckdienliche Eigenschaft, die hilft zu zeigen, dass der Algorithmus korrekt ist
Zeichen für Worst-case - Laufzeit
Θ (Theta)
Woraus besteht das Teile- und Beherrsche-Prinzip?
- Teilen (Aufteilen des Problems in kleinere Instanzen des gleichen Problems) 2. Beherrschen (rekursives Beherrschen des Teilproblems, direkte Lösung für ausreichend kleine Teilprobleme) 3. Vereinigen (Vereinigen der Teillösungen zur Gesamtlösung)
Θ(g(n))
eine Menge von Funktionen: {f(n): es existieren positive Konstanten c1, c2 und n0, so dass 0 <= c1*g(n) <= f(n) <= c2*g(n) für alle n >= n0}. Θ(g(n)) ist eine asymptotisch scharfe Schranke von f(n).
O(g(n)) (O-Notation)
eine Menge von Funktionen: {f(n): es existieren positive Konstanten c und n0, so dass 0 <= f(n) <= c*g(n) für alle n >= n0}. O(g(n)) ist eine asymptotische obere Schranke von f(n).
Omega(g(n))
eine Menge von Funktionen: {f(n): es existieren positive Konstanten c und n0, so dass 0 <= c*g(n) <= f(n) für alle n >= n0}. Omega(g(n)) ist eine asymptotische untere Schranke von f(n).
o(g(n)) (klein o-Notation)
eine Menge von Funktionen: {f(n): für jede positive Konstante c > 0 existiert ein konstantes n0, so dass 0 < cg(n) für alle n >= n0}. o(n) ist eine obere Schranke, die nicht asymptotisch scharf ist.
ω(g(n)) (klein omega-Notation)
eine Menge von Funktionen: {f(n): für jede positive Konstante c > 0 existiert ein konstantes n0, so dass 0 <= cg(n) <= f(n) für alle n >= n0}. ω(m) ist eine untere Schranke, die nicht asymptotisch scharf ist.
Eigenschaften von Insertion Sort
Einfach, effizient für kleine Datenmengen, adaptiv für grob vorsortierte Listen (O(n)), stabil, in place. Nach k Iterationen sind die ersten k+1 Elemente der Liste sortiert. Best-case: O(n), Worst-case: O(n^2), Average-case: O(n^2)
Eigenschaften von Selection Sort
Einfach, je nach Implementierung stabil. Nach k Iterationen enthält die Subliste 1..k die k kleinsten Elemente der Liste in sortierter Folge. Best-case=Worst-case=Average-case: O(n^2)
Eigenschaften von Bubble Sort
Einfach, stabil. Best-case: O(n), Worst-case: O(n^2), Average-case: O(n^2)
Eigenschaften von Heap Sort
In place. Best-case=Worst-case=Average-case: O(n log n).
Eigenschaften von Quick Sort
In place. Performance abhängig von Balance der Partitionierung. Kleine versteckte Faktoren in O(n log n). Best-case=Average-case: O(n log n). Worst-case: O(n^2).
Eigenschaften von Merge Sort
Stabil, gut parallelisierbar. Speichereffizienz worst-case: O(n). Best-case=Worst-case=Average-case: O(n log n).
Eigenschaften von Divisionshashes
h(k) = k mod m. Schnelle Berechnung. Zweierpotenzen für m sollten vermieden werden (da k mod m sonst nur von den zwei niederwertigen Bits von k abhängt). Wenn k eine Zeichenkette interpretiert, sollte m=2^p-1 vermieden werden, da sonst Permutationen des Strings kollidieren. Empfehlung für m: Primzahl, die nicht zu nahe an einer Zweierpotenz liegt.
Eigenschaften von Multiplikationshashes
h(k) = floor(m(k*A mod 1)). Wähle eine Konstante A aus ]0..1[, multipliziere mit k, extrahiere den gebrochenen Teil (mittels mod 1), multipliziere mit m, runde ab (oder auf). Nachteil: langsamer als Division. Vorteil: Wert von m spielt keine kritische Rolle (kann auch Zweierpotenz sein).
Laufzeit naives String Matching
Vorverarbeitung: O(1)
Matching: O((n-m+1)m)
Laufzeit Rabin-Karp
Vorverarbeitung: Theta(m)
Matching: O((n-m+1)m) (worst-case)
Laufzeit endlicher Automat
Vorverarbeitung: O(m*|Sigma|)
Matching: Theta(n)
Laufzeit Knuth-Morris-Pratt
Vorverarbeitung: Theta(m)
Matching: Theta(n)
Laufzeit Countingsort
Worstcase: Theta(k+n)
Laufzeit Radixsort
Worst
Laufzeit Bucketsort
Worst: Theta(n^2)
Avg/Best: Theta(n)
