Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Parametrisierte Algorithmen

MSc Lecture - Winter 2016/17

Beschreibung

Sehr viele in der Praxis auftretende Probleme sind NP-schwer und damit im Allgemeinen (vermutlich) nicht in polynomieller Zeit lösbar. Dennoch können diese Probleme häufig effizient gelöst werden, da die Eingaben "gutartig" sind.  Eine Möglichkeit diese Gutartigkeit der Instanzen formal zu fassen bietet die Betrachtung der parametrisierten Komplexität.  Dabei assoziiert man mit jeder Instanz einen Parameter k, der ein Maß für die Komplexität der Eingabe darstellt.  Ziel ist es dann, einen Algorithmus zu finden, dessen Laufzeit nur polynomiell von der Eingabegröße n aber ggf. exponentiell von dem Parameter k abhängt. Erhält man beispielsweise einen Algorithmus mit Laufzeit O(2k*n), so widerspricht das nicht der Annahme, dass es keinen Algorithmus mit polynomieller Laufzeit gibt, da theoretisch k=n gelten kann. Betrachtet man allerdings gutartige Instanzen, bei denen k als konstant angenommen werden kann, so hat der oben genannte Algorithmus lineare Laufzeit.  Im Vergleich zur groben Klassifizierung eines Problems als polynomiell lösbar bzw. NP-schwer bietet die parametrisierte Betrachtungsweise also eine deutlich differenziertere Sicht auf schwere Probleme.

Voraussetzungen

Die Vorlesung richtet sich an Master-Studierende, die Interesse am Entwurf und der Analyse von Algorithmen haben.  Es gibt keine formalen Voraussetzungen, um diese Vorlesung zu belegen.  Es ist jedoch vorteilhaft die Vorlesung "Algorithmix" oder "Graphenalgorithmen" bereits gehört zu haben.

Leistungserfassung

Es werden regelmäßig Hausaufgaben gestellt, von deren erfolgreicher Bearbeitung die Zulassung zur Prüfung abhängt.  Die Prüfung wird in mündlicher Form stattfinden.

Termine

Wir treffen uns wöchentlich Mittwochs um 13:30 in H-2.58. Außerdem findet alle zwei Dienstags um 13:30 in H-2.57 eine Übung statt. Die erste Vorlesung wird am Mittwoch den 19.10. stattfinden. Weitere Informationen im Moodle.