Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

• fundamentale Konzepte, die hinter algorithmischen Meta-Theoremen stecken, zu erklären,
• die vorgestellten Algorithmen zu erklären, zu begreifen, und zu analysieren, und
• neue Probleme zu analysieren und zu modellieren, um sie mittels algorithmischer Meta-Theoreme zu lösen.

Ein algorithmisches Meta-Theorem besagt, dass man alle Probleme, die in einem gewissen logischen Formalismus ausgedrückt werden können, auf bestimmten Klassen von Problemeingaben effizient lösen kann. Das erlaubt einen sehr allgemeinen Ansatz zur algorithmischen Problemlösung, der über einzelne Probleme hinausgeht.

Einige der Themen, die In der Lehrveranstaltung behandelt werden, sind:

• Lösung von Problemen auf dünnen Graphen, die in Logik erster Ordung ausgedrückt werden können.
• Lösung von Problemen auf baumartigen Graphen, die in monadischer Logik zweiter Ordung ausgedrückt werden können.
• Die Sätze von Gaifman und Feferman-Vaught.

Das Kernstück dieser Lehrveranstaltung sind die Vorlesungseinheiten, in welchen die Inhalte vorgestellt werden. Die Vorlesungen werden in einer informellen, seminarartigen Weise abgehalten und sind interaktiv; von den Studierenden wird erwartet, dass sie sich aktiv einbringen. Jede neue Methode und jedes neues Konzept das in den Vorlesungen eingeführt wird, wird mit verschiedenen Beispielen erläutert.

The lectures take place in room FAV 01 A and the exercises take place in room FAV 01 B. The course is planned to be held in person. We switch to online if the covid situation requires it.

Übungen und mündliche Prüfung.

Es werden Grundkenntnisse in Graphentheorie, Algorithmen und Datenstrukturen und Logik, auf Bachelor-Niveau erwartet.