Selected Topics of Theoretical Computer Science

Lectures:

Approximation algorithms and the related complexity classes


Probabilistic algorithms and the related complexity classes

Parallel algorithms and the related complexity classes

Distributed algorithms; communication complexity

Quantum computing; DNA computing

Concurrent systems, Petri nets

Verification of systems (temporal logic, model checking)


Exercises:

Design and analysis of concrete approximation algorithms. algoritmů. (2 sessions)

Design and analysis of concrete probabilistic algorithms. (2 sessions)

Design and analysis of concrete parallel algorithms.
(2 sessions)


Design and analysis of concrete distributed algorithms.
(2 sessions)

Analysis of a selected quantum or DNA algorithm.
(1 session)

Description and analysis of concrete concurrent systems.
(2 sessions)

Specification of simple system properties in temporal logic and algorithms of their verification.
(2 sessions)


Projects:
Individual study and written elaboration of a given topic,
which usually includes oral presentation.