19234401
Vorlesung
WiSe 19/20: Optimierung I
Ralf Borndörfer
Zusätzl. Angaben / Voraussetzungen
Diese Vorlesung überschneidet sich inhaltlich zum Teil mit der Vorlesung Algorithmische Kombinatorik. Falls beide dieser Kurse gewählt werden, können sie deshalb zusammen nur mit insgesamt 15LP im Masterestudiengang angerechnet werden (einer als 10LP Diskrete Mathematik, der andere als 5LP Ergänzungsmodul). Jeder Kurs einzeln zählt 10LP.
Vorkenntnisse: Diskreter Mathematik I, Linearer Algebra I-II, Analysis I-II.
Einige Übungsaufgaben erfordern grundlegenden Programmierkenntnisse.
Die Klausur findet in der letzten Vorlesung statt.
Die Nachklausur findet in der Woche vor dem Wiederbeginn der Vorlesungen zur Zeit der zweiten Vorlesung statt.
SchließenKommentar
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) Schließen
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) Schließen
Literaturhinweise
B. Korte, J. Vygen, Combinatorial Optimization, Springer 2018
V. Chvátal, Linear Programming, Freeman 1983
32 Termine
Zusätzliche Termine
Mo, 19.10.2020 10:00 - 12:00Klausur
Regelmäßige Termine der Lehrveranstaltung
Mo, 14.10.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 21.10.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 28.10.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 04.11.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 11.11.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 18.11.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 25.11.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 02.12.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 09.12.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 16.12.2019 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 06.01.2020 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 13.01.2020 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 20.01.2020 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 27.01.2020 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 03.02.2020 14:00 - 16:00
Optimierung I (Serientermin 2)
Mo, 10.02.2020 14:00 - 16:00
Optimierung I (Serientermin 2)
Fr, 18.10.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 25.10.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 01.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 08.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 15.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 22.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 29.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 06.12.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 13.12.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 20.12.2019 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 10.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 17.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 24.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 31.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 07.02.2020 14:00 - 16:00
Optimierung I (Serientermin 1)
Fr, 14.02.2020 14:00 - 16:00
Optimierung I (Serientermin 1)