Diskrete Mathematik II - Optimierung
Ralf Borndörfer
Zusätzl. Angaben / Voraussetzungen
Anrechnung
Diese Veranstaltung kann als Diskrete Mathematik II (DM II) gewählt werden.
Bei gleichzeitiger Belegung von Diskrete Mathematik II - Extremale Kombinatorik kann einer der beiden Kurse als DM II und der andere als Ergänzungsmodul gewählt werden.
Sprache
Die VL findet auf Englisch statt.
Klausur
Die Klausur findet in der letzten Vorlesung statt. Die Nachklausur findet in der Woche vor dem Wiederbeginn der Vorlesungen statt.
SchließenKommentar
Diese Vorlesung startet den Optimierungszweig der Diskreten Mathematik. Sie behandelt die Algorithmische Graphentheorie und die Lineare Optimierung.
Inhalt
- Komplexität: Komplexitätsmaße, Laufzeit von Algorithmen, die Klassen P und NP, NP-Vollständigkeit
- Matroide und Unabhängigkeitssysteme: Unabhängigkeitssysteme, Matroide, Bäume, Wälder, Orakel, Optimierung über Unabhängigkeitssystemen
- Kürzeste Wege: Nichtnegative Gewichte, allgemeine Gewichte, all pairs
- Netzwerflüsse: Das Max-Flow-Min-Cut Theorem, Augmentierende Wege, Minimalkostenflüsse, Transport- und Zuordnungsprobleme
- Polyeder: Seitenflächen, Dimensionsformel, Projektionen von Polyedern, Transformation, Polarität, Darstellungssätze.
- Grundlagen der Linearen Optimierung: Farkas Lemma, Dualitätssatz.
- Simplexalgorithmus: Basis, Degeneration, Basistausch, revidierter Simplexalgorithmus, Schranken, dualer Simplexalgorithmus, Postoptimierung, Numerik.
- Innere Punkte und Ellipsoidmethode: Grundlagen
Zielgruppe
Diese Veranstaltung richtet sich an Studierende der Mathematik mit Vorkenntnissen in Diskreter Mathematik I, Linearer Algebra und Analysis. Einige Übungsaufgaben erfordern den Einsatz eines Computers.
SchließenLiteraturhinweise
M. Grötschel, Lineare Optimierung, eines der Vorlesungsskripte
V. Chvátal, Linear Programming, Freeman 1983
Additional
Garey & Johnson, Computers and Intractability, 1979 (Complexity Theory)
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, 97 (Linear Programming)
Korte & Vygen, Combinatorial Optimization, 2006 (Flows, Shortest Paths, Matchings)
Schließen31 Termine
Regelmäßige Termine der Lehrveranstaltung