Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
| B4M35KO |
Kombinatorická optimalizace |
| Role: | P, PS, PV |
Rozsah výuky: | 3P+2C |
| Katedra: | 13135 |
Jazyk výuky: | CS |
| Garanti: | Hanzálek Z. |
Zakončení: | Z,ZK |
| Přednášející: | Hanzálek Z. |
Kreditů: | 6 |
| Cvičící: | Osob je mnoho |
Semestr: | L |
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/ko/start
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:
A4M35KO
Osnovy 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 |
Osnovy 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 |
Literatura:
| 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. |
https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf
Požadavky:
Optimalizace, Diskrétní matematika, Logika a grafy
Poznámka:
| Rozsah výuky v kombinované formě studia: 21p+6c |
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 28.1.2025 15:50:50, semestry: Z/2025-6, Z,L/2024-5, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |