Algorithmen und Komplexität - Stundenplan

Der Stundenplan dient als Tagebuch, um festzuhalten, was wir tatsächlich in den Vorlesungen gemacht haben. Hier kündige ich auch an, welche Übungsaufgaben Sie bis zum nächsten Termin anschauen sollten.

15. Januar 2024	Edit-Distanz. Definition, Beispiele. Algorithmus: Edit-Distanz als Problem günstigster Pfade in einem bestimmten DAG. Das Algorithmische Paradigma Dynamic Programming an drei Beispielen: Edit-Distanz; bestes Sub-Array; Knapsack. Dynamic Programming verstehen, indem man erst einen rekursiven Algorithmus hinschreibt, dann versteht, dass nur wenige Inputwerte überhaupt vorkommen und diese dann "auszurollen" und die Rekursion durch ein paar verschachtelte for-Schleifen zu ersetzen.
8. Januar 2024	Kürzeste Wege (nicht Pfade!) in Graphen, wo Kanten auch negative Kosten haben können: Bellman-Ford-Algorithmus.
18. Dezember 2023	Kruskals Algorithmus. Union-Find-Datenstrukturen. Union-by-Rank with Path Compression. Meine Folien zu Union-Find with Path Compression.
11. Dezember 2023	Gerichtete Graphen, starke Zusammenhangskomponenten. Dijkstras Algorithmus.
4. Dezember 2023	Gerichtete Graphen, topologisches Sortieren. Programmierübungen mit Graphenalgorithmen, u. A. mit der englischen Vokabelliste.
27. November 2023	Gerichtete Graphen, Breitensuche. Savitch's Algorithmus. Code: Meine Java-Implementierung von Graphen, in denen Sie Namen statt Zahlen für die Knoten verwenden können: 02-named-graphs.zip.
13. November 2023	Komplexität arithmetischer Operationen, also Kapitel 5. Insbesondere Fibonacci-Zahlen iterativ berechnen, was $O (n^{2})$ ergibt; empirisch, dass eine Verdopplung des Inputs zu einer Vervierfachung der Laufzeit führt; per Matrixmultiplikation, was auch $O (n^{2})$ ergibt; per schneller Matrixmultiplikation, was überraschenderweise dazu führt, dass eine Verdopplung des Inputs zu einer Verdreifachung der Laufzeit führt. Dann haben wir die Laufzeit der Integer-Multiplikation unter die Lupe genommen, insbesondere die Schulmethode für schriftliches Multiplizieren, die $O (n^{2})$ ergibt; einen naiven, von Mergesort inspirierten rekursiven Algorithmus, der auch $O (n^{2})$ ergibt; den rekursiven Karatsuba-Algorithmus, der $O (3^{\log_{2} n})$ ergibt, wo also eine Verdopplung des Inputs zu einer Verdreifachung des Outputs führt.
6. November 2023	Untere Schranken. Wägeproblem und die untere Schranke $\log_{3} n$ . Dann die Vergleichsbäume von Sortieralgorithmen und die untere Schranke von $\log_{2} (n!) = Θ (n \log n)$ für vergleichsbasierte Sortieralgorithmen. Quickselect und Median-of-Medians-Algorithmus. Fibonacci-Zahlen: rekursiv, iterativ. Empirische Messung der Laufzeit. Meine (schlampigen) Notizen finden Sie hier: quickselect.py quickselect.txt fib.py fib.txt Das Thema über die Fibonacci-Zahlen finden Sie auch im Kapitel 5 im Vorlesungsskript.
30. Oktober 2023	Asymptotik: $⌈ \log (n + 1) ⌉$ mit $\log_{2} (n)$ vergleichen. Laufzeiten von Quicksort, Heapsort, Mergesort vereinfachen. $O$ - und $Ω$ -Notation.
23. Oktober 2023	Heapsort und Quicksort.
16. Oktober 2023	Naive Sortieralgorithmen wie Selectionsort und Insertionsort. Effizienter Sortieralgorithmus Mergesort. Rekursionsbaum, Laufzeitanalyse.
9. Oktober 2023	Binäre Suche. Am Beispiel der englischen Vokabelliste. Dann am Beispiel der Wurzelfunktion.