Logik und KomplexitätModulbeschreibung #40547 / Version 1
- 6 LP
- Mündliche Prüfung
- Benotet
- Winter- und Sommersemester
- Deutsch
| Modul / Version | #40547 / #1 |
|---|---|
| Gültigkeit | Seit SS 2014 |
| Verfügbare Sprache(n) | Deutsch |
| Leistungspunkte | 6 |
| Modulverantwortliche*r | Kreutzer, Stephan |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Deutsch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34352200 FG Logik und Semantik (LaS) |
Kontakt
| Sekretariat | TEL 7-3 |
|---|---|
| Ansprechpartner*in | Keine Angabe |
| E-Mail-Adresse | stephan.kreutzer@tu-berlin.de |
| Webseite | 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
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.
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:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Logik und Komplexität | Integrierte Veranstaltung | 0432 L 673 | Unregelmässig | [de] | 4 | ISIS |
Arbeitsaufwand und Leistungspunkte
Logik und Komplexität (Integrierte Veranstaltung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 8 h | 120 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
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Sprache | 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.
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 / StuPO | Semester | Studiengangsbereich |
|---|---|---|
| Informatik StuPO 2015 | SoSe 2025 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik |
| WiSe 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| SoSe 2026 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| WiSe 2026/27 | Wahlpflichtbereich › Katalog Informatik | |
| Informatik StuPO 2025 | WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module |
| Naturwissenschaften in der Informationsgesellschaft StuPO 2018 | SoSe 2025 | Wahlpflichtbereich › Informatik › Weiterführende Module |
| WiSe 2025/26 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| SoSe 2026 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| WiSe 2026/27 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| Naturwissenschaften in der Informationsgesellschaft StuPO 2025 | WiSe 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
| SoSe 2026 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik | |
| WiSe 2026/27 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik | |
| Wirtschaftsinformatik StuPO 2015 | SoSe 2025 | Wahlpflichtbereich › Informatik |
| WiSe 2025/26 | Wahlpflichtbereich › Informatik | |
| SoSe 2026 | Wahlpflichtbereich › Informatik | |
| WiSe 2026/27 | Wahlpflichtbereich › Informatik | |
| Wirtschaftsinformatik StuPO 2021 | SoSe 2025 | Wahlpflichtbereich › Informatik |
| WiSe 2025/26 | Wahlpflichtbereich › Informatik | |
| SoSe 2026 | Wahlpflichtbereich › Informatik | |
| WiSe 2026/27 | Wahlpflichtbereich › Informatik |
Sonstiges
Keine Angabe