Detail předmětu

Moderní teoretická informatika

FIT-TIDAk. rok: 2020/2021

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

    Doporučená nebo povinná literatura

    Kopie přednášek (EN)
    Copy of lectures
    MEDUNA Alexander: Automata and Languages. London, Springer, 2000
    HOPCROFT John E., MOTWANI Rajeev, ULLMAN Jeffrey D. Introduction to Automata Theory, Languages, and Computation (3rd ed.). Pearson, 2013. ISBN 978-1-2920-3905-3
    MEDUNA Alexander a TECHET Jiří. Scattered Context Grammars and their Applications. WIT Press, UK, 2010. ISBN 978-1-84564-426-0 (EN)
    MEDUNA Alexander and TECHET Jiří. Scattered Context Grammars and their Applications. WIT Press, UK, 2010. ISBN 978-1-84564-426-0
    MEDUNA Alexander and ZEMEK Petr. Regulated Grammars and Automata. New York: Springer US, 2014. ISBN 978-1-4939-0368-9
    MEDUNA Alexander a ZEMEK Petr. Regulated Grammars and Automata. New York: Springer US, 2014. ISBN 978-1-4939-0368-9 (EN)
    mnoho nejnovějších článků, vědeckých zpráv a knih (EN)
    many very recent papers, scientific reports, and books

    Jazyk výuky

    čeština, angličtina

    Cíl

    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í dvou referátů během semestru:

    • Každý 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).
    • 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ů.

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

    • Program VTI-DR-4 doktorský

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

    • Program VTI-DR-4 doktorský

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

    Typ (způsob) výuky

     

    Přednáška

    39 hod., nepovinná

    Vyučující / Lektor

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

    Konzultace v kombinovaném studiu

    26 hod., nepovinná

    Vyučující / Lektor

    Projekt

    13 hod., povinná

    Vyučující / Lektor

    Osnova


    • Dvě tematické práce založené na vybraných vědeckých studiích z oblasti teoretické informatiky.

    eLearning