Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2023/2024
UPOZORNĚNÍ: Jsou dostupné studijní plány pro následující akademický rok.

Kombinatorická optimalizace

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
B4M35KO Z,ZK 6 3P+2C česky

Předmět B4M35KO může při kontrole studijních plánů nahradit předmět BE4M35KO

Předmět B4M35KO nesmí být zapsán, je-li v témže semestru zapsán anebo již dříve absolvován předmět BE4M35KO (vztah je symetrický)

Předmět B4M35KO může být splněn v zastoupení předmětem BE4M35KO

Garant předmětu:
Zdeněk Hanzálek
Přednášející:
Zdeněk Hanzálek
Cvičící:
Ondřej Benedikt, Josef Grus, Zdeněk Hanzálek, Vilém Heinz, Jakub Med, Anna Minaeva, István Módos, Antonín Novák, Marek Vlk
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é 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. Nejkratší cesty.

5. Formulace problémů pomocí nejkratších cest.

6. Toky a řezy v sítích - formulace problémů a algoritmy. Párování v bipartitních grafech. Test I.

7. Multi-komoditní toky.

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

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

10. Rozvrhování na jednom procesoru.

11. Paralelní procesory. Test II.

12. Rozvrhování projektu s časovými omezeními.

13. Programování s omezujícími podmínkami.

14. Rezerva

Osnova cvičení:

1. Seznámení s předmětem a pravidly.

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

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

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

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

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

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

8. Samostatná úloha III - konzultace

9. Test III

10. Rozvrhování

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

Další informace:
https://cw.fel.cvut.cz/wiki/courses/ko/start
Rozvrh na zimní semestr 2023/2024:
Rozvrh není připraven
Rozvrh na letní semestr 2023/2024:
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
Út
místnost T2:D3-309
Hanzálek Z.
11:45–14:15
(přednášková par. 1)
Dejvice
T2:D3-309
místnost T2:H1-131
Med J.
14:30–16:00
(přednášková par. 1
paralelka 101)

Dejvice haly
AlgDejvice
místnost T2:H1-130
Grus J.
16:15–17:45
(přednášková par. 1
paralelka 103)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130

18:00–19:30
(přednášková par. 1
paralelka 104)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130
Grus J.
14:30–16:00
(přednášková par. 1
paralelka 102)

Dejvice haly
AlgDejvice - Veřejná
St
Čt
místnost T2:H1-130
Heinz V.
11:00–12:30
(přednášková par. 1
paralelka 109)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130
Heinz V.
12:45–14:15
(přednášková par. 1
paralelka 105)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-130
Med J.
14:30–16:00
(přednášková par. 1
paralelka 106)

Dejvice haly
AlgDejvice - Veřejná
místnost T2:H1-131

16:15–17:45
(přednášková par. 1
paralelka 107)

Dejvice haly
AlgDejvice
místnost T2:H1-131

18:00–19:30
(přednášková par. 1
paralelka 108)

Dejvice haly
AlgDejvice

Předmět je součástí následujících studijních plánů:
Platnost dat k 27. 3. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet4670806.html