V kursu se stručně zopakuje základ teorie vyčíslitelnosti a složitosti, který studenti měli získat v magisterském studiu. Klade se ovšem důraz na exaktní přístup a hlubší pochopení. Dále je kurs věnován pokročilým partiím, jako je např. rozhodování logických teorií, aproximační algoritmy, pravděpodobnostní algoritmy, paralelní výpočty apod.
Povinná literatura
M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006
Doporučená literatura
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