The course first concisely repeats the basics of the comutability and complexity theory, which are usually covered in the master studies; an emphasis is put on the rigorous approach and deeper understanding. The course is then devoted to some advanced parts in these and further areas, including, e.g., deciding logical theories, approximation algorithms, probabilistic algorithms, parallel computation, etc.
Literature
M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006
Advised literature
D. Kozen: Automata and Computability, Springer 1997
D. Kozen: Theory of Computation; Springer 2006
I. Wegener: Complexity Theory; Springer 2005
Handbook of theoretical computer science (ed. Leeuwen J.); Vol. A : Algorithms and complexity; North-Holland 1990