Praktikum: Algorithm Engineering

• Betreuung: Dr. rer. nat. Robert Görke, Martin Holzer, Dr. Marcus Krug, Dr. Sascha Meinert, Dr. Ignaz Rutter, Prof. Dr. Dorothea Wagner
• Präsenztermine: freitags 9:45–11:15 Uhr, Seminarraum -119 (Informatikgebäude 50.34);
  erster Termin (Vorbesprechung): Freitag, 24. Oktober 2008, 9:45 Uhr, SR -119
• Teilnahme: Die Teilnehmerzahl ist auf zwölf Personen begrenzt. Der Kurs kommt ab einer Mindestzahl von vier Teilnehmern zustande.
  Die Anmeldung ist abgeschlossen.

• 12. November 2008: Übersicht über die nächsten Termine
• 31. Oktober 2008: Folien zur Einführung in FPT-Algorithmen

• Freitag, 13. Februar 2009: Abschlussvorträge
  
• Sonntag, 22. Feburar 2009: Ausarbeitung: Gliederung (Überschriften)
  
• Sonntag, 1. März 2009: Ausarbeitung: erste Fassung (Stichpunkte/Halbsätze)
  
• Sonntag, 15. März 2009: Ausarbeitung: Hauptfassung (vollständiger Inhalt)
  
• Sonntag, 29. März 2009: Ausarbeitung: endgültige Fassung (druckreif)

Um NP-schwere Probleme rechnerisch in den Griff zu bekommen, können diverse Wege beschritten werden: neben dem Einsatz von Heuristiken, der Einschränkung auf relevante Teilklassen und der Entwicklung von Approximations- oder randomisierten Algorithmen ist ein weiterer Angriffspunkt durch die Theorie der Fixed-Parameter Tractability (FPT) gegeben. Hierbei wird versucht, die Laufzeitexplosion eines Lösungsalgorithmus auf einen Parameter zu beschränken, der in der Praxis 'recht klein' ausfällt.

In diesem Programmierpraktikum sollen nun verschiedene FPT-Algorithmen hinsichtlich möglicher Parameter studiert und in Java oder C++ implementiert werden. Die Implementationen sollen dabei auf verschiedenen Instanzen mit Blick auf weitere Optimierungsmöglichkeiten experimentell ausgetestet werden.

In einem ersten Präsenztermin wird zunächst eine theoretische Fundierung des Stoffes vermittelt werden; daneben wird Gelegenheit zur praktischen Einarbeitung in die Thematik und die verwendeten Bibliotheken an Hand einiger Aufwärmaufgaben gegeben sein. Im Anschluss daran werden in Teams von zwei bis drei Personen und individueller Betreuung durch Lehrstuhlmitarbeiter eine oder mehrere größere Aufgaben bearbeitet werden. Jeweils etwa zu Semesterhalbzeit und -ende wird jede Gruppe in einer Präsentation ihre bisherige Arbeit vorstellen. Abschließend ist eine schriftliche Ausarbeitung der Ergebnisse in LaTeX zu erstellen.

• Einführung in FPT-Algorithmen, Folien vom 31.10.2008