Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Logic and ComplexityModule description #40421 / Version 1

← Module page Deutsche Fassung
This module description is not valid in the current semester (Winter semester 2026/27).
Module / Version#40421 / #1
ValiditySS 2014 – SS 2015
Available language(s)German
Credit points9
Person responsible for the moduleKreutzer, Stephan
GradingGraded
Exam formatOral exam
Language(s) of instructionGerman

Affiliation

FacultyFakultät IV
InstituteInstitut für Softwaretechnik und Theoretische Informatik
Academic chair34352200 FG Logik und Semantik (LaS)

Contact

OfficeTEL 7-3
Contact personNot specified
E-mail addressstephan.kreutzer@tu-berlin.de
WebsiteNot 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.
Das Modul vermittelt überwiegend:
Fachkompetenz 60x Methodenkompetenz 30x Systemkompetenz 0x Sozialkompetenz 10x

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.

Module components

Compulsory elective area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Logik und KomplexitätSeminar Irregular[de]2 ISIS
Logik und KomplexitätIntegrated course0432 L 673 Irregular[de]4 ISIS

Workload and credit points

Logik und Komplexität (Seminar)

Workload descriptionMultiplierHoursTotal
Präsenzzeit152 h30 h
Vor-/Nachbereitung154 h60 h
90 h

Logik und Komplexität (Integrated course)

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

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.

Mandatory requirements for the module examination registration:

This module has no examination requirements.

Completion of the module

GradingGraded
Exam formatOral exam
LanguageGerman

Exam description

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