460-6004/04 – Theory of Computation (TA)
| Gurantor department | Department of Computer Science | Credits | 10 |
| Subject guarantor | prof. RNDr. Petr Jančar, CSc. | Subject version guarantor | doc. Ing. Zdeněk Sawa, Ph.D. |
| Study level | postgraduate | Requirement | Choice-compulsory type B |
| Year | | Semester | winter + summer |
| | Study language | English |
| Year of introduction | 2019/2020 | Year of cancellation | |
| Intended for the faculties | FEI, USP | Intended for study types | Doctoral |
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
Lectures
Individual consultations
Project work
Summary
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.
E-learning
Other requirements
There are not defined other requirements for student.
Prerequisities
Subject has no prerequisities.
Co-requisities
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
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.