- 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!) = \Theta(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:

Das Thema über die Fibonacci-Zahlen finden Sie auch im Kapitel 5 im Vorlesungsskript.

30. Oktober 2023 Asymptotik: \(\ceil{\log(n+1)}\) mit \(\log_2(n)\) vergleichen. Laufzeiten von Quicksort, Heapsort, Mergesort vereinfachen. \(O\)- und \(\Omega\)-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.