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í.

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.

Doporučená nebo povinná literatura

Č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
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
Č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.
Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4
Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1
Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3. vydání, 2002. ISBN 0-072-32200-4
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
Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014.
Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8

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

Jazyk výuky

čeština

Cíl

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.

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

  • Program IT-MGR-2 magisterský navazující

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

  • Program MITAI magisterský navazující

    specializace NBIO , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NISD , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NISY , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NIDE , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NCPS , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NSEC , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NMAT , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NGRI , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NNET , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NVIZ , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NSEN , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NMAL , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NHPC , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NVER , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NEMB , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NADE , 1. ročník, zimní semestr, 7 kreditů, povinný
    specializace NSPE , 1. ročník, zimní semestr, 7 kreditů, povinný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

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í.]

Cvičení odborného základu

26 hod., povinná

Vyučující / Lektor

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ě.

Projekt

13 hod., povinná

Vyučující / Lektor

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í.

eLearning