PředmětyPředměty(verze: 853)
Předmět, akademický rok 2019/2020
  
Diskrétní optimalizace - D413004
Anglický název: Discrete Optimalization
Zajišťuje: Ústav matematiky (413)
Platnost: od 2011
Semestr: zimní
Body: zimní s.:0
E-Kredity: zimní s.:0
Způsob provedení zkoušky: zimní s.:
Rozsah, examinace: zimní s.:0/0 Jiné [hodiny/týden]
Počet míst: neurčen / neurčen (neurčen)
Minimální obsazenost: neomezen
Jazyk výuky: čeština
Způsob výuky: prezenční
Úroveň:  
Pro druh:  
Poznámka: předmět je určen pouze pro doktorandy
student může plnit i v dalších letech
Garant: Turzík Daniel doc. RNDr. CSc.
Je záměnnost pro: AP413004, P413004
Anotace
Poslední úprava: Turzík Daniel doc. RNDr. CSc. (01.10.2015)
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.
Výstupy studia předmětu
Poslední úprava: 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í.

Literatura
Poslední úprava: Turzík Daniel doc. RNDr. CSc. (01.10.2015)

Alexander Schrijver: A Course in Combinatorial Optimization

Sylabus
Poslední úprava: 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.

Studijní prerekvizity
Poslední úprava: Turzík Daniel doc. RNDr. CSc. (01.10.2015)

Matematika I. a Matematika II.

 
VŠCHT Praha