Prosím čekejte...
Nepřihlášený uživatel
logo VŠCHT
iduzel: 30011
idvazba: 38199
šablona: api_html
čas: 9.8.2020 19:56:32
verze: 4671
uzivatel:
remoteAPIs: https://cis-web-test.vscht.cz/studijni-system/
branch: trunk
Obnovit | RAW

Diskrétní optimalizace

Přednáška Cvičení/laboratoř
2019, letní semestr
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Po
Út
St
Čt
Examinace zkouška
Jazyk výuky čeština
Úroveň doktorský předmět
Garant doc. RNDr. Daniel Turzík, CSc.

Anotace

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.

Sylabus

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.

Literatura

Alexander Schrijver: A Course in Combinatorial Optimization

VŠCHT Praha
Technická 5
166 28 Praha 6 – Dejvice
IČO: 60461373
DIČ: CZ60461373

Datová schránka: sp4j9ch

Copyright VŠCHT Praha
Za informace odpovídá Oddělení komunikace, technický správce Výpočetní centrum

VŠCHT Praha
na sociálních sítích
zobrazit plnou verzi