Kombinatorická optimalizace
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| B4M35KO | Z,ZK | 6 | 3P+2C | česky |
- Vztahy:
- Předmět B4M35KO může při kontrole studijních plánů nahradit předmět BE4M35KO
- Předmět B4M35KO nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BE4M35KO (vztah je symetrický)
- Předmět B4M35KO může být splněn v zastoupení předmětem BE4M35KO
- Předmět je ekvivalentní s A4M35KO .
- Garant předmětu:
- Zdeněk Hanzálek
- Přednášející:
- Zdeněk Hanzálek
- Cvičící:
- Josef Grus, Zdeněk Hanzálek, Vilém Heinz, Jakub Med, Antonín Novák, Marek Vlk
- Předmět zajišťuje:
- katedra řídicí techniky
- Anotace:
-
Cílem předmětu je seznámit studenty s problémy a algoritmy kombinatorické optimalizace (často se nazývá diskrétní optimalizace, významně se překrývá s pojmem operační výzkum). V návaznosti na předměty z oblasti lineární algebry, algoritmizace, diskrétní matematiky a základů optimalizace jsou ukázány techniky založené na grafech, celočíselném lineárním programování, heuristikách, aproximačních algoritmech a metodách prohledávání prostoru řešení.
Předmět je zaměřen na aplikace optimalizace ve skladech, pozemní a letecké dopravě, logistice, plánování lidských zdrojů, rozvrhování výrobních linek, směrování zpráv, rozvrhování v paralelních počítačích.
Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M35KO
- Požadavky:
-
Optimalizace, Diskrétní matematika, Logika a grafy
- Osnova přednášek:
-
1. Uvedení základních pojmů z kombinatorické optimalizace, příklady aplikací.
2. Celočíselné lineární programování - algoritmy.
3. Formulace problémů pomocí celočíselného lineárního programování.
4. Nejkratší cesty.
5. Formulace problémů pomocí nejkratších cest.
6. Toky a řezy v sítích - formulace problémů a algoritmy. Párování v bipartitních grafech. Test I.
7. Multi-komoditní toky.
8. Problém batohu, pseudo-polynomiální a aproximační algoritmy.
9. Úloha obchodního cestujícího.
10. Rozvrhování na jednom procesoru.
11. Paralelní procesory. Test II.
12. Rozvrhování projektu s časovými omezeními.
13. Programování s omezujícími podmínkami.
14. Rezerva
- Osnova cvičení:
-
1. Seznámení s předmětem a pravidly.
2. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci
3. Celočíselné lineární programování
4. Samostatná úloha I - zadání a kategorizace
5. Úloha obchodního cestujícího
6. Samostatná úloha II - rešerše literatury a prezentace řešení
7. Aplikace toků a řezů v sítích
8. Samostatná úloha III - konzultace
9. Test III
10. Rozvrhování
11. Pokročilé metody pro řešení problémů kombinatorické optimalizace
12. Samostatná úloha IV - vyhodnocení a písemná zpráva
13. Zápočet
14. Rezerva
- Cíle studia:
- Studijní materiály:
-
B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.
Springer, sixth ed., 2018.
http://dx.doi.org/10.1007/978-3-662-56039-6
J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.
J. Demel, Grafy a jejich aplikace. Academia, second ed., 2015.
- Poznámka:
-
Rozsah výuky v kombinované formě studia: 21p+6c
- Další informace:
- https://cw.fel.cvut.cz/wiki/courses/ko/start
- Rozvrh na zimní semestr 2024/2025:
- Rozvrh není připraven
- Rozvrh na letní 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á - Předmět je součástí následujících studijních plánů:
-
- Lékařská elektronika a bioinformatika - Specializace Bioinformatika (PS)
- Otevřená informatika - Interakce člověka s počítačem 2018 (povinný předmět programu)
- Otevřená informatika - Kybernetická bezpečnost 2018 (povinný předmět programu)
- Otevřená informatika - Počítačová grafika 2018 (povinný předmět programu)
- Otevřená informatika - Počítačové inženýrství 2018 (povinný předmět programu)
- Otevřená informatika - Počítačové vidění a digitální obraz 2018 (povinný předmět programu)
- Otevřená informatika - Softwarové inženýrství 2018 (povinný předmět programu)
- Otevřená informatika - Umělá inteligence 2018 (povinný předmět programu)
- Otevřená informatika - Bioinformatika 2018 (povinný předmět programu)
- Otevřená informatika - Datové vědy 2018 (povinný předmět programu)
- Lékařská elektronika a bioinformatika - Specializace Lékařská technika (povinně volitelný předmět)
- Lékařská elektronika a bioinformatika - Specializace Zpracování obrazu (PS)
- Lékařská elektronika a bioinformatika - Specializace Zpracování signálů (povinně volitelný předmět)