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ßen

Kommentar

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

Regelmäßige Termine der Lehrveranstaltung

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

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

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 18.10.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 25.10.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 01.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 08.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 15.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 22.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 29.11.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 06.12.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 13.12.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 20.12.2019 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 10.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 17.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 24.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 31.01.2020 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 07.02.2020 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Fr, 14.02.2020 14:00 - 16:00
Optimierung I (Serientermin 1)

Dozenten:
Univ.-Prof. Dr. Ralf Borndörfer

Räume:
A6/SR 032 Seminarraum (Arnimallee 6)

Studienfächer A-Z