Logik und Datenbanktheorie Prof. Dr. Nicole Schweikardt Logik und diskrete Systeme Prof. Dr. Stephan Kreutzer

Logik in der Informatik, Institut für Informatik, Humboldt-Universität zu Berlin

Aktuelles

An dieser Stelle finden Sie im Laufe der Vorlesung aktuelle Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.

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 Johann von Neumann Haus (Rudower Chaussee 25), Raum 4.112

 

Dozent/in

Prof. Dr. Stephan Kreutzer und Prof. Dr. Nicole Schweikardt

Skript

• Inhaltsverzeichnis
• Kapitel 0 (Einleitung)
• Kapitel 1 (Grundlagen)
• Kapitel 2 (Deskriptive Komplexität)
• Kapitel 3 (Ehrenfeucht-Fraïssé Spiele)
• Kapitel 4 (Fixpunktlogiken)
• Kapitel 5 (Auswertungsspiele)

Übungen

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

Zeit und Raum

Mittwochs 11-13 im Johann von Neumann Haus (Rudower Chaussee 25), Raum 4.112

 

Übungsleiter/in

Prof. Dr. Stephan Kreutzer und Prof. 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 (ausgeteilt am 15.04.2005; Abgabe: Freitag, den 22.04.2005 zu Beginn der Vorlesung)
• Blatt 2 (ausgeteilt am 22.04.2005; Abgabe: Freitag, den 29.04.2005 zu Beginn der Vorlesung)
• Blatt 3 (ausgeteilt am 29.04.2005; Abgabe: Freitag, den 06.05.2005 zu Beginn der Vorlesung)
• Blatt 4 (ausgeteilt am 06.05.2005; Abgabe: Freitag, den 13.05.2005 zu Beginn der Vorlesung)
• Blatt 5 (ausgeteilt am 13.05.2005; Abgabe: Freitag, den 20.05.2005 zu Beginn der Vorlesung)
• Blatt 6 (ausgeteilt am 20.05.2005; Abgabe: Freitag, den 27.05.2005 zu Beginn der Vorlesung)
• Blatt 7 (ausgeteilt am 27.05.2005; Abgabe: Freitag, den 03.06.2005 zu Beginn der Vorlesung)
• Blatt 8 (ausgeteilt am 03.06.2005; Abgabe: Freitag, den 10.06.2005 zu Beginn der Vorlesung)
• Blatt 9 (ausgeteilt am 10.06.2005; Abgabe: Freitag, den 17.06.2005 zu Beginn der Vorlesung)
• Blatt 10 (ausgeteilt am 17.06.2005; Abgabe: Freitag, den 24.06.2005 zu Beginn der Vorlesung)
• Blatt 11 (ausgeteilt am 24.06.2005; Abgabe: Freitag, den 01.07.2005 zu Beginn der Vorlesung)
• Blatt 12 (ausgeteilt am 01.07.2005; Abgabe: Freitag, den 08.07.2005 zu Beginn der Vorlesung)

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