Faculty of Information Technology
esk verze
Skip main menu
Skip to body
You are in section
Faculty
Study
Courses
Studijní materiály 2019
Prezentace z přednášek 2019/2020 (jsou členěny dle témat, ne přímo dle dnů přednášek):
Formální jazyky obecně a úvod do regulárních jazyků
Úvod do bezkontextových jazyků a zásobníkových automatů
Převody regulárních výrazů a minimalizace konečných automatů
Vlastnosti regulárních jazyků
Transformace a normální formy bezkontextových gramatik
Vlastnosti bezkontextových jazyků a deterministické zásobníkové automaty
Turingovy stroje
Kontextové, rekurzívní a rekurzívně vyčíslitelné jazyky
Jazyky mimo třídu 0, univerzální TS, problém zastavení a redukce
Postův korespondenční problém, Riceova věta a alternativy k TS
Vyčíslitelné funkce a jejich vztah k Turingovým strojům
Složitost: časová a prostorová složitost, asymptotické odhady a třídy složitosti
Úvod do Petriho sítí