Kombinatorická optimalizace
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
AD4M35KO | Z,ZK | 6 | 21+6c | česky |
- Přednášející:
- Cvičící:
- 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í.
- Požadavky:
-
Optimalizace, Diskrétní matematika, Logika a grafy
Stránky předmětu: https://moodle.dce.fel.cvut.cz/
- 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. Test I.
5. Toky a řezy v sítích - formulace problémů a algoritmy. Párování v bipartitních grafech.
6. Multi-komoditní toky.
7. Problém batohu, pseudo-polynomiální a aproximační algoritmy.
8. Úloha obchodního cestujícího. Test II.
9. Rozvrhování na jednom procesoru.
10. Paralelní procesory.
11. Rozvrhování projektu s časovými omezeními.
12. Programování s omezujícími podmínkami.
13. Rezerva
- Osnova cvičení:
-
1. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci
2. Celočíselné lineární programování
3. Aplikace celočíselného lineárního programování
4. Samostatná úloha I - zadání a kategorizace
5. Nejkratší cesty
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. Rozvrhování
10. Test III
11. Samostatná úloha IV - odevzdání algoritmu a písemné zprávy
12. Zápočet
13. Rezerva
- Cíle studia:
- Studijní materiály:
-
B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.
Springer, third ed., 2006.
J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,
second ed., 2001.
J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.
- Poznámka:
-
Rozsah výuky v kombinované formě studia: 21p+6c
- Další informace:
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů:
-
- Otevřená informatika - Umělá inteligence_145417 (povinný předmět programu)
- Otevřená informatika - Počítačové inženýrství_145440 (povinný předmět programu)
- Otevřená informatika - Počítačové vidění a digitální obraz_145456 (povinný předmět programu)
- Otevřená informatika - Počítačová grafika a interakce_145515 (povinný předmět programu)
- Otevřená informatika - Softwarové inženýrství_145534 (povinný předmět programu)