Předmět Teorie grafů, optimalizace a složitost 2 (KMA / TGD2)
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 / TGD2 - Teorie grafů, optimalizace a složitost 2, 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
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.
Získané způsobilosti
Student bude schopen po absolvování předmětu:- ovládat základní optimalizační úlohy na grafech a sítích,- aktivně používat metody a algoritmy řešení jednotlivých úloh,- používat vzájemné převody úloh,- rozumět výpočetní složitosti jednotlivých problémů a u NP-těžkých problémů ovládat základní heuristické a aproximační algoritmy.
Literatura
http://www.kma.zcu.cz/TGD2Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989. Plesník, Ján; Dupačová, Jitka; Vlach, Milan. Lineárne programovanie. 1. vyd. Bratislava : Alfa, 1990. ISBN 80-05-00679-9.
Požadavky
U studentů se předpokládají znalosti algoritmické teorie grafů a základů teorie výpočetní složitosti v rozsahu předmětu KMA/TGD1.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.Prof. RNDr. Zdeněk Ryjáček, DrSc.