Dynamické grafové datové struktury - NTIN023

• Anglický název: Dynamic Graph Data Structures
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2015
• 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: čeština
• Způsob výuky: prezenční
• Garant: Mgr. Vladan Majerech, Dr.
• Vyučující: Mgr. Vladan Majerech, Dr.
• Třída: Informatika Mgr. - Matematická lingvistika
• Kategorizace předmětu: Informatika > Teoretická informatika
• Prerekvizity : NTIN062
• Je prerekvizitou pro: NTIN032

Anotace

čeština

Amortizovaná složitost, dynamické datové struktury. Datové struktury charakterizující graf umožňující rychlé odpovědi na základní grafové otázky (souvislost, rovinnost), které je možno rychle modifikovat při postupných změnách grafu.

Poslední úprava: ()

angličtina

Amortized, randomized complexity. Dynamic structures representing graph, allowing fast queries for given basic graph properties (connectivity, planarity) and fast updates of underlaying graph.

Poslední úprava: T_KTI (10.04.2001)

Cíl předmětu

Naučit základy dynamických datových struktur, zaměřených na grafy.

Poslední úprava: T_KTI (23.05.2008)

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

Zkouška sestává z ústní části (při níž používáme tužku a papír).

Požadavky odpovídají sylabu přednášky v rozsahu prezentovaném na přednášce.

Poslední úprava: Majerech Vladan, Mgr., Dr. (06.10.2017)

Literatura

Majerech V.: Datové struktury. (Skripta v elektronické podobě, zatím obsahují pouze některé kapitoly, aktuální verzi je možno získat pomocí: anonymous ftp na @kti.ms.mff.cuni.cz v adresáři /usr/maj)

Westbrook J.: Disertační práce

Tarjan R.E.: Data structures and network algorithms. SIAM, 1983

Články

Poslední úprava: Zakouřil Pavel, RNDr., Ph.D. (05.08.2002)

Sylabus

čeština

Rozklad množiny na třídy ekvivalence, zvětšování tříd (inkrementální udržování komponent souvislosti grafu při přidávání hran).

Tentýž problém s možností backtrackingu nebo obecného odebírání hran.

Splay stromy.

Reprezentace topologie lesa pomocí 'stromů cest'.

Využití 'stromů cest' při hledání blokujícího toku ve vrstevnaté síti v čase $O(m\log m)$.

Využití 'stromů cest' pro inkrementální udržování bloků a bridgebloků.

Problém backtrackingu při údržbě bloků a bridgebloků.

'Cluster'izace - metoda údržby bloků a bridgebloků při obecné operaci delete (nejhorší případ).

'Sparsifikace' (Rozřeďování) - metoda urychlování datových struktur. (dvě obecné varianty, varianta pro rovinné grafy).

SPQR reprezentace (rovinných) grafů.

Top trees - hranově orientovaná clusterizace. Reprezentace topologických lesů s jednoduchým uživatelským rozhraním.

Aplikace Top trees pro udržování bridgebloků a bloků v amortizovaném polylogaritmickém čase a další aplikace Top trees jsou ponechány na Seminář o dynamických datových strukturách (TIN032)

Poslední úprava: T_KTI (24.05.2004)

angličtina

Disjoint Find Union (unions of equivalence classes starting from singletons) application on incremental connectivity (allowing edge insertions).

The same problem with backtracking.

Splay trees.

How to maintain topology of the forest using 'trees of paths'.

Application of 'trees of paths' - finding blocking flow in layered net in $O(m\log m)$ time.

Application of 'trees of paths' - maintaining bridge blocks or blocks.

Backtracking and maintainance of bridge blocks or blocks.

Clusterisation - maintainance of bridge blocks or blocks with arbitrary delete (worst case).

Sparsification - speeding up method for graph algorithms.

SPQR decomposition of plan(e/ar) graphs.

Top trees - edge oriented clusterisation. Tree representation with friendly user interface.

Application of Top trees on maintainance of bridge blocks and blocks in amortized polylog time, and other Top trees applications are left on TIN032.

Poslední úprava: T_KTI (24.05.2004)