Comparison of Top trees implementations

• Název práce v češtině: Porovnání implementací Top stromů
• Název v anglickém jazyce: Comparison of Top trees implementations
• Klíčová slova: Top Trees, Složitost, Implementace
• Klíčová slova anglicky: Top Trees, Complexity, Implementation
• Akademický rok vypsání: 2016/2017
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: Mgr. Vladan Majerech, Dr.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 29.03.2017
• Datum zadání: 29.03.2017
• Datum potvrzení stud. oddělením: 07.04.2017
• Datum a čas obhajoby: 06.06.2018 09:00
• Datum odevzdání elektronické podoby: 11.05.2018
• Datum odevzdání tištěné podoby: 11.05.2018
• Datum proběhlé obhajoby: 06.06.2018
• Oponenti: Mgr. Martin Mareš, Ph.D.

Zásady pro vypracování

Autor implementuje Top Tree drivery 1. na základě "Self Adjusting Top Trees" a 2. na základě transformace "Topology Trees".
Implementace 1 negarantuje dobré chování v nejhorším případě, ale garantuje asymptoticky stejné časy, které implementace 2 dosahuje v nejhorším případě.
Multiplikativní konstanty implementace 1 očekáváme mnohem menší než u implementace 2.
Implementace 2 umožňuje při pro vyhodnocování dotazů zamrazit stav datové struktury,
provádět jen částečné modifikace a na konci dotazu vrátit datovou strukturu do zamraženého stavu.
U implementace 1 vypínání některých modifikací nepřichází v úvahu, návratem zpět bychom přišli o amortizační argumenty.

Příkladem použití Top Trees s vhodností vypínat aktualizace je udržování struktury pro komponenty hranové dvousouvislosti. Aktualizace dokáží obě implementace
provádět v O(log^4 n) amortizovaně. Dotazy na existenci mostu mezi dvěma body dokáže implementace 1 v čase O(log^3 n) amortizovaně, zatímco implementace 2 v čase O(log n) v nejhorším případě.

Odhad poměru multiplikativních konstant těchto dvou implementací naznačí do jaké velikosti dat je vhodnější preferovat implementaci 1 před implementací 2.

Seznam odborné literatury

Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity", Journal of the ACM (JACM), Vol. 48 Issue 4(July 2001), 723–760

Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup "Maintaining information in fully dynamic trees with top trees", ACM Transactions on Algorithms (TALG), Vol. 1 (2005), 243–264

Robert E. Tarjan, Renato F. Werneck "Self-adjusting Top Trees", Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05), 813-822

Greg N. Frederickson "Ambivalent data structures for 2-edge-connectivity and k-smallest spanning trees"