|
Lecturer(s)
|
-
Marek Josef, doc. Ing. Ph.D.
|
|
Course content
|
1. Languages. Reducibility. Computational models. Grammars. 2. Turing machines. Complexity measures. 3. Time-complexity classes. Class P. 4. Class NP and its structure. 5. Parametrized complexity. 6. Nonuniform complexity. 7. Complexity of optimisation problems. Approximability. 8. Boolean and polynomial hierarchy. 9. Space-complexity classes. 10. Probabilistic algorithms and complexity classes. 11. Interactive proof systems. PCP classes. 12. Parallel complexity. 13. Complexity of logical theories. Basics of Kolmogorov complexity. 14. Quantum computing.
|
|
Learning activities and teaching methods
|
Interactive lecture, Lecture, Practicum
- Contact hours
- 52 hours per semester
- Preparation for an examination (30-60)
- 56 hours per semester
- Preparation for comprehensive test (10-40)
- 35 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| popsat výpočetní model počítače s libovolným přístupem (RAM) |
| formulovat základní polynomiálně řešitelné úlohy |
| formulovat základní úlohy řešitelné nedeterministicky v polynomiálním čase |
| Skills |
|---|
| aplikovat algoritmy pro základní polynomiálně řešitelné úlohy |
| vyřešit jednoduchou úlohu lineárního programování |
| Competences |
|---|
| N/A |
| N/A |
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| definovat složitostní třídy optimalizačních úloh |
| popsat pravděpodobnostní třídy výpočetní složitosti |
| popsat výpočetní model Turingova stroje |
| vysvětlit aproximační algoritmy pro standardní úlohy |
| Skills |
|---|
| odhadnout výpočetní složitost dané úlohy |
| odhadnout aproximovatelnost dané optimalizační úlohy |
| navrhnout jednoduchý pravděpodobnostní algoritmus pro danou úlohu |
| Competences |
|---|
| N/A |
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture |
| Interactive lecture |
| Practicum |
| Skills |
|---|
| Practicum |
| Competences |
|---|
| Interactive lecture |
| assessment methods |
|---|
| Knowledge |
|---|
| Oral exam |
| Test |
| Individual presentation at a seminar |
| Skills |
|---|
| Skills demonstration during practicum |
| Competences |
|---|
| Oral exam |
|
Recommended literature
|
-
Bovet, Daniel Pierre; Crescenzi, Pierluigi. Introduction to the theory of complexity. 1994. ISBN 0-13-915380-2.
-
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.
-
Rothe, Jörg. Complexity theory and cryptology : an introduction to cryptocomplexity. 2005. ISBN 3-540-22147-6.
-
Sedgewick, Robert; Flajolet, Philippe. An introduction to the analysis of algorithms. Boston : Addison-Wesley, 1996. ISBN 0-201-40009-X.
-
Sipser, Michael. Introduction to the theory of computation. 2nd ed. Boston : Thomson Course Technology, 2006. ISBN 0-534-95097-3.
-
Vazirani, Vijay V. Approximation algorithms. Berlin : Springer, 2001. ISBN 3-540-65367-8.
|