Komise

Státní rigorózní komise

Teoretická informatika

Požadavky ke státní rigorózní zkoušce

Diskrétní matematika
Základy teorie grafů, prohledávání grafů, algoritmy nad grafy, toky v sítích. Lineární algebra a její aplikace pro teorii grafů. Dynamické programování. Kombinatorické principy a jejich aplikace. Kombinatorická teorie pravděpodobnosti.
Algebra, logika, algoritmy
Vybrané algebraické struktury, univerzální algebra, algebraické specifikace programů. Predikátový počet (a jeho speciální případy), syntax a sémantika a jejich vztah. Formální systémy, bezespornost a úplnost, Gödelovy věty. Teorie vyčíslitelnosti, Turingovy stroje a ekvivalentní modely. Algoritmy a jejich složitost, NP-úplné problémy. Algoritmicky nerozhodnutelné problémy, vlastnosti rekurzivně spočetných množin. Věta o rekurzi a její aplikace.
Jazyky a překladače
Formální jazyky a automaty, Chomského hierarchie. Syntaktická analýza, speciálně pro deterministické jazyky. Specifikace sémantiky jazyků. Konstrukce používané v procedurálních jazycích a jejich překlad, Pascal, C++, lexikální, syntaktická a sémantická analýza v překladačích.
Umělá inteligence
Rozhodnutelnost formálních systémů, Herbrandovy modely, unifikace. Automatické dokazování. Strojové učení. Logické programování, Prolog. Funkcionální programování, teorie pevného bodu. Objektově orientované programování. Expertní systémy. Neuronové sítě, základní paradigma, aplikace.

Uchazeč si z těchto čtyř okruhů vybere tři, z nichž bude zkoušen.

Doporučená literatura

[1]Aho A.V., Sethi R., Ullman J. D.: Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading 1986.
[2]Apt K.R.: From Logic Programming to Prolog. Prentice Hall International Series in Computer Science, London, New York, Toronto 1997.
[3]Barendregt H. P.: Functional Programming and Lambda Calculus. Chapter 7, Handbook of Theoretical Computer Science, Elsevier, Amsterdam, New York 1990.
[4]Demuth O., Kryl R., Kučera A.: Teorie algoritmů 1,2. SPN, Praha 1989.
[5]Chytil M.: Automaty a gramatiky. SNTL, Praha 1984.
[6]Mařík V., Štěpánková O., Lažanský J.: Umělá inteligence 1,2. Academia, Praha 1993 (1.díl), 1997 (2.díl).
[7]Matoušek J., Nešetřil J.: Kapitoly z diskrétní matematiky. Matfyzpress, Praha 1996.
[8]Muchnick S. S.: Advanced Compiler Design and Implementation. Morgan Kaufman, Academic Press, Orlando 1997.
[9]Papadimitrou C. H.: Computational complexity. Addison-Wesley, Reading 1994.
[10]Štěpánek P.: Matematická logika. SPN, Praha 1982.