Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage......
As this course is given in English, please ignore above introductory words.
These exercises accompany the course of the same title, with the goal of deepening the students' understanding of the matter taught. Students will be able to formalize computation and design algorithms related to logical problems.
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.
Übungsaufgaben werden gelöst.
Literatur: L. Libkin, Elements of finite model theory
http://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf
Vortrag der Lösungen von Übungsbeispielen.
Nicht erforderlich
The course is aimed at students with a basic knowledge of mathmatical logic or algebra.