Detail předmětu
Teoretická informatika
Garant předmětu
Jazyk výuky
česky
Zakončení
zápočet+zkouška
Rozsah
- 39 hod. přednášky
- 13 hod. projekty
Zajišťuje ústav
Ústav inteligentních systémů (UITS)
Osnova přednášek
- Úvod, aplikace teorie formálních jazyků, modelovací a rozhodovací síla formálního modelu, operace nad jazyky.
- Regulární jazyky a jejich vlastnosti, Kleenova věta, Nerodova věta, věta o vkládání (Pumping theorem).
- Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu.
- Uzávěrové vlastnosti regulárních jazyků, regulární jazyky jako množinová Booleova algebra, rozhodnutelné problémy regulárních jazyků.
- Bezkontextové jazyky a jejich vlastnosti. Normální tvary bezkontextových gramatik, jednoznačné a deterministické bezkontextové jazyky, věta o vkládání pro bezkontextové jazyky.
- Uzávěrové vlastnosti bezkontextových jazyků, uzavřenost vzhledem k substituci, důsledky, rozhodnutelné problémy bezkontextových jazyků.
- Turingovy stroje (TS), definice TS a jazyka přijímaného TS, rekurzivně vyčíslitelné a rekurzivní jazyky a problémy, TS a funkce, metody konstrukce TS.
- Modifikace TS, TS s obousměrně nekonečnou páskou, s více páskami, nedeterministický TS, stroj se dvěma zásobníky, stroje s čitači.
- TS a jazyky typu 0, diagonalizace, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1.
- Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů.
- Church-Turingova téze, univerzální TS, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém.
- Nerozhodnutelné problémy teorie formálních jazyků.
- Úvod do výpočetní složitosti, Turingovská složitost, třída P a NP problémů.
Zařazení předmětu ve studijních plánech