Zum Inhalt springen
Technische Universität Berlin English
Vorlesungsverzeichnis und Modultransfersystem

Algorithmische ModelltheorieModulbeschreibung #41250 / Version 1

← Zur Modulseite English version
Modul / Version#41250 / #1
GültigkeitSeit SoSe 2025
Verfügbare Sprache(n)Englisch
Leistungspunkte9
Modulverantwortliche*rKreutzer, Stephan
BenotungBenotet
PrüfungsformMündliche Prüfung
Lehrsprache(n)Englisch

Zugehörigkeit

FakultätFakultät IV
InstitutInstitut für Softwaretechnik und Theoretische Informatik
Fachgebiet34352200 FG Logik und Semantik (LaS)

Kontakt

SekretariatEN 25
Ansprechpartner*inKreutzer, Stephan
E-Mail-Adressestephan.kreutzer@tu-berlin.de
Webseitehttps://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.

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

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Computational Model TheoryIntegrierte Veranstaltung Unregelmässig[en]6 ISIS

Arbeitsaufwand und Leistungspunkte

Computational Model Theory (Integrierte Veranstaltung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit156 h90 h
Vor-/Nachbereitung1512 h180 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".

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

BenotungBenotet
PrüfungsformMündliche Prüfung
SpracheEnglisch, Deutsch
Dauer/Umfang20-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 / StuPOSemesterStudiengangsbereich
Computer Engineering
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Computer Science (Informatik)
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Studiengebiete › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Studiengebiete › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing
Elektrotechnik
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing

Sonstiges

Keine Angabe