Název:

Moderní teoretická informatika

Zkratka:TID
Ak.rok:2012/2013
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
VTI-DR-4DVI4-volitelný
Vyučovací jazyk:čeština
Informace veřejné:http://www.fit.vutbr.cz/study/courses/TID/public/
Ukončení:zkouška (ústní)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:3900013
 zkouškatestycvičenílaboratořeostatní
Body:6000040
Garant:Meduna Alexander, prof. RNDr., CSc., UIFS
Přednášející:Meduna Alexander, prof. RNDr., CSc., UIFS
Cvičící:Křivka Zbyněk, Ing., Ph.D., UIFS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav informačních systémů FIT VUT v Brně
Prerekvizity: 
Výstavba překladačů (VYPe), UIFS
 
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.
Anotace:
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.

 

  • 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.
Požadované prerekvizitní znalosti a dovednosti:
formalni jazyky
Získané dovednosti, znalosti a kompetence:
Podrobný přehled o poznatcích současné teoretické informatice a schopnost je využít ve vlastním výzkumu.
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:
  1. 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.
Literatura referenční:
  1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Autotmata Theory, Boston, Addison-Wesley, 2001
  2. mnoho nejnovějších článků, vědeckých zpráv a knih
Literatura studijní:
  1. kopie přednášek
  2. Meduna, A.: Automata and Languages. London, Springer, 2000
  3. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Introduction to Autotmata Theory, Boston, Addison-Wesley, 2001
Kontrolovaná výuka:

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