192.122 Algorithmic Meta-Theorems
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2022W, VU, 2.0h, 3.0EC
TUWEL

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: VU Lecture and Exercise
  • Format: Hybrid

Learning outcomes

After successful completion of the course, students are able to:

  • explain the fundamental concepts behind algorithmic meta-theorems
  • explain, assess, and analyze the discussed algorithms
  • model and analyze unknown problems in order to apply a meta-theorem 

 

Subject of course

An algorithmic meta-theorem states that if a problem can be formulated in a certain logical framework, it can be solved efficiently on a certain class of problem inputs. Hence, algorithmic meta-theorems allow formulating general results beyond individual problems and use logical methods to capture whole families of problems at once. In this course, several algorithmic meta-theorems will be considered. It will be discussed how the theorems can be established and how they can be applied to individual problems.

Some of the topics covered by the course:

  • Solving problems definable in first-order logic on sparse graphs.
  • Solving problems definable in monadic second-order logic on tree-like graphs.
  • Gaifman's theorem and Feferman-Vaught's theorem.

Teaching methods

The core of the course consists of a series of lectures that explore topics in the studied area. The lectures are held in an informal, seminar-like setting and are interactive - students are expected to to engage in what's going on actively. Every new method and technique introduced during the lecture is demonstrated in several examples.

Mode of examination

Immanent

Additional information

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.

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
Tue11:00 - 13:0011.10.2022 - 20.12.2022Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri11:00 - 13:0021.10.2022 - 16.12.2022Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Algorithmic Meta-Theorems - Single appointments
DayDateTimeLocationDescription
Tue11.10.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Tue18.10.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri21.10.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue25.10.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri28.10.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri04.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue08.11.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri11.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Fri18.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue22.11.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri25.11.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue29.11.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri02.12.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue06.12.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri09.12.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue13.12.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture
Fri16.12.202211:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Exercise
Tue20.12.202211:00 - 13:00Seminarraum FAV 01 A (Seminarraum 183/2) Lecture

Examination modalities

Exercises plus oral exam.

Exams

DayTimeDateRoomMode of examinationApplication timeApplication modeExam
Thu - 16.02.2023assessedno application-Exam

Course registration

Begin End Deregistration end
22.09.2022 19:00 03.11.2022 19:00 20.11.2022 19:00

Curricula

Literature

No lecture notes are available.

Previous knowledge

Bachelor-level knowledge of graph theory, discrete algorithms and logic is assumed.

Preceding courses

Accompanying courses

Language

English