Předmět Automaty, gramatiky a složitost (IB102)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IB102 - Automaty, gramatiky a složitost, Fakulta informatiky, Masarykova univerzita (MU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Na konci tohoto kurzu bude student schopen:vysvětlit základy teorie formálních jazyků a automatů;vysvětlit základy teorie složitosti;použít tyto teorie v běžné informatické praxi;
Osnova
Motivace: problém specifikace (nekonečných, regulárních) jazyků.Konečné automaty a regulární gramatiky: Pumping lemma, minimalizace konečných automatů, nedeterministické konečné automaty.Vlastnosti regulárních jazyků: uzávěrové vlastnosti, regulární výrazy, Kleeneho věta.Bezkontextové gramatiky a jazyky: transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti.Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám: nedeterministická syntaktická analýza shora dolů a zdola nahoru.Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky, rozhodnutelnost problémů, redukce.Výpočetní složitost algoritmů a problémů.Složitostní třídy: polynomiální redukce, úplnost a težkost problémů, NP-úplné problémy.
Literatura
doporučená literaturaČERNÁ, Ivana , Mojmír KŘETÍNSKÝ a Antonín KUČERA . Formální jazyky a automaty I. Elportál, Brno: Masarykova univerzita, 2006. ISSN 1802-128X. URL infoSIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. infoneurčenoMOLNÁR, L'udovít, Milan ČEŠKA a Bořivoj MELICHAR. Gramatiky a jazyky. 1. vyd. Bratislava: Alfa, 1987. 188 s. infoHOPCROFT, John E. a Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley Publishing Company, 1979. 418 s., ob. ISBN 0-201-02988-X. infoKOZEN, Dexter C. Automata and computability. New York: Springer, 1997. xiii, 400. ISBN 0-387-94907-0. info
Požadavky
( IB000 Mat. základy informatiky || PřF:M1125 Základy matematiky )&&! IB005 FJA
Garant
prof. RNDr. Mojmír Křetínský, CSc.
Vyučující
doc. RNDr. Jan Strejček, Ph.D.RNDr. František BlahoudekRNDr. Petra Budíková, Ph.D.Mgr. Martin JonášBc. Karel KubíčekBc. Henrich LaukoBc. Juraj MajorRNDr. Vojtěch Řehák, Ph.D.Bc. Eva TesařováBc. Martina VitovskáBc. Zuzana DankovčíkováMgr. Bc. Tomáš JaníkMgr. Lukáš MásilkoBc. Vladimír Štill