|
Vyučující
|
-
Barilla Jiří, doc. Ing. Mgr. CSc.
-
Škvor Jiří, RNDr. Ph.D.
|
|
Obsah předmětu
|
1. Konečné automaty (KA): reprezentace, jazyky rozpoznatelné konečnými automaty 2. Redukce a realizace konečných automatu 3. Nedeterministické konečné automaty 4. Gramatiky: Chomského rozdělení gramatik, regulární gramatiky 5. Regulární jazyky: uzávěrové vlastnosti, vztah ke KA 6. Aplikace regulárních jazyků a automatů: regulární výrazy a jejich druhy 7. Bezkontextové gramatiky 8. Zásobníkové automaty 9. Aplikace bezkontextových jazyků a zásobníkových automatů: LR/LL syntaktický analyzátor, ANTLR 10. Turingovy stroje: modely a jejich vlastnosti 11. Nerozhodnutelnost: Churchova-Turiingova teze, Postův korespondenční problém 12. Ekvivalentní reprezentace Turingova stroje: RASP 13. Praktické aplikace
|
|
Studijní aktivity a metody výuky
|
|
nespecifikováno
|
|
Výstupy z učení
|
V tomto předmětu se studenti seznámí s teoretickými základy konečných automatů, gramatik a zásobníkových automatů. Důraz je kladen na propojení matematické teorie s praktickou realizací a využití dané teorie v současných technologiích.
|
|
Předpoklady
|
nespecifikováno
|
|
Hodnoticí metody a kritéria
|
nespecifikováno
Požadavky pro udělení zápočtu - aktivní účast na přednáškách a cvičeních (povoleno je nejvýše 5 absencí) - absolvování dvou testů se ziskem alespoň 50 procent bodů z možných Zkouška je ústní a proběhne v časovém rozsahu zhruba 30 minut. Slouží k prověření teoretických znalostí, jako jsou definice základních pojmů, formulace stěžejních vět a vysvětlení vybraných algoritmů.
|
|
Doporučená literatura
|
-
Hopocroft J., Ulman J. Formálne jazyky a automaty. ALFA Bratislava, 1978.
-
Hopocroft J., Ulman J. Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1979.
-
Chytil M. Automaty a gramatiky. SNTL, Praha, 1984.
-
Chytil M. Teorie automatů a formálních jazyků. (Skripta), SPN Praha, 1978.
-
Kolář J., Štěpánková O., Chytil M. Logika, algebry a grafy. SNTL Praha, 1989.
-
Meduna A. Automata and Languages. Springer, 2000.
|