|
Vyučující
|
-
Brandejský Tomáš, doc. Ing. Dr.
-
Rak Josef, RNDr. Ph.D.
|
|
Obsah předmětu
|
Témata přednášek po týdnech semestru: 1. Úvod do teorie jazyků a gramatik, historie, základní pojmy. 2. Regulární výrazy a regulární množiny. 3. Využití regulárních výrazů, praktická práce s regulárními výrazy. 4. Regulární jazyk (podle Chomského klasifikace - jazyk typu 3), využití regulárních výrazů při definici pravidel regulárního jazyka. 5. Konečný automat jako nástroj pro vytvoření lexikálního analyzátoru - scanneru. 6. Bezkontextový jazyk (podle Chomského klasifikace - jazyk typu 2). Vlastnosti bezkontextových jazyků. 7. Derivační strom jako prostředek pro grafické vyjádření struktury věty. Chomského a Greibachové normální forma. 8. Zásobníkový automat a jeho vztah k bezkontextové gramatice. Využití zásobníkového automatu při tvorbě syntaktického analyzátoru parseru. 9. Turingovy stroje (TS). 10. Grafická reprezentace TS, modulární konstrukce, základní stavební bloky TS. 11. Použití TS jako akceptoru jazyků. Jazyk přijímaný TS. Modifikace TS. Turingovy stroje a jazyky typu 0. 12. Různé problémy a meze rozhodnutelnosti související s TS. 13. Složitost algoritmu, polynomiální převoditelnost a nezvládnutelné problémy. Obsah cvičení odpovídá výše uvedeným tématům přednášek.
|
|
Studijní aktivity a metody výuky
|
Monologická (výklad, přednáška, instruktáž), Dialogická (diskuze, rozhovor, brainstorming), Nácvik dovedností
- Domácí příprava na výuku
- 20 hodin za semestr
- Kontaktní výuka
- 52 hodin za semestr
- Semestrální práce
- 45 hodin za semestr
- Příprava na zkoušku
- 33 hodin za semestr
|
|
Výstupy z učení
|
Cílem předmětu je seznámit studenty s některými nosnými oblastmi teoretické informatiky. Získané znalosti jsou orientované na: analýzu textů programu zapsaného ve zvoleném programovacím jazyce, kompilátory, využití Turingových strojů, problém rozhodnutelnosti a problematiku složitosti algoritmů.
Absolvování předmětu jsou získány základní informace z teorie jazyků, Turingových strojů, složitosti algoritmů a problému rozhodnutelnosti.
|
|
Předpoklady
|
Předpokládají se základní znalosti matematiky, algoritmizace, programování a datových struktur.
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Posouzení zadané práce
Podmínkou k udělení zápočtu je aktivní účast na cvičení a úspěšné zpracování semestrálních prací. Předmět je zakončen zkouškou. Aktivní účast na cvičení lze nahradit vypracováním úkolů.
|
|
Doporučená literatura
|
-
JOHN E. HOPCROFT, Rajeev MOTWANI a JEFFREY D. ULLMAN. Introduction to automata theory, languages, and computation. 3. ed.. Pearson Addison: Wesley, 2014. ISBN 9781292039053.
-
LINZ, Peter. An introduction to formal languages and automata. Sixth edition.. Burlington, 2017. ISBN 9781284077247.
-
MAREŠ, Jan. Jazyky, gramatiky a automaty. 2. vyd.. Praha, 2011. ISBN 978-8001-04904-4.
|