|
Vyučující
|
-
Šenkeřík Roman, prof. Ing. Ph.D.
|
|
Obsah předmětu
|
- Úvod do problematiky algoritmů. - Výpočetní složitost, definice výpočetní složitosti, časová a prostorová výpočetní složitost, asymptotické třídy. - Výpočetní problém, P-složitost, třídy složitosti. - Jazyky a gramatiky. - Regulární výrazy. - Konečné automaty, KA s jedním a dvěma zásobníky, Přechodové grafy, Kleenova věta, Moorova věta o ekvivalenci. - Turingovy stroje (TS). Definice TS a jazyka přijímaného TS. - Modifikace TS, problém rozhodnutelnosti a nerozhodnutelnosti, problém zastavení TS, nedeterministický TS. - Postovy stroje, Konečné stroje se zásobníky, RASP stroje, ekvivalence strojů a automatů. - Predikátový počet, syntaxe a sémantika. - Verifikace programů a korektnost, parciální a totální korektnost, - Programová schémata, a jejich formalizace, syntaxe a interpretace, vlastností programů a programových schémat, Pevné body programů, rekurzivní programy. - Úvod do teorie grafů.
|
|
Studijní aktivity a metody výuky
|
|
Přednášení, Cvičení na počítači
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| Znalosti z oblastí: Matematika Základy informatiky Programování |
| Znalosti z oblastí: Matematika Základy informatiky Programování |
| Výsledky učení |
|---|
| Student umí definovat základní typy algoritmů a vysvětlit koncepty výpočetní složitosti, včetně časové a prostorové složitosti, a asymptotických tříd. |
| Student umí definovat základní typy algoritmů a vysvětlit koncepty výpočetní složitosti, včetně časové a prostorové složitosti, a asymptotických tříd. |
| Student dokáže popsat a analyzovat různé výpočetní modely, jako jsou Turingovy stroje, Postovy stroje, a konečné automaty, a jejich význam v teoretické informatice. |
| Student dokáže popsat a analyzovat různé výpočetní modely, jako jsou Turingovy stroje, Postovy stroje, a konečné automaty, a jejich význam v teoretické informatice. |
| Student umí vymezit a rozlišovat mezi různými typy jazyků a gramatik, včetně regulárních výrazů a jejich aplikací. |
| Student umí vymezit a rozlišovat mezi různými typy jazyků a gramatik, včetně regulárních výrazů a jejich aplikací. |
| Student je schopen objasnit základní principy predikátového počtu, včetně jeho syntaxe a sémantiky. |
| Student je schopen objasnit základní principy predikátového počtu, včetně jeho syntaxe a sémantiky. |
| Student umí analyzovat programová schémata a metodologie verifikace programů pro zajištění jejich korektnosti. |
| Student umí analyzovat programová schémata a metodologie verifikace programů pro zajištění jejich korektnosti. |
| Odborné dovednosti |
|---|
| Student dokáže navrhnout a vytvořit efektivní algoritmy s ohledem na časovou a prostorovou složitost. |
| Student dokáže navrhnout a vytvořit efektivní algoritmy s ohledem na časovou a prostorovou složitost. |
| Student umí realizovat a simulovat různé výpočetní modely, jako jsou Turingovy stroje a konečné automaty, pro řešení konkrétních problémů. |
| Student umí realizovat a simulovat různé výpočetní modely, jako jsou Turingovy stroje a konečné automaty, pro řešení konkrétních problémů. |
| Student používá regulární výrazy pro analýzu a zpracování textových dat a umí analyzovat strukturu jazyků. |
| Student používá regulární výrazy pro analýzu a zpracování textových dat a umí analyzovat strukturu jazyků. |
| Student aplikuje principy predikátového počtu pro řešení konkrétních logických a matematických problémů. |
| Student aplikuje principy predikátového počtu pro řešení konkrétních logických a matematických problémů. |
| Student umí provést verifikaci programů a navrhnout zlepšení pro zvýšení jejich efektivity a spolehlivosti. |
| Student umí provést verifikaci programů a navrhnout zlepšení pro zvýšení jejich efektivity a spolehlivosti. |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednášení |
| Přednášení |
| Cvičení na počítači |
| Cvičení na počítači |
| Hodnotící metody |
|---|
| Písemná zkouška |
| Písemná zkouška |
|
Doporučená literatura
|
-
Demel J. Grafy a jejich aplikace. Academia, 2002.
-
Eric C.R. Hehner, A. Practical Theory of Programming. Springer, 1993.
-
Koubková A., Pavelka J. Uvod do teoretické informatiky. Matfyzpress, 2003.
-
Linz, Peter. An introduction to formal languages and automata. 4th ed. Sudbury, Mass. : Jones and Bartlett Publishers, 2006. ISBN 0-7637-3798-4.
-
Manna Z. Matematická teorie programů. SNTL, 1981.
-
Martin J.C. Introduction to Languages and the Theory of Computation. 2002. ISBN 0-072-32200-4.
-
Vaníček J., Papík M., Pregl R., Vaníček T. Teoretické základy informatiky. Alfa Publishing, 2006.
|