Algorithmische ModelltheorieModulbeschreibung #41250 / Version 1
- 9 LP
- Mündliche Prüfung
- Benotet
- Sommersemester
- Englisch
| Modul / Version | #41250 / #1 |
|---|---|
| Gültigkeit | Seit SoSe 2025 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 9 |
| Modulverantwortliche*r | Kreutzer, Stephan |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34352200 FG Logik und Semantik (LaS) |
Kontakt
| Sekretariat | EN 25 |
|---|---|
| Ansprechpartner*in | Kreutzer, Stephan |
| E-Mail-Adresse | stephan.kreutzer@tu-berlin.de |
| Webseite | https://www.tu.berlin/las/studium-lehre/veranstaltungsangebot |
Lernergebnisse
At the end of the course student will
- be familiar with several important techniques from logic that can be facilitated to obtain algorithmic results
- have a good overview of important classes of graphs that are particularly well-suited for algorithmic applications
- be familiar with the structral properties of these classes and how they can be exploited algorithmically
- be able to employ the various tools learned in this course to develop efficient parameterized algorithms for hard computational problems on specific classes of input structures.
- be familiar with several important techniques from logic that can be facilitated to obtain algorithmic results
- have a good overview of important classes of graphs that are particularly well-suited for algorithmic applications
- be familiar with the structral properties of these classes and how they can be exploited algorithmically
- be able to employ the various tools learned in this course to develop efficient parameterized algorithms for hard computational problems on specific classes of input structures.
Lehrinhalte
As the starting point of this course we consider the simple question "How complex is it to evalute a sentence of first-order logic in a finite structure or graph". This question has a simple answer in classical complexity theory: the problem is PSPACE complete and remains so even for a fixed input graph with at least two vertices. On the other hand, if we fix the input formula the problem becomes polynomial time solvable.
The answer to this question becomes much more interesting in the context of parameterized complexity. That is, we ask under which circumstances can we evaluate a first-order sentence in a finite graph in time polynomial in the size of the graph (but with arbitrary dependence on the formula size). Under standard assumptions in complexity theory this will not be possible for all graphs or structures, but if additional restrictions are imposed on the input structure then such running time can be achieved.
In the quest to fully understand the structural restrictions that need to be imposed on the class of admissible input graphs to make such algorithms possible, a very rich and fruitful theory of the interplay between logic and structural graph theory has emerged. That is, in this field methods from computational logic and model theory are combined with methods from structural and algorithmic graph theory to achieve efficient evaluation algorithms for first-order sentences.
As a side effect, many of these methods have found numerous applications in graph algorithms and algorithms for hard computational problems.
In this course we will study several of these methods. More precisely, we will look at various structural parameters for graphs such as tree-width, tree-depth, nowhere denseness and other, identify their properties that can be exploited algorithmically, develop algorithms for NP-complete problems on these classes and finally see how this can be used to obtain efficient algorithms for first-order model checking.
At the end of the course students will have a good overview of several important graph classes and their algorithmic properties as well as a good command of the logical tools that can be employed to speed up computation and model-checking on these classes of graphs.
The most interesting aspect of this course is the way the methods from graph theory, algorithmics, and logic interact to get the results we want. As another highlight we will cover very recent results on dense classes of graphs that lead us very close to current and ongoing research problems.
The answer to this question becomes much more interesting in the context of parameterized complexity. That is, we ask under which circumstances can we evaluate a first-order sentence in a finite graph in time polynomial in the size of the graph (but with arbitrary dependence on the formula size). Under standard assumptions in complexity theory this will not be possible for all graphs or structures, but if additional restrictions are imposed on the input structure then such running time can be achieved.
In the quest to fully understand the structural restrictions that need to be imposed on the class of admissible input graphs to make such algorithms possible, a very rich and fruitful theory of the interplay between logic and structural graph theory has emerged. That is, in this field methods from computational logic and model theory are combined with methods from structural and algorithmic graph theory to achieve efficient evaluation algorithms for first-order sentences.
As a side effect, many of these methods have found numerous applications in graph algorithms and algorithms for hard computational problems.
In this course we will study several of these methods. More precisely, we will look at various structural parameters for graphs such as tree-width, tree-depth, nowhere denseness and other, identify their properties that can be exploited algorithmically, develop algorithms for NP-complete problems on these classes and finally see how this can be used to obtain efficient algorithms for first-order model checking.
At the end of the course students will have a good overview of several important graph classes and their algorithmic properties as well as a good command of the logical tools that can be employed to speed up computation and model-checking on these classes of graphs.
The most interesting aspect of this course is the way the methods from graph theory, algorithmics, and logic interact to get the results we want. As another highlight we will cover very recent results on dense classes of graphs that lead us very close to current and ongoing research problems.
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|---|---|---|---|---|---|
| Computational Model Theory | Integrierte Veranstaltung | Unregelmässig | [en] | 6 | ISIS |
Arbeitsaufwand und Leistungspunkte
Computational Model Theory (Integrierte Veranstaltung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 6 h | 90 h |
| Vor-/Nachbereitung | 15 | 12 h | 180 h |
| 270 h | |||
Der Aufwand des Moduls summiert sich zu 270 Stunden. Damit umfasst das Modul 9 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
The course will comprise a series of lectures and tutorials used to deepen the understanding of the concepts covered in the lectures.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
There are no formal prerequisites for this course as we will introduce the concepts we use from scratch.
However students are expected to be familiar with basic concepts of logic, especially first-order predicate logic as they are taught in the undergraduate course "Logik" in the computer science curriculum. Furthermore, basic knowledge of graph theory is helpful but these will be recalled in the course.
In any case, students should have a strong interest in theoretical computer science and sufficient "mathematical maturity".
However students are expected to be familiar with basic concepts of logic, especially first-order predicate logic as they are taught in the undergraduate course "Logik" in the computer science curriculum. Furthermore, basic knowledge of graph theory is helpful but these will be recalled in the course.
In any case, students should have a strong interest in theoretical computer science and sufficient "mathematical maturity".
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 | Englisch, Deutsch |
| Dauer/Umfang | 20-45 Minuten |
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Sommersemester.
Maximale teilnehmende Personen
Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.
Anmeldeformalitäten
Students can sign up for this course on the ISIS page. At the end of the term there will be an oral exam for which students can sign up in the usual way towards the end of the lecture period.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
Keine empfohlene Literatur angegeben
Zugeordnete Studiengänge
Diese Modulversion wird in folgenden Studiengängen verwendet:
| Studiengang / StuPO | Semester | Studiengangsbereich |
|---|---|---|
| Computer Engineering StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science (Informatik) StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Elektrotechnik StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
Sonstiges
Keine Angabe