|
|
|
||
Poslední úprava: Pátková Vlasta (16.11.2018)
|
|
||
Poslední úprava: Pátková Vlasta (16.11.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: Pátková Vlasta (16.11.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: Pátková Vlasta (16.11.2018)
https://www.emse.fr/~xie/SJTU/Ch4DMC.ppt https://web.ma.utexas.edu/users/gordanz/notes/discrete_martingales.pdf |
|
||
Poslední úprava: Pátková Vlasta (16.11.2018)
Samostudium, konzultace |
|
||
Poslední úprava: Pátková Vlasta (16.11.2018)
Kontrola studia se provádí během pravidelných konzultací v průběhu semestru. |
|
||
Poslední úprava: Pátková Vlasta (16.11.2018)
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.
|
|
||
Poslední úprava: Pátková Vlasta (16.11.2018)
nejsou |
|
||
Poslední úprava: Pátková Vlasta (16.11.2018)
Ústní zkouška |