Zum Inhalt springen
Technische Universität Berlin English
Vorlesungsverzeichnis und Modultransfersystem

Einführung in die Logik und deskriptive KomplexitätModulbeschreibung #40421 / Version 2

← Zur Modulseite English version
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
Modul / Version#40421 / #2
GültigkeitWS 2015/16 – WS 2019/20
Verfügbare Sprache(n)Deutsch
Leistungspunkte9
Modulverantwortliche*rKreutzer, Stephan
BenotungBenotet
PrüfungsformMündliche Prüfung
Lehrsprache(n)Deutsch

Zugehörigkeit

FakultätFakultät IV
InstitutInstitut für Softwaretechnik und Theoretische Informatik
Fachgebiet34352200 FG Logik und Semantik (LaS)

Kontakt

SekretariatTEL 7-3
Ansprechpartner*inKeine Angabe
E-Mail-Adressestephan.kreutzer@tu-berlin.de
WebseiteKeine 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.

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Logik und KomplexitätSeminar Unregelmässig[de]2 ISIS
Logik und KomplexitätIntegrierte Veranstaltung0432 L 673 Unregelmässig[de]4 ISIS

Arbeitsaufwand und Leistungspunkte

Logik und Komplexität (Seminar)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit152 h30 h
Vor-/Nachbereitung154 h60 h
90 h

Logik und Komplexität (Integrierte Veranstaltung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit154 h60 h
Vor-/Nachbereitung158 h120 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.

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.

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

BenotungBenotet
PrüfungsformMündliche Prüfung
SpracheDeutsch
Dauer/Umfang30 Minuten

Prüfungsbeschreibung (Abschluss des Moduls)

Mündliche Prüfung
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.