|
Lecturer(s)
|
-
Jančar Petr, prof. RNDr. CSc.
|
|
Course content
|
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. Variants of TM: TM with two-way infinite tape, multiple-tape TM, equivalences with basic TM. Universal TM: definition, description of computation. Languages and problems: Partial recursive and recursive languages, decision problems, reducibility of decision problems to languages, existence of languages which are not partially recursive. Non-recursive languages, non-computable problems: Halting problem, Post correspondence problem and its applications. Complexity: complexity of algorithms and problems. Basic complexity classes: class PTIME, nondeterministic TM and class NPTIME. NP-complete problems, selected NP-complete problems, proving NP-completeness. Introduction to the area of approximation algorithms and probabilistic algorithms.
|
|
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. (2013). Introduction to the Theory of Computation (Third Edition). Boston, MA, USA.
|