PředmětyPředměty(verze: 901)
Předmět, akademický rok 2022/2023
  
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 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: Mgr. Vladan Majerech, Dr.
Třída: Informatika Mgr. - Matematická lingvistika
Kategorizace předmětu: Informatika > Teoretická informatika
Prerekvizity : NTIN062
Je prerekvizitou pro: NTIN032
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: ()
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.
Cíl předmětu
Poslední úprava: T_KTI (23.05.2008)

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

Podmínky zakončení předmětu
Poslední úprava: Mgr. Vladan Majerech, Dr. (06.10.2017)

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.

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

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

Sylabus -
Poslední úprava: T_KTI (24.05.2004)

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)

 
Univerzita Karlova | Informační systém UK