Úvod do teoretické informatiky (01UTI)
last change: 15-04-2024
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 | |
19.2. | Množiny a operace s nimi. Abeceda a jazyk. Operace s formálními jazyky. | |
příklady k procvičení: cv01-FormJazyky.pdf | ||
26.2. | Definice konečného automatu, jazyk rozeznávaný automatem. Užitečná část automatu. | |
příklady k procvičení: cv02-KA.pdf | ||
4.3. | Neprázdnost a nekonečnost jazyka rozeznávaného automatem. Sjednocení, průnik a doplněk rozeznávaných jazyků. Deterministické automaty. | |
příklady k procvičení: cv03-KAII.pdf | ||
11.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 | ||
18.3. | Převod automatu na reg. výraz: BMC algoritmus. Minimalizace konečného automatu. | |
příklady k procvičení: cv05-Minimalizace.old.pdf | ||
25.3. | Minimalizace konečného automatu – dokončení. Rozhodování regularity: Pumping lemma a Myhillova-Nerodeova věta. | |
příklady k procvičení: — | ||
8.4. | Bezkontextové jazyky. | |
příklady k procvičení: cv06-BKG.old.pdf | ||
15.4. | Zásobníkové automaty. Vlastnosti BKJ. | |
příklady k procvičení: cv08-ZA_a_BKJ.pdf |
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.