Institut für Theoretische Informatik, Algorithmik

Praktikum: Algorithm Engineering

Allgemeines

Aktuelles

Nächste Termine

  • 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)

Inhalt

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.

Ablauf

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.

Materialien