Úvod do teoretické informatiky (01UTI)

poslední změna: 31-03-2025

Anotace

Základní oblasti teoretické informatiky:
1) Jazyky a automaty – konečné automaty, regulární jazyky a vyhledávání, zásobníkové automaty, bezkontextové jazyky, Turingovy stoje.
2) Složitost algoritmů – algoritmus, výpočetní složitost, třída P, základy NP-úplnosti.

Podrobný sylabus a příklady k procvičení

Pozn. příklady v každém souboru jsou rozdělené na dvě části. První část příkladů jsou základní typy příkladů ověřující vaše pochopení látky dané přednášky. Příklady označené hvězdičkou jsou o něco složitější, předkládané k zamyšlení.
Písemná záverečná zkouška z předmětu bude z 80% tvořena příklady prvního typu, ze 20% příklady druhého typu.

datum náplň předášky
24.2. Množiny a operace s nimi. Abeceda a jazyk. Operace s formálními jazyky.
příklady k procvičení: cv01-FormJazyky.pdf
3.3. Definice konečného automatu, jazyk rozeznávaný automatem. Užitečná část automatu. Neprázdnost a nekonečnost jazyka rozeznávaného automatem.
příklady k procvičení: cv02-KA.pdf
10.3. Sjednocení, průnik a doplněk rozeznávaných jazyků. Deterministické automaty.
příklady k procvičení: cv03-KAII.pdf
17.3. Automaty s ε-přechody. Regulární výrazy. Zřetězení a iterace rozeznávaného jazyka.
příklady k procvičení: cv04-reg_vyrazy.pdf
24.3. Převod automatu na reg. výraz: BMC algoritmus. Minimalizace konečného automatu.
příklady k procvičení: cv05-Minimalizace.old.pdf
31.3. Minimalizace konečného automatu – dokončení. Rozhodování regularity: Pumping lemma a Myhillova-Nerodeova věta.
příklady k procvičení: —

Literatura

  • J.E. Hopcroft, R. Motwani, J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson, 2013.
  • O. Carton. Langages formels, calculabilité et complexité. Vuibert, 2014.
  • M. Sipser. Introduction to the Theory of Computation. Cengage Learning, 2012.