Studenti porozumí základním algoritmům diskrétní optimalizace, jejich složitosti a možnosti aplikací. Naučí se popis kombinatorických úloh pomocí lineárního programování. Dále pochopí základní koncepty pro modelování náhodných procesů s diskrétní množinou stavů a naučí se počítat základní vlastnosti těchto modelů.

Students will understand basic algorithms of discrete optimization, their complexity and applications. They will learn the description of combinatorial tasks using linear programming. Further, students will get familiar with basic concepts for modelling random processes with discrete set of states and will be able to determine/calculate basic properties of these models.

Ústní zkouška

Oral exam

Z: Daniel Turzík: Matematika III - Základy optimalizace, Vydavatelství VŠCHT, 1999. ISBN 80-7080-363-0

Z: Nicolas Privault: Understanding Markov Chains - Examples and Applications (Springer Singapore, 2013)

D: Alexander Schrijver: A Course in Combinatorial Optimization (2017)

A: Alexander Schrijver: A Course in Combinatorial Optimization (2017)

Z: Nicolas Privault: Understanding Markov Chains - Examples and Applications (Springer Singapore, 2013)

Samostudium, konzultace

Self-study, consultations

Kontrola studia se provádí během pravidelných konzultací v průběhu semestru.

The progress of students is checked within regular consultations during the semester.

1. Základní pojmy teorie grafů.

2. Diskrétní náhodná procházka

3. Diskrétní markovské procesy – markovská vlastnost, matice přechodu, limitní rozdělení

4. Diskrétní martingaly – markovský čas, problém optimálního zastavení

5. Lineární programování. Dualita.

6. Základní úlohy kombinatorické optimalizace (úloha nejkratší cesty, minimální kostra grafu, párování a pokrytí v bipartitních grafech, toky v sítích atp.)

7. Slova, problémy, algoritmy.

8. Výpočetní složitost.Třídy P, NP, co-NP. NP-úplné problémy. Redukce.

9. Matroidy. Příklady a základní vlastnosti.

10. Hladový algoritmus.

1. Basic concepts of graph theory.

2. Discrete random walk.

3. Discrete Markov chains – Markov property, transition matrix, limiting distribution.

4. Discrete martingales – stopping time, optional stopping theorem.

5. Linear programming. Duality.

6. Combinatorial optimization problems (The task of the shortest route, Minimum spanning tree, Matching and Covering in Bipartite Charts, Flows in networks etc.)

7. Words, problems, algorithms.

8. Computational complexity. Class P, NP, co-NP. NP-complete problems. Reduction.

9. Matroids. Examples and basic features.

10. Greedy search.

https://www.emse.fr/~xie/SJTU/Ch4DMC.ppt

https://web.ma.utexas.edu/users/gordanz/notes/discrete_martingales.pdf

https://www.emse.fr/~xie/SJTU/Ch4DMC.ppt

https://web.ma.utexas.edu/users/gordanz/notes/discrete_martingales.pdf

nejsou

none