|
Lecturer(s)
|
-
Balun Jiří, Mgr.
-
Jančar Petr, prof. RNDr. CSc.
-
Osička Petr, Mgr. Ph.D.
|
|
Course content
|
Recalling of notions like Turing machine (TM), computation, language recognized by TM, computable function, Church-Turing thesis. Languages and problems: Recursive and partial recursive languages and their relationship to the languages from Chomsky hierarchy. Rice theorem, recursion theorem, and their applications. Further models of computation: machines RAM and their mutual simulation with TM. Recalling complexity of algorithms and complexity classes, in particular classes PTIME and NPTIME. Further complexity classes: class PSPACE, class NPSPACE and Savitch theorem. PSPACE-complete problems. Classes EXPTIME and EXPSPACE. Space complexity classes L and NL. Alternating Turing machines and the corresponding complexity classes, with their relation to the standard ones. Parallel algorithms, computational circuits, and classes AC, NC. PTIME-completeness. Polynomial hierarchy. Probabilistic algorithms a the corresponding complexity classes.
|
|
Learning activities and teaching methods
|
|
Lecture, Demonstration
|
|
Learning outcomes
|
Students will deepen an extend their knowledge in the area of complexity of algorithms and problems.
1. Knowledge Describe and understand comprehensively principles and methods of complexity theory.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Oral exam, Written exam
Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.
|
|
Recommended literature
|
-
Arora S., Barak B. (2009). Computational Complexity: A Modern Approach. Cambridge Univ. Press.
-
Kozen D. (2006). Theory of Computation. Springer-Verlag, London.
-
Kučera, L. (1989). Kombinatorické algoritmy. SNTL Praha.
-
Papadimitriou, C. H. (1995). Computational Complexity. Addison-Wesley, Reading (MA).
-
Sipser M. (2013). Introduction to the Theory of Computation (Third Edition). Cengage Learning, Boston, MA, USA.
|