Logik in der Informatik Prof. Dr. Martin Grohe

Aktuelles

An dieser Stelle finden Sie im Laufe der Vorlesung aktuelle Mitteilungen.

• 14. 4. 2009: Der Übungsbetrieb beginnt am 28. 4.

Einführung

Das constraint satisfaction Problem CSP ist von großer praktischer Bedeutung, da es viele kombinatorische Probleme auf natürliche Weise verallgemeinert. In seiner Allgemeinheit ist es NP-vollständig; deshalb sucht man nach leichteren Spezialfällen. Aus dieser Suche hat sich eine reichhaltige Theorie mit Querbezügen zu vielen anderen Themen der theoretischen Informatik entwickelt.

Inhalt

Die einzelnen Kapitel des Skripts werden im Laufe der Vorlesung hier erscheinen.

1. Einführung
2. Der Satz von Schaefer
3. Konsistenz
4. Etwas universelle Algebra
5. Wenige pp-definierbare Relationen
6. Linksseitige Einschränkungen

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich ergänzende Bemerkungen.

Informationen zum Vorlesungsbetrieb

Zeiten und Raum

Dienstags und Donnerstags 13-15 Uhr im Erwin-Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307 (Dienstags) beziehungsweise 1'308 (Donnerstags)

 

Dozent

Dr. Mark Weyer

Übungen

Ergänzend zu den Vorlesungen finden 2-stündige Übungen statt.

Zeit und Raum

Dienstags 15-17 Uhr im Erwin-Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307

 

Übungsleiter

Dipl.-Inf. Magdalena Grüber

Übungsaufgaben

Es gibt regelmäßig Übungsaufgaben, deren erfolgreiche Bearbeitung (mindestens 40% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.

• Blatt 1 (16. 4. 2009, Abgabe 23. 4. 2009)
• Blatt 2 (23. 4. 2009, Abgabe 30. 4. 2009)
• Blatt 3 (30. 4. 2009, Abgabe 7. 5. 2009)
• Blatt 4 (7. 5. 2009, Abgabe 14. 5. 2009)
• Blatt 5 (19. 5. 2009, Abgabe 26. 5. 2009)
• Blatt 6 (28. 5. 2009, Abgabe 4. 6. 2009)
• Blatt 7 (4. 6. 2009, Abgabe 11. 6. 2009)
• Blatt 8 (11. 6. 2009, Abgabe 18. 6. 2009)
• Blatt 9 (18. 6. 2009, Abgabe 25. 6. 2009)

Prüfung

Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 40% der Punkte in den Übungsaufgaben erworben werden.

Literatur

Die Vorlesung orientiert sich an keiner konkreten Vorlage.

[CKS01]	Nadia Creignou, Sanjeev Khanna und Madhu Sudan: Complexity Classifications of Boolean Constraint Satsifaction Problems. SIAM, 2001.
[FV98]	Tomás Feder und Moshe Y. Vardi: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. SIAM Journal on Computing 28 (1), 1998. Seiten 57-104.