Předmět Teorie grafů, optimalizace a složitost 1 (KMA / TGD1)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMA / TGD1 - Teorie grafů, optimalizace a složitost 1, Fakulta aplikovaných věd, Západočeská univerzita v Plzni (ZČU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
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á hornost 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.
Získané způsobilosti
Student bude schopen po absolvování předmětu:- aktivně ovládat základní pojmy a úlohy teorie grafů,- navrhnout, formulovat a prakticky použít algoritmy řešení základních grafových úloh,- ovládat klasifikaci algoritmů z hlediska jejich výpočetní složitosti a umět posoudit výpočetní složitost konkrétních algoritmů,- ovládat základy teorie NP-úplnosti, - u 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ů.
Literatura
http://www.kma.zcu.cz/TGD1Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989. Holenda, Jiří; Ryjáček, Zdeněk. Lineární algebra II : úvod do diskrétní matematiky. 2. vyd. Plzeň : Západočeská univerzita, 2000. ISBN 80-7082-638-X.
Požadavky
Zápočet: zápočtový test.Zkouška: písemná část - 3 příklady, 2 vyučovací hodiny, ústní část - 2 otázky. U všech otázek je hlavní důraz kladen na algoritmické aspekty daného problému (tj. algoritmy řešení a jejich výpočetní složitost).
Garant
Prof. RNDr. Zdeněk Ryjáček, DrSc.
Vyučující
Prof. RNDr. Zdeněk Ryjáček, DrSc.RNDr. Mgr. Jakub Teska, Ph.D.RNDr. Jan Ekstein, Ph.D.RNDr. Mgr. Jakub Teska, Ph.D.