Kombinatorická optimalizace
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| NI-KOP | Z,ZK | 6 | 2P+2C | česky |
- Přednášející:
- Jan Schmidt (gar.)
- Cvičící:
- Jan Schmidt (gar.), Jaroslav Borecký, Jiří Dostál, Petr Fišer, Robert Hülle, Karel Hynek, Jan Onderka
- 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. 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. 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://moodle.fit.cvut.cz/courses/MI-KOP/
- Rozvrh na zimní semestr 2022/2023:
-
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 2022/2023:
- 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)