Základními tématy předmětu jsou abstraktní stroje, formální gramatiky a jazyky, pojem vyčíslitelnosti a složitosti automatů, jazyků a výpočtů. Bude diskutováno chování individuálních objektů i fenoménů a důsledky spolupráce kolektivního chování objektů. Studenti se seznámí s Turingovým strojem, zásobníkovým automatem a konečným automatem, se vztahem strojů a formálních gramatik. Předmětem studia bude také omezení strojového přístupu a generativního přístupu k řešení úloh a související pojem (ne)rozhodnutelnosti.
Osnova
- Abeceda, slovo, jazyk
- Konečná reprezentace jazyků
- Gramatiky
- Konečné automaty a regulární jazyky
- Zásobníkové automaty
- Bezkontextové gramatiky a jazyky
- Úvod do teorie vyčíslitelnosti
Požadavky na studenta
Zkouška probíhá formou písemného testu, který obsahuje jak otázky na teorii tak příklady k vyřešení.
Literatura
Povinná:
- CIENCIALOVÁ, L., Teoretické základy informatiky. Opava 2014. ISBN: 978 – 80 –7510 – 130 – 3
Doporučená:
- DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990.
- CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984.
- GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997.
- MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: Alfa, 1987.
- HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987.