I 1 Teoretická informatika

Předseda	doc. RNDr. Iveta Mrázová, CSc.	KTIML MFF UK	schváleno ve vědecké radě dne 5.12.2012
Experti MŠ	prof. RNDr. Pavel Pudlák, DrSc.	Matematický ústav AV ČR, v.v.i.
	prof. RNDr. Jiří Wiedermann, DrSc.	Ústav informatiky AV ČR, v.v.i.
Členové	doc. RNDr. Ondřej Čepek, Ph.D.	KTIML MFF UK
	RNDr. Jan Hric	KTIML MFF UK
	doc. RNDr. Antonín Kučera, CSc.	KTIML MFF UK
	RNDr. Petr Kučera, Ph.D.	KTIML MFF UK	schváleno ve vědecké radě dne 5.12.2012
	doc. RNDr. Josef Mlček, CSc.	KTIML MFF UK	schváleno ve vědecké radě dne 5.12.2012

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

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