Předmět Grafové algoritmy (NDMI010)
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 NDMI010 - Grafové algoritmy, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
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í.
Literatura
Robert E. Tarjan: Data Structures and Network Algorithms, Philadelphia, 1983Luděk Kučera: Kombinatorické algoritmy, SNTL, 1989Alexander Schrijver: Combinatorial Optimization, Springer, 2003Martin Mareš: Krajinou grafových algoritmů, ITI, Praha, 2007. Dostupné online na http://mj.ucw.cz/vyuka/ga/.
Garant
Mgr. Martin Mareš, Ph.D.