After successful completion of the course, students are able to formalize computation and design algorithms related to logical problems.These exercises accompany the course of the same title, with the goal of deepening the students' understanding of the matter taught.
A logical characterization of the complexity class NP, some (un-)definability results for finite structures, Gödel's incompleteness theorem and the undecidability of the halting problem for Turing machines.
Students solve given exercises.
Literature: L. Libkin, Elements of finite model theory
http://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf
Presentation of solutions by students.
Not necessary
The course is aimed at students with a basic knowledge of mathmatical logic or algebra.
