Modulcode:	MS1402
Englische Bezeichnung:
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	unregelmäßig (WS08/09)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	240 Std.
Dauer:	ein Semester
Modulkategorien:	TG (Sonstige) MV (Sonstige)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Die Vorlesung ist eine Einführung in die kombinatorische Optimierung. Zunächst werden Grundbegriffe der Komplexitätstheorie und der Graphentheorie dargelegt. Dann werden zentrale Probleme der Kombinatorischen Optimierung wie minimal aufspannende Bäume oder kürzeste Wege in Graphen, maximale Matchings und Vertex-Cover sowie optimale Flüsse und Schnitte in Netzwerken behandelt. Ein zentraler Schwerpunkt der Vorlesung ist die lineare Programmierung und polyedrische Kombinatorik.

Lernziele:

Entwurf und Analyse von Algorithmen für kombinatorische Probleme, die in Polynomialzeit lösbar sind.

Lehrinhalte:

Komplexitätstheorie, Suboptimalität, Bäume und Wege, Matching und Knotenüberdeckung in Bipartiten Graphen, Matching in allgemeinen Graphen, Flüsse und Zusammenhang, Minimum-Kosten-Flüsse und Zirkulation, Planarität von Graphen, Färbbarkeit, Lineare Programmierung - Dualitätssatz und Algorithmen.

Weitere Voraussetzungen:

Grundmodule Analysis und Algebra oder Mathematik für Informatiker I, II, IV

Prüfungsleistung:

Lösung von 50 Prozent der Übungen und Präsentationen, evtl. mündliche Prüfung oder Klausur.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

Skript zur Vorlesung. Weitere Literatur wird in der Vorlesung bekannt gegeben.

Verweise:

Kommentar: