Modelování dynamických stromů
| Název práce v češtině: | Modelování dynamických stromů |
|---|---|
| Název v anglickém jazyce: | Modelling Dynamic Trees |
| Akademický rok vypsání: | 2006/2007 |
| Typ práce: | diplomová práce |
| Jazyk práce: | čeština |
| Ústav: | Katedra softwarového inženýrství (32-KSI) |
| Vedoucí / školitel: | RNDr. Kamil Toman |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 13.11.2006 |
| Datum zadání: | 13.11.2006 |
| Datum a čas obhajoby: | 26.05.2008 00:00 |
| Datum odevzdání elektronické podoby: | 26.05.2008 |
| Datum proběhlé obhajoby: | 26.05.2008 |
| Oponenti: | doc. RNDr. Irena Holubová, Ph.D. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| [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. |
| Předběžná náplň práce |
| Cílem práce je navrhnout a implementovat programové prostředí pro aplikační využití dynamických datových struktur. |
| Předběžná náplň práce v anglickém jazyce |
| The aim of this work is to design and implement a programing framework for application usage of dynamic data structures. |