Arbeitsgruppe Algorithmen und Komplexität

Effiziente Algorithmen 2017

Inhalt

Jenseits der grundsätzlichen Lösbarkeit von Problemen eröffnet sich ein neues Problemfeld: Es ist interessant, ein Optimierungsproblem möglichst schnell und gut lösen zu können. Effiziente Algorithmen sind solche Algorithmen, deren Laufzeit durch ein Polynom in der Problemgröße beschränkt ist. Besonders für Optimierungsprobleme aus der Praxis sind solche Algorithmen von großer Bedeutung, um relevante Lösungen in angemessener Zeit zu finden.

Die Vorlesung lässt sich in folgende Hauptbereiche zusammenfassen:

  1.  Einfache Komplexitätstheorie
  2.  algorithmische Lösungsverfahren
  3.  Anwendungen wie Maschinenbelegung (Scheduling), Transport- und Packungsprobleme, Tourenplanung, ...

 

Konkret behandelte Themen:

  • Zeitkomplexität von Algorithmen
  • Grundlegende algorithmische Methoden: Divide-and-conquer, dynamische Programmierung, Greedy-Algorithmen, approximative Algorithmen
  • Grundlegende Algorithmen für Bin Packing und 2D-Packungsprobleme
  • Approximationsschemata für das Rucksackproblem und Verallgemeinerungen
  • Asymptotische Approximationsschemata für Bin Packing
  • Approximative Algorithmen für Schedulingprobleme auf identischen und nicht-identischen Maschinen
  • Approximative Algorithmen für Scheduling mit parallelen Jobs
  • Approximative Algorithmen für 2D-Packungsprobleme
  • Approximative Algorithmen für das Problem des Handlungsreisenden (Traveling Salesman Problem, TSP) und Varianten
  • Approximative Algorithmen für Tourenplanung
  • Untere Schranken zur Laufzeit von exakten und approximativen Algorithmen

 

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 unteilt sich in zwei Teile. 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. Statt eines Forschungsergebnisses kann auch eine neue algorithmische Idee implementiert werden und eine Ausarbeitung dazu erstellt werden.
    2. Vortrag über Forschungsergebnis (bzw Vortrag über neue algorithmische Idee und Implementierung), Dauer ca 30 min
       
  • Die Note der Forschungsaufgabe wird, wenn sie besser  als die Note zu den Übungsaufgaben ist, als Gesamtnote genommen.

 

Readingseminar

Liste der besprochenen Paper

 

Material

Serie 1

Serie 2

Serie 3

Serie 4

Serie 5

Serie 6

Serie 7

Serie 8

Serie 9

Serie 10

 

Betreuer

Klaus Jansen und Lars Rohwedder

 

Weitere Informationen in der Moduldatenbank und im  Univis