Optimalizace v inteligentních systémech

B162 - Letní 16/17

Optimalizace v inteligentních systémech - A7B35OIS

Kredity 6
Semestry letní
Zakončení zápočet a zkouška
Jazyk výuky čeština
Rozsah výuky 2+2c
Anotace
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.
Cíle studia
Žádná data.
Osnovy 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.
Osnovy 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.
Literatura
Main textbook
[1] B. H. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms. Springer, third ed., 2006.

Some parts of:
[2] J. Demel, Grafy a jejich aplikace. Academia, second ed., 2002.
[3] J. Blazevicz, Scheduling Computer and Manufacturing Processes. Springer, second ed., 2001.
Požadavky
Lineární algebra
Agoritmizace
Stránky předmětu: https://moodle.dce.fel.cvut.cz/course/view.php?id=28