| Course Unit Code | 460-4115/01 |
|---|
| Number of ECTS Credits Allocated | 4 ECTS credits |
|---|
| Type of Course Unit * | Optional |
|---|
| Level of Course Unit * | Second Cycle |
|---|
| Year of Study * | Second Year |
|---|
| Semester when the Course Unit is delivered | Summer Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | Course succeeds to compulsory courses of previous semester |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| SAW75 | doc. Ing. Zdeněk Sawa, Ph.D. |
| 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. |
| Learning Outcomes of the Course Unit |
|---|
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 |
| Course Contents |
|---|
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)
|
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
[1] P. Jančar: a working text for the course "Selected Topics of Theoretical Computer Science"
|
[1] P. Jančar: pracovní text ke kursu "Vybrané partie teoretické informatiky"
(dostupný z web-stránky předmětu)
|
| Recommended Reading: |
|---|
[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. |
[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.
|
| Planned learning activities and teaching methods |
|---|
| Lectures, Tutorials |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Credit and Examination | Credit and Examination | 100 (100) | 51 |
| Credit | Credit | 45 | 20 |
| Examination | Examination | 55 | 6 |