Modulcode:	Inf-KOptPO
Englische Bezeichnung:	Combinatorial Optimization - Polynomiality and Optimality
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	unregelmäßig (SS11)
Präsenzzeiten:	4V 2Ü
ECTS:	9
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 180 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	MSc Math (Export) WI (MSc WInf) TG (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Die Vorlesung ist eine Einführung in die kombinatorische Optimierung.

Lernziele:

Entwurf und Analyse von Algorithmen für kombinatorische Optimierungsprobleme, die in Polynomialzeit lösbar sind, Erlernen der Modellierung von Optimierungsaufgaben. Einüben der Polyedertheorie.

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, Einführung in die lineare Programmierung.

Weitere Voraussetzungen:

In Informatik und Wirtschaftsinformatik: Module Inf-Math-A,-B.

In Mathematik: Module Analysis I, II und Lineare Algebra I, II.

Prüfungsleistung:

Abschließende mündliche Prüfung oder schriftliche Klausur.

Lehr- und Lernmethoden:

Lösen von Übungsaufgaben, Präsentation von Lösungen, Korrektur in Anwesenheit.

Verwendbarkeit:

Als Vorbereitung einer Bachelorabschlussarbeit oder als einführende Grundlage für Masterstudiengänge.

Literatur:

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

Verweise:

Kommentar:

Dieses Modul wurde bis zum Sommersemester 2010 als Bachelorwahlfplichtmodul angeboten und mit 8 ECTS bewertet.

Dieses Modul kann auch im Wahlpflichtbereich des Bachelorstudiengangs Informatik gehört werden.