1. Modulverzeichnis (MTS)
  2. Module
  3. Modulbeschreibung anzeigen

Algorithmische Modelltheorie

Zur Modulseite PDF generieren

#41250 / #1

Seit SoSe 2025

English

Computational Model Theory
Algorithmische Modelltheorie

9

Kreutzer, Stephan

Benotet

Mündliche Prüfung

English

Zugehörigkeit


Fakultät IV

Institut für Softwaretechnik und Theoretische Informatik

34352200 FG Logik und Semantik

Keine Angabe

Kontakt


Keine Angabe

Kreutzer, Stephan

stephan.kreutzer@tu-berlin.de

Keine Angabe

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.

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.

Modulbestandteile

Compulsory area

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWS ISIS VVZ
Computational Model TheoryIVk.A.en6
ISIS-Kurssuche nach Veranstaltungen des Moduls

Arbeitsaufwand und Leistungspunkte

Computational Model Theory (IV):

AufwandbeschreibungMultiplikatorStundenGesamt
Attendance15.06.0h90.0h
Pre/post processing15.012.0h180.0h
270.0h(~9 LP)
Der Aufwand des Moduls summiert sich zu 270.0 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".

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

Benotung

Benotet

Prüfungsform

Oral exam

Sprache(n)

English, German

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

Verfügbarkeit:  nicht verfügbar

 

Skript in elektronischer Form

Verfügbarkeit:  nicht verfügbar

 

Literatur

Empfohlene Literatur
Keine empfohlene Literatur angegeben

Zugeordnete Studiengänge


Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOStuPOsVerwendungenErste VerwendungLetzte Verwendung
Computer Engineering (M. Sc.)11SoSe 2025SoSe 2025
Computer Science (Informatik) (M. Sc.)12SoSe 2025SoSe 2025
Elektrotechnik (M. Sc.)11SoSe 2025SoSe 2025

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

Sonstiges

Keine Angabe