|
|
|
||
|
Studenti se seznámí se základními pojmy teorie grafů. Probírají se 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 programování, či úlohy celočíselného lineárního programování. Ukazuje 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: Turzík Daniel (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í. Poslední úprava: Turzík Daniel (01.10.2015)
|
|
||
|
Alexander Schrijver: A Course in Combinatorial Optimization Poslední úprava: Turzík Daniel (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. Poslední úprava: Turzík Daniel (01.10.2015)
|
|
||
|
Matematika I. a Matematika II. Poslední úprava: Turzík Daniel (01.10.2015)
|