Logik und Komplexität

Modulnummer: Q10-03
Englischer Titel: Logic and Complexity
Leistungspunkte: 10
Lehrperson: Schweikardt

Empfohlene Vorkenntnisse

solide Grundkenntnisse in den Bereichen Logik und Komplexitätstheorie

Zwingende Voraussetzungen

keine

Inhalt

Viele algorithmische Probleme lassen sich durch logische Formeln beschreiben. Dabei besteht ein enger Zusammenhang zwischen der Kompliziertheit der Formeln und der Berechnungskomplexität der Probleme. Dieser Zusammenhang spielt in verschiedenen Bereichen der Informatik eine Rolle, zum Beispiel in der Theorie formaler Sprachen, der Datenbanktheorie, der Komplexitätstheorie und im Zusammenhang mit automatischer Verifikation.
Themen dieser Vorlesung sind beispielsweise:
* Erweiterungen der Logik erster Stufe: Logik zweiter Stufe, Fixpunktlogiken
* Automatentheorie und Logik: logische Charakterisierung der regulären Sprachen
(z.B. die Sätze von Büchi und Doner, Thatcher & Wright)
* deskriptive Komplexitätstheorie: logische Charakterisierungen von Komplexitätsklassen
(z.B. die Sätze von Fagin und Immerman & Vardi)
* Endliche Modelltheorie: Trennungsresultate zwischen logisch definierten Klassen endlicher Strukturen, 0-1-Gesetze
Ziel dieser Veranstaltung ist, den Zusammenhang zwischen der logischen Beschreibbarkeit und der Berechnungskomplexität von Problemen zu verstehen.
Voraussetzung für die Teilnahme an der Veranstaltung sind solide Grundkenntnisse in den Bereichen Logik und Komplexitätstheorie.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- schriftlich eingereichte und/oder mündlich vorgetragene Loesungen zu Übungsaufgaben
- erfolgreiche Teilnahme an schriftlichen Tests
- aktive Teilnahme

Lehrveranstaltungen

Vorlesung: 4 SWS
Übung: 2 SWS

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: ja
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: nein
Sommersemester: ja

Turnus

Alle zwei Jahre