Logic and ComplexityModule description #40421 / Version 2
- 9 CP
- Oral exam
- Graded
- Winter and summer semester
- German
This module description is not valid in the current semester (Winter semester 2026/27).
| Module / Version | #40421 / #2 |
|---|---|
| Validity | WS 2015/16 – WS 2019/20 |
| Available language(s) | German |
| Credit points | 9 |
| Person responsible for the module | Kreutzer, Stephan |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | German |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34352200 FG Logik und Semantik (LaS) |
Contact
| Office | TEL 7-3 |
|---|---|
| Contact person | Not specified |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | Not specified |
Learning outcomes
Die Studierenden kennen die verschiedenen Anwendungen der Logik in der Informatik. Sie haben das methodische Rüstzeug um die Ausdrucksstärke eines logischen Systems zu analysieren und verstehen den engen Zusammenhang zwischen Logik und algorithmischer Komplexität. Sie werden im Rahmen dieses Moduls im Schnittgebiet zwischen Logik und Algorithmik bis an den aktuellen Stand der Forschung herangeführt und somit auf eigene Arbeiten in diesem Gebiet vorbereitet.
Content
Aufbauend auf der Grundvorlesung über Logik im Bachelorstudiengang (z.B. TheGI3 an der
TU Berlin) behandelt dieses Modul weiterführende Themen der Logik in der Informatik.
Es werden zunächst verschiedene Anwendungsgebiete der Logik eingeführt, besonders
Anwendungen in der Datenbanktheorie, der Algorithmik und Komplexitätstheorie, sowie der
automatischen Verifikation.
Im Zentrum des ersten Teils der Vorlesung stehen Fragen zur Ausdrucksstärke verschiedener
Logiken und Datenbankabfragesprachen. Es werden Methoden eingeführt um nachzuweisen,
dass bestimmte Abfragen nicht in der Prädikatenlogik definiert werden kann. Aufbauend
darauf werden dann sogenannte „Lokalitätssätze" bewiesen, die die Ausdrucksstärke der
Prädikatenlogik auf sehr überraschende Art charakterisieren.
Thema des zweiten Teils der Vorlesung ist der Zusammenhang zwischen Logik und
Komplexität. Hier steht zunächst die Frage im Vordergrund, wie schwierig es ist, Formeln
einer gegebene Logik in einer Struktur auszuwerten. Vor allem aber werden wir den Bereich
der „deskriptiven Komplexitätstheorie" behandeln, in dem algorithmische Probleme nicht
anhand der zu ihrer Lösung benötigten Ressourcen wie Speicherplatz und Laufzeit
klassifiziert werden, sondern der zu ihrer Beschreibung nötigen Art und Zahl logischer
Quantoren und Operatoren. Es stellt sich heraus, dass es einen erstaunlich engen
Zusammenhang zwischen diesen beiden Arten der Beschreibung von Problemen gibt, in dem
Sinne, dass Probleme, die in natürlichen Komplexitätsklassen wie PTIME oder NP berechnet
werden können, auch Beschreibungen in natürlichen Logiken haben. Die Logik bietet
demnach einen alternativen und sehr eleganten Zugang zur Komplexitätstheorie, den wir in
diesem Teil der Vorlesung behandeln werden.
Im letzten Teil des Moduls wird auf die Rolle der Logik um Zusammenhang mit sogenannten
Constraint-Satisfaction-Problemen eingegangen, die im Bereich der künstlichen Intelligenz
sehr intensiv untersucht werden. Auch hier hat die Logik wichtige Anwendungsmöglichkeiten,
die im Rahmen der Vorlesung behandelt werden.
TU Berlin) behandelt dieses Modul weiterführende Themen der Logik in der Informatik.
Es werden zunächst verschiedene Anwendungsgebiete der Logik eingeführt, besonders
Anwendungen in der Datenbanktheorie, der Algorithmik und Komplexitätstheorie, sowie der
automatischen Verifikation.
Im Zentrum des ersten Teils der Vorlesung stehen Fragen zur Ausdrucksstärke verschiedener
Logiken und Datenbankabfragesprachen. Es werden Methoden eingeführt um nachzuweisen,
dass bestimmte Abfragen nicht in der Prädikatenlogik definiert werden kann. Aufbauend
darauf werden dann sogenannte „Lokalitätssätze" bewiesen, die die Ausdrucksstärke der
Prädikatenlogik auf sehr überraschende Art charakterisieren.
Thema des zweiten Teils der Vorlesung ist der Zusammenhang zwischen Logik und
Komplexität. Hier steht zunächst die Frage im Vordergrund, wie schwierig es ist, Formeln
einer gegebene Logik in einer Struktur auszuwerten. Vor allem aber werden wir den Bereich
der „deskriptiven Komplexitätstheorie" behandeln, in dem algorithmische Probleme nicht
anhand der zu ihrer Lösung benötigten Ressourcen wie Speicherplatz und Laufzeit
klassifiziert werden, sondern der zu ihrer Beschreibung nötigen Art und Zahl logischer
Quantoren und Operatoren. Es stellt sich heraus, dass es einen erstaunlich engen
Zusammenhang zwischen diesen beiden Arten der Beschreibung von Problemen gibt, in dem
Sinne, dass Probleme, die in natürlichen Komplexitätsklassen wie PTIME oder NP berechnet
werden können, auch Beschreibungen in natürlichen Logiken haben. Die Logik bietet
demnach einen alternativen und sehr eleganten Zugang zur Komplexitätstheorie, den wir in
diesem Teil der Vorlesung behandeln werden.
Im letzten Teil des Moduls wird auf die Rolle der Logik um Zusammenhang mit sogenannten
Constraint-Satisfaction-Problemen eingegangen, die im Bereich der künstlichen Intelligenz
sehr intensiv untersucht werden. Auch hier hat die Logik wichtige Anwendungsmöglichkeiten,
die im Rahmen der Vorlesung behandelt werden.
Module components
Compulsory area
The following courses are mandatory for this module:
Workload and credit points
Logik und Komplexität (Seminar)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Logik und Komplexität (Integrated course)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 8 h | 120 h |
| 180 h | |||
The workload of the module adds up to 270 hours. The module therefore comprises 9 credit points.
Description of teaching and learning methods
Die Veranstaltungen bestehen aus einer flexiblen Abfolge von Vorlesungen und Übungen.
Zusätzlich werden weitere Themen im Tutorium sowie zum Teil in Gruppenarbeit von den
Studierenden selbst erarbeitet.
Zusätzlich werden weitere Themen im Tutorium sowie zum Teil in Gruppenarbeit von den
Studierenden selbst erarbeitet.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Interesse an theoretischer Informatik sowie Grundkenntnisse in Logik und
Komplexitätstheorie, wie sie in den Modulen „Berechenbarkeit und Komplexität“ sowie
„Logiken und Kalküle“ vermittelt werden.
Komplexitätstheorie, wie sie in den Modulen „Berechenbarkeit und Komplexität“ sowie
„Logiken und Kalküle“ vermittelt werden.
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | German |
| Duration/Extent | 30 Minuten |
Exam description
Mündliche Prüfung
Zulassung zur Prüfungsanmeldung auf der Basis eines Nachweises über jeweils bestandene
Hausaufgaben.
Zulassung zur Prüfungsanmeldung auf der Basis eines Nachweises über jeweils bestandene
Hausaufgaben.
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Winter and summer semester.
Maximum number of participants
The maximum capacity of participants is 50.
Registration procedures
Modulanmeldung gemäß TU-Standard.
Recommended reading, lecture notes
Lecture notes
available
Electronic lecture notes
unavailable
Recommended literature
No recommended literature given
Assigned programs
This module is not used in any program.
Miscellaneous
Literatur:
Die Vorlesung orientiert sich am Skript Logik und Komplexität. Ergänzende Literaturangaben
zu den einzelnen Kapiteln werden in der Vorlesung bekannt gegeben.
Die Vorlesung orientiert sich am Skript Logik und Komplexität. Ergänzende Literaturangaben
zu den einzelnen Kapiteln werden in der Vorlesung bekannt gegeben.