Logic and ComplexityModule description #40547 / Version 1
- 6 CP
- Oral exam
- Graded
- Winter and summer semester
- German
| Module / Version | #40547 / #1 |
|---|---|
| Validity | Since SS 2014 |
| Available language(s) | German |
| Credit points | 6 |
| Person responsible for the module | Kreutzer, Stephan |
| Grading | Graded |
| Exam format | Oral exam |
| Language(s) of instruction | German |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34352200 FG Logik und Semantik (LaS) |
Contact
| Office | TEL 7-3 |
|---|---|
| Contact person | Not specified |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | Not 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
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.
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:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|---|---|---|---|---|---|
| Logik und Komplexität | Integrated course | 0432 L 673 | Irregular | [de] | 4 | ISIS |
Workload and credit points
Logik und Komplexität (Integrated course)
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 4 h | 60 h |
| Vor-/Nachbereitung | 15 | 8 h | 120 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
| Grading | Graded |
|---|---|
| Exam format | Oral exam |
| Language | German |
| Duration/Extent | 30 Minuten |
Exam description
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.
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 version | Semester(s) | Curriculum component |
|---|---|---|
| Computer Science Computer Science (B. Sc.) - StuPO 2015 | SS 2025 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik |
| WS 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| SS 2026 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| WS 2026/27 | Wahlpflichtbereich › Katalog Informatik | |
| Computer Science Computer Science (B. Sc.) - StuPO 2025 | WS 2026/27 | Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module |
| Information Systems Management Information Systems Management (B. Sc.) - StuPO 2015 | SS 2025 | Wahlpflichtbereich › Informatik |
| WS 2025/26 | Wahlpflichtbereich › Informatik | |
| SS 2026 | Wahlpflichtbereich › Informatik | |
| WS 2026/27 | Wahlpflichtbereich › Informatik | |
| Information Systems Management Information Systems Management (B. Sc.) - StuPO 2021 | SS 2025 | Wahlpflichtbereich › Informatik |
| WS 2025/26 | Wahlpflichtbereich › Informatik | |
| SS 2026 | Wahlpflichtbereich › Informatik | |
| WS 2026/27 | Wahlpflichtbereich › Informatik | |
| Natural Sciences in the Information Society StuPO 2018 | SS 2025 | Wahlpflichtbereich › Informatik › Weiterführende Module |
| WS 2025/26 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| SS 2026 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| WS 2026/27 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| Natural Sciences in the Information Society Natural Sciences in the Information Society (B. Sc.) - StuPO 2025 | WS 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
| SS 2026 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik | |
| WS 2026/27 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
Miscellaneous
Not specified