Detail předmětu

Regulované gramatiky a automaty

FIT-RGDAk. rok: 2021/2022

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:

  1. Regulované automaty a gramatiky: základní idea.
  2. Gramatiky s regulovaným užitím pravidel.
  3. Kontextově založené regulované gramatiky.
  4. Gramatiky s algebraicky založenou regulací.
  5. Redukce regulovaných gramatik.
  6. Paralelní verze regulovaných gramatik.
  7. Regulované konečné automaty.
  8. Regulované zásobníkové automaty.
  9. Hluboké zásobníkové automaty.
  10. Skákající automaty.

Jazyk výuky

čeština

Garant předmětu

prof. RNDr. Alexandr Meduna, CSc.

Zajišťuje ústav

Ústav informačních systémů (UIFS)

Výsledky učení 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.

Prerekvizity

formalni jazyky

Učební cíle

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.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

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ů.

Doporučená literatura

copies of lectures (EN)
kopie přednášek
kopie přednášek (CS)
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
MEDUNA Alexander a ZEMEK Petr. Regulated Grammars and Automata. New York: Springer US, 2014. ISBN 978-1-4939-0368-9
mnoho nejnovějších článků, vědeckých zpráv a knih
ROZENBERG Grzegorz a SALOMAA Arto. Handbook of Formal Languages, Volumes 1-3. Springer, 1997

Zařazení předmětu ve studijních plánech

  • Program DIT doktorský 0 ročník, zimní semestr, povinně volitelný
  • Program DIT doktorský 0 ročník, zimní semestr, povinně volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

  • Program DIT-EN doktorský 0 ročník, zimní semestr, povinně volitelný
  • Program DIT-EN doktorský 0 ročník, zimní semestr, povinně volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.

Osnova

  1. Regulované formální modely: úvod a principy.
  2. Regulace gramatik založená na kontextu a na pravidlech.
  3. Regulované gramatiky: transformace, normální formy, vymazávání, omezené derivace.
  4. Rozšíření jazyků generovaných regulovanými gramatikami.
  5. Regulace gramatik založená na algebraických omezeních.
  6. Částečně a úplně paralelní regulované gramatiky.
  7. Regulované gramatické systémy.
  8. Multigenerativní gramatické systémy.
  9. Regulované automaty: principy.
  10. Automaty regulované řídicím jazykem.
  11. Skákající konečné automaty.
  12. Hluboké zásobníkové automaty.
  13. Aplikační perspektivy; shrnutí.

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Zbyněk Křivka, Ph.D.

Osnova

Dvě tematická práce o regulovaném přepisování.

Konzultace v kombinovaném studiu

26 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Alexandr Meduna, CSc.