Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
Studenti se seznámí se základními pojmy a koncepty teorie grafů a diskrétních náhodných procesů (náhodná procházka, markovský proces, martingal). Studují se základní vlastnosti těchto procesů, zejména jejich dynamika a limitní chování (limitní rozdělení a jeho výpočet). Dále se probírají základní úlohy kombinatorické optimalizace jako úloha nejkratší cesty, úlohy o párování, barvení grafu apod. Mnohé úlohy jsou formulovány jako úlohy lineárního či celočíselného programování. Ukazuje se význam duality pro řešení těchto úloh. Dále se probírá výpočetní složitost vyšetřovaných úloh. Zkoumá se vztah polynomiálně a nedeterministicky polynomiálně řešitelných úloh.
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
Students will learn basic concepts of graph theory and discrete random processes (random walk, Markov chains, martingales). Fundamental properties (especially dynamics and limiting behaviour) of such processes are studied. The basic combinatorial optimization tasks (the shortest path, matching, coloring, etc.) are discussed. Many tasks are formulated as linear programming problems or integer linear programming problems. The importance of duality to solve these problems is shown. Further, the computational complexity of the investigated tasks is discussed. The relation of polynomially and non-deterministically polynomially solved problems is investigated.
Výstupy studia předmětu -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
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ů.
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
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.
Literatura -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (12.10.2018)
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)
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (12.10.2018)
A: Alexander Schrijver: A Course in Combinatorial Optimization (2017)
Z: Nicolas Privault: Understanding Markov Chains - Examples and Applications (Springer Singapore, 2013)
Studijní opory -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
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.)
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.
Studijní prerekvizity -
Poslední úprava: Mareš Jan doc. Ing. Ph.D. (03.10.2018)
nejsou
Poslední úprava: Mareš Jan doc. Ing. Ph.D. (03.10.2018)
none
Podmínky zakončení předmětu -
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
Ústní zkouška
Poslední úprava: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)