Teoretická informatika

• 39 hod. přednášky
• 26 hod. cvičení
• 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 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.

Předmět seznámí studenty se základními principy, na kterých informatika stojí, a umožní jim chápat, kde leží meze počítání, jaká je cena řešení různých problémů na počítačích a kde jsou tedy meze toho, co lze od řešení problémů na výpočetních zařízeních - minimálně v té podobě, v jaké jsou v současné době chápány - čekat. Předmět studenty dále seznámí, a to výrazně hlouběji než předměty na bakalářském stupni, s řadou konkrétních konceptů, jako jsou různé typy automatů a gramatik, a konkrétních algoritmů nad nimi, které se běžně používají v celé řadě aplikačních oblastí (např. překladače, zpracování textu, analýza síťového provozu, optimalizace hardware i software, modelování a návrh systémů, statická i dynamická analýza a verifikace, umělá inteligence apod.). Hlubší znalosti z této oblasti umožní studentům nejen aplikovat existující algoritmy, ale také je dále rozvíjet a dolaďovat na míru konkrétních řešených problémů, jak je v praxi často zapotřebí. V neposlední řadě pak předmět buduje ve studentech schopnost abstraktního a systematického myšlení, schopnost číst a chápat formální zápisy (a být pak schopen pochopit a v praxi aplikovat průběžně publikované nové výsledky vědy a výzkumu) a také schopnost přesného vyjadřování.

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.

• Č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
• Č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)
• 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
• Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014.
• 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

• 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
• 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

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. Minimalizace konečného automatu, věta o vkládání (Pumping theorem), Nerodova věta, rozhodnutelné problémy regulárních jazyků. 
3. Bezkontextové jazyky a gramatiky, zásobníkové automaty, transformace a normální tvary bezkontextových gramatik. 
4. Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků, deterministické bezkontextové jazyky. 
5. Turingovy stroje (TS), rekurzivně vyčíslitelné a rekurzivní jazyky a problémy.
6. TS s více páskami, nedeterministický TS, univerzální TS. 
7. Vztah vyčíslitelných funkcí a Turingových strojů.
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, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém, nerozhodnutelné problémy teorie formálních jazyků. 
10. Gödelovy věty o neúplnosti.
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.

1. Formální jazyky a operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik. 
2. Regulární jazyky a konečné automaty, determinizace automatů
3. Převod regulárních výrazů na konečné automaty. Minimalizace automatů, Pumping lemma.
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. Turingovy stroje a vyčíslitelné funkce.
9. Jazyky rekurzívní a rekurzívně vyčíslitelné a jejich vlastnosti. 
10. Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů.  
11. Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti. 
12. P a NP problémy. Polynomiální redukce. 

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í a složitosti.

Bodové hodnocení výsledků zkoušky ve 5. týdnu (max 10 bodů), zkoušky ve 10. 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ů).

Písemná zkouška ve 4. týdnu výuky zaměřená na základní i pokročilé znalosti z oblasti regulárních jazyků. Písemná zkouška v 9. týdnu výuky zaměřená na pokročilejší znalosti z 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 5. a 10. týdnu (tj. celkem z 35 bodů).