Název:
Porovnání implementací Top stromů
Překlad názvu:
Comparison of Top trees implementations
Autoři:
Setnička, Jiří ; Majerech, Vladan (vedoucí práce) ; Mareš, Martin (oponent) Typ dokumentu: Diplomové práce
Rok:
2018
Jazyk:
eng
Abstrakt: [eng][cze] Comparison of Top trees implementations - Abstract Jiří Setnička Definition and description of Top trees and introduction of problems solvable by them including problem of edge 2-connectivity. Definition and description of Topology trees used as one of the drivers for Top trees. After the initial descriptions the two top trees implementations are introduced: one based on self adjusting trees, second based on topology trees. Comparison of these implementations is done by two experiments. Measurements are discussed in conclusion - results corresponds with initial estimates but with different multiplicative constant than expected. 1Porovnání implementací Top stromů - Abstrakt Jiří Setnička Definice a zavedení Top stromů a představení problémů, které se jimi dají efektivně řešit včetně problému hranové 2-souvislosti. Definice a zavedení topologických stromů, které jsou následně použity jako jeden z driverů pro Top stromy. Po úvodním seznámení s problematikou jsou představeny dvě implementace: jedna založená na samovyvažujících se stromech a druhá založená na topologických stromech. Porovnání obou imple- mentací je provedeno na dvou experimentech. Naměřené hodnoty jsou diskutovány v závěru - výsledky korespondují s úvodními odhady, ale s výrazně odlišnými multiplikativními konstantami, než bylo před- pokládáno. 1
Klíčová slova:
Implementace; Složitost; Top Trees; Complexity; Implementation; Top Trees