|
Albert-Ludwigs-Universität Freiburg |
| Institut für mathematische Logik und Grundlagen der Mathematik |
Vorlesungen: Mo 14-16 SR 218, Mi 14-16 SR 404 Eckerstr. 1
Übung: Fr 11-13 SR 218 Eckerstr. 1
Gegenstand der Vorlesung sind die Modelltheorie endlicher Strukturen und
ihre Beziehung zu komplexitäts-
bezogenen Problemen der theoretischen Informatik.
Die meisten Methoden der klassischen Modelltheorie versagen bei
der Anwendung auf endliche Strukturen
oder führen nur zu trivia-
len Ergebnissen. Andererseits werfen endliche Strukturen andere
Fragestellungen
auf, die zum Beispiel darauf beruhen, daß man
sie kodieren und dann als Objekte von Berechnungen verwenden
kann. In der endlichen Modelltheorie spielen daher solche Spra-
chen eine Rolle, die zur Beschreibung von
Berechnungsprozessen
gebraucht werden können.
In der Vorlesung werden die wichtigsten dieser Sprachen mit ihren modelltheoretischen und berechenbarkeits-
theoretischen Eigenschaften vorgestellt. Dabei zeigt sich, daß die rechnerische
Komplexität von Problemen
eng mit deren Beschreibbarkeit in diesen Sprachen zusammenhängt. So öffnet sich ein modelltheoretischer
Zugang zu den zentralen Problemen der Komplexitätstheorie.
Überdies befaßt sich die Vorlesung mit Sprachen
der Datenbanktheorie (Datenbanken können als endliche Strukturen aufgefaßt
werden) und - abhängig von der
zur Verfügung stehenden Zeit - mit wahrscheinlichkeitstheoretischen Fragestellungen.
Voraussetzung zum Besuch sind gute Kenntnisse der mathematischen
Logik und Grundkenntnisse aus der
Modelltheorie; nützlich, wenn auch nicht notwendig, sind Kenntnisse aus der Theorie der Berechenbarkeit (Turingmaschinen) und der Komplexitätstheorie.
Neben der Vorlesung findet - zusammen mit den Herren Basin
(Informatik), Flum und Grohe - ein Seminar
über Model Checking statt. Im Anschluß an diese Veranstaltungen ist die Vergabe von Diplom- und Staatsarbeitsthemen möglich.
Zur den Übungsblättern
21. April 1999
Markus Frick
