Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Computational Model TheoryModule description #41250 / Version 1

← Module page Deutsche Fassung
Module / Version#41250 / #1
ValiditySince Summer semester 2025
Available language(s)English
Credit points9
Person responsible for the moduleKreutzer, Stephan
GradingGraded
Exam formatOral exam
Language(s) of instructionEnglish

Affiliation

FacultyFakultät IV
InstituteInstitut für Softwaretechnik und Theoretische Informatik
Academic chair34352200 FG Logik und Semantik (LaS)

Contact

OfficeEN 25
Contact personKreutzer, Stephan
E-mail addressstephan.kreutzer@tu-berlin.de
Websitehttps://www.tu.berlin/las/studium-lehre/veranstaltungsangebot

Learning outcomes

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.

Content

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.

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog
Computational Model TheoryIntegrated course Irregular[en]6 ISIS

Workload and credit points

Computational Model Theory (Integrated course)

Workload descriptionMultiplierHoursTotal
Attendance156 h90 h
Pre/post processing1512 h180 h
270 h

The workload of the module adds up to 270 hours. The module therefore comprises 9 credit points.

Description of teaching and learning methods

The course will comprise a series of lectures and tutorials used to deepen the understanding of the concepts covered in the lectures.

Requirements for participation and examination

Desirable prerequisites for participation in the courses:

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".

Mandatory requirements for the module examination registration:

This module has no examination requirements.

Completion of the module

GradingGraded
Exam formatOral exam
LanguageEnglish, German
Duration/Extent20-45 Minuten

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: Summer semester.

Maximum number of participants

This module is not limited to a number of students.

Registration procedures

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.

Recommended reading, lecture notes

Lecture notes

unavailable

Electronic lecture notes

unavailable

Recommended literature

No recommended literature given

Assigned programs

This module version is used in the following programs:

Program / program versionSemester(s)Curriculum component
Computer Engineering
Computer Engineering (M. Sc.) - StuPO 2015
SS 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SS 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Computer Science (Informatik)
Computer Science (Informatik) (M. Sc.) - StuPO 2015
SS 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2025/26Studiengebiete › Grundlagen der Informatik / Foundations of Computing
SS 2026Studiengebiete › Grundlagen der Informatik / Foundations of Computing
WS 2026/27Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing
Electrical Engineering
Electrical Engineering (M. Sc.) - StuPO 2015
SS 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SS 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WS 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing

Miscellaneous

Not specified