|
|
Modelování dynamických stromů
Vajbar, Michal ; Holubová, Irena (oponent) ; Toman, Kamil (vedoucí práce)
Existuje velké množství algoritmů, které pracují se stromovými grafy. Různé algoritmy mohou pro své potřeby reprezentovat stejný strom prostřednictvím odlišných datových struktur. Chceme-li provozovat více takových algoritmů současně nad jedním lesem, může se stát, že každý bude potřebovat svou vlastní reprezentaci tohoto lesa. Pokud se les navíc průběžně mění přidáváním a odebíráním hran, musí se tyto změny přenášet do datových struktur všech provozovaných algoritmů. Takový postup však není efektivní. Bylo navrženo několik datových struktur, nad kterými lze současně provozovat různé stromové algoritmy. Každá z těchto struktur vyniká některými vlastnostmi, ale má také své slabiny. Rozumný kompromis představují Top-stromy. V této práci se zabýváme Top-stromy. Nejprve vytvoříme implementaci Top-stromů a celou ji podrobně popíšeme. Speciálně pro sestavování algoritmů nad navrženou datovou strukturou pak vyvineme programovací jazyk Top Tree Friendly Language (TFL). Kombinuje v sobě deklarativní přístup s procedurálním, čímž velmi zjednodušuje a urychluje návrh stromových algoritmů. Nakonec vytvoříme dotazovací jazyk Top Tree Query Language (TQL), který umožňuje naši strukturu pohodlně spravovat. Implementace Top-stromů, programovací jazyk TFL a dotazovací jazyk TQL dohromady tvoří komplexní řešení pro práci s...
|
host ::
RSS.