Detail předmětu

Teoretická informatika

FIT-TINAk. rok: 2019/2020

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 a Petriho  sítí.

Jazyk výuky

čeština

Počet kreditů

Garant předmětu

prof. RNDr. Milan Češka, CSc.

Zajišťuje ústav

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

Výsledky učení předmětu

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.

Prerekvizity

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.

Způsob a kritéria hodnocení

Bodové hodnocení výsledků zkoušky ve 4. týdnu (max 10 bodů), zkoušky ve 9. týdnu (max 15 bodů), vypracovaných projektů (max. 3-krát 5 bodů) a závěrečné semestrální zkoušky (max 60 bodů).
Podmínky zápočtu:
Celkový zisk minimálně 15 bodů z prvních dvou úkolů a ze zkoušek v 4. a 9. týdnu (tj. celkem z 35 bodů).

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.

Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky

Písemná zkouška ve 4. týdnu výuky zaměřená na základní znalosti z oblasti regulárních a bezkontextových jazyků, písemná zkouška v 9. týdnu výuky zaměřená na pokročilejší znalosti z oblasti regulárních a bezkontextových jazyků a na Turingovy stroje, průběžná kontrola a hodnocení projektů, závěrečná semestrální zkouška. Pro získání bodů ze závěrečné semestrální zkoušky je nutné tuto zkoušku složit tak, aby byla hodnocena nejméně 25 body. V opačném případě bude zkouška hodnocena 0 body.

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., 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 IT-MGR-2 magisterský navazující

    obor MMI , 1 ročník, zimní semestr, povinný
    obor MBI , 1 ročník, zimní semestr, povinný
    obor MSK , 1 ročník, zimní semestr, povinný
    obor MMM , 1 ročník, zimní semestr, povinný
    obor MBS , 1 ročník, zimní semestr, povinný
    obor MPV , 1 ročník, zimní semestr, povinný
    obor MIS , 1 ročník, zimní semestr, povinný
    obor MIN , 1 ročník, zimní semestr, povinný
    obor MGM , 1 ročník, zimní semestr, povinný

  • Program MITAI magisterský navazující

    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 NISD , 1 ročník, zimní semestr, povinný
    specializace NSEC , 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 NNET , 1 ročník, zimní semestr, povinný
    specializace NMAL , 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 NEMB , 1 ročník, zimní semestr, povinný
    specializace NSPE , 1 ročník, zimní semestr, povinný
    specializace NADE , 1 ročník, zimní semestr, povinný
    specializace NMAT , 1 ročník, zimní semestr, povinný
    specializace NISY , 1 ročník, zimní semestr, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

prof. RNDr. Milan Češka, CSc.
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. Bezkontextové jazyky a gramatiky, zásobníkové automaty.
  3. Regulární jazyky jako množinová Booleova algebra, Kleeneho algebra, Kleenova věta, minimalizace konečného automatu.
  4. Věta o vkládání (Pumping theorem), Nerodova věta, rozhodnutelné problémy regulárních jazyků. Transformace a normální tvary bezkontextových gramatik. 
  5. Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků. Deterministické bezkontextové jazyky. 
  6. 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. 
  7. 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 čítači. 
  8. TS a jazyky typu 0, diagonalizace, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1. 
  9. 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ů. 
  10. Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů. 
  11. Úvod do výpočetní složitosti, Turingovská složitost, asymptotická složitost.
  12. Třída P a NP problémů, problémy mimo třídu NP, polynomiální redukce, úplnost.
  13. Úvod do Petriho sití, motivace, definice P/T Petriho sítě, metody analýzy, třídy Petriho sítí.
[Úvodní dvě přednášky opakují a formalizují předpokládané znalosti získané v bakalářském studiu (v předmětu IFJ na FIT VUT), přednášky 3-5 prohlubují znalosti z oblasti regulárních a bezkontextových jazyků, přednášky 6-12 se věnují základním principům a konceptům z oblasti vyčíslitelnosti a složitosti formálních jazyků a problémů, poslední přednáška představuje základní principy v oblasti matematického popisu, modelování a analýzy paralelních a distribuovaných dynamických systémů s využitím Petriho sítí.]

Projekt

13 hod., povinná

Vyučující / Lektor

Ing. Ondřej Lengál, Ph.D.
Lukáš Duránik
doc. Mgr. Adam Rogalewicz, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
prof. Ing. Tomáš Vojnar, Ph.D.
doc. RNDr. Milan Češka, Ph.D.

Osnova

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

Cvičení odborného základu

26 hod., povinná

Vyučující / Lektor

doc. Mgr. Adam Rogalewicz, Ph.D.
Ing. Ondřej Lengál, Ph.D.
doc. Mgr. Lukáš Holík, Ph.D.
doc. RNDr. Milan Češka, Ph.D.
prof. Ing. Tomáš Vojnar, Ph.D.
Lukáš Duránik

Osnova

  1. Množiny a relace. Řetězce, jazyky, operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik. 
  2. Regulární jazyky a konečné automaty, determinizace a minimalizace automatů, převod regulárních výrazů na konečné automaty. 
  3. Kleeneho algebra. Pumping lemma, důkaz neregularity jazyků. 
  4. Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik. 
  5. Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků. 
  6. Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky. 
  7. Turingovy stroje. 
  8. Jazyky rekurzívní a rekurzívně vyčíslitelné a jejich vlastnosti. 
  9. Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů. 
  10. Vyčíslitelné funkce. Další Turingovsky úplné výpočetní mechanismy (automaty s více zásobníky, automaty s čítači). 
  11. Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti. 
  12. NP problémy. Polynomiální redukce. 
  13. Petriho sítě.