PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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.
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 -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (28.04.2013)
Obsah přednášky tvoří pokročilejší grafové algoritmy a techniky jejich návrhu.
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (24.09.2020)

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

Literatura
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/.

Požadavky ke zkoušce -
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.

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

 
Univerzita Karlova | Informační systém UK