|
|
|
||
Poslední úprava: ()
|
|
||
Poslední úprava: T_KTI (23.05.2008)
Naučit základy dynamických datových struktur, zaměřených na grafy. |
|
||
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. |
|
||
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 |
|
||
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) |