Detail předmětu

Teoretická informatika (v angličtině)

FIT-TINeAk. rok: 2025/2026

Aplikace teorie formálních jazyků v informatice a informačních technologiích (překladače, modelování a analýza systémů, lingvistika, biologie atd.), modelovací a rozhodovací síla formálního modelu, regulární jazyky a jejich vlastnosti, minimalizace konečného automatu, bezkontextové jazyky a jejich vlastnosti, Turingovy stroje, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, vyčíslitelné funkce, nerozhodnutelnost, nerozhodnutelné problémy teorie formálních jazyků, úvod do výpočetní složitosti.

Jazyk výuky

angličtina

Počet kreditů

Garant předmětu

doc. RNDr. Milan Češka, Ph.D.

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

Nabízen zahraničním studentům

Všech fakult

Vstupní znalosti

Základní znalosti z binárních relací, teorie grafů a formálních jazyků včetně konečných a zásobníkových automatů a pojmů algoritmické složitosti.

Způsob zakončení předmětu a pravidla hodnocení studentů

Bodové hodnocení výsledků půlsemestrální zkoušky (max 20 bodů) a vypracovaných projektů (max. 20 bodů).
Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů.

Učební cíle

Rozšíření znalostí teorie formálních jazyků a osvojení základů teorie vyčíslitelnosti a základních pojmů výpočetní složitosti.
Znalosti základních a pokročilejších pojmů, přístupů a výsledků teorie automatů a teorie vyčíslitelnosti a základů teorie výpočetní složitosti, vedoucí k hlubšímu pochopení povahy popisu a realizace výpočetních procesů. Student je schopen aplikovat získané znalosti při řešení teoretických i praktických problémů modelování, programování, formální specifikace, automatizace návrhu, verifikace a umělé inteligence.
Student získává základní kompetence k teoretické výzkumné práci.

Prerekvizity a korekvizity

povinná prerekvizita
Formální jazyky a překladače

Základní literatura

Brookshear, J.G. : Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7 (EN)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0-201-44124-1 (EN)
Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0. (EN)
Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4. (EN)

Doporučená literatura

Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8
Brookshear, J.G. : Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7
Češka, M. a kol.: Vyčíslitelnost a složitost, Nakl. VUT Brno, 1993. ISBN 80-214-0441-8 (CS)
Kozen, D.C.: Automata and Computability, Springer-Verlag, New York, Inc, 1997. ISBN 0-387-94907-0 (EN)
Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4 (EN)
Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014. (EN)

Elearning

eLearning: aktuální otevřený kurz

Zařazení předmětu ve studijních plánech

Program IT-MGR-1H magisterský navazující
specializace MGH , 0 ročník, letní semestr, doporučený kurs
Program MIT-EN magisterský navazující 1 ročník, letní semestr, povinný, základní teoretický předmět profilujícího základu

Typ (způsob) výuky

Přednáška

39 hod., nepovinná

Vyučující / Lektor

doc. RNDr. Milan Češka, Ph.D.
Ing. Filip Macák

Osnova

Ú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ů.

Projekt

13 hod., povinná

Vyučující / Lektor

doc. RNDr. Milan Češka, Ph.D.

Osnova