Detail předmětu

Moderní teoretická informatika

TID Ak. rok 2020/2021 zimní semestr

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.

Garant předmětu

Zástupce garanta předmětu

Jazyk výuky

český

Zakončení

zkouška (ústní)

Rozsah

39 hod. přednášky, 13 hod. projekty

Bodové hodnocení

60 zkouška, 40 projekty

Zajišťuje ústav

Přednášející

Cvičící

Stránky předmětu

Získané dovednosti, znalosti a kompetence z předmětu

Podrobný přehled o poznatcích současné teoretické informatice a schopnost je využít ve vlastním výzkumu.

Cíle předmětu

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.

Prerekvizity

Požadované prerekvizitní znalosti a dovednosti

Formální jazyky.

Literatura studijní

  • Kopie přednášek
  • 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 ZEMEK Petr. Regulated Grammars and Automata. New York: Springer US, 2014. ISBN 978-1-4939-0368-9

Literatura referenční

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

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

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

Kontrolovaná výuka

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

Rozvrh

DenTypTýdnyMístn.OdDoPSKSkupInfo
Útpřednáškavýuky A112 11:0013:50 1DVI xx

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

  • Program VTI-DR-4, obor DVI4, libovolný ročník, volitelný
Nahoru