Grafové algoritmy - NDMI010

• Anglický název: Graph Algorithms
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní 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: angličtina, čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: http://mj.ucw.cz/vyuka/ga/
• Garant: Mgr. Martin Mareš, Ph.D.
• Vyučující: Mgr. Martin Mareš, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Matematická lingvistika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Obsah přednášky tvoří pokročilejší grafové algoritmy a techniky jejich návrhu.

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

angličtina

This course covers advanced graph algorithms and techniques of their design.

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

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

čeština

Ústní zkouška, může být vedena distančně.

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

angličtina

Oral examination, possibly in distance form.

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

Literatura

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: Mareš Martin, Mgr., Ph.D. (24.04.2012)

Požadavky ke zkoušce

čeština

Ke zkoušce je nutné rozumět teorii z přednášky a být schopen ji aplikovat.

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

angličtina

It is necessary to understand the theory presented at the lecture and to be able to apply it.

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

Sylabus

čeština

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í.

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

angličtina

Network flows: Dinic's algorithm, Malhotra-Kumar-Maheshwari blocking flows, methods for sparse networks and networks with integer capacities.

Testing of k-connectivity: searching for cuts and separators using flows, Karger-Stein's randomized algorithm.

Shortest paths: General relaxation scheme, Dijkstra's algorithm and related data structures (heaps, single- and multi-level buckets). Potential reduction and heuristics based on it. Algebraic connections with matrix multiplications, Kleene algebras. Transitive closures and Seidel's algorithm.

Minimum spanning trees: Fredman-Tarjan's algorithm for general graphs, Fredman-Willard's for integer weights and special algorithms for planar graphs and minor-closed graph classes.

Tree decomposition techniques: clusterization and micro/macro-tree decomposition, the tree ancestor problem and Union-Find problem.

Reduction of string problems to graph problems: suffix trees and their construction in linear time.

Testing of planarity and construction of plannar embeddings.

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