Course: null

« Back
Course title -
Course code KMI/VS
Organizational form of instruction Lecture + Lesson
Level of course Master
Year of study not specified
Semester Winter
Number of ECTS credits 6
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Beránek Ladislav, doc. Ing. CSc.
  • 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.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester