Teoretická informatika

• 39 hod. přednášky
• 12 hod. seminář
• 14 hod. cvičení
• 20 hod. projekty

• 70 bodů závěrečná zkouška (písemná část)
• 30 bodů půlsemestrální test (písemná část)

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.

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.

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

• Rozpis cvičení a seminářů + výukové materiály
• E-learning VUT (diskuzní fóra a domácí úlohy)

Bodové hodnocení předmětu se skládá z výsledků testu ve 4. týdnu (max 10 bodů), testu ve 8. týdnu (max 20 bodů) a závěrečné semestrální zkoušky (max 70 bodů).

Písemný test ve 4. týdnu výuky je zaměřen na regulární jazyky. Písemný test v 8. týdnu výuky je zaměřený na bezkontextové jazyky, rozhodnutelnost včetně konstrukce Turingových strojů a základy složitosti.

Podmínky pro udělení zápočtu, který je podmínkou pro připuštění k závěrečné semestrální zkoušce: Celkový zisk minimálně 15 bodů  z testů v 4. a 8. týdnu (tj. celkem z 30 bodů).

Závěrečné semestrální zkouška má 4 části. Pro získání bodů ze závěrečné zkoušky je nutné mít z každé části alespoň 4 body a celkově získat alespoň 30 bodů. V opačném případě bude zkouška hodnocena 0 body.