|
Vyučující
|
-
Leuchter Ondřej, prof. RNDr. DrSc.
-
Mlčoch Jan, doc. RNDr. Ph.D.
|
|
Obsah předmětu
|
Optimalizační úlohy na grafech a sítích: tok v síti s cenami, minimalizace celkové ceny řešení a optimální tok, potenciály, algoritmy nalezení optimálního toku. Lineární programování (reálné), různé formulace úlohy a jejich ekvivalence, simplexový algoritmus, výpočetní složitost. Degenerované úlohy a cyklení. Dualita úloh LP. Úloha celočíselného lineárního programování a její NP-úplnost, celočíselné optimalizační úlohy s totálně unimodulární maticí. Formulace optimalizačních úloh na grafech a sítích jako úloh lineárního programování. Přiřazovací problémy, maximální a optimální párování a maďarská metoda. Speciální třídy grafů a vliv speciální struktury grafu na výpočetní složitost problému: hranové grafy, rovinné grafy. Přibližné algoritmy a heuristiky pro některé úlohy diskrétní optimalizace.
|
|
Studijní aktivity a metody výuky
|
Skupinová výuka, Přednáška
- Kontaktní výuka
- 52 hodin za semestr
- Příprava na souhrnný test [6-30]
- 25 hodin za semestr
- Příprava na zkoušku [10-60]
- 60 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| analyzovat konkrétní algoritmy z hlediska jejich výpočetní složitosti |
| vysvětlit základy teorie výpočetní složitosti a základní principy teorie NP-úplnosti |
| vysvětlit pojmy a úlohy teorie grafů (v rozsahu předmětu KMA/TGD1) a jejich základní vlastnosti, včetně porozumění souvislostem |
| klasifikovat základní problémy teorie grafů a diskrétní matematiky z hlediska výpočetní složitosti |
| Odborné dovednosti |
|---|
| navrhnout, formulovat a prakticky použít algoritmy řešení základních grafových úloh |
| u vybraných konkrétních grafových a kombinatorických problémů ověřit jejich NP-úplnost, včetně konstrukce příslušných polynomiálních převodních algoritmů |
| pro vybrané algoritmicky obtížné úlohy navrhnout heuristické algoritmy umožňující jejich přibližné nebo částečné řešení |
| ovládat klasifikaci algoritmů z hlediska jejich výpočetní složitosti a posoudit výpočetní složitost konkrétních algoritmů |
| aktivně ovládat pojmy a úlohy teorie grafů v rozsahu předmětu KMA/TGD1 |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| formulovat základní optimalizační úlohy na grafech a sítích, vysvětlit jejich vlastnosti a základní metody |
| popsat algoritmy řešení základních optimalizačních úloh a posoudit jejich výpočetní složitost |
| vysvětlit teoretické pozadí jednotlivých metod a jejich vzájemné převoditelnosti, včetně role charakterizačních vět a dobrých charakteristik při konstrukci efektivních algoritmů |
| Odborné dovednosti |
|---|
| používat vzájemné převody úloh, včetně převodů grafových a síťových optimalizačních úloh na úlohy lineárního programování |
| klasifikovat jednotlivé problémy z hlediska výpočetní složitosti a u NP-těžkých problémů ovládat základní heuristické a aproximační algoritmy |
| ovládat základní optimalizační úlohy na grafech a sítích |
| aktivně používat metody a algoritmy řešení jednotlivých úloh |
| Obecné způsobilosti |
|---|
| aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
| mgr. studium: srozumitelně a přesvědčivě sdělují odborníkům i širší veřejnosti vlastní odborné názory, |
| mgr. studium: používají své odborné znalosti, odborné dovednosti a obecné způsobilosti alespoň v jednom cizím jazyce, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška založená na výkladu, |
| Skupinová výuka, |
| Odborné dovednosti |
|---|
| Skupinová výuka, |
| Obecné způsobilosti |
|---|
| Přednáška založená na výkladu, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Kombinovaná zkouška, |
| Test, |
| Demonstrace dovedností (praktická činnost), |
| Odborné dovednosti |
|---|
| Demonstrace dovedností (praktická činnost), |
| Obecné způsobilosti |
|---|
| Kombinovaná zkouška, |
|
Doporučená literatura
|
-
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.
-
Korte, Bernhard; Vygen, Jens. Combinatorial optimization : theory and algorithms. 2nd ed. Berlin : Springer, 2002. ISBN 3-540-43154-3.
-
Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989.
-
Lovász L. Matching Theory. American Mathematical Society, 2009. ISBN 978-0821847596.
-
Matoušek J., Gaertner B. Understanding and Using Linear Programming. Springer. 2006.
-
Papadimitriou, Christos H.; Steiglitz, Kenneth. Combinatorial optimization : algorithms and complexity. 1st pub. Mineola : Dover Publications, 1998. ISBN 0-486-40258-4.
-
Plesník, Ján; Dupačová, Jitka; Vlach, Milan. Lineárne programovanie. 1. vyd. Bratislava : Alfa, 1990. ISBN 80-05-00679-9.
|