Název: Worst case driver pro Top stromy
Překlad názvu: Worst case driver for Top trees
Autoři: Ondráček, Lukáš ; Majerech, Vladan (vedoucí práce) ; Fink, Jiří (oponent)
Typ dokumentu: Diplomové práce
Rok: 2018
Jazyk: eng
Abstrakt: [eng] [cze]
A top tree data structure solves one of the most general variants of a well- studied dynamic trees problem consisting in maintenance of a tree along with some aggregated information on paths or in individual trees, possibly in a mutable way, under operations of inserting and removing edges. It provides a simple interface separated from both an internal top tree structure representing a hierarchical partitioning of the graph, and a driver ensuring its depth to be logarithmic, which has a crucial role for the efficiency of the data structure. The driver proposed in this thesis is based on biased trees, combining techniques used in the worst-case version of link/cut trees and in the amortized driver for top trees: An input forest is decomposed into heavy paths and interleaving vertices, all of them being represented by biased trees connected together to form exactly the top tree structure. The driver is meant to be a more efficient alternative to the originally proposed one, and a comparably efficient alternative to the driver proposed by Werneck; there is a room for their experimental comparison. Top strom je datová struktura řešící jednu z nejobecnějších variant pro- blému dynamických stromů, který spočívá v udržování lesa spolu s urči- tými souhrnnými informacemi na cestách nebo v jednotlivých stromech bě- hem přidávání a odebírání hran. Jednoduché rozhraní odděluje aplikaci od vnitřní struktury top stromu i od ovladače, který zajišťuje jeho logaritmic- kou hloubku a určuje celkovou efektivitu datové struktury. Ovladač popsaný v této práci je založen na biased trees a využívá techniky z worst-case verze link/cut stromů a amortizovaného ovladače top stromů: Vstupní les je roz- ložen na těžké cesty a mezilehlé vrcholy; obojí je reprezentováno jako biased trees, jejichž spojením vznikne struktura top stromu. Ovladač by měl být efektivnější alternativou k původně navrženému ovladači a srovnatelnou al- ternativou k ovladači, který navrhl Renato Werneck. Jejich experimentální srovnání může být předmětem dalšího výzkumu.
Klíčová slova: Biased Trees; Top Trees; Biased Trees; Top Trees

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/101914

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-388131


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce