|
Lecturer(s)
|
-
Jančar Petr, prof. RNDr. CSc.
|
|
Course content
|
<ol> <li>Introduction to computability: Turing machine (TM) definition, concept of computation, language recognized by TM (configuration, etc.), language decided by TM, TM computable function, Church-Turing thesis.</li> <li>Variants of TM: TM with two-way infinite tape, multiple-tape TM, equivalences with basic TM.</li> <li>Universal TM: definition, description of computation.</li> <li>Languages and problems: Partial recursive and recursive languages, decision problems, reducibility of decision problems to languages, existence of languages which are not partial recursive.</li> <li>Non-recursive languages, non-computable problems: Halting problem, Post correspondence problem and its applications.</li> <li>Recursive nad partial recursive languages and their relationship to the languages from Chomsky hierarchy.</li> <li>Further results: Rice theorem, recursion theorem, applications.</li> <li>Further models of computation: Post machines, non-deterministic TM, probabilistic TM.</li> <li>Complexity: complexity of algorithms and problems.</li> <li>Basic complexity classes: class P, class NP, NP-complete problems, selected NP-complete problems,proving NP-completeness.</li> <li>Further complexity classes: class PSPACE, class NPSPACE, PSPACE-complete problems.</li> <li>Applications of hard problems: Cryptography, RSA method.</li> </ol>
|
|
Learning activities and teaching methods
|
|
Lecture, Demonstration
|
|
Learning outcomes
|
The students become familiar with basic concepts of computability and complexity.
1. Knowledge Identify unsolvable problems and solvable problems and their computational complexity.
|
|
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
|
-
Copeland B.J. et al. (2015). Computability: Turing, Goedel, Church, and Beyond. MIT Press.
-
Hopcroft J. E., Motwani R., Ullmann J. D. (2003). Introduction to Automata Theory, Languages, and Computation. Pearson Education.
-
Koubková, A., Pavelka, J. (1998). Úvod do teoretické informatiky. Matfyzpress, Praha.
-
Kozen D. C. (1997). Automata and Computability. Springer.
-
Kučera, L. (1989). Kombinatorické algoritmy. SNTL, Praha.
-
Lewis, H. R., Papadimitriou, C. H. (1998). Elements of the Theory of Computation. Prentice Hall, Upper Saddle River (NJ).
-
Papadimitriou, C. H. (1995). Computational Complexity. Addison-Wesley, Reading (MA).
-
Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|