Тема: Vorlesungsfolien | WS23: Algorithmen und Datenstrukturen

Section outline

Für die meisten (aber nicht alle!) Vorlesungen wird es Videos geben, die man sich spätestens zum jeweiligen Vorlesungstermin anschauen kann.
In der Tabelle unten liefert ein Klick aufs jeweilige Datum die Kurz-/Druckversion der Folien; ein Klick aufs Thema die Langversion.

Datum	Thema	Videos (alt!)	Literatur
17.10.2023	Organisation und Einführung
17.10.2023	Sortieren I (InsertionSort)	Inkrementeller Algorithmus (24') – Fakultät (11')
19.10.2023	Sortieren II (MergeSort)	Pseudocode + Beispiel (18') – Korrektheit (16')
24.10.2023	Laufzeitanalyse, Groß-Oh-Notation	Vergleich InsertionSort und MergeSort (18') – Klassifikationsschema für Funktionen (12')
26.10.2023	Laufzeitanalyse am Beispiel	Kubischer Algorithmus für MaxSum (15') – Schnellere Algorithmen für MaxSum (22')
31.10.2023	Rekursionsgleichungen lösen	Substitutionsmethode (10') – Rekursionsbaummethode (10') – Meistermethode (10')
02.11.2023	Prioritätsschlangen, Heaps, HeapSort	Prioritätsschlange, MaxHeapify, BuildMaxHeap (23') – HeapSort (12')
07.11.2023	Zufallsexperimente	Gedankenexperiment (17') – Average-Case-Analyse von InsertionSort (11') – Geburtstagsparadoxon & Bonustrack (7')
09.11.2023	QuickSort und RandomizedQuickSort	(Deterministisches) QuickSort (16') – Erwartete Laufzeit von Randomized QuickSort (19')
14.11.2023	Sortieren in Linearzeit [18.12.: Kleine Änderung beim Entscheidungsbaum]	Untere Schranke (13') – CountingSort (10') – RadixSort (7') – BucketSort (14')
16.11.2023	1. Zwischentest	Anmelden nicht vergessen!
21.11.2023	Das Auswahlproblem	Randomisiertes Select (23') – Deterministisches Select (15')
23.11.2023	Elementare Datenstrukturen	Abstrakter Datentyp: Dynamische Menge (8') – Stapel, Schlange, Liste (10') – Von Pseudocode zu Javacode (8')
28.11.2023	Hashing	direkte Adressierung und Hashing mit Verkettung (22') – gute Hashfunktionen und Hashing mit offener Adressierung (23')
30.11.2023	Binäre Suchbäume	Vorarbeiten und Traversierung (21') – Methoden (15')
05.12.2023	Rot-Schwarz-Bäume	Logarithmische Höhe (16') – Einfüge-Operation (16')
07.12.2023	fällt aus!	–
12.12.2023	Datenstrukturen augmentieren [12.01.: Kleine Änderung auf S. 12]	Augmentieren – komplett (28')
14.12.2023	2. Zwischentest	Anmelden nicht vergessen!
19.12.2023	Amortisierte Analyse [21.12.: Klammer hinzugefügt]	Aggregationsmethode (9') – Buchhaltermethode (6') – Potentialmethode (9')
21.12.2023	Nächstes Paar	Leider gibt's für diese Vorlesung kein Video :-(
09.01.2024	Graphen: Repräsentation und Breitensuche	Beispiele und Repräsentation (16') – Breitensuche (23')
11.01.2024	Kürzeste Wege und Dijkstras Algorithmus	Dijkstras Algorithmus (22') – Kürzeste Wege und T9 (7')	Dijkstras Originalartikel (3 Seiten, 1959) Das Geheimnis des kürzesten Weges (Gritzmann & Brandenberg, 2005)
16.01.2024	Tiefensuche und topologische Sortierung	Tiefensuche (Beispiel, Pseudocode, Eigenschaften) (22') – Topologische Sortierung (Anwendung, Korrektheit) (12')
18.01.2024	3. Zwischentest
23.01.2024	Minimale Spannbäume [24.01.: bei Def. Schnitt Detail ergänzt]	Generischer Algorithmus und Korrektheit (13') – Algorithmen von Jarník–Prim(–Dijkstra) und von Kruskal (18')
25.01.2024	Dynamisches Programmieren	Stabzerlegung (22') – Längste Wege (8')
30.01.2024	Greedy-Algorithmen	Ein einfaches Problem der Ablaufplanung (15') – Ein gewichtetes Problem der Ablaufplanung (14')
01.02.2024	Problem des Handlungsreisenden	Vorlesungsmitschnitt vom WS 2021, leider ohne die ersten 5' (59')	In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Cook, 2012)
03.02.2024	1. Klausur	Anmelden auf WueCampus nicht vergessen!
11.04.2024	2. Klausur	Anmelden auf WueStudy (ab 15.03. oder 01.04.2024) nicht vergessen!