Kombinatorické algoritmy

Garant předmětu:

Zdeněk Hanzálek

Přednášející:

Zdeněk Hanzálek

Cvičící:

Zdeněk Hanzálek, Antonín Novák

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í.

Předmět je zaměřen na aplikace optimalizace ve skladech, pozemní a letecké dopravě, logistice, plánování lidských zdrojů, rozvrhování výrobních linek, směrování zpráv, rozvrhování v paralelních počítačích.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/A4M35KO

Požadavky:

Optimalizace, Diskrétní matematika, Logika a grafy

Osnova přednášek:

1.Uvedení základních pojmů z kombinatorických algoritmů, příklady aplikací.

2.Složitost kombinatorických problémů.

3.Celočíselné lineární programování - algoritmy.

4.Formulace problémů pomocí celočíselného lineárního programování.

5.Nejkratší cesty.

6.Formulace problémů pomocí nejkratších cest. Test I

7.Toky a řezy v sítích - algoritmy.

8.Toky a řezy v sítích - formulace problémů.

9. Multikomoditní toky

10.Problém batohu, pseudo-polynomiální a aproximační algoritmy.

11.Úloha obchodního cestujícího.

12.Rozvrhování na jednom procesoru.

13.Paralelní procesory.

14.Rezerva

Osnova cvičení:

1. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci

2. SAT a celočíselné lineární programování

3. Celočíselné lineární programování

4. Celočíselné lineární programování

5. Samostatná úloha I - zadání a kategorizace

6. Úloha obchodního cestujícího

7. Samostatná úloha II - rešerše literatury a prezentace řešení

8. Aplikace toků a řezů v sítích

9. Samostatná úloha III - konzultace

10. Rozvrhování. Test II

11. Pokročilé metody pro řešení problémů kombinatorické optimalizace

12. Samostatná úloha IV - vyhodnocení a písemná zpráva

13. Zápočet

14. Rezerva

Cíle studia:

Studijní materiály:

B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms.

Springer, sixth ed., 2018.

http://dx.doi.org/10.1007/978-3-662-56039-6

J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer,

second ed., 2001.

J. Demel, Grafy a jejich aplikace. Academia, second ed., 2015.

https://kix.fsv.cvut.cz/~demel/grafy/gr.pdf

Poznámka:

Rozsah výuky v kombinované formě studia: 21p+6c

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost T2:C2-82 Hanzálek Z. 14:30–16:00 (přednášková par. 1) Dejvice T2:C2-82
Út
St
Čt	místnost T2:H1-130 Novák A. 09:15–10:45 (přednášková par. 1 paralelka 101) Dejvice haly AlgDejvice - Veřejnámístnost T2:H1-131 Novák A. 12:45–14:15 (přednášková par. 1 paralelka 102) Dejvice haly AlgDejvice
Pá

Předmět je součástí následujících studijních plánů: