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

Logic and ComplexityModule description #40547 / Version 1

← Module page Deutsche Fassung
Module / Version#40547 / #1
ValiditySince SS 2014
Available language(s)German
Credit points6
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.

Das Modulvermittelt überwiegend:
Fachkompetenz 60x Methodenkompetenz 30x Systemkompetenz 0x Sozialkompetenz 10x

Content

Aufbauend auf der Vorlesung TheGI3 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 Datnbankabfragesprachen. Es werden Methoden eingeführt um nachzuweisen, dass bestimmte Abfragen nicht in der Prädikatenlogik definiert werden
können. Aufbauend darauf werden dann sogenannte "Lokalitätssätze" bewiesen, die die Ausdrucksstärke der Prädikatenlogik auf sehr überraschende Weise 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 gegebenen 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.

Module components

Compulsory area

The following courses are mandatory for this module:

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

Workload and credit points

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 180 hours. The module therefore comprises 6 credit points.

Description of teaching and learning methods

Die Veranstaltungen bestehen aus einer flexiblen Abfolge von Vorlesungen und Übungen.

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
Duration/Extent30 Minuten

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

available

Recommended literature

No recommended literature given

Assigned programs

This module version is used in the following programs:

Program / program versionSemester(s)Curriculum component
Computer Science
Computer Science (B. Sc.) - StuPO 2015
SS 2025Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WS 2025/26Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
SS 2026Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WS 2026/27Wahlpflichtbereich › Katalog Informatik
Computer Science
Computer Science (B. Sc.) - StuPO 2025
WS 2026/27Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module
Information Systems Management
Information Systems Management (B. Sc.) - StuPO 2015
SS 2025Wahlpflichtbereich › Informatik
WS 2025/26Wahlpflichtbereich › Informatik
SS 2026Wahlpflichtbereich › Informatik
WS 2026/27Wahlpflichtbereich › Informatik
Information Systems Management
Information Systems Management (B. Sc.) - StuPO 2021
SS 2025Wahlpflichtbereich › Informatik
WS 2025/26Wahlpflichtbereich › Informatik
SS 2026Wahlpflichtbereich › Informatik
WS 2026/27Wahlpflichtbereich › Informatik
Natural Sciences in the Information Society
StuPO 2018
SS 2025Wahlpflichtbereich › Informatik › Weiterführende Module
WS 2025/26Wahlpflichtbereich › Informatik › Weiterführende Module
SS 2026Wahlpflichtbereich › Informatik › Weiterführende Module
WS 2026/27Wahlpflichtbereich › Informatik › Weiterführende Module
Natural Sciences in the Information Society
Natural Sciences in the Information Society (B. Sc.) - StuPO 2025
WS 2025/26Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik
SS 2026Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik
WS 2026/27Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik

Miscellaneous

Not specified