Parametrisierte Algorithmen

Prof. Dr. Henning Fernau / Daniel Meister

Vorlesungsankündigung

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.