Detail předmětu

Moderní teoretická informatika

FIT-TIDAk. rok: 2023/2024

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:

  1. Normální formy obecných gramatik.
  2. Regulované gramatiky.
  3. Maticové gramatiky.
  4. Programované přepisovaní.
  5. Gramatiky s nahodilým kontextem.
  6. CD gramatické systémy.
  7. PC gramatické systémy.
  8. L systémy.
  9. Gramatiky s rozptýleným kontextem.
  10. Převodníky.

Jazyk výuky

čeština

Vstupní znalosti

Formální jazyky.

Pravidla hodnocení a ukončení předmětu

1. Vypracování referátu během semestru:

  • Hodnocení až 40 bodů, z toho 30 písemná část a 10 ústní část (prezentace, typicky v angličtině)
  • Téma referátu nejlépe se vztahem k tématu dizertace, ale s využitím vhodného matematického aparátu, nejlépe s blízkou vazbou k teoretické informatice. Téma musí být schváleno garantem předmětu (prof. Meduna).
  • Referát nutno odevzdat alespoň týden před prezentací. Odevzdání se provede elektronicky na email meduna@fit.vut.cz s předmětem "TID-referat". Pozor! Při opožděném odevzdání, dojde ke ztrátě cca 10 bodů za každý den zpoždění.
  • 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ů.

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.
Podrobný přehled o poznatcích současné teoretické informatice a schopnost je využít ve vlastním výzkumu.

Doporučená literatura

Kopie přednášek
MEDUNA Alexander: Automata and Languages. London, Springer, 2000
mnoho nejnovějších článků, vědeckých zpráv a knih

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 DIT-EN doktorský 0 ročník, zimní semestr, povinně volitelný
  • Program DIT-EN doktorský 0 ročník, zimní semestr, povinně volitelný

  • Program IT-DR-1H doktorský

    specializace DRH , 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 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

Osnova

  1. Úvod; zopakování důležitého materiálu.
  2. Řízené formální modely: principy.
  3. Maticové gramatiky.
  4. Programované přepisovaní.
  5. Gramatiky s nahodilým kontextem.
  6. Levé verze řízených gramatik.
  7. Hierarchie jazykových tříd definovaných řízenými gramatikami.
  8. CD gramatické systémy.
  9. PC gramatické systémy.
  10. L systémy.
  11. Semiparalelní formální modelů; multi-gramatiky.
  12. Gramatiky s rozptýleným kontextem.
  13. Nové verze klasických automatů.
  14. 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.