PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Grafové algoritmy II - NDMI088
Anglický název: Graph Algorithms II
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: http://mj.ucw.cz/vyuka/ga2
Garant: Mgr. Martin Mareš, Ph.D.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (02.05.2013)

Přednáška pojednává o pokročilejších grafových algoritmech, technikách jejich návrhu a příbuzných datových strukturách. Tematicky navazuje na Grafové algoritmy (NDMI010).
Literatura -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (02.05.2013)

Alexander Schrijver: Combinatorial Optimization, Springer, 2003

Martin Mareš: Krajinou grafových algoritmů, ITI, Praha, 2007. Dostupné online na http://mj.ucw.cz/vyuka/ga/.

Sylabus -
Poslední úprava: doc. Mgr. Milan Hladík, Ph.D. (02.05.2013)

Toky v sítích: Goldbergův algoritmus a jeho varianty.

Zrychlení tokových algoritmů v řídkých sítích pomocí Sleatorových-Tarjanových stromů.

Popis minimálních řezů pomocí Gomory-Hu Trees.

Datové struktury pro práci s celými čísly: Van Emde-Boasovy stromy, Q-haldy, atomické haldy.

Minimální kostry: Celočíselné algoritmy, verifikace minimality,

Pettieho optimální algoritmus.

 
Univerzita Karlova | Informační systém UK