Einführung in die Logik und deskriptive KomplexitätModulbeschreibung #40421 / Version 2
- 9 LP
- Mündliche Prüfung
- Benotet
- Winter- und Sommersemester
- Deutsch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
| Modul / Version | #40421 / #2 |
|---|---|
| Gültigkeit | WS 2015/16 – WS 2019/20 |
| Verfügbare Sprache(n) | Deutsch |
| Leistungspunkte | 9 |
| Modulverantwortliche*r | Kreutzer, Stephan |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Deutsch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34352200 FG Logik und Semantik (LaS) |
Kontakt
| Sekretariat | TEL 7-3 |
|---|---|
| Ansprechpartner*in | Keine Angabe |
| E-Mail-Adresse | stephan.kreutzer@tu-berlin.de |
| Webseite | Keine Angabe |
Lernergebnisse
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.
Lehrinhalte
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.
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
Arbeitsaufwand und Leistungspunkte
Logik und Komplexität (Seminar)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Logik und Komplexität (Integrierte Veranstaltung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 8 h | 120 h |
| 180 h | |||
Der Aufwand des Moduls summiert sich zu 270 Stunden. Damit umfasst das Modul 9 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
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.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
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.
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Sprache | Deutsch |
| Dauer/Umfang | 30 Minuten |
Prüfungsbeschreibung (Abschluss des Moduls)
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.
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Winter- und Sommersemester.
Maximale teilnehmende Personen
Die maximale Teilnehmerzahl beträgt 50.
Anmeldeformalitäten
Modulanmeldung gemäß TU-Standard.
Literaturhinweise, Skripte
Skript in Papierform
verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
Keine empfohlene Literatur angegeben
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Sonstiges
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.