|
Vyučující
|
-
Lhotka Ladislav, Ing. CSc.
-
Skrbek Miroslav, Ing. Ph.D.
|
|
Obsah předmětu
|
Obsah přednášky: 1. Potřebné partie z diskrétní matematicky 2. Symboly, řetězy, jazyky, gramatiky 3. Regulární jazyky: regulární výrazy, konečné automaty a regulární gramatiky 4. Vlastnosti regulárních jazyků, pumpovací lemma 5. Bezkontextové gramatiky a jazyky 6. Syntaktická analýza: derivační strom, algoritmy, LL gramatiky 7. Zjednodušování bezkontextových gramatik, normální formy Chomskyho a Greibachové 8. Zásobníkové automaty 9. Vlastnosti bezkontextových jazyků 10. Turingův stroj 11. Turingova hypotéza a pojem algoritmu 12. Modifikace Turingova stroje, univerzální Turingův stroj 13. Lineárně omezený automat 14. Rekurzivně spočetné jazyky, Chomskyho hierarchie 15. Meze možností algoritmických výpočtů, problém zastavení Turingova stroje Obsah cvičení: Cvičení rozšiřují a doplňují látku přednášek o praktické problémy zaměřené především na syntaktickou analýzu.
|
|
Studijní aktivity a metody výuky
|
Monologická (výklad, přednáška, instruktáž)
- Účast na výuce
- 56 hodin za semestr
- Domácí příprava na výuku
- 56 hodin za semestr
- Příprava na zkoušku
- 38 hodin za semestr
|
|
Výstupy z učení
|
Kurs se zabývá teorií formálních jazyků a automatů se zaměřením na syntaktickou analýzu.
Studenti získají základní přehled o hierarchii formálních jazyků a podrobnější znalosti o regulárních a bezkontextových jazycích. To jim usnadní návrh vlastních jednodušších jazyků a výběr vhodných softwarových nástrojů.
|
|
Předpoklady
|
Základní znalosti diskrétní matematiky (množiny, funkce, grafy, stromy)
|
|
Hodnoticí metody a kritéria
|
Písemná zkouška, Průběžné hodnocení
Studenti v průběhu semestru získávají body. Celkem lze získat 100 bodů s následující strukturou: * Zkouška 55 bodů (minimum 25) * Cvičení 45 bodů (minimum 25), rozdělených takto: - test 1 (15 bodů) - test 2 (15 bodů) - domácí úlohy a samostatné úlohy na cvičeních (15 bodů) V případě dosažení aspoň minimálního počtu bodů ze zkoušky i ze cvičení se určuje výsledná známka podle následující tabulky: | body | 90-100 | 80-89 | 70-79 | 60-69 | 50-59 | < 50 | | známka | 1 | 1- | 2 | 2- | 3 | 4 | Tolerovány jsou maximálně 2 neomluvené neúčasti na cvičeních. Testy v řádném termínu lze nahradit pouze při prokázání závažného důvodu (např. nemoc doložená potvrzením od lékaře, nebo důvod předem uznaný vyučujícím). Na vlastní žádost lze opravit pouze jeden test (dle výběru studenta), a to v termínu stanoveném vyučujícím. Body opravného testu plně nahrazují body řádného testu, výsledek řádného testu se tedy opravným testem anuluje. Zkouška je písemná, ústní část je dobrovolná (např. pro vysvětlení nejasností v písemce). Pro úspěšné zvládnutí testů a zkoušky se požadují znalosti jak z přednášek, tak ze cvičení a výukových materiálů poskytnutých WWW stránkách předmětu (https://elearning.jcu.cz).
|
|
Doporučená literatura
|
-
Chytil, M. Automaty a gramatiky. Praha: SNTL, 1984.
-
Linz, P. Formal Languages and Automata. Fifth Edition. Sudbury:Jones and Bartlett, 2012. ISBN 978-1-4496-1552-9.
-
Melichar B. et al. Jazyky a překlady: Cvičení. Skriptum FEL ČVUT. Praha: Nakladatelství ČVUT, 2004. ISBN 80-01-03031-8.
-
Melichar, B. Jazyky a překlady. Skriptum FEL ČVUT, 2. vydání. Praha: Nakladatelství ČVUT, 2003. ISBN 80-01-02776-7.
|