Parametrisierte Algorithmen
Prof. Dr. Henning Fernau / Daniel Meister
Erneute Terminänderung - Stand 27.10.2011
Die Veranstaltungen finden wie folgt statt:
Vorlesung DI 14:15 - 15:45 h H 406
Übungen DO 14:00 - 15:30 h H 405
Folien:
Vorlesung 1 (18.10.)
Vorlesung 2 (25.10.)
Vorlesung 3 (03.11.+8.11.)
In der Woche vom 12.-20.11. sind Henning Fernau und Daniel Meister dienstlich verreist.
Bitte beschäftigen Sie sich in den Vorlesungs- und Übungsstunden mit dem folgenden Übungsblatt.
Vorlesung 4 (22.11.)
Vorlesung 5 (29.11.)
6.12.: Wiederholung
Vorlesung 6 (13.12.)
Vorlesung 7 (20.12.)
Vorlesung 8 (10.1.2012)
Vorlesung 9 (17.1.)
Vorlesung 10 (24.1.)
Vorlesung 11 (31.1.)
Empfehlung: Besuchen Sie ab Freitag auch die Veranstaltungen der Komplexitätstheorie; in den Übungen am Freitag in dieser Woche werden wir (aus Ihrem Blickwinkel) Stoff aus den Parameterisierten Algorithmen wiederholen, in der letzten Semesterwoche allerdings parameterisierte Komplexitätstheorie betreiben. Dazu kommen wir in dieser Veranstaltung aufgrund des zähen Beginns nicht, aber normalerweise ist das Teil dieser Veranstaltung...
Vorschlag für eine Übungsaufgabe für den 2.2.2012:
Entwerfen Sie einen parameterisierten Algorithmus mit Hilfe der Methode des iterativen Verbesserns, welcher das folgende Problem in Zeit O*(2^k) löst: Gegeben ein ungerichteter Graph G=(V,E) und eine natürliche Zahl k (der Parameter). Gibt es eine höchstens k-elementige Knotenteilmenge C von V, sodass G-C Maximalgrad Eins besitzt?
Vorlesung 12 (7.2.)
Prüfungstermine
Die mündlichen Prüfungen finden ab der Woche vom 13.02.2012 im Büro von Prof. Fernau statt. Für Mai 2012 sind Nachprüfungen vorgesehen. Im LSF-Portal angegebene Termine sind pro forma; eine konkrete Terminierung erfolgt auf jeden Fall nach Vereinbarung.