Studijní program P4I1 Teoretická informatika a umělá inteligence

Oborová rada

Aktuální složení rady je na adrese http://mff.cuni.cz/phd/or/p4i1 .

Spolupracující ústavy

– Matematický ústav AV ČR, v.v.i.
Žitná 25, 115 67 Praha 1
http://www.math.cas.cz

– Ústav informatiky AV ČR, v.v.i.
Pod vodárenskou věží 2, 182 07 Praha 8
http://www.cs.cas.cz/

– Ústav teorie informace a automatizace AV ČR, v.v.i.
Pod vodárenskou věží 4/1143, 182 08 Praha 8
http://www.utia.cas.cz/

Vypsaná témata

Jsou k nahlédnutí v SIS na adrese http://mff.cuni.cz/phd/temata/p4i1 .

Poskytovaná výuka

Seznam požadavků ke státní doktorské zkoušce

Státní doktorská zkouška se skládá ze čtyř otázek. Tři otázky dostane student ze tří různých témat, která si po konzultaci se školitelem sám zvolí z následující nabídky. Alespoň jedno zvolené téma musí být z témat 1-5. Čtvrtá otázka je z tématu profilujícího podle dohody se školitelem (může být jedno z ostatních témat).

1. Logika
Výroková a predikátová logika, syntax a sémantika, jejich vztah. Formální dokazovací systémy, formální aritmetika, bezespornost a úplnost, Gödelovy věty. Turingovy stroje. Algoritmicky nerozhodnutelné problémy, nerozhodnutelnost predikátové logiky, nerozhodnutelnost bezesporných rozšíření elementární aritmetiky. Nedefinovatelnost pravdy v aritmetice. Věty o rekurzi.

2. Pravděpodobnost
Náhodné veličiny, nezávislost a podmíněná nezávislost. Zákony velkých čísel a centrální limitní věta. Koncept konvergence v kontextu teorie pravděpodobnosti. Teorie informace pro náhodné veličiny na konečných množinách. Teorie informace pro spojité náhodné veličiny. Bayesovské a pravděpodobnostní grafické modely. Gaussovské procesy. Klasifikace a regrese pomocí umělých neuronových sítí. Klasifikace založená na opěrných vektorech nadrovin. Rozhodovací stromy a náhodné lesy.

3. Teorie složitosti
Modely sekvenčních a paralelních počítačů. Booleovské formule a obvody. Míry složitosti (čas a prostor). Nedeterministické, alternující a interaktivní výpočty. Třídy složitosti, redukce a úplné úlohy, polynomiální hierarchie. Základní pojmy důkazové složitosti. Dolní odhady pro náhodné a explicitní funkce. Randomizované algoritmy a pseudonáhodnost. Komunikační složitost a její aplikace. Základy teoretické kryptografie. Kvantové obvody a algoritmy.

4. Datové struktury
Výpočetní modely (RAM a jeho varianty). Komprese dat. Vyhledávací stromy. Hešování. Pokročilé haldy. Datové struktury pro práci s celými čísly. Datové struktury pro práci s řetězci. Vícerozměrné datové struktury. Struktury pro práci s grafy. Dynamizace a persistence. Práce s paměťovou hierarchií. Data-streamové problémy.

5. Algoritmy
Deterministické, pravděpodobnostní a paralelní algoritmy. Návrh efektivních algoritmů a jejich analýza. Grafové algoritmy. Efektivní algoritmy pro lineární programování a jejich aplikace. Metody pro řešení obtížných úloh: aproximační algoritmy, schémata a heuristické metody. Základní kryptografické protokoly.

6. Umělá inteligence
Reprezentace znalostí, automatické dokazování, rezoluční metoda. Booleovská splnitelnost, splňování omezujících podmínek. Deklarativní programovací jazyky. Prohledávání stavového prostoru, metaheuristiky, jejich příklady a aplikace, lokální prohledávání. Plánování akcí. Práce s neurčitostí, Bayesovské sítě, Markovské rozhodovací problémy. Multiagentní systémy a teorie her.

7. Strojové učení a analýza dat
Teoretické aspekty strojového učení. Typy modelů: penalizovaná složitost, jádrové metody, systémy bazických funkcí. Pravděpodobnostní přístupy. Algoritmy strojového učení. Zpětnovazební učení. Umělé neuronové sítě, jejich učení, aplikace a vlastnosti. Hluboké učení. Metody pro dobývání znalostí. Reprezentace, vyhodnocování a vizualizace získaných znalostí.

8. Přírodou inspirované optimalizační algoritmy
Evoluční algoritmy, reprezentace jedince, genetické operátory, adaptace a sebe-adaptace parametrů, metody pro práci s omezujícími podmínkami. Evoluční strategie. Vícekriteriální evoluční algoritmy. Stromové, lineární a kartézské genetické programování, gramatická evoluce. Aplikace evolučních algoritmů – kombinatorická optimalizace, spojitá optimalizace, neuroevoluce a pravidlové systémy. Koevoluce a meta-evoluce. Optimalizace hejnem částic a koloniemi mravenců a jejich aplikace.

Doporučená literatura

–Nerode A., Shore R. A.: Logic for Applications. 2nd ed., Springer, 1997.

–Pudlák P.: Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction. Springer, 2013.

–Rautenberg W.: A concise introduction to mathematical logic. Springer, 2010.

–Soare, R.I.: Turing Computability, Theory and Applications. Springer, 2016.

–Bhattacharya, R., Waymire, E.C.: A Basic Course in Probability Theory. Springer, 2nd ed., 2016.

–Cover T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, 2nd edition, 2006.

–Holeňa, M., Pulc, P., Kopp, M.: Classification Methods for Internet Applications. Springer, 2020.

–Rasmussen, E., Williams, C.: Gaussian Processes for Machine Learning. MIT Press, 2006.

–Zhou, Z.H.: Machine Learning. Springer, 2021.

–Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Text přístupný na http://theory.cs.princeton.edu/complexity/ .

–Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, Cambridge, 1997.

–Papadimitriou, C. H.: Computational Complexity. Addison–Wesley, Reading, MA, 1994.

–Jukna S.: Boolean Function Complexity: Advances and Frontiers. Springer–Verlag, 2012.

–Navarro, G.: Compact Data Structures: A Practical Approach. Cambridge University Press, 2016.

–Crochemore, M., Hancart, Ch., Lecroq. T.: Algorithms on Strings. Cambridge University Press, 2014.

–Navarro, G., Raffinot. M.: Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, 2002.

–Mehta, D.P., Sahni, S.: Handbook of Data Structures and Applications. Chapman & Hall/CRC Computer and Information Science Series, 2004.

–Chakrabarti, A.: Data Stream Algorithms, Lecture Notes, by Dartmouth College, 2014.

–Cormen et al: Introduction to Algorithms. 3rd ed., MIT press, 2009.

–Kleinberg, J., Tardos, E.: Algorithms Design. Addison–Wesley, Reading, MA, 2005.

–Vazirani, V. V.: Approximation Algorithms. Springer–Verlag, 2001.

–Williamson, D. P., Shmoys, D. B.: The Design of Approximation Algorithms. Cambridge University Press, 2011.

–Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univeristy Press, 2005.

–Russell, S. J., Norvig, P.: Artificial Intelligence: A Modern Approach. 3rd ed., Pearson, 2009.

–Ghallab, M., Nau, D., Traverso, P.: Automated Planning: Theory and Practice. Morgan Kaufmann, 2004.

–Rossi, F., Beek van, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, 2006.

–Dechter, R.: Constraint Processing. Morgan Kaufmann, 2003.

–Aggarwal, C. C.: Data Mining: The Textbook. Springer–Verlag, 2015.

–Aggarwal, C. C.: Neural Networks and Deep Learning: A Textbook. Springer-Verlag, 2018.

–Goodfellow, I., Bengio, Y., Courville, A.: Deep Learning. The MIT Press, 2016.

–Hastie, T., Tibshirani, R., Friedman, J.: The Elements of Statistical Learning. Springer, 2013.

–Marsland, S.: Machine Learning: An Algorithmic Perspective. 2nd ed., Taylor & Francis, 2015.

–Eiben, A. E., Smith, J. E.: Introduction to Evolutionary Computing. 2nd ed., Springer, 2015.

–Michalewicz. Z., Fogel, D.B.: How to Solve It: Modern Heuristics. 2nd ed., Springer, 2004.

–Poli R., Langdon. W.B., McPhee. N.F.: Field Guide to Genetic Programming. Lulu, 2008.

–Yang, X.-S.: Nature-Inspired Optimization Algorithms. Elsevier, 2014.

–Ryan C., O'Neill, M., Collins, J.J. (Eds): Handbook of Grammatical Evolution. Springer, 2018.