Course detail

Moderní teoretická informatika

FIT-TIDAcad. year: 2021/2022

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.

Language of instruction

čeština

Mode of study

Not applicable.

Guarantor

prof. RNDr. Alexandr Meduna, CSc.

Department

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

Co-requisites

Not applicable.

Planned learning activities and teaching methods

Not applicable.

Assesment methods and criteria linked to learning outcomes

Not applicable.

Course curriculum

Not applicable.

Work placements

Not applicable.

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

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Not applicable.

Recommended reading

MEDUNA Alexander: Automata and Languages. London, Springer, 2000
Kopie přednášek
mnoho nejnovějších článků, vědeckých zpráv a knih
MEDUNA Alexander a ZEMEK Petr. Regulated Grammars and Automata. New York: Springer US, 2014. ISBN 978-1-4939-0368-9
MEDUNA Alexander a TECHET Jiří. Scattered Context Grammars and their Applications. WIT Press, UK, 2010. ISBN 978-1-84564-426-0
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

Classification of course in study plans

  • Programme DIT doktorský 0 year of study, zimní semester, povinně volitelný
  • Programme DIT doktorský 0 year of study, zimní semester, povinně volitelný

  • Programme VTI-DR-4 doktorský

    branch DVI4 , 0 year of study, zimní semester, volitelný

  • Programme VTI-DR-4 doktorský

    branch DVI4 , 0 year of study, zimní semester, volitelný

  • Programme DIT-EN doktorský 0 year of study, zimní semester, povinně volitelný
  • Programme DIT-EN doktorský 0 year of study, zimní semester, povinně volitelný

  • Programme VTI-DR-4 doktorský

    branch DVI4 , 0 year of study, zimní semester, volitelný

  • Programme VTI-DR-4 doktorský

    branch DVI4 , 0 year of study, zimní semester, volitelný

  • Programme IT-DR-1H doktorský

    branch DRH , 0 year of study, zimní semester, volitelný

Type of course unit

 

Přednáška

39 hod., optionally

Teacher / Lecturer

prof. RNDr. Alexandr Meduna, CSc.

Syllabus

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

Projekt

13 hod., compulsory

Teacher / Lecturer

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

Syllabus

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

Konzultace v kombinovaném studiu

26 hod., optionally

Teacher / Lecturer

prof. RNDr. Alexandr Meduna, CSc.