Detail předmětu

Teoretická informatika

FIT-TINAk. rok: 2024/2025

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ů

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.

Elearning

eLearning: aktuální otevřený kurz

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

  • Program MITAI magisterský navazující

    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ý
    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ý

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. Tomáš Kocourek
Ing. Ondřej Lengál, Ph.D.
doc. RNDr. Milan Češka, Ph.D.
prof. Ing. Tomáš Vojnar, 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.
Ing. Tomáš Kocourek
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.

Elearning

eLearning: aktuální otevřený kurz