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
a ověření znalostí z prerekvizit formou testu
Springer, third ed., 2006.
second ed., 2001.
AD4M77KO | Kombinatorická optimalizace | ||
---|---|---|---|
Role: | Rozsah výuky: | 21KP+6KC | |
Katedra: | 13135 | Jazyk výuky: | CS |
Garanti: | Zakončení: | Z,ZK | |
Přednášející: | Kreditů: | 6 | |
Cvičící: | Semestr: | L |
Webová stránka:
https://moodle.dce.fel.cvut.cz/course/view.php?id=21Anotace:
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í |
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. |
J. | Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, |
J. | Demel, Grafy a jejich aplikace. Academia, second ed., 2002. |
Požadavky:
Poznámka:
Rozsah výuky v kombinované formě studia: 21p+6c |
Stránky předmětu: |
https://moodle.dce.fel.cvut.cz/course/view.php?id=21 |
Předmět je zahrnut do těchto studijních plánů:
Plán | Obor | Role | Dop. semestr |
Stránka vytvořena 15.5.2024 07:51:43, semestry: Z,L/2023-4, Z/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) |