Detail předmětu

Moderní teoretická informatika

FIT-TIDAk. rok: 2018/2019

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

    Formální jazyky.

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

    Doporučená literatura

    Copy of lectures
    John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Automata Theory, Boston, Addison-Wesley, 2001
    many very recent papers, scientific reports, and books
    Meduna, A.: Automata and Languages. London, Springer, 2000

    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 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 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, volitelný

    Typ (způsob) výuky

     

    Přednáška

    39 hod., nepovinná

    Vyučující / Lektor

    prof. RNDr. Alexandr Meduna, CSc.

    Osnova

    • Ú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í.

    Projekt

    13 hod., povinná

    Vyučující / Lektor

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

    Osnova

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

    Konzultace v kombinovaném studiu

    26 hod., nepovinná

    Vyučující / Lektor

    prof. RNDr. Alexandr Meduna, CSc.