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.

E-learning

Materiály jsou dostupné na webu pedagoga: https://www.cs.vsb.cz/sawa/ti

Konzultace prostřednictvím MS Teams.

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.

zpět na vyhledávání