19234401

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 ... Lesen Sie weiter

Kommentar

Dieser Kurse bietet eine algorithmische Vertiefung der Diskreten Mathematikl. Er vermittelt Kenntnisse in Algorithmischer Graphentheorie und Linearer ... Lesen Sie weiter

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

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:00

Klausur

Regelmäßige Termine der Lehrveranstaltung

Mo, 14:00 - 16:00 Optimierung I (Serientermin 2) 16 Termine

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, 14:00 - 16:00 Optimierung I (Serientermin 1) 16 Termine

Fr, 18.10.2019 14:00 - 16:00