Dieser Kurse bietet eine algorithmische Vertiefung der Diskreten Mathematikl. Er vermittelt Kenntnisse in Algorithmischer Graphentheorie und Linearer Optimierung.
Übersicht
Woche 1 (Unabhängigkeitssysteme): Unabhängigkeitssysteme, Rang, Matroide, Greedy Min/Max/Dual, Satz von Edmonds-Rado, Rangquotient
Woche 2 (Branchings): Arboreszenzen, Branchings, Alg. von Edmonds
Woche 3 (Komplexität): Kodierunglänge, Laufzeit von Algorithmen, Klassen P, NP, co-NP, NP-Vollständigkeit, SAT, Reduktionen
Woche 4 (Kürzeste Wege): Alg. von Dijkstra, [A* Alg.], Bellman-Rekursion, Alg. von Floyd-Warshall
Woche 5 (Minimum Mean Cycles): Alg. von Karp
Woche 6 (Maximale Flüsse): Satz von Menger, Augmentierende Wege, Alg. von Edmonds-Karp, Max Flow Min Cut Satz, [Blocking Flows, Alg. von Dinic]
Woche 7 (Minimalkostenflüsse): Verallg. Max Flow Min Cut Satz, Äquiv. zum Transportproblem, Residualer Graph, Min. Mean Cycle Cancelling Alg., Sucessive Shortest Path Alg.
Woche 8 (Matchings): Alternierende und Augmentierende Wege, Alg. von Hopcroft-Karp (für den Kardinalitätsfall)
Woche 9 (Polyeder): Polyeder, Gültige Ungleichungen, Seitenflächen und Facetten, Ecken und Extremalstrahlen, H- und V-Darstellung, Satz von Caratheodory
Woche 10 (Zulässigkeit): Fourier-Motzkin-Elimination, Alternativsätze, Farkas Lemma, Redundanz, Degeneration, Transformationen von Polyedern
Woche 11 (Basen): Gleichungsmenge, Dimension, Basis, Ecken und Basen
Woche 12 (Lineare Programme): Primales/Duales LP, Schwache Dualität, Standardform, Optimalitätsbedingung, Starke Dualität, Komplementärer Schlupf
Woche 13 (Simplex I): Tableau, Revidierter Simplex Alg. Degeneration, Endlichkeit, Worst-Case-Verhalten
Woche 14 (Simplex II): Dualer Simplex, Sensitivitätsanalyse
Woche 15 (Innere-Punkte-Alg. und Ellipsoidmehtode, nur Überblick): Primal-Duale-Formulierung, Barriereproblem, KKT-System, Zentraler Pfad, Pfadverfolgungsmethoden, Laufzeit, Ellipsoide, Volumen, Löwner-John-Ellipsoid, Ellpsoidmethode, Laufzeit
Woche 16 (Wiederholung, Klausur)