Modulcode:	WI23
Englische Bezeichnung:	Combinatorial Optimization - Polynomiality and Optimality
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	unregelmäßig (WS09/10)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	60 Std. Vorlesung, 30 Std. Präsenzübung, 150 Std. Selbststudium
Dauer:	ein Semester
Modulkategorien:	WI (Sonstige)
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.

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

Weitere Voraussetzungen:

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

In Mathematik: Module Analysis und Lineare Algebra.

Prüfungsleistung:

Lösung von 50 Prozent der Übungen und Präsentationen, regelmäßige, nachgewiesene Teilnahme an den Übungen, Korrektur in Anwesenheit, mündliche Prüfung. Die in den Übungen erzielten Punkte können als Bonus bei der Modulnote eingehen. Einzelheiten werden in der Vorlesung gekannt gegeben.

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: