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
Počet kreditů
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Student získává základní kompetence k teoretické výzkumné práci.
Prerekvizity
Způsob a kritéria hodnocení
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
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Doporučená 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
Č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
Vyučující / Lektor
Osnova
- Úvod do teorie formálních jazyků, způsoby specifikace jazyků, regulární jazyky a gramatiky, konečné automaty, regulární výrazy.
- Bezkontextové jazyky a gramatiky, zásobníkové automaty.
- Regulární jazyky jako množinová Booleova algebra, Kleeneho algebra, Kleenova věta, minimalizace konečného automatu.
- 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.
- Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků. Deterministické bezkontextové jazyky.
- 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 čítač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.
- 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ů.
- Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů.
- Úvod do výpočetní složitosti, Turingovská složitost, asymptotická složitost.
- Třída P a NP problémů, problémy mimo třídu NP, polynomiální redukce, úplnost.
- Úvod do Petriho sití, motivace, definice P/T Petriho sítě, metody analýzy, třídy Petriho sítí.
Projekt
Vyučující / Lektor
Osnova
- Řešení problému z oblasti regulárních a bezkontextových jazyků.
- Řešení problému z oblasti Turingových strojů a teorie nerozhodnutelnosti.
- Řešení problému z oblasti vyčíslitelných funkcí, složitosti a Petriho sítí.
Cvičení odborného základu
Vyučující / Lektor
Osnova
- Množiny a relace. Řetězce, jazyky, operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik.
- Regulární jazyky a konečné automaty, determinizace a minimalizace automatů, převod regulárních výrazů na konečné automaty.
- Kleeneho algebra. Pumping lemma, důkaz neregularity jazyků.
- Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik.
- Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků.
- Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky.
- Turingovy stroje.
- Jazyky rekurzívní a rekurzívně vyčíslitelné a jejich vlastnosti.
- Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů.
- Vyčíslitelné funkce. Další Turingovsky úplné výpočetní mechanismy (automaty s více zásobníky, automaty s čítači).
- Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti.
- NP problémy. Polynomiální redukce.
- Petriho sítě.