|
Vyučující
|
-
Rak Josef, RNDr. Ph.D.
-
Benedikovič Miroslav, RNDr.
-
Karamazov Simeon, prof. Ing. Dr.
|
|
Obsah předmětu
|
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.
|
|
Studijní aktivity a metody výuky
|
|
Monologická (výklad, přednáška, instruktáž), Dialogická (diskuze, rozhovor, brainstorming), Pozorování, Demonstrace, Nácvik dovedností, Laborování
|
|
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 jako součást popředí kompilátoru, využitím Turingových strojů, problému rozhodnutelnosti a problematiky složitosti algoritmů.
Absolvent by měl získat dostatečné teoretické znalosti z teoretické informatiky, zejména z konstrukce textových analyzátorů jako základ ke tvorbě kompilátorů. Další přínosem předmětu jsou vědomosti z problematiky Turingových strojů (TS), rozhodnutelnosti a pojmu složitosti v oblasti programování textových analyzátorů.
|
|
Předpoklady
|
Předpokladem je absolvování předmětů souvisejících s programováním.
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Posouzení zadané práce
Podmínkou udělení zápočtu z tohoto předmětu je úspěšné splnění všech zadaných praktických úloh a příslušných testů. Každou neúčast na cvičení je třeba nahradit vypracováním domácího cvičení na téma látky probírané na konkrétním cvičení, přičemž maximálně je možné akceptovat 2 absence.
|
|
Doporučená literatura
|
-
Aho, A. V., Sethi, R., Ullmann, J. D. Compilers, Principles, Techniques, and Tools. Berkley: Addison-Wesley Publishing Company, 2006. ISBN 0-201-10088-6.
-
Hopcroft, J. E., Ullmann, J. D. Formální jazyky a automaty. ALFA, Bratislava, 1978. ISBN 63-096-78.
-
Louden, Keneth C. Compiler Construction - Principles and Praktice. Boston, PWS Publishing Comp, 1997.
-
Mak, R. Writing Compilers & Interpreters. New York, John Wiley & Sons, 1991.
|