|
Vyučující
|
-
Bělohlávek Radim, prof. RNDr. Ph.D., DSc.
-
Osička Petr, Mgr. Ph.D.
-
Masopust Tomáš, doc. RNDr. Ph.D., DSc.
|
|
Obsah předmětu
|
<ol> <li>Formální jazyky a automaty: základní pojmy, Chomského hierarchie gramatik a hierarchie jazyků.</li> <li>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.</li> <li>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.</li> <li>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.</li> </ol>
|
|
Studijní aktivity a metody výuky
|
|
Přednášení, Dialogická (diskuze, rozhovor, brainstorming)
|
|
Výstupy z učení
|
Předmět je úvodem do Formálních jazyků a automatů, Vyčíslitelnosti a Složitosti.
1. Znalost Rozpoznej neřešitelné a řešitelné problémy a jejich výpočetní složitost.
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška
Zkouška je udělována na základě ústního zkoušení.
|
|
Doporučená literatura
|
-
Hopcroft J. E., Motwani R., Ullman J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston.
-
LAWSON. (2003). Finite Automata. Chapman & Hall/CRC.
-
Linz, P. (2016). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers, Inc.
-
Melichar, B. (2003). Jazyky a překlady. Skriptum, přepracované 2. vydání. Vydavatelství ČVUT, Praha.
-
Simovici D. A., Tenney R. L. (1999). Theory of Formal Languages with Applications. World Scientific, Singapore.
-
Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|