Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Aktuelles

Mi, 07.07.04:
Der Inhalt von Kapitel 6: Baumautomaten ist nicht prüfungsrelevant.

Einführung

Thema dieser Vorlesung ist der Zusammenhang zwischen logischer Beschreibbarkeit und Komplexität.
Einen Schwerpunkt bilden dabei Fragestellungen aus der Datenbanktheorie und der Verifikation. Beispielsweise wird die Ausdrucksstärke verschiedener Datenbank-Anfragesprachen sowie die Schwierigkeit der Auswertung von Anfragen analysiert.
Ein weiterer Schwerpunkt ist die deskriptive Komplexitätstheorie, in der der Zusammenhang zwischen Beschreibungs- und klassischer Berechnungskomplexität von Problemen untersucht wird. So können wichtige Komplexitätsklassen wie P und NP durch Erweiterungen der Logik erster Stufe beschrieben werden.
Zur Bestimmung der Ausdrucksstärke der relevanten Logiken werden unter anderem Zwei-Personen Spiele behandelt.
Behandelte Themen: Datenbanken und Logik, deskriptive Komplexität, endliche Modelltheorie, Fixpunktlogiken, XML-Datenbanken und Baumautomaten, Ehrenfeucht-Fraïssé-Spiele, Model-Checking und Verifikation.

Logbuch

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

Informationen zum Vorlesungsbetrieb

Zeiten und Raum

Mittwochs 9-11 und Freitags 9-11 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308

 

Dozent/in

Dr. Stephan Kreutzer und Dr. Nicole Schweikardt

Übungen

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

Zeit und Raum

Mittwochs 11-13 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308

 

Übungsleiter/in

Dr. Stephan Kreutzer

Dr. Nicole Schweikardt

Übungsaufgaben

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

• Blatt 1 (16.4.2004, Abgabe, Freitag, der 23.4.2004, zu Beginn der Vorlesung)
• Blatt 2 (23.4.2004, Abgabe, Freitag, der 30.4.2004, zu Beginn der Vorlesung)
• Blatt 3 (30.4.2004, Abgabe, Freitag, der 7.5.2004, zu Beginn der Vorlesung)
• Blatt 4 (7.5.2004, Abgabe, Freitag, der 14.5.2004, zu Beginn der Vorlesung)
• Blatt 5 (17.5.2004, Abgabe, Montag, der 24.5.2004, am Lehrstuhl)
• Blatt 6 (21.5.2004, Abgabe, Montag, der 31.5.2004, am Lehrstuhl)
• Blatt 7 (28.5.2004, Abgabe, Freitag, der 4.6.2004, zu Beginn der Vorlesung)
• Blatt 8 (04.6.2004, Abgabe, Montag, der 14.6.2004)
• Blatt 9 (11.6.2004, Abgabe, Montag, der 21.6.2004)
• Blatt 10 (18.6.2004, Abgabe, Montag, der 28.6.2004)

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 Übungaufgaben erworben werden.

Literatur