Arbeitsgruppe Algorithmen und Komplexität

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.

 

Material

Hier finden Sie die Übungsblätter.

Serie 1

Serie 2

Serie 3

Serie 4

Serie 5

Serie 6

Serie 7

Serie 8

Serie 9

Serie 10

Serie 11

Serie 12

Betreuer

Klaus Jansen und Malin Rau

 

Weitere Informationen im Univis