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

Logik und KomplexitätModulbeschreibung #40547 / Version 1

← Zur Modulseite English version
Modul / Version#40547 / #1
GültigkeitSeit SS 2014
Verfügbare Sprache(n)Deutsch
Leistungspunkte6
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.

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

Lehrinhalte

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.

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

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

Arbeitsaufwand und Leistungspunkte

Logik und Komplexität (Integrierte Veranstaltung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit154 h60 h
Vor-/Nachbereitung158 h120 h
180 h

Der Aufwand des Moduls summiert sich zu 180 Stunden. Damit umfasst das Modul 6 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

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

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

verfügbar

Empfohlene Literatur

Keine empfohlene Literatur angegeben

Zugeordnete Studiengänge

Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOSemesterStudiengangsbereich
Informatik
StuPO 2015
SoSe 2025Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WiSe 2025/26Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
SoSe 2026Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WiSe 2026/27Wahlpflichtbereich › Katalog Informatik
Informatik
StuPO 2025
WiSe 2026/27Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module
Naturwissenschaften in der Informationsgesellschaft
StuPO 2018
SoSe 2025Wahlpflichtbereich › Informatik › Weiterführende Module
WiSe 2025/26Wahlpflichtbereich › Informatik › Weiterführende Module
SoSe 2026Wahlpflichtbereich › Informatik › Weiterführende Module
WiSe 2026/27Wahlpflichtbereich › Informatik › Weiterführende Module
Naturwissenschaften in der Informationsgesellschaft
StuPO 2025
WiSe 2025/26Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik
SoSe 2026Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik
WiSe 2026/27Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik
Wirtschaftsinformatik
StuPO 2015
SoSe 2025Wahlpflichtbereich › Informatik
WiSe 2025/26Wahlpflichtbereich › Informatik
SoSe 2026Wahlpflichtbereich › Informatik
WiSe 2026/27Wahlpflichtbereich › Informatik
Wirtschaftsinformatik
StuPO 2021
SoSe 2025Wahlpflichtbereich › Informatik
WiSe 2025/26Wahlpflichtbereich › Informatik
SoSe 2026Wahlpflichtbereich › Informatik
WiSe 2026/27Wahlpflichtbereich › Informatik

Sonstiges

Keine Angabe