Předmět Dynamické grafové datové struktury (NTIN023)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN023 - Dynamické grafové datové struktury, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Naučit základy dynamických datových struktur, zaměřených na grafy.
Sylabus
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(mlog 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)
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
Garant
Mgr. Vladan Majerech, Dr.