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

Uchazeč si zvolí 4 z povinných témat, a to 2 témata z okruhů 1.– 4. a 2 témata z okruhů 5.– 12. Po dohodě se školitelem bude stanoveno volitelné téma, které může také patřit do jednoho z okruhů 5.– 12.

Zvolené téma musí rozsahově odpovídat jednomu z pokročilých přehledových textů z doporučené literatury k příslušnému okruhu, může ale po dohodě se zkoušejícím být úžeji zaměřeno na hlubší zvládnutí některé z partií v daném okruhu. Téma a studijní literatura (knižní či časopisecká) v takovém případě podléhá schválení oborové rady.

1. Diskrétní matematika
Párování, pakování a pokrytí v grafech. Souvislost grafů. Kreslení na plochy. Barevnost. Toky v grafech. Extremální a Ramseyovská teorie. Hamiltonovské cykly. Náhodné grafy. Strukturální teorie grafů.

2. Logika
Úvod do teorie modelů, algebraické specifikace programů. Výrokový a predikátový počet, syntax a sémantika, jejich vztah. Formální systémy, bezespornost a úplnost, Gödelovy věty.

3. Výpočetní složitost
Základní složitostní třídy. Diagonalizace. Polynomiální hierarchie. Obvody. Náhodnost, derandomizace. Interaktivní protokoly. Dolní meze v různých výpočetních modelech. PCP věta.

4. Návrh a analýza algoritmů
Párování. Toky v sítích. Nejkratší cesty. Kostry. Algoritmy pro matroidy. Algoritmy pro rovinné grafy, aplikace sublineárních řezů.

5. Kombinatorická a spojitá optimalizace
Polyedrální kombinatorika. Lineární programování, dualita. Celočíselné programování. Kombinatorické algoritmy.

6. Kombinatorika a algebraická kombinatorika
Metody lineární algebry, vlastní čísla, aplikace. Grafové polynomy. Symetrie a regularita. Teorie matroidů.

7. Teorie struktur
Kategorie, funktory. Faktorizace struktur. Monády. Topologické a algebraické kategorie. Kategorické aspekty kombinatorických objektů.

8. Pravděpodobnostní metoda
Nekonstruktivní metody v kombinatorice. Střední hodnota a momenty. Lokální lemma. Koncentrační odhady. Náhodné grafy. Geometrické aplikace. Pseudonáhodnost.

9. Topologické metody a diskrétní geometrie
Spravedlivé dělení, Borsuk-Ulamova věta. Aplikace v grafové barevnosti. Vnořování. Konvexní množiny a polytopy. Obálky. Transverzály a epsilon-sítě. Objemy ve velké dimenzi.

10. Kryptografie
Výpočetní složitost a jednosměrné funkce. Aplikace teorie čísel. Pseudonáhodné generátory. Zero Knowledge Proofs. Šifrovací a autentizační schémata.

11. Datové struktury
Fronty. Slovníky. Vícerozměrné struktury. Dynamické struktury. Aplikace.

12. Algoritmická teorie her
Nashova rovnováha. Hry dvou hráčů. Kombinatorické algoritmy. Aplikace v kryptografii a výpočetní složitosti. Kombinatorické aukce.

Doporučená literatura

–Diestel, R.: Graph theory. Springer–Verlag 2010.

–Bollobás, B.: Modern graph theory. Graduate Text in Mathematics 184, Springer–Verlag, New York, 1998.

–Hell, P., Nešetřil, J.: Graphs and homomorphisms. Oxford University Press, Oxford, 2004.

–Abramsky, S., Gabbay, D.:Handbook of Logic in Computer Science. Clarendon Press, Oxford, 1992.

–Shoenfield, J. R.: Mathematical logic. Addison–Wesley, Reading, 1967.

–Arora, S. and Barak, B.: Computational Complexity: A Modern Approach

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

–Garey, M. R., Johnson, D. S.: Computers and Intractability, A guide to the theory of NP–completness. W. H. Freeman, San Francisco, 1979.

–Sipser, M.: Introduction to the Theory of Computation. PWS Publishing Company, Boston, 1997.

–Kozen, D. C.: The Design and Analysis of Algorithms. 1992.

–Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer, 2015.

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

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

–Knuth, Donald E.: Art of Computer Programming, Volumes 1-4A. Addison-Wesley Professional, 2011.

–Cook, W. J., Cunnigham, W. H., Pulleyblank, W. R., Schrijver, A.: Combinatorial optimization. Wiley, New York, 1998.

–Schrijver, A.: Theory of linear and integer programming. Wiley, New York, 1998.

–Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer- Verlag 2003.

–Biggs, N. L.: Algebraic graph theory. Cambridge University Press, Cambridge 1994.

–Oxley, J.: Matroid theory. Oxford University Press, Oxford, 1992.

–Graham, R. L., Spencer, J., Rothschild, B.: Ramsey Theory. Wiley, New York, 1990.

–Nešetřil, J., Ossona de Mendez, P.: Sparsity, Graphs, Structures, and Algorithms.

–Cvetkovic, D. M., Doob, M., Sachs, H.: Spectra of graphs, Theory and applications. J. A. Barth Verlag, Leipzig, 1995.

–Adámek, J., Herrlich, H., Strecker, G. E.: Abstract and Concrete Categories. Wiley, New York, 1990.

–MacLane, S.: Categories for the working mathematician. Graduate Texts in Mathematics 5, Springer–Verlag, New York, 1971.

–Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York, 2000.

–Grimmet, G. R., Stirzaker, D. R.: Probability and random processes: Problems and solutions. Claredon Press, Oxford, 1992.

–Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press, Cambridge, 1995.

–de Longueville, M.: A Course in Topological Combinatorics. Springer 2013.

–Matoušek, J.: Lectures on Discrete Geometry. Springer 2002.

–Kelly, J.: General Topology. Van Nostrand, New York, 1955.

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

–Hatcher, A.: Algebraic Topology. Cambridge University Press 2001.

–Berg de, M., Kreveld van, M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and applications. Springer–Verlag, Berlin, 2000.

–Pach, J., Agarwal, P.: Combinatorial Geometry. Cambridge University Press, Cambridge, 1995.

–O. Goldreich: The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press 2001

–O. Goldreich: The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press 2004

–J. Katz, Y. Lindell: Introduction to Modern Cryptography. Second Edition, CRC Press 2014

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

–K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984.

–Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: Algorithmic Game Theory. Cambridge University Press, 2007.

–J. Conway: On numbers and games. AK Peters/CRC Press, 2000.