|
Vyučující
|
-
Teska Jakub, RNDr. Mgr. Ph.D.
-
Čada Roman, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
Základní úlohy řešitelné v polynomiálním čase: minimální cesty a kostry, vzdálenost, souvislost a k-souvislost, Eulerovské grafy, acyklické grafy, kritická cesta a metody CPM. Toky v sítích a transportní úlohy, Ford-Fulkersonova věta o maximálním toku. Grafy a matice: rozložitelnost, slabá rozložitelnost a generická hodnost matice a její určení převodem na grafovou úlohu. Základní NP-úplné úlohy: hamiltonovské grafy a problém obchodního cestujícího, nezávislé množiny a pokrytí, klikovost, dominance, jádro, barevnost grafu. Základy teorie NP-úplnosti: deterministické a nedeterministické algoritmy, jazyky třídy P a NP, NP-úplnost úlohy splnitelnosti logických formulí, vzájemné polynomiálních převody NP-úplných úloh, NP-úplnost úloh nezávislosti, klikovosti a 3-obarvitelnosti grafu.
|
|
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 |
|---|
| vysvětlit základní pojmy z teorie relačních struktur: binární relace, ekvivalence (včetně aplikace na aritmetiku modulo 2), uspořádání a částečné uspořádání, Booleovy algebry a Booleovské polynomy a funkce |
| formulovat základní pojmy z teorie grafů (v rozsahu předmětu KMA/DMA) a vysvětlit jejich základní vlastnosti, včetně porozumění souvislostem |
| popsat maticový popis grafu a vysvětlit vztahy mezi vlastnostmi grafu a algebraickými vlastnostmi příslušné matice |
| Odborné dovednosti |
|---|
| navrhnout a formulovat algoritmy řešení základních grafových úloh (v rozsahu předmětu KMA/DMA) |
| aktivně ovládat pojmy ekvivalence a rozkladu množiny na třídy ekvivalence |
| prakticky použít základy teorie Booleových algeber, včetně vyjádření Booleovského polynomu v konjunktivní a disjunktivní normální formě |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| vysvětlit probírané pojmy a úlohy teorie grafů a jejich základní vlastnosti, včetně porozumění souvislostem |
| analyzovat konkrétní algoritmy z hlediska jejich výpočetní složitosti |
| klasifikovat základní problémy teorie grafů a diskrétní matematiky z hlediska výpočetní složitosti |
| vysvětlit základy teorie výpočetní složitosti a základní principy teorie NP-úplnosti |
| Odborné dovednosti |
|---|
| 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ů |
| ovládat klasifikaci algoritmů z hlediska jejich výpočetní složitosti a posoudit výpočetní složitost konkrétních algoritmů |
| navrhnout, formulovat a prakticky použít algoritmy řešení základních grafových úloh |
| aktivně ovládat probírané pojmy a úlohy teorie grafů |
| pro vybrané algoritmicky obtížné úlohy navrhnout heuristické algoritmy umožňující jejich přibližné nebo částečné řešení |
| Obecné způsobilosti |
|---|
| bc. studium: samostatně získávají další odborné znalosti, dovednosti a způsobilosti na základě především praktické zkušenosti a jejího vyhodnocení, ale také samostatným studiem teoretických poznatků oboru, |
| aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Cvičení (praktické činnosti), |
| Přednáška založená na výkladu, |
| Odborné dovednosti |
|---|
| Cvičení (praktické činnosti), |
| 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), |
| Test, |
| Obecné způsobilosti |
|---|
| Kombinovaná zkouška, |
|
Doporučená literatura
|
-
Bondy, Adrian; Murty, U. S. R. Graph theory. 2008. ISBN 978-1-84996-690-0.
-
Bovet, Daniel Pierre; Crescenzi, Pierluigi. Introduction to the theory of complexity. 1994. ISBN 0-13-915380-2.
-
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
-
Gross, Jonathan L.; Yellen, Jay; Anderson, Mark. Graph theory and its applications. Third edition. 2019. ISBN 978-1-4822-4948-4.
-
Sanjoy Dasgupta; Papadimitriou, Christos; Vazirani, Umesh. Algorithms. New York : McGraw-Hill, 2008. ISBN 978-0-07-352340-8.
|