Theoretical Computer Science

Type of study	Follow-up Master
Language of instruction	English
Code	460-4065/04
Abbreviation	TI
Course title	Theoretical Computer Science
Credits	6
Coordinating department	Department of Computer Science
Course coordinator	doc. Ing. Zdeněk Sawa, Ph.D.

Subject syllabus

1. Introduction. Models of computation (Turing machines, random-access machines, ...), recalling computational complexity of algorithms.
2. Complexity classes. Classes P and NP, reduction between problems, NP-completeness, classical NP-complete problems.
3. Other complexity classes - PSPACE, EXPTIME, EXPSPACE, polynomial hierarchy.
4. Undecidable problems, Rice's theorem.
5. Advanced techniques for analysis and design of algorithms: amortized complexity, average-case complexity of algorithms (probabilistic analysis).
6. Randomized algorithm, approximation algorithms.
7. Computational complexity of parallel algorithms: computational models for parallel algorithms (PRAM).
8. Analysis of computational complexity of parallel algorithms, class NC, correspondence with circuits (circuit complexity).
9. Distributed algorithms: models of computation for distributed algorithms, communication complexity.
10. Kolmogorov complexity.
11. Semantics of programming languages: formal descriptions of semantics (operational semantics, denotational semantics).
12. Methods of proving correctness of programs, Hoare logic.
13. Quantum computing.

E-learning

Materials are available on the educator's website: https://www.cs.vsb.cz/sawa/tcs

Consultation through MS Teams.

Literature

[1] Michael Sipser: Introduction to the Theory of Computation, Thomson
2006

Advised literature

[2] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[5] Kozen, D.: Theory of computation, Springer 2006.
[6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[7] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[8] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.

back to search page