Popis předmětu - AD7B35OIS
Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
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.
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
Předmět je zahrnut do těchto studijních plánů:
Plán |
Obor |
Role |
Dop. semestr |
Stránka vytvořena 31.10.2024 17:51:58, semestry: Z,L/2024-5, L/2023-4, Z/2025-6, 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) |