|
Lecturer(s)
|
-
Kosková Třísková Lenka, Ing. Ph.D.
|
|
Course content
|
Lecture: 1. Mathematical models of computation, Turing machine. 2. Decidability, halting problem, Post correspondence problem. 3. Computability, recursive functions, Turing and Church thesis. 4. Algorithmical complexity. 5. Asymptotical complexity. 6. Polynomial decidability. 7. NP-languages, NP-problems, NP-complexity.
|
|
Learning activities and teaching methods
|
Monological explanation (lecture, presentation,briefing)
- Class attendance
- 14 hours per semester
|
|
Learning outcomes
|
Complexity of algorithms, polynomial, NP, exponential, NP-complete problems. Primality. Cryptography. Computability: Turing machines, primitive recursive functions, Kleene Normal Form Theorem, unsolvable problems, recursive sets, recursively enumerable sets.
The students gain overview of main terms related to theoretical decidability and complexity of algorithms.
|
|
Prerequisites
|
Unspecified
|
|
Assessment methods and criteria
|
Combined examination
Requirements for getting a credit are activity at the practicals /seminars and successful passing the tests.
|
|
Recommended literature
|
-
Hopcroft, J. E., Ullman, J. D. Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979.
-
Jiří Vaníček. Teoretické základy informatiky. Praha, 2007. ISBN 9788090396241.
|