Detail předmětu
Teoretická informatika
FIT-TINAk. rok: 2018/2019
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í.
Garant předmětu
Zajišťuje ústav
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 je schopen aplikovat získané znalosti při řešení teoretických i praktických problémů modelování, programování, formální specifikace, automatizace návrhu, verifikace a umělé inteligence.
Student získává základní kompetence k teoretické výzkumné práci.
Prerekvizity
Základní znalosti z binárních relací, 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
- 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
- Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8
- Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8
- Č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
- 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, 2nd ed., 2000. ISBN 0-201-44124-1
- Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4
Způsob a kritéria hodnocení
Bodové hodnocení
výsledků zkoušky ve 3. 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 3. a 9. týdnu (tj. celkem z 35
bodů).
Jazyk výuky
čeština
Osnovy výuky
- Osnova přednášek:
- Ú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í.
- Ř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í.
Osnova ostatní - projekty, práce:
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 3. 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, 5 kreditů, povinný
obor MBI , 1. ročník, zimní semestr, 5 kreditů, povinný
obor MIS , 1. ročník, zimní semestr, 5 kreditů, povinný
obor MIN , 1. ročník, zimní semestr, 5 kreditů, povinný
obor MMI , 1. ročník, zimní semestr, 5 kreditů, povinný
obor MMM , 1. ročník, zimní semestr, 5 kreditů, povinný
obor MGM , 1. ročník, zimní semestr, 5 kreditů, povinný
obor MPV , 1. ročník, zimní semestr, 5 kreditů, povinný
obor MSK , 1. ročník, zimní semestr, 5 kreditů, povinný
Typ (způsob) výuky
Přednáška
39 hod., nepovinná
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í.
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
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í.