# DS

## 1-3 Zahlentheorie

- Euklidischer Algorithmus
- Chinesischer Restsatz
- Schwacher Primzahlsatz
- RSA-Verfahren
- Kettenbrüche
- Approximationen durch rationale Zahlen

## 4-5 Einführung Graphentheorie
Video (Vorlesung): Graphentheorie – 1.1 Erste Begriffe (15:51)Link/URL
Video (Vorlesung): Graphentheorie – 1.2 Spaziergänge, Wege und Kreise (10:23)Link/URL
Video (Vorlesung): Graphentheorie – 1.3 Bäume und Wälder (20:05)Link/URL
Video (Vorlesung): Graphentheorie – 1.3 Charakterisierung von Bäumen (13:35)Link/URL
Video (Vorlesung): Graphentheorie – 1.4 Eulersche Graphen (15:35)Link/URL
Video (Vorlesung): Graphentheorie – 1.5 Bipartitionen (11:13)Link/URL

## 6-7 Matroide
2. Woche: Matroide (15. - 19. Juni)
Stichworte: Unabhängigkeitssysteme, Matroide, Basen, Greedy-Algorithmus, kürzeste Spannbäume

Video (Vorlesung): Matroide – 2.1 Unabhängigkeitssysteme und der Greedy-Algorithmus (24:32)Link/URL
Video (Vorlesung): Matroide – 2.2 Matroide (13:19)Link/URL
Video (Vorlesung): Matroide – 2.2 Der Greedy-Algorithmus für Matroide (16:08)Link/URL
Video (Vorlesung): Matroide – 2.3 Minimale Spannbäume (10:47)Link/URL
Video (Vorlesung): Matroide – 2.4 Clustering

## 8-9 Kürzeste Wege

4. Woche: Dynamische Programmierung (29. Juni - 3. Juli)
Stichworte: Kürzeste Wege, Bellman-Ford, Dijkstra, Rucksackproblem

Video (Vorlesung): Dynamische Programmierung – 4.1 Idee (11:40)Link/URL
Video (Vorlesung): Dynamische Programmierung – 4.2 Kürzeste Wege: Bellman-Ford (40:13)Link/URL
Video (Vorlesung): Dynamische Programmierung – 4.3 Rucksack-Problem (15:11)Link/URL
In Lemma 4.13 hatte sich ein Fehler eingeschlichen, der auch im Video unbemerkt blieb. Die korrekte Rekursionsformel findet sich im aktualisierten Skript.

Video (Vorlesung): Dynamische Programmierung – 4.4 Kürzeste Wege: Dijkstra (24:38)Link/URL

## 10-11 Netzwerke
5. Woche: Netzwerke (6. Juli - 10. Juli)
Eingeschränkt Verfügbar ab 8. Juli 2020, 08:00 (ansonsten verborgen)
Stichworte: Maximale Flüsse, minimale Schnitte, Augmentationen, Ford-Fulkerson, Max-Flow-Min-Cut, Edmonds-Karp

Video (Vorlesung): Netzwerke – 5.1 Maximale Flüsse (14:23)Link/URL
Video (Vorlesung): Netzwerke – 5.2 Minimale Schnitte (12:46)Link/URL
Video (Vorlesung): Netzwerke – 5.3 Augmentationsnetzwerke (34:31)Link/URL
Video (Vorlesung): Netzwerke – 5.4 Ford-Fulkerson (15:15)Link/URL
Video (Vorlesung): Netzwerke – 5.5 Max-Flow-Min-Cut (10:14)Link/URL
Video (Vorlesung): Netzwerke – 5.6 Edmonds-Karp (10:55)Link/URL

## 12-13 Anwendungen MFMC
6. Woche: Anwendungen von Max-Flow-Min-Cut (13. Juli - 17. Juli)
Eingeschränkt Verfügbar ab 15. Juli 2020, 08:00 (ansonsten verborgen)
Stichworte: Bipartites Matching, Satz von Hall, Satz von König, Satz von Dilworth, Satz von Erdős-Szekeres

Video (Vorlesung): MFMC - 6.1 Bipartites Matching (15:07)Link/URL
Video (Vorlesung): MFMC - 6.2 Satz von König (20:02)Link/URL
Video (Vorlesung): MFMC - 6.3 Satz von Hall (12:11)Link/URL
Video (Vorlesung): MFMC - 6.4 Satz von Dilworth (22:07)Link/URL
Video (Vorlesung): MFMC - 6.5 Satz von Erdős-Szekeres (7:44)Link/URL

## 14 Ausblick

- Probleme der diskreten Mathematik (algorithmische aber auch strukturelle, etwa in Graphentheorie)