Materiály jsou dostupné na webu pedagoga: https://www.cs.vsb.cz/sawa/ti
Konzultace prostřednictvím MS Teams.
Teoretická informatika
| Typ studia | navazující magisterské |
|---|---|
| Jazyk výuky | čeština |
| Kód | 460-4065/03 |
| Zkratka | TI |
| Název předmětu česky | Teoretická informatika |
| Název předmětu anglicky | Theoretical Computer Science |
| Kreditů | 6 |
| Garantující katedra | Katedra informatiky |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
Osnova předmětu
1. Úvod. Základní výpočetní modely (Turingovy stroje, stroje RAM, ...), připomenutí výpočetní složitosti algoritmu.
2. Třídy složitosti. Třídy P a NP, redukce mezi problémy NP-úplnost, klasické NP-úplné problémy.
3. Další třídy složitosti - PSPACE, EXPTIME, EXPSPACE, polynomiální hierarchie.
4. Algoritmicky nerozhodnutelné problémy, Riceova věta.
5. Pokročilejší techniky analýzy a návrhu algoritmů: amortizovaná složitost, složitost algoritmů v průměrném případě (pravděpodobnostní analýza).
6. Randomizované algoritmy, aproximační algoritmy.
7. Výpočetní složitost paralelních algoritmů: výpočetní modely pro paralelní algoritmy (PRAM).
8. Analýza výpočetní složitosti paralelních algoritmů, třída NC, souvislost s obvody (circuit complexity).
9. Distribuované algoritmy: výpočetní modely pro distribuované algoritmy, komunikační složitost.
10. Kolmogorov complexity.
11. Sémantika programovacích jazyků: formální popis sémantiky (operační sémantika, denotační sémantika).
12. Metody dokazování korektnosti programů.
13. Kvantové výpočty.
2. Třídy složitosti. Třídy P a NP, redukce mezi problémy NP-úplnost, klasické NP-úplné problémy.
3. Další třídy složitosti - PSPACE, EXPTIME, EXPSPACE, polynomiální hierarchie.
4. Algoritmicky nerozhodnutelné problémy, Riceova věta.
5. Pokročilejší techniky analýzy a návrhu algoritmů: amortizovaná složitost, složitost algoritmů v průměrném případě (pravděpodobnostní analýza).
6. Randomizované algoritmy, aproximační algoritmy.
7. Výpočetní složitost paralelních algoritmů: výpočetní modely pro paralelní algoritmy (PRAM).
8. Analýza výpočetní složitosti paralelních algoritmů, třída NC, souvislost s obvody (circuit complexity).
9. Distribuované algoritmy: výpočetní modely pro distribuované algoritmy, komunikační složitost.
10. Kolmogorov complexity.
11. Sémantika programovacích jazyků: formální popis sémantiky (operační sémantika, denotační sémantika).
12. Metody dokazování korektnosti programů.
13. Kvantové výpočty.
E-learning
Povinná literatura
[1] Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007 (dostupná z web-stránky předmětu).
Doporučená literatura
[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.
[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.