Úvod do teoretické informatiky (01UTI/01UTIZ)

poslední změna: 02-05-2018

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é vykřičníkem 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
21.2. Množiny a operace s nimi. Abeceda a jazyk. Operace s formálními jazyky.
Příklady k procvičení: cv1.pdf
28.2. Definice konečného automatu, jazyk rozeznávaný automatem. Neprázdnost a nekonečnost jazyka rozeznávaného automatem.
Příklady k procvičení: cv2.pdf
7.3. Sjednocení, průnik a doplněk rozeznávaných jazyků. Nedeterministické automaty.
Příklady k procvičení: cv3.pdf
14.3. Regulární výrazy. Zřetězení a iterace regulárních jazyků. Kleenova věta. Převod regulárního výrazu na automat.
Příklady k procvičení: cv4.pdf
21.3. MNY algoritmus, minimalizace konečného automatu.
Příklady k procvičení: cv5.pdf
28.3. Rozhodování regularity jazyka (Pumping lemma, Věta Myhill–Nerode).
Příklady k procvičení: v souboru cv5.pdf z minulého týdne
4.4. Bezkontextové jazyky a zásobníkové automaty.
Příklady k procvičení: cv6.pdf
11.4. Matematické základy složitosti. Asymptotické značení funkcí, rekurentní vztahy.
Příklady k procvičení: cv7.pdf
18.4. Kódování slov a problémů. Formalizace pojmu algoritmus. Turingův stroj.
Příklady k procvičení: cv8.pdf
25.4.
2.5. Problém zastavení TS. RAM model počítače. Výpočetní složitost algoritmů a problémů.
Příklady k procvičení: cv9.pdf
9.5. Třída P a polynomiální redukce. Základy NP-úplnosti.

Literatura

  • J. Mareš. Jazyky, gramatiky a automaty. Skriptum ČVUT, 2011.
  • V. Majerech. Úvod do složitosti a NP-úplnosti. link
  • O. Carton. Langages formels, calculabilité et complexité. Vuibert, 1993.