460-4065/03 – Teoretická informatika (TI)
| Garantující katedra | Katedra informatiky | Kredity | 6 |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | | |
| | Jazyk výuky | čeština |
| Rok zavedení | 2022/2023 | Rok zrušení | |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student po úspěšném absolvování předmětu:
- umí vyhodnotit vhodnost a rozsah možného nasazení metod konečných automatů,
bezkontextových gramatik apod. při řešení konkrétních problémů praxe
a umí příslušná řešení vytvářet, analyzovat a porovnávat
- je schopen analyzovat výpočtovou složitost problémů vyskytujících se
v inženýrské praxi a navrhovat vhodné algoritmy pro jejich řešení
- rozumí pojmům jako aproximační algoritmy, pravděpodobnostní
algoritmy apod. a umí vyhodnotit možnosti jejich použití v
konkrétních praktických kontextech
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Kurs prohlubuje a rozšiřuje teoretické základy v oblasti
formálních jazyků, automatů, gramatik, výpočtových problémů a
hlavně algoritmů a jejich složitosti, které student měl v základní formě nabýt v bakalářském studiu. Je také kladen speciální důraz na správné používání formalismu matematické logiky a důkazových technik.
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.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
V průběhu semestru se bude psát zápočtová písemka.
Každý student dále v průběhu semestru vypracuje referát na zadané téma z oblasti teoretické informatiky, který bude prezentovat.
Předmět je zakončen zkouškou. Tato zkouška probíhá písemnou formou.
E-learning
Další požadavky na studenta
Další požadavky na studenty nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
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.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky