Popis předmětu - AD4M77KO
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://moodle.dce.fel.cvut.cz/course/view.php?id=21
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í.
Osnovy 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 |
Osnovy 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 |
Literatura:
| 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. |
Požadavky:
Poznámka:
Předmět je zahrnut do těchto studijních plánů:
| Plán |
Obor |
Role |
Dop. semestr |
| Stránka vytvořena 26.3.2025 17:50:36, semestry: Z/2024-5, Z,L/2025-6, 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) |