Studijní program P4I4 Informatika - teorie, diskrétní modely a optimalizace

Oborová rada

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

Spolupracující ústavy

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

Vypsaná témata

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

Poskytovaná výuka

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

Cílem zkoušky je ověřit širokou přehledovou znalost oboru a s tím související schopnost v případě potřeby dostudovat relevantní partie do hloubky dostatečné pro využití ve výzkumu. Zkouška se skládá ze dvou částí.

K první části uchazeč předloží research statement, tj. stručné shrnutí své stávající výzkumné práce a budoucích výzkumných záměrů (zejména k tématu zadané doktorské disertační práce), a proběhne jeho diskuse.

Ve druhé části jsou kladeny otázky ze tří témat. Dvě z témat musí být ze dvou různých níže uvedených okruhů. Třetí téma je volitelné; může patřit do libovolného z níže uvedených okruhů, ale i do jiných oblastí matematiky a informatiky. Témata jsou typicky úžeji zaměřená na hlubší zvládnutí konkrétní pokročilé partie oboru. Ke každému z témat je po dohodě s uchazečem a jeho školitelem stanoven studijní materiál (knižní či časopisecký), jehož rozsah a obtížnost by měly odpovídat níže uvedeným příkladům.

Diskrétní matematika
Příklady témat a studijních materiálů:

–pravděpodobnostní metoda; kapitoly 6-11 z Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York, 2000.

–topologické metody v kombinatorice; Matoušek, J.: Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Springer 2003.

–teorie grafových minorů; Norin, S.: Graph Minor Theory, lecture notes (2017).

–kombinatorické aplikace toků; kapitoly 1-5 a 8 z Zhang, C.-Q.: Integer flows and cycle covers of graphs. CRC Press, 1997.

Algoritmy a výpočetní složitost
Příklady témat a studijních materiálů:

–výpočetní složitost; kapitoly 2-8 z Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

–parametrizované algoritmy a složitost; kapitoly 1-4 a 13-14 z Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, Ma., Pilipczuk, Mi., Saurabh, S.: Parameterized Algorithms. Springer, 2015.

–aproximační algoritmy; kapitoly 2-8 z Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, 2011.

–výpočetní geometrie; kapitoly 5-11 z Berg de, M., Kreveld van, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and applications. Springer–Verlag, Berlin, 2000.

Optimalizace
Příklady témat a studijních materiálů:

–celočíselné programování; kapitoly 16-22 z Schrijver, A.: Theory of linear and integer programming. Wiley, New York, 1998.

–teorie konvexní optimalizace; kapitoly 3-5 z Boyd, S., Vandenberghe, L..: Convex Optimization. Cambridge University Press, 2004.

–algoritmická teorie her; kapitoly 1,2,3,6,7 z Nisan, N., Roughgarden, T., Tardos, E., Vazirani V.V.: Algorithmic Game Theory. Cambridge University Press, 2007.

–teorie kooperativních her; kapitoly 2-6 z Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational Aspects of Cooperative Game Theory. Springer, 2012.