|
|
|
||
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)
|
|
||
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)
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í. |
|
||
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)
Alexander Schrijver: A Course in Combinatorial Optimization |
|
||
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)
1. Základní pojmy teorie grafů. 2. Konvexní množiny polyedry a polytopy. 3. Lineární programování. Dualita. 4. Úloha nejkratší cesty. 5. Stromy. Minimální kostra grafu. 6. Párování a pokrytí v bipartitních grafech. 7. Vážené párování. Polytop párování. 8. Toky v sítích. 9. Maximální tok a algoritmy pro jeho nalezení. 10. Slova, problémy, algoritmy. 11. Výpočetní složitost.Třídy P, NP, co-NP. 12. NP-úplné problémy. Redukce. 13. Matroidy. Příklady a základní vlastnosti. 14. Hladový algoritmus. |
|
||
Last update: Turzík Daniel doc. RNDr. CSc. (01.10.2015)
Matematika I. a Matematika II. |