Detail předmětu

Teoretická informatika

FIT-TINAk. 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ů a úvod do logiky a výpočetní složitosti.

Jazyk výuky

čeština

Počet kreditů

7

Garant předmětu

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

Zajišťuje ústav

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

Vstupní znalosti

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

Pravidla hodnocení a ukončení předmětu

Bodové hodnocení předmětu se skládá z výsledků testu ve 4. týdnu (max 10 bodů), testu ve 8. týdnu (max 15 bodů), vypracovaných 2 projektů (max. 7 bodů a 8 bodů) a závěrečné semestrální zkoušky (max 60 bodů).

Písemný test ve 4. týdnu výuky je zaměřen na regulární jazyky. Písemný test v 8. týdnu výuky je zaměřený na bezkontextové jazyky, rozhodnutelnost včetně konstrukce Turingových strojů a základy složitosti.

Podmínky pro udělení zápočtu, který je podmínkou pro připuštění k závěrečné semestrální zkoušce: Celkový zisk minimálně 18 bodů z z projektů a z testů v 4. a 8. týdnu (tj. celkem z 40 bodů).

Závěrečné semestrální zkouška má 4 části. Pro získání bodů ze závěrečné zkoušky je nutné mít z každé části alespoň 4 body a celkově získat alespoň 25 bodů. V opačném případě bude zkouška hodnocena 0 body.

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 získává základní kompetence k teoretické výzkumné práci.

Studijní opory

Základní 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
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
Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4

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
Češka, M., Rábová, Z.: Gramatiky a jazyky, Nakl. VUT Brno, 1992. ISBN 80-214-0449-3
Češka, M., Vojnar, T.: Studijní  text k předmětu Teoretická informatika (http://www.fit.vutbr.cz/study/courses/TIN/public/Texty/TIN-studijni-text.pdf), 165 str. (in Czech)
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
Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4
Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014.

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

  • Program MITAI magisterský navazující

    specializace NSEC , 1 ročník, zimní semestr, povinný
    specializace NISY do 2020/21 , 1 ročník, zimní semestr, povinný
    specializace NNET , 1 ročník, zimní semestr, povinný
    specializace NMAL , 1 ročník, zimní semestr, povinný
    specializace NCPS , 1 ročník, zimní semestr, povinný
    specializace NHPC , 1 ročník, zimní semestr, povinný
    specializace NVER , 1 ročník, zimní semestr, povinný
    specializace NIDE , 1 ročník, zimní semestr, povinný
    specializace NISY , 1 ročník, zimní semestr, povinný
    specializace NEMB do 2023/24 , 1 ročník, zimní semestr, povinný
    specializace NSPE , 1 ročník, zimní semestr, povinný
    specializace NEMB , 1 ročník, zimní semestr, povinný
    specializace NBIO , 1 ročník, zimní semestr, povinný
    specializace NSEN , 1 ročník, zimní semestr, povinný
    specializace NVIZ , 1 ročník, zimní semestr, povinný
    specializace NGRI , 1 ročník, zimní semestr, povinný
    specializace NADE , 1 ročník, zimní semestr, povinný
    specializace NISD , 1 ročník, zimní semestr, povinný
    specializace NMAT , 1 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

doc. Mgr. Lukáš Holík, Ph.D.
doc. RNDr. Milan Češka, Ph.D.

Osnova

  1. Úvod do teorie formálních jazyků, způsoby specifikace jazyků, regulární jazyky a gramatiky, konečné automaty, regulární výrazy.
  2. Minimalizace konečného automatu, věta o vkládání (Pumping theorem), Nerodova věta, rozhodnutelné problémy regulárních jazyků. 
  3. Bezkontextové jazyky a gramatiky. Zásobníkové automaty. Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků.
  4. Turingovy stroje (TS), rekurzivně vyčíslitelné a rekurzivní jazyky a problémy. TS a jazyky typu 0, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1. 
  5. Úvod do výpočetní složitosti, Turingovská složitost a asymptotická složitost. Třídy složitosti.
  6. Analýzy složitosti mimo Turingovy stroje, amortizovaná složitost.
  7. Vlastnoti složitostních tříd (P vs NP), polynomiální redukce, problémy mimo NP.
  8. Regex Matching: od regulárních výrazů přes automaty a algoritmy ke složitosti a bezpečnosti.
  9. Church-Turingova téze, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém, nerozhodnutelné problémy teorie formálních jazyků, diagonalizace. 
  10. Logické systémy pro výrokovou a predikátovou logiku.
  11. Gödelovy věty o neúplnosti logických systémů.
  12. Hromadná konzultace

Seminář

12 hod., nepovinná

Vyučující / Lektor

doc. Mgr. Adam Rogalewicz, Ph.D.
Ing. Ondřej Lengál, Ph.D.
doc. RNDr. Milan Češka, Ph.D.

Osnova

  1. Opakování diskrétní matematiky a formální jazyky.
  2. Regulární jazyky.
  3. Bezkontextové jazyk, Turingovy stroje a rozhodnutelnost.
  4. Pokročilá složitost a polynomiální redukce.
  5. Nerozhodnutelnost: použití redukce a diagonalizace.
  6. Neúplnost logických systémů.

Cvičení odborného základu

14 hod., nepovinná

Vyučující / Lektor

Ing. Ondřej Lengál, Ph.D.
doc. Mgr. Adam Rogalewicz, Ph.D.
doc. RNDr. Milan Češka, Ph.D.

Osnova

  1. Regulární jazyky.
  2. Úvod do bezkontextových jazyků.
  3. Bezkontextové jazyk, Turingovy stroje a rozhodnutelnost.
  4. Asymptotická a amortizovaná analýza složitosti.
  5. Pokročilá složitost a polynomiální redukce.
  6. Nerozhodnutelnost: použití redukce.
  7. Logické systémy.

Projekt

13 hod., povinná

Vyučující / Lektor

doc. Mgr. Adam Rogalewicz, Ph.D.
Ing. Ondřej Lengál, Ph.D.

Osnova

  1. Řešení problému z oblasti regulárních a bezkontextových jazyků. 
  2. Řešení problému z oblasti bezkontextových jazyků, Turingových strojů a teorie nerozhodnutelnosti. 
  3. Řešení problému z oblasti nerozhodnutelnosti a složitosti.