Kombinatorická optimalizace
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
AD4M77KO | Z,ZK | 6 | 21KP+6KC | česky |
- Garant předmětu:
- 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:
- Osnova přednášek:
-
1. Uvedení základních pojmů z kombinatorické optimalizace, příklady aplikací
a ověření znalostí z prerekvizit formou testu
2. Celočíselné lineární programování - algoritmy
3. Formulace problémů pomocí celočíselného lineárního programování
4. Heuristiky, test
5. Nejkratší cesty
6. Toky v sítích a řezy
7. Multi-komoditní toky
8. Metoda dynamického programování, test
9. Problém batohu a pseudo-polynomiální algoritmy
10. Úloha obchodního cestujícího a aproximační algoritmy
11. Rozvrhování na jednom procesoru
12. Paralelní procesory
13. Rozvrhování projektu s časovými omezeními
14. Programování s omezujícími podmínkami
- 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. Zadání samostaných úloh
5. Metoda větví a mezí
6. Nejkratší cesty
7. Aplikace toků a řezů v sítích
8. Prezentace průběžných výsledků samostatných úloh
9. Rozvrhování na jednom procesoru - Earliest deadline first
10. Aproximační algoritmy - List scheduling
11. Rezerva
12. Test
13. Odevzdávání samostatné úlohy
14. Zápočet
- 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
Stránky předmětu:
- Další informace:
- https://moodle.dce.fel.cvut.cz/course/view.php?id=21
- Pro tento předmět se rozvrh nepřipravuje
- Předmět je součástí následujících studijních plánů: