Okruh Teoretické základy informatiky

Podokruhy:

Teorie grafů

Anotace:
Grafy jsou jednou z nejpoužívanějších matematických struktur v informatice. Uchazeč si do hloubky prostuduje všechny základní oblasti teorie grafů. Téma je vhodné pro všechny studenty i bez teoretického zaměření.

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

Základní studijní materiál:
Reinhard Diestel, Graph Theory, 4th edition 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9, kapitoly 1-6, 167 stran (zahrnuje i základní pasáže probírané v rámci magisterského studia).

Zkoušející: prof. Petr Hliněný, dr. Jan Obdržálek

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

Topologická teorie grafů

Anotace:
Topologická teorie grafů (stručně řečeno "kreslení grafů") se vyvinula ze snahy vyřešit problém čtyř barev do poměrně rozsáhlé disciplíny a později se ukázala jako nesmírně důležitá v oblasti grafových minorů a odvozených algoritmů.
Toto specializované téma pokrývá přehled základních poznatků a technik práce v topologických grafech podle skutečně skvělé monografie Mohara a Thomassena. Mimo jiné také ukazuje, jak teorie grafů poskytuje nový a přístupnější pohled na klasické topologické poznatky typu Jordanovy věty nebo klasifikace ploch.

Osnova:
Základy rovinné topologie, Jordanova věta, rovinné grafy, Kuratowského věta, základní klasifikace ploch, kreslení grafů na plochách, genus grafu, kombinatorický popis nakreslení grafu, edge-width a face-width

Základní studijní materiál:
Bojan Mohar, Carsten Thomassen: Graphs on Surfaces, Johns Hopkins University Press, 2001 kapitoly 1-4, 5.1, 5.5, 136 stran

Zkoušející: prof. Petr Hliněný

Další doporučená literatura:
Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky. Karolinum, Praha 2009
Reinhard Diestel: Graph Theory, Springer-Verlag, 2010

Strukturální teorie grafů

Anotace:
Strukturální teorie grafů poskytuje hluboké matematické poznatky s přímou aplikací v mnoha nových sofistikovaných algoritmech (příkladem budiž stromové dekompozice nebo Graph Minors Theorem). Tento speciální podokruh umožní nahlédnout do hlubin strukturální teorie grafů v podání známé Diestelovy monografie a ukázat přehled nejdůležitějších výsledků i důkazových technik.
Alternativně: Zaměření na novou teorii "Sparsity" Nešetřila a Ossony de Mendez, mělké minory, hloubku grafů a charakterizace řídkých tříd grafů.

Osnova:
Souvislost grafů (vícenásobná), extremální teorie grafů, minory, Hadwigerova hypotéza, stromové dekompozice, zakázané minory, dobré kvaziuspořádání.
Alternativně: mělké minory (shallow minors), stromová hloubka, řídké třídy grafů a jejich charakterizace.

Základní studijní materiál:
Reinhard Diestel, Graph Theory, 4th edition 2010, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, ISBN 978-3-642-14278-9, kapitoly 1,3,7,12, 136 stran.
Alternativně: J. Nešetřil and P. Ossona de Mendez, Sparsity, Springer, 2012, ISBN 978-3-642-27874-7. Kapitoly 1-7, 170 stran.

Zkoušející: prof. Petr Hliněný, dr. Jan Obdržálek

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

Parametrizovaná složitost

Anotace:
Parametrizovaná složitost se zabývá studiem a klasifikací výpočetních problémů dle jejich "obtížnosti" v závislosti na více než jednom parametru vstupu. Složitost problému je pak vyjádřena jako funkce těchto parametrů. Tento přístup umožňuje například jemněji klasifikovat NP-těžké problémy v závislosti na jejich "skutečné" složitosti.

Osnova:
Parametrizované problémy, fixed-parameter tractability, třídy FPT a XP, W[i] hierarchie a W[1]-úplné problémy, kernelizace.

Základní studijní materiál:
J. Flum and M. Grohe, Parameterized Complexity Theory, Springer, 2006.
Kapitoly 1-6.1 (str.1-114), 9.1-9.3 (str. 207-222)

Zkoušející: prof. Petr Hliněný, Dr. Jan Obdržálek

Další doporučená literatura:
R. Downey and M. Fellows, Parameterized Complexity, Springer, 1999.
R. Downey and M. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.
R. Niedermayer, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

Fundamenty teorie pravděpodobnosti

Anotace:
Obecná teorie pravděpodobnosti je budována 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á proměnná, střední hodnota, apod.) a s vybranými nástroji teorie pravděpodobnosti, které se v praxi často používají.

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

Základní studijní materiál:
J.S. Rosenthal, A First Look at Rigorous Probability Theory, World Scientific, 2000, kapitoly 1-7 (str. 1-67).

Zkoušející: doc. Tomáš Brázdil, prof. Antonín Kučera

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

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

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

Osnova:
Rekurentní a tranzientní stavy, pravděpodobnost a střední doba návratu, invariantní pravděpodobnostní rozložení, Ergodická věta.

Základní studijní materiál:
J.R. Norris, Markov chains, Cambridge Univ. Press, 1997, kapitoly 1-3 (str. 1-125).

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

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

Výpočetní složitost

Anotace:
Student se seznámí se základními metodami a technikami z oblasti výpočetní složitosti a možnostmi jejich využití v dalších oblastech informatiky.

Osnova:
Výpočetní modely a výpočetní složitost, Složitostní třídy a jejich těžké a úplné problémy. Metoda diagonalizace a separace složitostech tříd. Prostorová složitost. Polynomiální hierarchia a alternování. Logické obvody. Náhodnostní výpočty, Interaktivní důkazové systémy. Dolní odhady pro konkrétní výpočetní modely. Komunikační složitost. PCP a neaproximovatelnost.

Základní studijní materiál:
Zkoušející stanoví výběr kapitol v rozsahu 100-200 stran z učebního textu S. Arora, B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009

Zkoušející: prof. Ivana Černá

Další doporučená literatura:
D. Kozen, Theory of Computation. Springer, 2006.

Algoritmika pro těžké problémy

Anotace:
tudent se seznámí se metodami a technikami pro řešení (nejen NP) těžkých problémů, Probírané techniky jsou aplikovány při návrhu konkrétních algoritmů z různých aplikačních oblastí.

Osnova:
Deterministické přístupy (pseudopolynomiální a parametrizované algoritmy, exponenciální algoritmy nízkého stupně). Aproximativní techniky (kombinatorický přístup, přístup založený na lineárním a semilineárním programování, náhodnostní přístup). Náhodnostní 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ší).

Základní studijní materiál:
Zkoušející stanoví výběr kapitol v rozsahu 100-200 stran z učebního textu J. Hromkovič, Algorithmics for Hard Problems. 2nd Edition. Spinger, 2006.

Zkoušející: prof. Ivana Černá

Další doporučená literatura:
V. Vazirani, Approximation Algorithms. Springer, 2001.
R. Motwani, P. Raghava, Randomized Algorithms. Cambridge University Press, 1995.