| Course Unit Code | 460-4065/03 |
|---|
| Number of ECTS Credits Allocated | 6 ECTS credits |
|---|
| Type of Course Unit * | Compulsory |
|---|
| Level of Course Unit * | Second Cycle |
|---|
| Year of Study * | Second Year |
|---|
| Semester when the Course Unit is delivered | Winter 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. |
| KOT06 | Ing. Martin Kot, Ph.D. |
| 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. |
| Learning Outcomes of the Course Unit |
|---|
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 |
| Course Contents |
|---|
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. |
| Recommended or Required Reading |
|---|
| Required Reading: |
|---|
[1] Michael Sipser: Introduction to the Theory of Computation, Thomson
2006 |
| [1] Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007 (dostupná z web-stránky předmětu). |
| Recommended Reading: |
|---|
[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. |
[2] Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
[3] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[4] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[6] Kozen, D.: Theory of computation, Springer 2006.
[7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[9] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006. |
| 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 | 35 (35) | 15 |
| Written test | Written test | 20 | 10 |
| Presentation | Other task type | 15 | 1 |
| Examination | Examination | 65 | 25 |