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