| 15.10.2024 |
Organisation und Einführung |
|
|
| 15.10.2024 |
Inkrementell sortieren (InsertionSort) |
Inkrementeller Algorithmus (24') – Fakultät (11') |
|
| 17.10.2024 |
Teilen und herrschen (MergeSort) |
Pseudocode + Beispiel (18') – Korrektheit (16') |
|
| 22.10.2024 |
Laufzeitanalyse, Groß-Oh-Notation |
Vergleich InsertionSort und MergeSort (18') – Klassifikationsschema für Funktionen (12') |
|
| 24.10.2024 |
Laufzeitanalyse am Beispiel "Maximales Teilfeld" |
Kubischer Algorithmus für MaxSum (15') – Schnellere Algorithmen für MaxSum (22') |
|
| 29.10.2024 |
Rekursionsgleichungen lösen |
Substitutionsmethode (10') – Rekursionsbaummethode (10') – Meistermethode (10') |
|
| 31.10.2024 |
Prioritätsschlangen, Heaps, HeapSort |
Prioritätsschlange, MaxHeapify, BuildMaxHeap (23') – HeapSort (12') |
|
| 05.11.2024 |
Zufallsexperimente |
Gedankenexperiment (17') – Average-Case-Analyse von InsertionSort (11') – Geburtstagsparadoxon & Bonustrack (7') |
|
| 07.11.2024 |
QuickSort und RandomizedQuickSort |
(Deterministisches) QuickSort (16') – Erwartete Laufzeit von Randomized QuickSort (19') |
|
| 12.11.2024 |
Sortieren in Linearzeit |
Untere Schranke (13') – CountingSort (10') – RadixSort (7') – BucketSort (14') |
|
| 14.11.2024 |
1. Zwischentest |
|
|
| 19.11.2024 |
Das Auswahlproblem |
Randomisiertes Select (23') – Deterministisches Select (15') |
|
| 21.11.2024 |
Abstrakter Datentyp: Dynamische Menge (8') – Stapel, Schlange, Liste (10') – Von Pseudocode zu Javacode (8') |
|
| 26.11.2024 |
Hashing |
direkte Adressierung und Hashing mit Verkettung (22') – gute Hashfunktionen und Hashing mit offener Adressierung (23') |
|
| 28.11.2024 |
Binäre Suchbäume |
Vorarbeiten und Traversierung (21') – Methoden (15') |
|
| 03.12.2024 |
Rot-Schwarz-Bäume |
Logarithmische Höhe (16') – Einfüge-Operation (16') |
|
| 05.12.2024 |
fällt aus! |
– |
|
| 10.12.2024 |
Datenstrukturen augmentieren |
Augmentieren – komplett (28') |
|
| 12.12.2024 |
2. Zwischentest |
Anmelden nicht vergessen! |
|
| 17.12.2024 |
Amortisierte Analyse |
Aggregationsmethode (9') – Buchhaltermethode (6') – Potentialmethode (9') |
|
| 19.12.2024 |
Nächstes Paar |
– |
|
| 07.01.2025 |
Graphen: Repräsentation und Breitensuche |
Beispiele und Repräsentation (16') – Breitensuche (23') |
|
| 09.01.2025 |
Kürzeste Wege und Dijkstras Algorithmus |
Dijkstras Algorithmus (22') – Kürzeste Wege und T9 (7') |
Dijkstras Originalartikel (3 Seiten, Num. Math., 1959)
Das Geheimnis des kürzesten Weges (Gritzmann & Brandenberg, 2005)
|
| 14.01.2025 |
Tiefensuche und topologische Sortierung |
Tiefensuche (Beispiel, Pseudocode, Eigenschaften) (22') – Topologische Sortierung (Anwendung, Korrektheit) (12') |
|
| 16.01.2025 |
3. Zwischentest |
Anmelden nicht vergessen! |
|
|
| 21.01.2025 |
Minimale Spannbäume |
Generischer Algorithmus und Korrektheit (13') – Algorithmen von Jarník–Prim und von Kruskal (18') |
|
| 23.01.2025 |
Dynamisches Programmieren |
Stabzerlegung (22') – Längste Wege (8') |
|
| 28.01.2025 |
Greedy-Algorithmen |
Ein einfaches Problem der Ablaufplanung (15') – Ein gewichtetes Problem der Ablaufplanung (14') |
|
| 30.01.2025 |
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) |
| 04.02.2025 |
Keine Vorlesung! (wegen GADS-Klausur) |
|
|
| 06.02.2025 |
Leichte Kreise per Dynamischer Programmierung [Folie 2 am 6.2., 15 Uhr aktualisiert.] |
Kein Video :-( |
Karps Originalartikel (3 Seiten, Discrete Math., 1978) |
| 12.02.2025 |
1. Klausur |
Bitte stimmen Sie bei der Umfrage hier im Kursraum mit "ja" ab, wenn Sie teilnehmen wollen.
|
|
| 14.04.2025 |
2. Klausur |
Anmelden auf WueStudy (ab 15.03. oder 01.04.2024) nicht vergessen! |
|
