Selected Topics of Theoretical Computer Science

Type of study	Follow-up Master
Language of instruction	Czech
Code	460-4115/01
Abbreviation	VPTI
Course title	Selected Topics of Theoretical Computer Science
Credits	4
Coordinating department	Department of Computer Science
Course coordinator	doc. Ing. Zdeněk Sawa, Ph.D.

Subject syllabus

Lectures:

1.-2. Approximation algorithms and the related complexity classes
3. Probabilistic algorithms and the related complexity classes
4.-5. Parallel algorithms and the related complexity classes
6.-7. Distributed algorithms; communication complexity
8. Quantum computing; DNA computing
9. Concurrent systems, Petri nets
10. Verification of systems (temporal logic, model checking)

Exercises:
1. Design and analysis of concrete approximation algorithms. algoritmů. (2 sessions)
2. Design and analysis of concrete probabilistic algorithms.
3. Design and analysis of concrete parallel algorithms.
(2 sessions)
4. Design and analysis of concrete distributed algorithms.
(2 sessions)
5. Analysis of a selected quantum or DNA algorithm.
(1 session)
6. Description and analysis of concrete concurrent systems.
(1 sessions)
7. Specification of simple system properties in temporal logic and algorithms of their verification.
(1 sessions)

E-learning

Consultation through MS Teams.

Literature

[1] P. Jančar: a working text for the course "Selected Topics of Theoretical Computer Science"

Advised literature

[2] Kozen, D.: Theory of computation, Springer 2006
[3] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[4] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[5] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[6] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.

back to search page