|
|
|
||
Last update: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
|
|
||
Last update: 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. |
|
||
Last update: 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)
|
|
||
Last update: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
https://www.emse.fr/~xie/SJTU/Ch4DMC.ppt https://web.ma.utexas.edu/users/gordanz/notes/discrete_martingales.pdf |
|
||
Last update: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
Self-study, consultations |
|
||
Last update: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
The progress of students is checked within regular consultations during the semester. |
|
||
Last update: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
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. |
|
||
Last update: Mareš Jan doc. Ing. Ph.D. (03.10.2018)
none |
|
||
Last update: Kříž Pavel Ing. Mgr. Ph.D. (03.10.2018)
Oral exam |