Arbeitsgruppe Algorithmen und Komplexität

Abschlussprojekt Wirtschaftsinformatik (Operations Research)

(Bitte den Inhalt anpassen)

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 drei Teile. Jeder der drei Teile fließt zu einem Drittel in die Bewertung
    der Forschungsaufgabe ein:
    1. Vortrag (ähnlich einer Vorlesung) über die Problemstellung, Techniken und Ergebnisse einer zugrundeliegenden wissenschaftlichen Publikation,
      Dauer ca 90 min
    2. 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.
    3. 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.

 

Material

Hier finden Sie sie Übungsblätter.

 

Betreuer

Klaus Jansen, Felix Land, Kati Land, Malin Rau und Kim-Manuel Klein

 

Weitere Informationen im Univis