460-4065/04 – Theoretical Computer Science (TI)
Gurantor department | Department of Computer Science | Credits | 6 |
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 | Compulsory |
Year | 2 | Semester | winter |
| | Study language | English |
Year of introduction | 2022/2023 | 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
- is able to evaluate the possible extent of using the methods of
finite automata, context-free grammars etc. by solving concrete
practical problems, and is able to design, analyse and compare the
respective solutions
- is able to analyse computational complexity of practical problems,
and to design algorithms for their solution
- understands the notions like approximation algorithms, probabilistic
algorithms, etc. and can evaluate the possibilities of their use in
concrete practical situations
Teaching methods
Lectures
Tutorials
Summary
The course extends the theoretical background for computer science
gained in bachelor studies, in particular in the areas of automata,
languages, computability and complexity.
Compulsory literature:
[1] Michael Sipser: Introduction to the Theory of Computation, Thomson
2006
Recommended 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.
Way of continuous check of knowledge in the course of semester
There will be a written test during a semester.
Every students also prepares a report on a selected topic from theoretical computer science during semester and presents it.
The course is finished with an exam. This exam has a written 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:
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.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.