Zur Modulseite PDF generieren

#40547 / #1

Seit SS 2014

Deutsch

Logik und Komplexität

6

Kreutzer, Stephan

Benotet

Mündliche Prüfung

Deutsch

Zugehörigkeit


Fakultät IV

Institut für Softwaretechnik und Theoretische Informatik

34352200 FG Logik und Semantik

Keine Angabe

Kontakt


TEL 7-3

Keine Angabe

stephan.kreutzer@tu-berlin.de

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. 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:

LehrveranstaltungenArtNummerTurnusSpracheSWS ISIS VVZ
Logik und KomplexitätIV0432 L 673k.A.de4

Arbeitsaufwand und Leistungspunkte

Logik und Komplexität (IV):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.04.0h60.0h
Vor-/Nachbereitung15.08.0h120.0h
180.0h(~6 LP)
Der Aufwand des Moduls summiert sich zu 180.0 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

Benotung

Benotet

Prüfungsform

Mündliche Prüfung

Sprache(n)

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.

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ügbarkeit:  verfügbar

 

Skript in elektronischer Form

Verfügbarkeit:  verfügbar

 

Literatur

Empfohlene Literatur
Keine empfohlene Literatur angegeben

Zugeordnete Studiengänge


Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOStuPOsVerwendungenErste VerwendungLetzte Verwendung
Informatik (B. Sc.)130WS 2014/15SoSe 2025
Naturwissenschaften in der Informationsgesellschaft (B. Sc.)446WS 2015/16WiSe 2025/26
Wirtschaftsinformatik (B. Sc.)226WS 2016/17SoSe 2025

Studierende anderer Studiengänge können dieses Modul ohne Kapazitätsprüfung belegen.

Sonstiges

Keine Angabe