Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Kombinatorická optimalizace

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
AD4M77KO Z,ZK 6 21KP+6KC č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:
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:

https://moodle.dce.fel.cvut.cz/course/view.php?id=21

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ů:
Platnost dat k 16. 10. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1191906.html