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

Kombinatorická optimalizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
MI-KOP Z,ZK 5 2+2 česky
Přednášející:
Jan Schmidt (gar.)
Cvičící:
Jan Schmidt (gar.), Petr Fišer
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.

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:

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

Další informace:
https://moodle.fit.cvut.cz/courses/MI-KOP/
Rozvrh na zimní semestr 2018/2019:
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 TH:A-1042
Fišer P.
14:30–16:00
(přednášková par. 1
paralelka 101)

Thákurova 7 (FSv-budova A)
Hlavickova laborka
místnost TK:BS
Schmidt J.
18:00–19:30
(přednášková par. 1)
Dejvice
NTK Ballingův sál
Út
St
Čt

Rozvrh na letní semestr 2018/2019:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 17. 2. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet5523306.html