Approximative Algorithmen

Inhalt

In diesem Modul werden neue Techniken des Entwurfes und der Analyse von approximativen Algorithmen für verschiedene Probleme der kombinatorischen Optimierung vorgestellt. Weiter werden Grundlagen der Komplexitätstheorie vermittelt, um auch theoretisch fundierte Grenzen der algorithmischen Möglichkeiten aufzuzeigen.

Dieses Modul besteht aus drei Teilen. Dem Reading-Seminar, der Vorlesung und einer Übung. In dem Reading-Seminar soll zusammen mit einem Wissenschaftlichen Mittarbeiter eine aktuelle Forschungsarbeit Vorgesellt werden.

Prüfungsleistung (bewertet werden die Übungsaufgaben und die Forschungsaufgabe je zu 50%)

Erfolgreiche Bearbeitung der Übungsaufgaben, d.h. es werden mindestens 40% der Gesamtpunktzahl erreicht.
Die Note dieses Teils ergibt sich aus den erreichten Punkten im Verhältnis zu 80% der Gesamtpunktzahl.
Erfolgreiche Bearbeitung einer Forschungsaufgabe: Diese Aufgabe besteht aus zwei Teilen. Jeder der zwei Teile fließt zur Hälfte in die Bewertung
der Forschungsaufgabe ein
1. Schriftliche Ausarbeitung (ca 8-15 Seiten) eines Forschungsergebnisses, zB Verbesserung eines Alorithmus bezüglich Laufzeit oder Approximationsgüte
2. Vortrag über Forschungsergebnis, Dauer ca 30 min
Die Note der Forschungsaufgabe wird, wenn sie besser als die Note zu den Übungsaufgaben ist, als Gesamtnote genommen.