Modelování dynamických stromů

• Thesis title in Czech: Modelování dynamických stromů
• Thesis title in English: Modelling Dynamic Trees
• Academic year of topic announcement: 2006/2007
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Software Engineering (32-KSI)
• Supervisor: RNDr. Kamil Toman
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 13.11.2006
• Date of assignment: 13.11.2006
• Date and time of defence: 26.05.2008 00:00
• Date of electronic submission: 26.05.2008
• Date of proceeded defence: 26.05.2008
• Opponents: doc. RNDr. Irena Holubová, Ph.D.

Guidelines

Prozkoumejte techniky, které lze využít pro efektivní reprezentaci dynamických stromů. Navrhněte způsob vyjadřování, který by umožnil deklarativní nebo funkcionální zápis dalších vlastností požadovaných pro aplikační algoritmické zpracování.

Cílem je vyvinout model chování, který by umožnil využívat konkrétní dynamické datové struktury bez nutnosti zásahů do jejich vnitřní implementace. Tento model by měl umožňoval rychlé a efektivní aplikační nasazení existujících datových struktur pro nové typy dynamických problémů.

Nedílnou součástí práce je implementace dle definovaných rozhraní pro jazyky C a Java.

References

[1] R.E. Tarjan, R.F. Werneck. Self-Adjusting Top Trees. Symposium on Discrete Algorithms. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Vancouver, British Columbia, p.813-822, 2005.

[2] S. Alstrup, J. Holm, K. de Lichtenberg, M. Thorup. Maintaining diameter, center, and median of fully-dynamic trees with top trees.
http://arxiv.org/abs/cs/0310065, 2003.

[3] G. N. Frederickson. A data structure for dynamically maintaining rooted trees. Journal of Algorithms, 24:37–65, 1997.

[4] D. D. Sleator and R. E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362–391, 1983.

[5] R. E. Tarjan. Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Mathematical Programming, 78(2):169–177, 1997.

[6] R. E. Tarjan. Amortized computational complexity. SIAM J. Alg. Disc. Meth., 6(2):306–318, 1985.

Preliminary scope of work

Cílem práce je navrhnout a implementovat programové prostředí pro aplikační využití dynamických datových struktur.

Preliminary scope of work in English

The aim of this work is to design and implement a programing framework for application usage of dynamic data structures.