Detail předmětu

Moderní teoretická informatika

FIT-TIDAk. rok: 2017/2018

Předmět diskutuje pokročilá témata teoretické informatiky. Zaměřuje se na nejmodernější výzkum v oblasti automatů, formálních jazyků, formálních modelů, vyčíslitelnosti, složitosti a překladu. Detailně jsou objasněny souvislosti mezi teoretickou informatikou a matematikou. Filosofické aspekty informatiky jsou rovněž vyloženy. Získání a porozumnění presentovaných poznatků je ověřeno zpracováním vlastní tvůrčí tématické práce studenta.

Okruhy otázek k SDZ

 

  • Normální formy obecných gramatik
  • Regulované gramatiky.
  • Maticové gramatiky.
  • Programované přepisovaní.
  • Gramatiky s nahodilým kontextem.
  • CD gramatické systémy.
  • PC gramatické systémy.
  • L systémy.
  • Gramatiky s rozptýleným kontextem.
  • Převodníky.

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 a schopnost je využít ve vlastním výzkumu.

Prerekvizity

formalni jazyky

Způsob a kritéria hodnocení

Hodnocení studia je založeno na bodovacím systému. Pro úspěšné absolvování předmětu je nutno dosáhnout 50 bodů.

Osnovy výuky

    Osnova přednášek:
    • Úvod; zopakování důležitého materiálu.
    • Řízené formální modely: principy.
    • Maticové gramatiky.
    • Programované přepisovaní.
    • Gramatiky s nahodilým kontextem.
    • Levé verze řízených gramatik.
    • Hierarchie jazykových tříd definovaných řízenými gramatikami.
    • CD gramatické systémy.
    • PC gramatické systémy.
    • L systémy.
    • Semiparalelní formální modelů; multi-gramatiky.
    • Gramatiky s rozptýleným kontextem.
    • Nové verze klasických automatů.
    • Stávající trendy teoretické informatiky; shrnutí.

    Osnova ostatní - projekty, práce:
    • Tematické práce založená na vybraných vědeckých studií z oblasti teoretické informatiky v problematice řešené v disertační práci studenta.

Učební cíle

Vytvořit podrobný přehled o současné problematice diskutované v teoretické informatice. 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í referátu během semestru:

  • Celkem 40 bodů, z toho 30 písemná část a 10 ústní část (prezentace)
  • Téma referátu musí být vztaženo k látce předmětu a schváleno jak garantem předmětu (Prof. Meduna), tak i školitelem studenta.
  • Referát nutno odevzdat do pondělí v týdnu, kdy bude prezentován. Odevzdání se provede elektronicky na email meduna@fit.vutbr.cz s předmětem "TID-referat". Pozor! Pokud bude referát odevzdán v úterý, automaticky ztráta 5 bodů. Pokud ještě později či vůbec, bude řešeno individuálně.
  • 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ů.

Základní literatura

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Boston, Addison-Wesley, 2001 mnoho nejnovějších článků, vědeckých zpráv a knih

Doporučená literatura

Kopie přednášek Meduna, A.: Automata and Languages. London, Springer, 2000 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Autotmata Theory, Boston, Addison-Wesley, 2001

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

  • Program VTI-DR-4 doktorský

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

  • Program IT-DR-1H doktorský

    obor DRH , 0 ročník, zimní semestr, povinně volitelný