460-4115/02 – Selected Topics of Theoretical Computer Science (VPTI)
Gurantor department | Department of Computer Science | Credits | 4 |
Subject guarantor | doc. Ing. Zdeněk Sawa, Ph.D. | Subject version guarantor | doc. Ing. Zdeněk Sawa, Ph.D. |
Study level | undergraduate or graduate | Requirement | Optional |
Year | 2 | Semester | summer |
| | Study language | English |
Year of introduction | 2015/2016 | Year of cancellation | |
Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
On successful completion of the course, the student, e.g.,
- is able to evaluate the possible extent of using the methods of approximation and probabilistic algorithms for sloving practical problems, and is able to design, analyse and compare such algorithms.
- is able to exactly explain further notions and methods in advanced areas of the theoretical background of computer science
Teaching methods
Lectures
Tutorials
Summary
In the course we deal with selected methods and results of some advanced topics in theoretical computer science, e.g. in the area of approximation algorithms, probabilistic algorithms, verification of concurrent systems.
Compulsory literature:
[1] P. Jančar: a working text for the course "Selected Topics of Theoretical Computer Science"
Recommended 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.
Additional study materials
Way of continuous check of knowledge in the course of semester
Every student prepares a report on a specified topic from theoretical computer science, and presents it.
The course is finished with an exam. This exam has an oral form.
E-learning
Other requirements
No additional requirements are placed on students.
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
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)
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.