Modulcode:	MS1403
Englische Bezeichnung:	Combinatorial Optimization - Approximation and Randomization
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	jedes Jahr (SS09 WS10/11 SS13 SS14 SS15 SS16)
Präsenzzeiten:	4V 2Ü
ECTS:	9
Workload:	270 Std.
Dauer:	ein Semester
Modulkategorien:	WI (MSc Inf (15)) MSc Math (Export) WI (MEd Inf) WPI (MEd Inf) TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Der Schwerpunkt der Vorlesung liegt auf der Approximation von Lösungen NP-harter kombinatorischer Optimierungsprobleme mit Hilfe randomisierter Algorithmen. Behandelt werden u.a. das Travelling-Salesperson-Problem, Steinerbäume in Graphen, Mehrgüterflüsse, Packungs- und Überdeckungsprobleme in Hypergraphen, die Konzentration von Wahrscheinlichkeitsverteilungen um den Erwartungswert sowie Derandomisierung.

Lernziele:

Entwurf und Analyse von Algorithmen für NP-schwere Probleme. Erlernen von Techniken wie Randomisierung, Approximation und Beweis komplexitätstheoretischer Schranken.

Lehrinhalte:

Traveling-Salesperson-Problem, Steinerbäume, Mehrgüterflüsse, Large-Deviation-Ungleichungen, Randomisierte Algorithmen (Randomisiertes Runden), Packen und Überdecken in Hypergraphen, Die Random-Hyperplane Methode, Semidefinite Optimierung, Max-Cut-Problem, Flüsse unter spieltheoretischen Aspekten.

Weitere Voraussetzungen:

Graphentheorie (Inf-GraphTheo) oder Kombinatorische Optimierung - Polynomialität und Optimalität (Inf-KoptPO)

Prüfungsleistung:

Im ersten Prüfungszeitraum wird eine Klausur geschrieben. Im zweiten Prüfungszeitraum finden je nach Angemeldetenzahl mündliche Prüfungen oder eine Klausur statt.

Regelmäßige, angemessene und sinnvolle Bearbeitung von Übungsaufgaben wird bei der Bewertung der Modulprüfung berücksichtigt.

Falls eine Klausur geschrieben wird, so gibt es ein Bonuspunktesystem. Wenn mindestens 50% aller Übungspunkte bei der Durchführung des Moduls erreicht wurden und die Klausur alleine durch die Klausurpunkte bestanden ist, so werden zur Bildung der Note die Übungspunkte auf 20% der erreichbaren Klausurpunkte skaliert und zu den erreichten Klausurpunkten hinzugerechnet. Dies bedeutet, dass z.B. bei 100% erreichten Übungspunkten und bestandener Klausur 20% der erreichbaren Klausurpunkte als Bonus bei der Klausur hinzugefügt werden, und z.B. bei 50% erreichten Übungspunkten und bestandener Klausur 10% der erreichbaren Klausurpunkte hinzugefügt werden. Wenn man die Klausur nicht alleine mit den dort erreichten Punkten besteht, so haben die Bonuspunkte keine Wirkung.

Im Falle einer mündlichen Prüfung gehen positive Studienleistungen in informeller Weise ein.

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

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

Verweise:

Kommentar:

Dieses Modul wurde bis zum Wintersemester 2010/11 mit 8 ECTS bewertet.