Anrechnung
Diese Veranstaltung kann als Diskrete Mathematik II (DM II) gewählt werden.
Bei gleichzeitiger Belegung von Diskrete Mathematik II - Extremale Kombinatorik kann ... Lesen Sie weiter
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.
Schließen
Kommentar
Diese Vorlesung startet den Optimierungszweig der Diskreten Mathematik. Sie behandelt die Algorithmische Graphentheorie und die Lineare Optimierung.
Inhalt
Komplexität: ... Lesen Sie weiter
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.
Diese Veranstaltung richtet sich an Studierende der Mathematik mit Vorkenntnissen in Diskreter Mathematik, Linearer Algebra und Analysis. Einige Übungsaufgaben erfordern den Einsatz eines Computers.
Schließen
Literaturhinweise
M. Grötschel, Lineare Optimierung, eines der Vorlesungsskripte
V. Chvátal, Linear Programming, Freeman 1983
Lesen Sie weiter
