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 diskretní 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.

Předmět je ekvivalentní s MI-KOP a MI-PAA

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, úvod.

2. Experimentální vyhodnocení algoritmů.

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

4. NP-těžké a NP-úplné problémy. NPI problémy.

5. Třídy PO a NPO. Deterministické aproximační algoritmy. Třídy aproximativních problémů.

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

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

8. Simulované ochlazování

9. Simulovaná evoluce I: přehled, genetické algoritmy.

10. Simulovaná evoluce II: evoluční strategie, genetické programování.

11. Simulovaná evoluce III: teorie stavebních bloků, kompetentní evoluce, 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. Problém splnění omezení

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:

Předmět je ekvivalentní s MI-KOP a MI-PAA // Informace o předmětu a výukové materiály naleznete na https://moodle.fit.cvut.cz/courses/MI-KOP/ Předmět je ekvivalentní s MI-KOP a MI-PAA

Další informace:

https://moodle.fit.cvut.cz/courses/MI-KOP/

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

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