Teoretická informatika

• 39 hod. přednášky
• 13 hod. projekty

• 60 bodů závěrečná zkouška (písemná část)
• 25 bodů půlsemestrální test (písemná část)
• 15 bodů projekty

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.

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.

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.

• 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
• Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8
• Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 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

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

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

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

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.

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