Detail předmětu
Seminář teoretické informatiky
FIT-STIAk. rok: 2018/2019
Výuka probíhá formou demonstračních cvičení s aktivním podílem studentů na řešení konkrétních problémů a příkladů z oblastí teoretické informatiky včetně teorie vyčíslitelnosti a složitosti. Řešené problémy a příklady spadají do témat pokročilé teorie a aplikací regulárních jazyků, bezkontextových jazyky a kontextových jazyků, Turingových strojů, rozhodnutelnosti, redukce rozhodovacích problémů, vyčíslitelných funkcí a základů složitosti. Aplikačními oblastmi jsou modelování systémů, formální analýza a verifikace systémů, překladače, umělá inteligence, lingvistika ap.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Rozšíření a zkvalitnění schopností samostatně formalizovat a řešit informatické i aplikační problémy, vytvářet algoritmy i konstruovat důkazy. Student mj. získává hlubší kompetence k výzkumné práci v různých oblastech informatiky.
Prerekvizity
Způsob a kritéria hodnocení
Učební cíle
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Doporučená literatura
Brookshear, J.G.: Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7
Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997. ISBN 1-85032-243-0
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0-201-44124-1
Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc., 1997. ISBN 0-387-94907-0
Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4
Zařazení předmětu ve studijních plánech
- Program IT-MGR-2 magisterský navazující
obor MMI , 1 ročník, zimní semestr, volitelný
obor MBI , 1 ročník, zimní semestr, volitelný
obor MSK , 1 ročník, zimní semestr, volitelný
obor MMM , 1 ročník, zimní semestr, volitelný
obor MBS , 1 ročník, zimní semestr, volitelný
obor MPV , 1 ročník, zimní semestr, volitelný
obor MIS , 1 ročník, zimní semestr, volitelný
obor MIN , 1 ročník, zimní semestr, volitelný
obor MGM , 1 ročník, zimní semestr, volitelný
Typ (způsob) výuky
Seminář
Vyučující / Lektor
Osnova
- Množiny a relace. Řetězce, jazyky, operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik.
- Regulární jazyky a konečné automaty, determinizace a minimalizace automatů, převod regulárních výrazů na konečné automaty.
- Kleeneho algebra. Pumping lemma, důkaz neregularity jazyků.
- Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik.
- Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků.
- Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky.
- Turingovy stroje.
- Jazyky rekurzívní a rekurzívně vyčíslitelné a jejich vlastnosti.
- Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů.
- Vyčíslitelné funkce. Další Turingovsky úplné výpočetní mechanismy (automaty s více zásobníky, automaty s čítači).
- Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti.
- NP problémy. Polynomiální redukce.
- Aplikace poznatků z teoretické informatiky v překladačích, automatizované verifikaci, lingvistice, ... Přehled různých oblastí rozšiřujících probranou látku (automatizované učení jazyků ze vzorků, stromové jazyky s využitím ve verifikaci nebo např. při manipulaci XML, automaty s omezeními, hierarchie nerozhodnutelných problémů, ...).