|
Vyučující
|
-
Kadavý Tomáš, Ing.
-
Š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í |
|---|
| The student can define basic types of algorithms and explain concepts of computational complexity, including time and space complexity, and asymptotic classes. |
| The student can define basic types of algorithms and explain concepts of computational complexity, including time and space complexity, and asymptotic classes. |
| The student can describe and analyze various computational models, such as Turing machines, Post machines, and finite automata, and their significance in theoretical computer science. |
| The student can describe and analyze various computational models, such as Turing machines, Post machines, and finite automata, and their significance in theoretical computer science. |
| The student is able to delineate and distinguish between different types of languages and grammars, including regular expressions and their applications. |
| The student is able to delineate and distinguish between different types of languages and grammars, including regular expressions and their applications. |
| The student is capable of clarifying the basic principles of predicate calculus, including its syntax and semantics. |
| The student is capable of clarifying the basic principles of predicate calculus, including its syntax and semantics. |
| The student can analyze program schemata and methodologies for program verification to ensure their correctness. |
| The student can analyze program schemata and methodologies for program verification to ensure their correctness. |
| Odborné dovednosti |
|---|
| The student can design and create efficient algorithms considering time and space complexity. |
| The student can design and create efficient algorithms considering time and space complexity. |
| The student is able to implement and simulate various computational models, such as Turing machines and finite automata, for solving specific problems. |
| The student is able to implement and simulate various computational models, such as Turing machines and finite automata, for solving specific problems. |
| The student uses regular expressions for analyzing and processing text data and can analyze the structure of languages. |
| The student uses regular expressions for analyzing and processing text data and can analyze the structure of languages. |
| The student applies principles of predicate calculus to solve specific logical and mathematical problems. |
| The student applies principles of predicate calculus to solve specific logical and mathematical problems. |
| The student can perform program verification and suggest improvements to increase their efficiency and reliability. |
| The student can perform program verification and suggest improvements to increase their efficiency and reliability. |
| 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.
|