Suchen
Suchen Sie den Wert 17 mittels Interpolationssuche in der Folge
1, 3, 5, 8, 11, 17, 25, 29, 37, 39, 41.
Geben Sie in jedem Schritt den Index der linken und der rechten Grenze sowie den Index des
zu prüfenden Elements, das zu prüfende Element selber und Ihre Rechnung an. Die Regel für
die Interpolationssuche lautet:
Wir haben zur asymptotischen Aufwandsabschätzung die Klasse Groß-O definiert. Ge-
ben Sie diese Definition an und erklären Sie die einzelnen Teile.
Wie ist die Worst-Case-Laufzeitkomplexität definiert?
ben Sie diese Definition an und erklären Sie die einzelnen Teile
Wie ist Groß-Omega definiert
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.
Welche Idee liegt der Greedy-Methode zugrunde und welche Probleme haben wir mit
Greedy-Algorithmen gelöst?
Wie funktioniert ”divide and conquer“
Divide the problem into subproblems.
Conquer the subproblems by solving them recursively.
Combine subproblem solutions
Dynamische Programmierung Bedingungen
Es werden rein ”lokale Entscheidungen“ getroffen, bei denen nach einem gegebenen
Kostenmaß das jeweils nächste Element gewählt wird. Das Verfahren ist iterativ. Im Schritt i
wird aus allen möglichen ”Fortsetzungen Ai einer Teillösung“ diejenige ausgewählt, die momentan den besten Erfolg bringt. Es werden also nicht verschiedene Kombinationen von Teillösungen getestet, sondern nur eine einzige ausgewählt. Diese Lösung ist ggf. nicht optimal.
Probleme: Rucksack-Problem, Handlungsreisenden-Problem (nur approximativ), Wechselgeld-
Problem (ist nicht für alle Münzsysteme exakt), Präfix-Code nach Huffman und bei einigen
Graphalgorithmen wie z.B. minimaler Spannbaum nach Kruskal
Welche Laufzeit hat Quicksort im mittleren Fall? Skizzieren1 Sie, wie man zu diesem
Ergebnis kommt.
Welche Worst-Case-Laufzeit hat Quicksort und für welche Folgen wird diese tatsächlich
erreicht
Worst-Case-Laufzeit ist O(n^2)
stark vorsortierte Folgen oder solche Folgen, die viele gleiche Elemente enthalten
Wie groß ist die Rekursionstiefe bei Quicksort im worst-case und wie können wir die
Rekursionstiefe beschränken?
Was ist ein allgemeines Sortierverfahren und welche untere Schranke gilt für solche
allgemeinen Sortierverfahren?
Allgemeine Sortierverfahren verwenden ausschließlich Vergleichsoperationen zwi-
schen Schlüsseln, um die Positionen der Werte in der sortierten Folge zu bestimmen, aber
keine arithmetischen Operationen oder ähnliches.
Jedes allgemeine Sortierverfahren benötigt zum Sortieren von n verschiedenen Schlüsseln im
schlechtesten Fall und im Mittel wenigstens Ω(n · log(n)) Schlüsselvergleiche
Ist es möglich, im Worst-Case schneller als in Zeit O(n * log(n)) zu sortieren? Falls ja, dann beschreiben Sie einen solchen Algo
Ja, unter bestimmten Voraussetzungen. Counting bzw Radixsort für Integer-Werte.
Einzelnen Ziffern bzw bit Gruppen werden sortiert, durch ein zählbasiertes verfahren, (wie bucket sort), sodass das ganze branchless und in immer gleich in bekannter Zeit passiert, egal welcher Datensatz, durch jegliche verschieben durch bit shiften und swapen, und der aufsteigenden signifikanz der buckets sind die zahlen in konstanter Zeit O(n) sortiert.
Was ist eine topologische Sortierung und wie können wir algorithmisch eine solche
bestimmen?
dfb,dfe, kanten typen
kanten typen
Welche Idee liegt der ”dynamischen Programmierung“ zugrunde?
Warum macht es Sinn, Bäume zu balancieren
Welche asymptotische Laufzeit ergibt sich beim Einfügen von n zufälligen Werten in einen balancierten Suchbaum? Mit Formel.
O(N log(N))
unbalancierten T(N)∈Θ(N log N) d. h. im Mittel werden pro Einfüge-Operation Θ(logN) \Theta(\log N)Θ(logN) Vegleiche ausgeführt
Welche Struktur und welche Eigenschaft hat ein Suchbaum
oder AVL
Suchbaum: Höhen balanciert (binär baum z.B)…
Greedy algs
Münzwechselproblem
Minimaler Spannbaum (MST) → Kruskal oder Prim sind greedy.
Treffe in jedem Schritt die lokal beste Entscheidung, in der Hoffnung, dass die Gesamtlösung dadurch optimal wird. Keine Rückschau, kein Zurücksetzen.
Divide & Conquer
Mergesort (Teilen: Liste halbieren, Rekursion, Kombinieren: Merge).
Quicksort (Pivot wählen, partitionieren, rekursiv sortieren).
Binäre Suche (Problem halbieren, richtige Hälfte weiter durchsuchen).
Matrixmultiplikation (Strassen-Algorithmus).
Dyn Prog
Kernidee Statt dieselben Teilprobleme immer wieder rekursiv zu lösen (Divide & Conquer), berechne jede Teillösung nur einmal und speichere sie in einer Tabelle. Man arbeitet
Top-Down mit Memoisation (rekursive Formel + Cache) oder
Bottom-Up (Iteration über wachsende Teilproblemgrößen).
Damit sinkt die Laufzeit von exponentiell auf polynomial, weil sich „überlappende Teilprobleme“ mehrfach nutzen lassen.
Wann darf ich DP einsetzen?
Das Optimalitätsprinzip von Bellman muss gelten: Eine optimale Gesamtlösung setzt sich aus optimalen Teillösungen zusammen (→ optimal substructure). Außerdem darf es nur endlich viele verschiedene Teilprobleme geben, sonst explodiert die Tabelle.
greedy vs dyn
Interpolationsuche
Last changeda month ago
