Modulcode:	MSS0202
Englische Bezeichnung:	Seminar (Approximation Algorithms)
Modulverantwortliche(r):	Prof. Dr. Klaus Jansen
Turnus:	jedes Semester (WS09/10 SS10 WS10/11 SS11 WS11/12 SS12 SS14)
Präsenzzeiten:	2S
ECTS:	4
Workload:	120 Std.
Dauer:	ein Semester
Modulkategorien:	Sem (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Das Seminar ist studienbegleitend für die Studenten, welche eine Master- oder Diplomarbeit bei Prof. Jansen schreiben.

Lernziele:

Die Studenten lernen wissenschaftliches Arbeiten und das Präsentieren ihrer Arbeit.

Lehrinhalte:

Gegenstand des Seminars sind approximative Algorithmen, also solche, die zugunsten einer besseren Laufzeit statt einer optimalen Lösung nur eine "`gute"' Lösung berechnen. Anhand klassischer Optimierungsprobleme werden wichtige Techniken des Designs und der Analyse von Approximiationsalgorithmen behandelt. Außerdem wird behandelt, wie sich die Grenzen der Approximierbarkeit untersuchen lassen. Im Rahmen dieses Seminars werden aktuelle Forschungsarbeiten aus dem Gebiet der approximativen Algorithmen vorgestellt.

Weitere Voraussetzungen:

Master- und Diplomstudenten, die planen eine Abschlußarbeit in dem Bereich der effizienten und/oder approximativen Algorithmen zu schreiben. Eine der Vorlesungen zum Thema Effiziente Algorithmen, Approximative Algorithmen oder Lineare Optimierung wird vorausgesetzt.

Prüfungsleistung:

schriftliche Seminarausarbeitung und gruppeninterner Vortrag

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

K. Jansen, M. Margraf: Approximative Algorithmen und Nichtapproximierbarkeit, de Gruyter 2008. V. V. Vazirani: Appoximation Algorithms, Springer 2001. Weitere Literatur wird in der Vorbesprechung bekanntgegeben.

Verweise:

Kommentar: