Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

Kombinatorická optimalizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
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
místnost TK:BS
Schmidt J.
18:00–19:30
(přednášková par. 1)
Dejvice
NTK Ballingův sál
Út
místnost TH:A-1042
Fišer P.
16:15–17:45
(přednášková par. 1
paralelka 101)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Fišer P.
18:00–19:30
(přednášková par. 1
paralelka 102)

Thákurova 7 (budova FSv)
Hlavickova laborka
St
místnost TH:A-1042
Pešek J.
18:00–19:30
(přednášková par. 1
paralelka 103)

Thákurova 7 (budova FSv)
Hlavickova laborka
Čt
místnost TH:A-1042
Vyskočil J.
11:00–12:30
(přednášková par. 1
paralelka 104)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Vyskočil J.
12:45–14:15
(přednášková par. 1
paralelka 105)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Vyskočil J.
14:30–16:00
(přednášková par. 1
paralelka 106)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Schmidt J.
16:15–17:45
(přednášková par. 1
paralelka 107)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042

18:00–19:30
(přednášková par. 1
paralelka 108)

Thákurova 7 (budova FSv)
Hlavickova laborka

místnost TH:A-1042

09:15–10:45
(přednášková par. 1
paralelka 109)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Hülle R.
11:00–12:30
(přednášková par. 1
paralelka 110)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Hülle R.
12:45–14:15
(přednášková par. 1
paralelka 111)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Borecký J.
14:30–16:00
(přednášková par. 1
paralelka 112)

Thákurova 7 (budova FSv)
Hlavickova laborka
místnost TH:A-1042
Borecký J.
16:15–17:45
(přednášková par. 1
paralelka 113)

Thákurova 7 (budova FSv)
Hlavickova laborka
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 6. 10. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6085706.html