Popis předmětu - B4M35KO

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
B4M35KO Kombinatorická optimalizace Rozsah výuky:3P+2C
Garanti:Hanzálek Z. Role:P,PV Jazyk výuky:CS
Vyučující:Hanzálek Z. Zakončení:Z,ZK
Zodpovědná katedra:13135 Kreditů:6 Semestr:L

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: A4M35KO

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

Osnovy 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. Modelovácí jazyky pro řešení problémů kombinatorické optimalizace
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 - odevzdání algoritmu a písemné zprávy
13. Zápočet
14. Rezerva

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.
TORSCHE http://rtime.felk.cvut.cz/scheduling-toolbox/

Požadavky:

Optimalizace, Diskrétní matematika, Logika a grafy

Poznámka:

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

Webová stránka:

https://cw.fel.cvut.cz/wiki/courses/a4m35ko/start

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPBIO3_2018 Před zařazením do oboru PV 2
MPBIO2_2018 Před zařazením do oboru PV 2
MPBIO4_2018 Před zařazením do oboru PV 2
MPBIO1_2018 Před zařazením do oboru PV 2
MPOI1_2016 Interakce člověka s počítačem P 2
MPOI9_2016 Datové vědy P 2
MPOI8_2016 Bioinformatika P 2
MPOI7_2016 Umělá inteligence P 2
MPOI6_2016 Softwarové inženýrství P 2
MPOI5_2016 Počítačové vidění a digitální obraz P 2
MPOI4_2016 Počítačové inženýrství P 2
MPOI3_2016 Počítačová grafika P 2
MPOI2_2016 Kybernetická bezpečnost P 2
MPOI1_2018 Interakce člověka s počítačem P 2
MPOI9_2018 Datové vědy P 2
MPOI8_2018 Bioinformatika P 2
MPOI7_2018 Umělá inteligence P 2
MPOI6_2018 Softwarové inženýrství P 2
MPOI5_2018 Počítačové vidění a digitální obraz P 2
MPOI4_2018 Počítačové inženýrství P 2
MPOI3_2018 Počítačová grafika P 2
MPOI2_2018 Kybernetická bezpečnost P 2


Stránka vytvořena 16.9.2019 14:51:34, semestry: Z,L/2020-1, L/2018-9, Z,L/2019-20, 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)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.