| 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! |
|
