Předmět: Teorie grafů, diskrétní optimalizace a výpočetní složitost 2

» Seznam fakult » FAV » KMA
Název předmětu Teorie grafů, diskrétní optimalizace a výpočetní složitost 2
Kód předmětu KMA/TGD2
Organizační forma výuky Přednáška + Seminář
Úroveň předmětu Magisterský
Rok studia nespecifikován
Semestr Letní
Počet ECTS kreditů 5
Vyučovací jazyk Čeština
Statut předmětu nespecifikováno
Způsob výuky Kontaktní
Studijní praxe Nejedná se o pracovní stáž
Doporučené volitelné součásti programu Není
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.


Studijní plány, ve kterých se předmět nachází
Fakulta Studijní plán (Verze) Kategorie studijního oboru/specializace Doporučený ročník Doporučený semestr