|
Lecturer(s)
|
-
Beránek Ladislav, prof. Ing. CSc., MBA
-
Houda Michal, Mgr. Ph.D.
-
Klán Petr, doc. Mgr. Ing. CSc.
|
|
Course content
|
Topics: 1. Motivational example. Definition of Turing machine, TS variants. 2. Conversion of a k-tape Turing machine to a single-tape. RAM and its equivalence with Turing machines. 3. Algorithm as a computational model. Church's thesis. 4. Classification of problems. Decidable, indecidable and partially decidable problems. Computable functions. 5. Closure properties, Rice's theorems. Computational complexity of problems. 6. Reduction and completeness in problem classes. 7. Reduction and polynomial reduction. 8. Complete problems in terms of decidability, NP-complete problems. 9. Memory complexity class PSPACE and NPSPACE-complete problems. 10. Approximation algorithms and schemes. 11. Applications.
|
|
Learning activities and teaching methods
|
|
Monologic (reading, lecture, briefing), Work with text (with textbook, with book)
|
|
Learning outcomes
|
The aim of the course is to clarify the basic approaches and methods of classification of problems in terms of the possibility of their algorithmic solution and to perform the basic classification. Students will understand the basic concepts formalizing algorithmic solvability, they will be able to apply the techniques discussed to some situations, understand the theoretical and practical limits of the use of computers and the implications of these limitations for the development of information technology.
Students will understand the basic concepts formalizing algorithmic solvability, they will be able to apply the techniques discussed to some situations, understand the theoretical and practical limits of the use of computers and the implications of these limitations for the development of information technology.
|
|
Prerequisites
|
Basic knowledge of algorithms and discrete mathematics.
|
|
Assessment methods and criteria
|
Combined exam, Seminar work, Interim evaluation
Elaboration of assigned tasks from exercises, active participation in seminars in the form of presentation of student problem solving.
|
|
Recommended literature
|
-
ARORA, Sanjeev a Boaz BARAK. Computational complexity: a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 978-0-521-42426-4.
-
DEMUTH, Osvald, Antonín KUČERA a Rudolf KRYL. Teorie algoritmů. 2. vyd. Praha: Státní pedagogické nakladatelství, 1989.
-
SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing, 1997. ISBN 0-534-94728-X.
|