|
|
||
Poslední úprava: Mgr. Martin Mareš, Ph.D. (28.04.2013)
|
|
||
Poslední úprava: Mgr. Martin Mareš, Ph.D. (24.09.2020)
Ústní zkouška, může být vedena distančně. |
|
||
Poslední úprava: Mgr. Martin Mareš, Ph.D. (24.04.2012)
Robert E. Tarjan: Data Structures and Network Algorithms, Philadelphia, 1983
Luděk Kučera: Kombinatorické algoritmy, SNTL, 1989
Alexander Schrijver: Combinatorial Optimization, Springer, 2003
Martin Mareš: Krajinou grafových algoritmů, ITI, Praha, 2007. Dostupné online na http://mj.ucw.cz/vyuka/ga/. |
|
||
Poslední úprava: Mgr. Martin Mareš, Ph.D. (11.10.2017)
Ke zkoušce je nutné rozumět teorii z přednášky a být schopen ji aplikovat. |
|
||
Poslední úprava: Mgr. Martin Mareš, Ph.D. (28.04.2013)
Toky v sítích: Dinicův algoritmus, algoritmus Tří Indů, metody pro řídké sítě a sítě s celočíselnými kapacitami.
Testování k-souvislosti grafů: hledání řezů a separátorů pomocí toků, Kargerův-Steinův pravděpodobnostní algoritmus.
Nejkratší cesty: Obecné relaxační schéma, Dijkstrův algoritmus a datové struktury pro něj (haldy, jedno- a víceúrovňové přihrádky). Potenciálová redukce a na ní založené heuristiky. Algebraické souvislosti s násobením matic, Kleeneho algebry. Tranzitivní uzávěry a Seidelův algoritmus.
Minimální kostry: Fredmanův-Tarjanův algoritmus pro obecné grafy, Fredmanův-Willardův pro celočíselné váhy a speciální algoritmy pro rovinné grafy a minorově uzavřené třídy.
Techniky dekompozice stromů: clusterizace a micro/macro-tree dekompozice, problém stromových předchůdců a Union-Find problem.
Převod řetězcových problémů na grafové: suffixové stromy a jejich konstrukce v lineárním čase.
Testování rovinnosti grafů a konstrukce rovinných nakreslení. |