Teoretické základy informatiky
doc. RNDr. Lucie Ciencialová, Ph.D.
Teoretické základy informatiky

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

  1. Abeceda, slovo,  jazyk
  2. Konečná reprezentace jazyků
  3. Gramatiky
  4. Konečné automaty a regulární jazyky
  5. Zásobníkové automaty
  6. Bezkontextové gramatiky a jazyky
  7. Ú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á:

  1. CIENCIALOVÁ, L., Teoretické základy informatiky. Opava 2014. ISBN: 978 – 80 –7510 – 130 – 3 

Doporučená:

  1. DEMLOVÁ, M. - KOUBEK, V. Algebraická teorie automatů. Praha: SNTL, 1990. 
  2. CHYTIL, M. Automaty a gramatiky. Praha: SNTL, 1984. 
  3. GRUSKA, J. Foundations of Computing. London: International Thomson Computer Press, 1997. 
  4. MOLNÁR, Ľ. - ČEŠKA, M. - MELICHAR, B. Gramatiky a jazyky. Bratislava: Alfa, 1987. 
  5. HOPCROFT, J. E. - ULLMAN, J. D. Teória jazykov a automatov. Bratislava: Alfa, 1987.
Chapter contains:
1
PDF
Previous