translated by Google

Stránka přeložená strojově pro lepší dosažitelnost obsahu tazateli užívajícími češtinu.

Stránka v původním, anglickém jazyce.

Teoretické základy informatiky

Témata nabízená ke zkoušce

Kromě uvedených témat mohou být s garantem a zkoušejícími projednána a zadána další témata patřící do matematických a teoretických základů informatiky.

Teorie grafů

Grafy jsou jednou z nejčastěji používaných matematických struktur v informatice. Student prostuduje náležitě do hloubky všechny základní oblasti teorie grafů. Téma je vhodné pro všechny studenty i bez teoretického základu a studijní literaturu lze upravit s větším důrazem na praktickou stránku grafových aplikací.

Osnova:
Základní pojmy, párování a pokrytí, konektivita, rovinné grafy, zbarvení grafů, toky v grafech.

Hlavní studijní materiály:
Reinhard Diestel, Teorie grafů , 4. vydání 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9, Chapter 1-6, 167 pages (to zahrnuje i základní oblasti vyučované v magisterských kurzech na FI).

zkoušející: prof. RNDr. Petr Hliněný, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. Mgr. Jan Obdržálek, PhD.

Další doporučená literatura:
Matoušek, J., Nešetřil, J .: Kapitoly z diskrétní matematiky. Karolinum, Praha 2009

Pokročilá teorie grafů

Grafy jsou jednou z nejčastěji používaných matematických struktur v informatice. Toto téma je vhodné pro studenty, kteří již bádají v samotné teorii grafů nebo v teoretických disciplínách úzce spjatých s grafy. Student do hloubky prostuduje vybrané směry teorie grafů, zejména ty související s pokročilými algoritmy a výpočetní složitostí (např. strukturní teorie grafů).

Osnova:
Vyberte si jeden z níže uvedených směrů:

  • Strukturální teorie grafů - extremální teorie grafů, minoritní grafy, konektivita, WQO, stromové rozklady.
  • Topologická teorie grafů - vložení a kreslení grafů, rod grafu, kombinatorický popis vložení grafu, šířka hrany a šířka.
  • Teorie řídkosti grafů - mělké minory, stromová hloubka, řídké třídy grafů a jejich charakterizace.

Hlavní studijní materiály (jeden z):
Reinhard Diestel, Teorie grafů , 4. vydání 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9. Výběr pokročilých kapitol zadaných zkoušejícím.
Bojan Mohar, Carsten Thomassen: Grafy na plochách, Johns Hopkins University Press, 2001, kapitoly 1-4, 5.1, 5.5, 136 stran.
J. Nešetřil a P. Osson de Mendez: Sparsity, Springer, 2012, ISBN 978-3-642-27874-7. Kapitoly 1-7, 170 stran.

zkoušející: prof. RNDr. Petr Hliněný, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. Mgr. Jan Obdržálek, PhD.

Výpočetní složitost

Student si osvojí základní metody a techniky v oblasti výpočetní náročnosti a seznámí se s jejich využitím v dalších oblastech informatiky. Toto je téma vhodné pro obecné seznámení s výpočetní náročností.

Osnova:
Výpočtové modely a výpočetní složitost. Třídy složitosti, těžké a úplné problémy. Metody diagonalizace a separace tříd složitosti. Prostorová složitost. Polynomiální hierarchie a alternace. Logické obvody. Randomizované algoritmy, interaktivní důkazové systémy. Dolní hranice pro konkrétní výpočetní modely. Složitost komunikace. PCP a neaproximovatelnost.

Hlavní studijní materiály:
S. Arora, B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Zkoušející určí výběr kapitol v rozsahu 100-200 stran z učebnice.

zkoušející: prof. RNDr. Ivana Černá, CSc. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. RNDr. Petr Novotný, Ph.D.

Další doporučená literatura:
D. Kožen, Teorie počítání. Springer, 2006.

Algoritmy a složitost pro těžké problémy

Téma pokrývá metody a techniky řešení těžkých problémů (a nejen těch v NP). Studenti si mohou vybrat "klasické" přístupy včetně aproximace, randomizovaných a heuristických technik a pseudopolynomiálních a (rozumných) exponenciálních algoritmů. Druhou možností je zaměřit se na v poslední době rostoucí parametrizované přístupy, které měří složitost algoritmů a problémy s ohledem na dodatečné (obvykle pevné) parametry. Diskutované techniky lze aplikovat při návrhu specifických algoritmů z různých aplikačních oblastí.

Osnova:
Vyberte si jeden z níže uvedených směrů (nebo proberte další možnosti s garantem a/nebo potenciálními zkoušejícími):

  • Klasické algoritmy: Deterministické přístupy (pseudopolynomiální a parametrizované algoritmy, nízkoúrovňové exponenciální algoritmy). Aproximativní techniky (kombinatorní přístup, přístup založený na lineárním a semilineárním programování, náhodný přístup). Náhodné algoritmy (klasifikace, techniky, aplikace v oblasti návrhu datových struktur, grafové algoritmy). Heuristické metody (lokální vyhledávání, simulované žíhání a další).
  • Parametrizované algoritmy a složitost: Parametrizované problémy a redukce. Poddajnost pevných parametrů, třídy FPT a XP, W[i] hierarchie a W[1]-kompletní problémy. Kernelizace. Algoritmické metateorémy.

Hlavní studijní materiály (jeden z):
J. Hromkovič, Algoritmiky pro těžké problémy. 2. vydání. Spinger, 2006. Zkoušející určí výběr kapitol v rozsahu 100-200 stran z učebnice.
J. Flum a M. Grohe, Parameterized Complexity Theory, Springer, 2006. Kapitoly 1-6.1 (str. 1-114), 9.1-9.3 (str. 207-222)
Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015, https://link.springer.com/book/10.1007/978-3-319-21275-3. Kombinace libovolných čtyř kapitol (kromě úvodu), 110 až 150 stran.

zkoušející: prof. RNDr. Ivana Černá, CSc. , prof. RNDr. Petr Hliněný, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , doc. Mgr. Jan Obdržálek, PhD.

Další doporučená literatura:
V. Vazirani, Aproximační algoritmy. Springer, 2001.
R. Motwani, P. Raghava, Randomizované algoritmy. Cambridge University Press, 1995.
R. Downey a M. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.
R. Niedermayer, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

Základy teorie pravděpodobnosti

Obecná teorie pravděpodobnosti je postavena na základech teorie míry a integrálu. Uchazeč se seznámí s obecným způsobem zavedení základních pojmů (pravděpodobnostní prostor, náhodná veličina, střední hodnota atd.) a s vybranými v praxi často využívanými nástroji teorie pravděpodobnosti.

Osnova:
Lebesgueova míra, měřitelná funkce, náhodná veličina; Lebesgueův integrál, střední hodnota; zákon velkých čísel a jeho varianty; Borel-Cantelliho lemma, Kolmogorovův zákon 0-1.

Hlavní studijní materiál:
JS Rosenthal, První pohled na rigorózní teorii pravděpodobnosti, World Scientific, 2000, kapitoly 1-7 (str. 1-67).

zkoušející: doc. RNDr. Tomáš Brázdil, Ph.D. , prof. RNDr. Daniel Kráľ, Ph.D., DSc. , prof. RNDr. Antonín Kučera, Ph.D. , doc. RNDr. Vojtěch Řehák, Ph.D.

Další doporučená literatura:
P. Billingsley. Probability and Measure, Wiley, 1995.

Markovovy řetězce s diskrétním a spojitým časem

Markovovy řetězce jsou základním nástrojem pro modelování a analýzu náhodných procesů v přírodních a technických vědách, včetně informatiky. Uchazeč se seznámí se základy teorie Markovových řetězců s diskrétním a spojitým časem.

Osnova:
Rekurentní a přechodné stavy, pravděpodobnost a střední doba návratu, invariantní rozdělení pravděpodobnosti, Ergodova věta.

Hlavní studijní materiál:
JR Norris, Markovovy řetězce, Cambridge Univ. Press, 1997, kapitoly 1-3 (str. 1-125).

zkoušející: doc. RNDr. Tomáš Brázdil, Ph.D. , prof. RNDr. Antonín Kučera, Ph.D. , doc. RNDr. Vojtěch Řehák, Ph.D.

Další doporučená literatura:
W. Feller. Úvod do teorie pravděpodobnosti a její aplikace, Wiley, 1966 (svazek I, II).
John G. Kemeny, J. Laurie Snell, Anthony W. Knapp. Počitatelné Markovovy řetězy. Springer, 1976.

Logika a teorie konečných modelů

Logika, zejména teorie konečných modelů, se používá na mnoha místech v informatice. Uchazeč se seznámí se základy teorie konečných modelů a jejím vztahem k informatice. Případně se uchazeč může zaměřit na studium základů matematické logiky a jejího vztahu k informatice.

Osnova:
Vyberte si jeden z níže uvedených směrů (nebo proberte další možnosti s garantem a/nebo potenciálními zkoušejícími):

  • Teorie konečných modelů - Ehrenfeucht-Fraïssé hry, Hanfovy a Gaifmanovy teorémy, zachycující třídy složitosti.
  • Matematická logika - syntax, sémantika, úplnost, neúplnost, Löwenheim-Skolem, kompaktnost.

Hlavní studijní materiály:
Ebbinghaus, Flum: Teorie konečných modelů, Springer, 1995 (kapitoly 1-2, 4-6).
Ebbinghaus, Flum, Thomas: Matematická logika, Springer, 1994 (kapitoly 1-7).

zkoušející: Dr. rer. nat. Achim Blumensath , prof. RNDr. Antonín Kučera, Ph.D. , doc. Mgr. Jan Obdržálek, PhD.

Další doporučená literatura:
...

Pokročilá témata z matematiky

Je možné zadávat pokročilá témata z vybrané oblasti matematiky, pokud jsou tato témata relevantní pro doktorandské studium studenta. Mezi oblasti matematiky patří zejména algebra, matematická analýza, teorie čísel a teorie množin. Příklady vhodných studijních materiálů jsou uvedeny níže jako vodítko. Přesný výběr témat bude stanoven případ od případu.

Osnova:
Konkrétní oblast matematiky a témata v této oblasti stanovena v každém případě individuálně.

Hlavní studijní materiály:
Donald L. Cohn: Teorie měření, Springer, 2013.
Allen Hatcher: Algebraická topologie, Cambridge University Press, 2002.
Kenneth Ireland, Michael Rosen: Klasický úvod do moderní teorie čísel, Springer, 1990.
Thomas Jech: Teorie množin, Springer 2003.
James C. Robinson: Úvod do funkční analýzy, Cambridge University Press, 2020.
Loring T. Wu: An Introduction to Manifolds, Springer, 2011.
Peter Walters: Ergodic Theory, Springer, 1982.

zkoušející: prof. RNDr. Daniel Kráľ, Ph.D., DSc. ,