Optimalizace v inteligentních systémech

Cílem předmětu je seznámit studenty s algoritmy řešícími problémy kombinatorické optimalizace. V návaznosti na předmět algoritmizace jsou ukázány základní 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 optimalizačních technik v inteligentních systémech pro využití skladů, pozemní přepravu, leteckou přepravu, logistiku, plánování lidských zdrojů, rozvrhování strojů ve výrobě, směrování zpráv v sítích, rozvrhování úloh v paralelních počítačích.

Kód
A7B35OIS
Semestr
letní
Forma studia
prezenční
Rozsah
2+2c
Obsazeno
0
Počet kreditů
6
Zakončení
zápočet a zkouška
Jazyk výuky
čeština
Obsah přednášek

1. Příklady aplikací a formulace problémů.
2. Základní pojmy z teorie grafů.
3. Optimalizační problémy založené na hledání nejlevnější kostry.
4. Toky v sítích.
5. Lineární programování.
6. Algoritmy pro lineární programování. Test I.
7. Časová náročnost algoritmů.
8. Příklady řešení kombinatorických problémů metodou větví a mezí.
9. Metaheuristiky a metody umělé inteligence. Aproximační algoritmy.
10. Aplikace úloh rozvrhování na jednom procesoru.
11. Rozvrhování na paralelní procesory.
12. Rozvrhování v dílně.
13. Rezerva.

Náplň cvičení

1. Seznámení s experimentálním prostředím a knihovnou pro optimalizaci.
2. Vlastnosti grafů.
3. Minimální kostra grafu a shluková analýza.
4. Samostatná práce - zadání a kategorizace.
5. Aplikace toků v sítích.
6. Lineární programování.
7. Rozvrhování a Metoda větví a mezí.
8. Aproximační algoritmy a SAT problém.
9. Samostatná práce - odevzdání programu a rešerše.
10. Test II.
11. Samostatná práce - odevzdání závěrečné zprávy.
12. Zápočet.
13. Rezerva.