Logik und Datenbanktheorie
Prof. Dr. Nicole Schweikardt |
![]() Logik in der Informatik, Institut für Informatik, Humboldt-Universität zu Berlin |
Aktuelles Einführung Inhalt Logbuch Vorlesung&Übung Übungsaufgaben Prüfung Literatur Links
An dieser Stelle finden Sie im Laufe des Semesters aktuelle
Mitteilungen. Bitte sehen Sie regelmäßig nach, ob es Neues gibt.
|
Thema dieser Vorlesung ist der Zusammenhang zwischen logischer Beschreibbarkeit und Komplexität.
Ein Schwerpunkt ist die deskriptive Komplexitätstheorie, in der der Zusammenhang zwischen Beschreibungskomplexität 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.
Stichworte: deskriptive Komplexität, endliche Modelltheorie, Ehrenfeucht-Fraïssé-Spiele, Fixpunktlogiken. |
Begleitend zur Vorlesung wurde nach und nach ein Vorlesungsskript erstellt. Das gesamte Skript ist hier als postscript oder als PDF erhältlich. Die einzelnen Kapitel können auch separat betrachtet werden: |
Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Teile des Vorlesungsskripts und gelegentlich ergänzende Bemerkungen. |
Informationen zum Vorlesungs- und Übungsbetrieb:
|
Es wird regelmäßig Übungsaufgaben geben, deren
erfolgreiche Bearbeitung
Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung
ist.
|
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.
Prüfungstermine: 30.+31.07.2007 (Raum 4.426, J.v.N.-Haus) und 27.+28.08.2007 (Raum 4.410, J.v.N.-Haus) Anmeldung bei Frau Eisenmann (Raum 4.402, J.v.N.-Haus) bzw. bei Frau Kämpfer (Raum 4.407, J.v.N-Haus) |
Last modified: Fri Jul 20 12:51:36 CEST 2007
Nicole Schweikardt |