Kombinatorická optimalizace
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| NI-KOP | Z,ZK | 6 | 2P+2C | česky |
- Garant předmětu:
- Jan Schmidt
- Přednášející:
- Jan Schmidt
- Cvičící:
- Jaroslav Borecký, Petr Fišer, Robert Hülle, Jaroslav Pešek, Jan Schmidt, Jiří Vyskočil
- 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:
-
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. 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.
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/
- Další informace:
- https://courses.fit.cvut.cz/NI-KOP/
- Rozvrh na zimní semestr 2024/2025:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Rozvrh na letní semestr 2024/2025:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Mgr. specializace Počítačová bezpečnost, 2020 (povinný předmět programu)
- Mgr. specializace Návrh a programování vestavných systémů, 2020 (povinný předmět programu)
- Mgr. specializace Počítačové systémy a sítě, 2020 (povinný předmět programu)
- Mgr. specializace Manažerská informatika, 2020 (povinný předmět programu)
- Mgr. specializace Softwarové inženýrství, 2020 (povinný předmět programu)
- Mgr. specializace Systémové programování, verze od 2020 (povinný předmět programu)
- Mgr. specializace Webové inženýrství, 2020 (povinný předmět programu)
- Mgr. specializace Znalostní inženýrství, 2020 (povinný předmět programu)
- Mgr. specializace Teoretická informatika, 2020 (povinný předmět programu)
- Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (povinný předmět programu)
- Mgr. specializace Systémové programování, verze od 2023 (povinný předmět programu)
- Mgr. specializace Teoretická informatika, 2023 (povinný předmět programu)