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.
|