Listas de Prioridades Cinéticas
Autores
|
2241 |
257,613
|
|
|
2242 |
257,613
|
Informações:
Publicações do PESC
Uma estrutura de dados cinética visa determinar, ao longo do tempo, um atributo geométrico de um conjunto de objetos em movimento contínuo. 0 atributo mais simples e natural de um conjunto de números reais e o elemento de valor máximo do conjunto. Uma lista de prioridades cinética e um tipo especial de estrutura de dados cinética que determina este elemento máximo ao longo do tempo, quando os elementos variam continuamente com o tempo. Alem da variação dos elementos, as listas de prioridades cinéticas permitem que, a qualquer instante, elementos sejam inseridos ou removidos. Devido ao grande interesse prático e teórico nessas estruturas, várias construções foram sugeridas na literatura. Nesta tese, apresentamos as estruturas mais conhecidas, assim como uma nova estrutura descoberta pelo autor, 0 hanger cinético. Apresentamos também a análise de complexidade das estruturas, incluindo a análise justa de um caso do heap cinético realizada pelo autor.
Kinetic data structures compute a geometric atribute in a set of continuosly moving objects. The most natural atribute in a set of real numbers is the maximum element contained in the set. A kinetic priority queue is a special kinetic data structure, which determines this maximum element along time, when the elements change continuously with time. Kinetic priority queues also support insertions and deletions of elements, at any time. Due to the large practical and theoretical interest in these structures, many different constructions have been suggested in the literature. In this thesis, we present the most famous structures, and a new structure discovered by the author, the kinetic hanger. We also present the complexity analysis of the structures, including the author's tight analysis of a special case of the kinetic heap.