Grafové algoritmy 2 - NDMI088

• Anglický název: Graph Algorithms 2
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2025
• 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í
• 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

Anotace

čeština

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

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)

angličtina

This course covers advanced graph algorithms, techniques of their design, and related data structures. It extends the Graph algorithms course (NDMI010).

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)

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

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

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

Literatura

čeština

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: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)

angličtina

Alexander Schrijver: Combinatorial Optimization, Springer, 2003

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)

Sylabus

čeština

• Testování rovinnosti grafů a konstrukce rovinných nakreslení.

• Výpočetní modely v grafových algoritmech: RAM vs. Pointer Machine,

vektorové operace na RAMu, dekompozice grafu na PM.

• Verifikace minimality koster, Komlósův algoritmus.

• Kargerův-Kleinův-Tarjanův randomizovaný algoritmus na minimální kostru.

• Soft haldy

• Pettieho optimální algoritmus na minimální kostru.

Poslední úprava: Maxová Jana, RNDr., Ph.D. (17.05.2025)

angličtina

Network flows: Goldberg's algorithm and its kin.

Accelerating flow algorithms on sparse graphs using Sleator-Tarjan Trees.

Description of minimum cuts by Gomory-Hu Trees.

Data structures for integers: Van Emde-Boas Trees, Q-Heaps, atomic heaps.

Minimum spanning trees: Integer algorithms, verification of minimality, Pettie's optimal algorithm.

Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (02.05.2013)