|
Lecturer(s)
|
-
Vorel Kryštof, prof. RNDr. DrSc.
-
Kopal Stanislav, doc. RNDr. Ph.D.
|
|
Course content
|
Optimization problems on graphs and networks: flows with costs and minimum cost flows, potentials. Maximum matching and optimum matching in a (weighted) bipartite graph. Maximum matching in a nonbipartite graph (Tuttes Theorem and Edmonds algorithm). Real linear programming: simplex algorithm, duality, computational complexity. Integer linear programming: NP-completeness, totally unimodular matrices, branch-and-bound methods and Gomory algorithms. Formulation of various optimization problems on graphs and networks as linear programming problems.
|
|
Learning activities and teaching methods
|
Collaborative instruction, Lecture
- Contact hours
- 52 hours per semester
- Preparation for comprehensive test (10-40)
- 25 hours per semester
- Preparation for an examination (30-60)
- 60 hours per semester
|
| prerequisite |
|---|
| Knowledge |
|---|
| 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 |
| Skills |
|---|
| 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 |
| Competences |
|---|
| N/A |
| learning outcomes |
|---|
| Knowledge |
|---|
| 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ů |
| Skills |
|---|
| 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 |
| Competences |
|---|
| aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
| N/A |
| N/A |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecture |
| Collaborative instruction |
| Skills |
|---|
| Collaborative instruction |
| Competences |
|---|
| Lecture |
| assessment methods |
|---|
| Knowledge |
|---|
| Combined exam |
| Test |
| Skills demonstration during practicum |
| Skills |
|---|
| Skills demonstration during practicum |
| Competences |
|---|
| Combined exam |
|
Recommended literature
|
-
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.
|