460-6004/03 – Theory of Computation (TA)

Gurantor departmentDepartment of Computer ScienceCredits10
Subject guarantorprof. RNDr. Petr Jančar, CSc.Subject version guarantordoc. Ing. Zdeněk Sawa, Ph.D.
Study levelpostgraduateRequirementChoice-compulsory type B
YearSemesterwinter + summer
Study languageCzech
Year of introduction2019/2020Year of cancellation
Intended for the facultiesUSP, FEIIntended for study typesDoctoral
Instruction secured by
LoginNameTuitorTeacher giving lectures
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Examination 28+0
Part-time Examination 28+0

Subject aims expressed by acquired skills and competences

On successful completion of the course, the student - understands the notions from theory of computability and complexity - is able to design algorithms suitable for practical problems - is able to analyse complexity of algorithms and categorize problems according to their complexity - masters design and analysis of approximation, probabilistic and parallel algorithms, - is able by self-study to master and present an advanced topic in theory of algorithms

Teaching methods

Individual consultations
Project work


The course first concisely repeats the basics of the comutability and complexity theory, which are usually covered in the master studies; an emphasis is put on the rigorous approach and deeper understanding. The course is then devoted to some advanced parts in these and further areas, including, e.g., deciding logical theories, approximation algorithms, probabilistic algorithms, parallel computation, etc.

Compulsory literature:

M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006

Recommended literature:

D. Kozen: Automata and Computability, Springer 1997 D. Kozen: Theory of Computation; Springer 2006 I. Wegener: Complexity Theory; Springer 2005 Handbook of theoretical computer science (ed. Leeuwen J.); Vol. A : Algorithms and complexity; North-Holland 1990

Way of continuous check of knowledge in the course of semester

The student writes a concise, cogent and understandable article about a selected advanced topic, which he/she presents during the course.


Other requirements

There are not defined other requirements for student.


Subject has no prerequisities.


Subject has no co-requisities.

Subject syllabus:

The intuitive notion of algorithm and effectively computable function. Various mathematical formalizations of these notions (Turing machines, partially recursive functions). The idea of the universal algorithm. Main ideas showing the equivalence of the above formalizations, Church-Turing thesis. Halting problem, Post Correspondence problem, and further undecidable problems. Universal function, Kleene's Normal Form Theorem, recursive and recursively enumerable sets, Post's Theorem. Recursion Theorem, Rice's Theorem. Recursive reducibility. Creative sets. Decidability of logical theories. Time and space complexity of algorithms and problems. The P-NP question. NP-completeness and PSPACE-completeness. EXPTIME, EXPSPACE, provably intractable problems. Approximation algorithms, probabilistic algorithms. Parallel and distributed algorithms. Further topics (alternation, cryptography, ...).

Conditions for subject completion

Full-time form (validity from: 2019/2020 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Examination Examination  
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2020/2021 (P0613D140005) Computer Science K Czech Ostrava Choice-compulsory type B study plan
2020/2021 (P0613D140005) Computer Science P Czech Ostrava Choice-compulsory type B study plan
2019/2020 (P0613D140005) Computer Science P Czech Ostrava Choice-compulsory type B study plan
2019/2020 (P0613D140005) Computer Science K Czech Ostrava Choice-compulsory type B study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner