Lecturer(s)


Beránek Ladislav, doc. Ing. CSc.

Houda Michal, Mgr. Ph.D.

Course content

Topics: 1. Motivational example. Definition of Turing machine, TS variants. 2. Conversion of a ktape Turing machine to a singletape. 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, NPcomplete problems. 9. Memory complexity class PSPACE and NPSPACEcomplete 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 9780521424264.

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 053494728X.
