Předmět Základy teoretické informatiky (KMI / XZTI)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / XZTI - Základy teoretické informatiky, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
Formální jazyky a automaty: základní pojmy, Chomského hierarchie gramatik a hierarchie jazyků.Regulární jazyky: Konečné automaty deterministické a nedeterministické, jejich vzájemný vztah, regulární výrazy, vztah konečných automatů a regulárních výrazů k regulárním jazykům.Bezkontextové jazyky: Zavedení zásobníkových automatů a jejich vztah k bezkontextovým jazykům.Vyčíslitelnost: Turingův stroj (TS), jazyky přijímané TS, jazyky rozhodované TS, částečně řešitelné a řešitelné problémy, problém zastavení TS.Složitost: Třídy složitostí úloh, třídy P a NP, jejich vzájemný vztah, NP-úplné problémy, využití výpočetně obtížných úloh.
Získané způsobilosti
1. ZnalostRozpoznej neřešitelné a řešitelné problémy a jejich výpočetní složitost.
Literatura
Chytil M. Automaty a gramatiky. SNTL Praha, 1984. Lewis H. R., Papadimitriou C. H. Elements of the Theory of Computation. Prentice Hall, Upper Saddle River (NJ), 1998. Hopcroft J. E., Motwani R., Ullman J. D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston, 2006. ISBN 978-0321462251.Sipser M. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA, 1997. ISBN 0-534-94728-X.Kučera, Luděk. Kombinatorické algoritmy. SNTL, 1989. Koubková, A., Pavelka, J. Úvod do teoretické informatiky. Matfyzpress, Praha, 1998. ISBN 8085863332.Martinek P. Základy teoretické informatiky. Interní text distančního vzdělávání, Olomouc, 2006.
Požadavky
Zkouška je udělována na základě ústního zkoušení.
Garant
prof. RNDr. Radim Bělohlávek, Ph.D., DSc.