Detail předmětu
Regulované gramatiky a automaty
RGD Ak. rok 2021/2022 zimní semestr
Předmět diskutuje regulované přepisování jako jedno z ústředních témat teoretické informatiky posledních let. Zaměřuje se na nejmodernější výzkum v oblasti regulovaných gramatik a automatů včetně jejich praktického využití. Získání a porozumění prezentovaných poznatků je ověřeno zpracováním vlastní tvůrčí tématické práce studenta.
Okruhy otázek k SDZ:
- Regulované automaty a gramatiky: základní idea.
- Gramatiky s regulovaným užitím pravidel.
- Kontextově založené regulované gramatiky.
- Gramatiky s algebraicky založenou regulací.
- Redukce regulovaných gramatik.
- Paralelní verze regulovaných gramatik.
- Regulované konečné automaty.
- Regulované zásobníkové automaty.
- Hluboké zásobníkové automaty.
- Skákající automaty.
Garant předmětu
Koordinátor předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 13 hod. projekty
Bodové hodnocení
- 60 bodů závěrečná zkouška
- 40 bodů projekty
Zajišťuje ústav
Přednášející
Cvičící
Stránky předmětu
Získané dovednosti, znalosti a kompetence z předmětu
Podrobný přehled o poznatcích současné teoretické informatice v oblasti regulovaného přepisování a schopnost je využít ve vlastním výzkumu.
Cíle předmětu
Předat studentům podrobný přehled modelů a výsledků týkajících se regulovaného přepisování v rámci teoretické informatiky. Zdokonalit a utvrdit schopnost tvůrčím způsobem využívat získaných poznatků z moderní teoretické informatiky ve vlastním výzkumu.
Požadované prerekvizitní znalosti a dovednosti
formalni jazyky
Literatura studijní
- kopie přednášek
- kopie přednášek
- ROZENBERG Grzegorz a SALOMAA Arto. Handbook of Formal Languages, Volumes 1-3. Springer, 1997
- MEDUNA Alexander a ZEMEK Petr. Regulated Grammars and Automata. New York: Springer US, 2014. ISBN 978-1-4939-0368-9
- MEDUNA Alexander a SOUKUP Ondřej. Modern Language Models and Computation: Theory with Applications. New York: Springer US, 2017. ISBN 978-3-319-63099-1
- mnoho nejnovějších článků, vědeckých zpráv a knih
Osnova přednášek
- Regulované formální modely: úvod a principy.
- Regulace gramatik založená na kontextu a na pravidlech.
- Regulované gramatiky: transformace, normální formy, vymazávání, omezené derivace.
- Rozšíření jazyků generovaných regulovanými gramatikami.
- Regulace gramatik založená na algebraických omezeních.
- Částečně a úplně paralelní regulované gramatiky.
- Regulované gramatické systémy.
- Multigenerativní gramatické systémy.
- Regulované automaty: principy.
- Automaty regulované řídicím jazykem.
- Skákající konečné automaty.
- Hluboké zásobníkové automaty.
- Aplikační perspektivy; shrnutí.
Osnova ostatní - projekty, práce
Dvě tematická práce o regulovaném přepisování.
Kontrolovaná výuka
1. Vypracování dvou referátů během semestru:
-
Každý celkem 20 bodů, z toho 15 písemná část a 5 ústní část (prezentace).
- Téma referátů musí být vztaženo k látce předmětu a schváleno garantem předmětu (prof. Meduna).
- Po prezentaci bude možno stávající verzi referátu vylepšit a znovu odevzdat. Tato verze pak bude hodnocena.
2. Ústní zkouška se skládá ze dvou otázek, každá za 30 bodů.
Zařazení předmětu ve studijních plánech
- Program DIT, libovolný ročník, povinně volitelný skupina T
- Program DIT, libovolný ročník, povinně volitelný skupina T
- Program DIT-EN (anglicky), libovolný ročník, povinně volitelný skupina T
- Program DIT-EN (anglicky), libovolný ročník, povinně volitelný skupina T
- Program VTI-DR-4, obor DVI4, libovolný ročník, volitelný
- Program VTI-DR-4, obor DVI4, libovolný ročník, volitelný
- Program VTI-DR-4 (anglicky), obor DVI4, libovolný ročník, volitelný
- Program VTI-DR-4 (anglicky), obor DVI4, libovolný ročník, volitelný