Prof. Dr. Henning Fernau 

Vorlesungsankündigung

Folien:

VL1 (17.10. sowie 21.10, 10-12 h, H 406)

Ergänzung (21.10., 14-16 h, H 7)

VL2 (24.10., verschoben auf 31.10. bzw. 4.11.)

Ergänzung (28.10., 10:05-11.35, HZ 201)

VL3 (neuer Termin: MI, 9.11., 16 Uhr s.t. im H 406)

VL4 (FR, 11.11., 10:05-11.35, HZ 201)

VL5 in der Woche 21.11 bzw. 25.11.

VL6 (28.11.)

Übungsaufgaben für Freitag:

1) Zeigen Sie: 2SAT liegt in co-NL (und somit in NL)

2) Zeigen Sie: Horn-SAT ist P-vollständig

3) Zeigen Sie durch Angabe entsprechender logspace-Reduktionen Vollständigkeiten für die am Ende von VL6 angesprochenen Schaltkreisprobleme.

VL7 (5.12.)

VL8 (12.12.)

VL9 (19.12.)

VL10 (9.1.2012)

Übungsaufgabe für Freitag:

Zeigen Sie, dass das folgende Entscheidungsproblem NP-vollständig ist: Gegeben sei eine Formel F in KNF über den Variablen x1,...,xn und eine Zahl k. Gibt es eine Belegung der Variablen, so dass höchstens k Klauseln erfüllt werden?

VL11 (16.1. und 23.1.)

Übungsaufgabe für Freitag

VL12 (Beginn 23.1.)

VL13 (30.1./6.2.)

Zu den Übungen am FR., 3.2.:

1) Modellieren Sie folgende Probleme als Model-Checking Probleme (unter Angabe geeigneter Strukturen und Formeln):

a) Gegeben ein ungerichteter Graph G und eine Zahl k, gibt es eine dominierende Menge von G (also eine Menge von Knoten, sodass jeder Knoten von G in dieser Menge liegt oder einen Nachbarn in dieser Menge hat) mit höchstens k Knoten?

b) Gegeben ein ungerichteter Graph G und eine Zahl k, gibt es eine Menge F von höchstens k Kanten, sodass jede Kante mit mindestens einer Kante aus F inzidiert?

c) Gegeben ein gerichteter Graph G, gibt es einen gerichteten Hamiltonschen Kreis in G?

d) Gegeben ein ungerichteter Graph G und ein Knoten v, gibt es eine kleinstmögliche Knotenüberdeckung, die v enthält?

2) Finden Sie geeignete Model-Checking Formulierungen für die Ihnen bekannten Probleme AGAP, Geographie und Planning.

3) Finden Sie eine Problemkernreduktion für folgendes Problem:

Gegeben seien ein ungerichteter Graph G=(V,E) und eine natürliche Zahl k (k ist der Parameter), gibt es eine Menge N von mindestens k Knoten, sodass V-N eine dominierende Menge ist?

4) Finden Sie einen Suchbaumalgorithmus für folgendes Problem, der zeigt, dass dieses Problem in FPT liegt:

Gegeben ein gerichteter Graph G und eine natürliche Zahl k (k ist der Parameter), gibt es eine Menge X von höchstens k Knoten, sodass der von V-X induzierte Graph keinen gerichteten Pfad der Länge zwei enthält?

Übungsaufgaben für Freitag, 10.2.:

1) Finden Sie Polynomzeit(!)reduktionen, die sowohl zeigen, dass MINSAT in NP liegt bzw NP-hart ist, als auch, dass dieses Problem in FPT liegt.

Bei MINSAT ist eine KNF-Formel gegeben und eine Zahl k und gefragt, ob es eine Belegung gibt, die höchstens k Klauseln wahr macht.

2) Zeigen Sie, dass Set Packing W[1]-vollständig ist (siehe [neuer] Foliensatz).

3) Zeigen Sie, dass Hitting Set W[2]-vollständig ist (siehe [neuer] Foliensatz).