Kombinatorická optimalizace

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra číslicového návrhu

Anotace:

Studenti získají znalosti a porozumění nutné pro úspěšné nasazení heuristik pro diskrétní

optimalizační problémy na profesionální úrovni.

Dokáží nejen vybrat a implementovat, ale hlavně aplikovat a experimentálně vyhodnotit

vhodnou heuristiku pro praktické problémy.

Od B201 je vypisována nová, ekvivalentní verze předmětu NI-KOP.

Požadavky:

Osnova přednášek:

1. Optimalizace, příklady optimalizačních úloh v praxi. Kombinatorické problémy.

2. Modely výpočtu. Třídy P, NP. Polynomiální hierarchie.

3. Pojem úplnosti problému. Techniky srovnání složitosti. Tvrdý NP-úplný, NP-těžký, NPI.

4. Komunikační a obvodová složitost.

5. Třídy PO a NPO. Deterministické aproximační algoritmy. Třídy aproximativních problémů. Pseudopolynomiální algoritmy. Randomizace, randomizované algoritmy.

6. Praktické nasazení heuristik a exaktních algoritmů. Experimentální vyhodnocení.

7. Stav, stavový prostor, prohledávač prostor. Exaktní metody.

8. Jednoduché lokální heuristiky ve stavovém a prohledávacím prostoru.

9. Simulované ochlazování.

10. Simulovaná evoluce: typy, genetické algoritmy.

11. Pokročilé genetické algoritmy: kompetentní GA, fmGA, metoda sobeckého genu. Použití v multikriteriální optimalizaci. Stochastická optimalizace.

12. Tabu prohledávání.

13. Globální metody, typy dekompozice. Exaktní a heuristické globální metody, algoritmus Davis-Putnam jako globální metoda.

Osnova cvičení:

1. Cvičení: terminologie, příklady na složitost.

2. Cvičení: příklady stavového prostoru algoritmů.

3. Konzultace; samostudium: dynamické programování.

4. Proseminář: třídy P, NP, důkazy, problémy horší než NP.

5. Proseminář: úplnost, redukce.

6. Konzultace.

7. Konzultace.

8. Konzultace.

9. Proseminář: test.

10. Konzultace.

11. Proseminář: nasazení pokročilých heuristik.

12. Konzultace.

13. Konzultace.

14. Proseminář: náhradní test, zápočty.

Cíle studia:

Mnoho praktických úloh je výpočetně nezvládnutelných. V předmětu se studenti seznámí s rychlými algoritmy pro přesná, ale hlavně přibližná řešení. Tyto algoritmy jsou sice programátorsky jednoduché, ale jejich nasazení vyžaduje hlubší porozumění jejich práci i základům teorie složitosti. Série samostatných prací vede studenta od základních technik vyhodnocení až po nasazení a vyhodnocení

pokročilých heuristik na prakticky významném problému.

Studijní materiály:

1. Arora, S. : Computational Complexity: A Modern Approach. Cambridge University Press, 2017. ISBN 978-1316612156.

2. Hromkovic, J. : Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics 2nd Edition. Springer, 2004. ISBN 978 3540441342.

3. Kučera, L. : Kombinatorické algoritmy. SNTL, 1993.

4. Ausiello, G. - Crescenzi, P. - Kann, V. - Gambosi, G. - Spaccamela, A. M. : Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, 2003. ISBN 3540654313.

Poznámka:

Předmět je nahrazen ekvivalentním NI-KOP // Informace o předmětu a výukové materiály naleznete na

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Mgr. specializace Teoretická informatika, 2018-2019 (povinný předmět programu)