|
Vyučující
|
-
Šenkeřík Roman, prof. Ing. Ph.D.
|
|
Obsah předmětu
|
- Moderní informatické přístupy k řešení matematických a optimalizačních úloh. Soft-computing vs. Hard-computing, Heuristické algoritmy, Rozdělení heuristik. Bodové a populační strategie. - Definice účelové funkce jako matematického modelu optimalizačního problému, argumenty, omezení. Testovací funkce pro benchmarkování algoritmů. - Vícekriteriální optimalizace, pareto množiny. Mnohokriteriální optimalizace, včetně dynamických úloh. - Bodové heuristiky I: Local Search, Metoda náhodného prohledávání (procházky) Random Search/Random Walk, Hill Climber. - Bodové heuristiky II: Tabu Search, Simulované žíhání. - Populační heuristiky - Harmony Search a odvozené heuristiky podobné evolučním strategiím. - Úvod do operačního výzkumu. Složitost problémů a převoditelnost: Třídy složitosti, P, NP, NPC problémy. - Permutační a kombinatorické úlohy a jejich řešení I: Problém naplňování zásobníku, problém batohu, kapacitní rozvozní problém, problém obchodního cestujícího. - Permutační a kombinatorické úlohy a jejich řešení II: Přiřazovací problémy, problémy plánování výroby a zpracování dat. - Formální modely výpočtu, automaty, stroje, komplexita, buněčné automaty a jejich aplikace. - Grafy a grafové algoritmy. - Komplexní sítě a jejich analýza. - Generování náhodných čísel.
|
|
Studijní aktivity a metody výuky
|
|
Přednášení, Cvičení na počítači
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| Znalosti z oblasti: Matematika Teoretická Informatika Programování Optimalizace |
| Znalosti z oblasti: Matematika Teoretická Informatika Programování Optimalizace |
| Výsledky učení |
|---|
| Student umí vyjmenovat a definovat různé typy optimalizačních algoritmů, včetně jejich vlastností a heuristických přístupů. |
| Student umí vyjmenovat a definovat různé typy optimalizačních algoritmů, včetně jejich vlastností a heuristických přístupů. |
| Student rozumí základním konceptům operačního výzkumu, včetně tříd složitosti problémů P, NP a NPC. |
| Student rozumí základním konceptům operačního výzkumu, včetně tříd složitosti problémů P, NP a NPC. |
| Student má znalosti o algoritmické řešitelnosti problémů a základních prohledávacích algoritmech. |
| Student má znalosti o algoritmické řešitelnosti problémů a základních prohledávacích algoritmech. |
| Student umí popsat principy buněčného automatu a základní grafové algoritmy. |
| Student umí popsat principy buněčného automatu a základní grafové algoritmy. |
| Student rozumí principům komplexních sítí a má znalosti o vícekriteriální optimalizaci, včetně pareto množin. |
| Student rozumí principům komplexních sítí a má znalosti o vícekriteriální optimalizaci, včetně pareto množin. |
| Odborné dovednosti |
|---|
| Student umí aplikovat různé heuristické algoritmy pro řešení komplexních optimalizačních úloh. |
| Student umí aplikovat různé heuristické algoritmy pro řešení komplexních optimalizačních úloh. |
| Student dokáže vytvořit a použít účelové funkce pro testování a benchmarkování algoritmů. |
| Student dokáže vytvořit a použít účelové funkce pro testování a benchmarkování algoritmů. |
| Student je schopen navrhnout řešení pro různé permutační a kombinatorické úlohy, včetně problémů naplňování zásobníku a obchodního cestujícího. |
| Student je schopen navrhnout řešení pro různé permutační a kombinatorické úlohy, včetně problémů naplňování zásobníku a obchodního cestujícího. |
| Student má dovednost v analýze a modelování komplexních sítí. |
| Student má dovednost v analýze a modelování komplexních sítí. |
| Student dokáže implementovat algoritmy pro různé vícekriteriální aplikace. |
| Student dokáže implementovat algoritmy pro různé vícekriteriální aplikace. |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Cvičení na počítači |
| Cvičení na počítači |
| Přednášení |
| Přednášení |
| Hodnotící metody |
|---|
| Ústní zkouška |
| Ústní zkouška |
| Písemná zkouška |
| Písemná zkouška |
|
Doporučená literatura
|
-
Demel J. Grafy a jejich aplikace. Academia, 2002.
-
Dreo J. Metaheuristics for hard optimization: methods and case studies. Berlin, 2006. ISBN 9783540230229.
-
Ilachinski, Andrew. Cellular automata : a discrete universe. 1st pub. Singapore : World Scientific, 2001. ISBN 981-238-183-X.
-
Koubková A., Pavelka J. Uvod do teoretické informatiky. Matfyzpress, 2003.
-
Kučera L. Kombinatorické algoritmy. Praha, 1983.
-
Linz, Peter. An introduction to formal languages and automata. 4th ed. Sudbury, Mass. : Jones and Bartlett Publishers, 2006. ISBN 0-7637-3798-4.
-
Naim B.E. Complex Networks. Springer, 2004. ISBN 13: 978-354022354.
-
Nešetřil J. Teorie grafů. MS, Praha, 1979.
-
Vaníček J., Papík M., Pregl R., Vaníček T. Teoretické základy informatiky. Alfa Publishing, 2006.
-
Zelinka I. Handbook of optimization: from classical to modern approach. Berlin, 2013. ISBN 9783642305030.
|