Kombinatorická optimalizace

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra číslicového návrhu

Anotace:

Studenti se naučí posoudit diskrétní problémy podle složitosti a podle účelu optimalizace (on-line, multikriteriální, atd.). Porozumí principům a vlastnostem heuristik a exaktních algoritmů. Dokáží vybrat, aplikovat a experimentálně vyhodnotit vhodné heuristiky pro praktické problémy.

Požadavky:

Algoritmus. Pojem výpočetní složitosti a asymptotické složitosti. Pojem formálního jazyka. Základy teorie grafů. Náhodná veličina. Booleova algebra. Metoda větví a hranic. Základy dynamického programování. Praktické programování v libovolném imperativním jazyce.

Osnova přednášek:

1. Kombinatorické problémy a algoritmy.

2. Experimentální práce s algoritmy

3. Třídy P a NP, komplementární problémy, polynomiální hierarchie.

4. NP-těžké a NP-úplné rozhodovací problémy. NP-těžké optimalizační problémy.

5. Prakticky významné rozhodovací problémy, převody a užití SAT, SMT.

6. Prakticky významné optimalizační problémy, převody a užití ILP, CSP

7. Stavový prostor, prostor prohledávání, pohyb ve stavovém prostoru, lokální heuristiky, metoda větví a hranic.

8. Randomizované algoritmy. Experimentální nasazení parametrizovaných heuristik.

9. Simulované ochlazování

10. Simulovaná evoluce I: přehled, genetické algoritmy, genetické programování.

11. Simulovaná evoluce II: evoluční strategie, fast messy GA. Stochastická optimalizace: modely a aplikace. Bayesovská optimalizace.

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

13. Metody multikriteriální optimalizace

Osnova cvičení:

1. Úvod, problém splnitelnosti formule, problém plnění batohu.

2. Přehled problémů, hledání konfiguračních proměnných.

3. Jednoduché algoritmy splnitelnosti formule, experimenty na jedné instanci.

4. Jednoduché algoritmy splnitelnosti formule, experimenty na sadách instancí .

5. Třídy problémů P a NP, NPC, NPH.

6. Stavový prostor

7. Test

8. Nasazení simulovaného ochlazování I

9. Konzultace

10. Nasazení simulovaného ochlazování II.

11. Nasazení simulované evoluce I.

12. Nasazení simulované evoluce II.

13. Opravný a náhradní test

Cíle studia:

Studenti se naučí posoudit diskrétní problémy podle složitosti a podle účelu optimalizace (on-line, multikriteriální, atd.). Porozumí principům a vlastnostem heuristik a exaktních algoritmů. Dokáží vybrat, aplikovat a experimentálně vyhodnotit vhodné heuristiky pro praktické problémy.

Studijní materiály:

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

2. Hromkovič, 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. ISBN xxxx.

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:

Materiály budou dostupné na Courses.

Další informace:

https://courses.fit.cvut.cz/ANI-KOP/

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

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

• Mgr. program Aplikovaná informatika (kód ANI) pro fázi studia bez specializace (povinný předmět programu)
• Mgr. specializace Manažerská informatika, 2026 (povinný předmět programu)