Arbeitsgruppe Algorithmen und Komplexität

Approximative Algorithmen Sommer 2019

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

serie01 serie01-eng

serie02 serie02-eng

serie03

serie04

serie05

serie06

serie07

serie08

serie09