Předměty

Váš prohlížeč nepodporuje JavaScript nebo je jeho podpora vypnutá. Některé funkce nemusejí být dostupné.

Grafové algoritmy 2 - NDMI088

Anglický název:	Graph Algorithms 2
Zajišťuje:	Katedra aplikované matematiky (32-KAM)
Fakulta:	Matematicko-fyzikální fakulta
Platnost:	od 2023
Semestr:	letní
E-Kredity:	3
Rozsah, examinace:	letní s.:2/0, Zk [HT]
Počet míst:	neomezen
Minimální obsazenost:	neomezen
4EU+:	ne
Virtuální mobilita / počet míst pro virtuální mobilitu:	ne
Stav předmětu:	vyučován
Jazyk výuky:	čeština, angličtina
Způsob výuky:	prezenční
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

Výsledky anket Termíny zkoušek Rozvrh LS Nástěnka

Anotace -

Poslední úprava: prof. 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).

Podmínky zakončení předmětu

Poslední úprava: Mgr. Martin Mareš, Ph.D. (02.03.2018)

Předmět je zakončen zkouškou, u níž se ověřuje porozumění látce z přednášky a schopnost aplikovat ji na řešení obdobných problémů.

Literatura -

Poslední úprava: prof. 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: prof. 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.