Přeloženo pomocí DeepL

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 se bude přiměřeně podrobně zabývat všemi základními oblastmi teorie grafů. Téma je vhodné pro všechny studenty i bez teoretického základu, studijní literaturu lze upravit s větším důrazem na praktické aspekty aplikací grafů.

Učební plán:
Základní pojmy, přiřazování a obálky, konektivita, planární grafy, barvení grafů, toky v grafech.

Hlavní studijní materiály:
Reinhard Diestel, Graph Theory, 4. vydání 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, svazek 173, ISBN 978-3-642-14278-9, kapitoly 1-6, 167 stran (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

Teorie grafů pro pokročilé

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

Učební plán:
Zvolte si jeden z níže uvedených směrů:

  • Strukturální teorie grafů - extremální teorie grafů, minory grafů, konektivita, WQO, rozklady stromů.
  • Topologická teorie grafů - vnoření a kresby grafů, rod grafu, kombinatorický popis vnoření grafů, šířka hran a šířka tváří.
  • Teorie řídkosti grafů - mělké minory, hloubka stromu, řídké třídy grafů a jejich charakterizace.

Hlavní studijní materiály (jeden z nich):
Reinhard Diestel, Graph Theory, 4th edition 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: Graphs on Surfaces, 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 se seznámí se základními metodami a technikami v oblasti výpočetní složitosti a dozví se o jejich využití v dalších oblastech informatiky. Jedná se o téma vhodné pro obecné seznámení s výpočetní složitostí.

Sylabus: Učební plán pro studenty, kteří se chtějí naučit složitostní složitosti:
Výpočetní 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. Náhodné algoritmy, interaktivní důkazové systémy. Dolní meze pro specifické výpočetní modely. Komunikační složitost. 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. Kozen, Theory of Computation. Springer, 2006.
B. Barak: An Intensive Introduction to Cryptography (Lecture Notes), výběr kapitol.

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

Téma se zabývá metodami a technikami pro řešení těžkých problémů (a to nejen těch z NP). Studenti si mohou vybrat "klasické" přístupy zahrnující aproximace, randomizované a heuristické techniky a pseudopolynomiální a (rozumné) exponenciální algoritmy. Druhou možností je zaměřit se na v poslední době se rozvíjející parametrizované přístupy, které měří složitost algoritmů a problémů s ohledem na další (obvykle pevně dané) parametry. Probírané techniky lze uplatnit při návrhu konkrétních algoritmů z různých aplikačních oblastí.

Sylabus:
Zvolte si jeden z níže uvedených směrů (případně prodiskutujte s garantem a/nebo potenciálními zkoušejícími jiné možnosti):

  • Klasické algoritmy: Deterministické přístupy (pseudopolynomiální a parametrizované algoritmy, nízkoúrovňové exponenciální algoritmy). Aproximativní techniky (kombinatorický 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í prohledávání, simulované žíhání a další).
  • Parametrizované algoritmy a složitost: Parametrizované problémy a redukce. Dohledatelnost s pevnými parametry, třídy FPT a XP, W[i] hierarchie a W[1]-úplné problémy. Kernelizace. Algoritmické metateorémy.

Hlavní studijní materiály (jeden z nich):
J. Hromkovič, Algoritmika pro těžké problémy. Druhé 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, Parametrizovaná teorie složitosti, 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, Approximation Algorithms. Springer, 2001.
R. Motwani, P. Raghava, Randomized Algorithms. 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. Kandidát 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 nástroji teorie pravděpodobnosti, které se často používají v praxi.

Učební plán:
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, A First Look at Rigorous Probability Theory, World Scientific, 2006. Kapitoly 1-7 (str. 1-82) nebo kapitoly 1-6,8.

Zkoušející: doc. RNDr. Tomáš Brázdil, Ph.D., MBA, prof. RNDr. Daniel Kráľ, Ph.D., DSc., prof. Dr. rer. nat. RNDr. Mgr. Bc. Jan Křetínský, Ph.D., 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.

Sylabus:
Opakující se a přechodné stavy, pravděpodobnost a střední doba návratu, invariantní rozdělení pravděpodobnosti, ergodická věta.

Hlavní studijní materiál:
JR Norris, Markov chains, Cambridge Univ. Press, 1997, kapitoly 1-3 (str. 1-125).

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

Další doporučená literatura:
W. Feller. An Introduction to Probability Theory and Its Applications, Wiley, 1966 (díl I, II).
John G. Kemeny, J. Laurie Snell, Anthony W. Knapp. Denumerable Markov Chains. Springer, 1976.

Logika a teorie konečných modelů

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

Učební plán:
Učitel si vybere jeden z níže uvedených směrů (případně projedná s garantem a/nebo potenciálními zkoušejícími jiné možnosti):

  • Teorie konečných modelů - Ehrenfeucht-Fraïsséovy hry, věty Hanfa a Gaifmana, zachycení tříd 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: Mathematical Logic, 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é zadat pokročilá témata z vybrané oblasti matematiky, pokud jsou tato témata relevantní pro doktorské studium studenta. Mezi oblasti matematiky patří zejména algebra, matematická analýza, teorie čísel a teorie množin a 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.

Učební plán:
Konkrétní oblast matematiky a témata v rámci této oblasti se určují v každém případě individuálně.

Hlavní studijní materiály:
Donald L. Cohn: D. L. Cohn: Measure Theory, Springer, 2013.
Allen Hatcher: Measure Measure: Algebraic Topology, Cambridge University Press, 2002.
Kenneth Ireland, Michael Rosen: A Classical Introduction to Modern Number Theory, Springer, 1990.
Thomas Jech: Jech: Teorie množin, Springer 2003.
James C: Robinson: An Introduction to Functional Analysis, Cambridge University Press, 2020.
Loring T. Wu: An Introduction to Manifolds, Springer, 2011.
Peter Walters: Walters: Ergodic Theory, Springer, 1982.

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