UNIFEI - Campus 1: Itajubá PPG - Programas de Pós Graduação Dissertações
Use este identificador para citar ou linkar para este item: https://repositorio.unifei.edu.br/jspui/handle/123456789/2330
Tipo: Dissertação
Título: Estruturas de dados retroativas: aplicações na dinamização de algoritmos
Autor(es): ANDRADE JÚNIOR, José Wagner de
Primeiro Orientador: SEABRA, Rodrigo Duarte
Resumo: A retroatividade em programação é um conceito que pode ser definido como o estudo da modificação da linha temporal em uma estrutura de dados, bem como a análise dos efeitos dessa modificação através de toda a sua existência. Em geral, essa análise e implementação tendem a serem mais custosas do ponto de vista computacional, observando-se que uma modificação no passado pode gerar um efeito cascata por toda a existência dessa estrutura. O conceito de retroatividade gera ferramentas e estruturas que otimizam as soluções para a natureza desses problemas temporais. Esse tipo de estrutura pode ser utilizada nas aplicações das mais diversas naturezas, desde em algoritmos de caminho mínimo, aplicações em segurança e até em aplicações geométricas. Nessa dissertação, tem-se os subsídios teóricos sobre essas estruturas, um material detalhado sobre a implementação das estruturas mais comuns utilizando o paradigma da retroatividade, e a implementação de alguns problemas que podem ser resolvidos utilizando técnicas de retroatividade, como, por exemplo, o algoritmo de árvore geradora mínima totalmente dinâmica. Para cada estrutura, foram executados testes práticos sobre as estruturas retroativas e seu desempenho foi comparado às outras implementações dessas mesmas estruturas. Os testes mostraram que as implementações retroativas propostas por Demaine et. al (2007) obtiveram os melhores resultados do ponto de vista temporal. Além disso, foram propostos dois algoritmos que utilizam os conceitos de retroatividade para sua construção: o algoritmo para o problema da árvore geradora mínima totalmente retroativa e o algoritmo do caminho mínimo a partir de um vértice inicial fixo em grafos dinâmicos. Seja m o tamanho da linha temporal em que a estrutura está implementada, V(G) e A(G) o conjunto de vértices e arestas de um grafo G respectivamente. Foi alcançada a complexidade de tempo amortizada de O(√m· log |V(G)|) por operação de atualização ou consulta, para o problema da árvore geradora mínima totalmente retroativa. Para o algoritmo do caminho mínimo, a partir de um vértice inicial fixo em grafos dinâmicos, por meio do algoritmo proposto por Sunita et. al [52], foi obtida a complexidade temporal de O(|A(G)| · lg |V(G)|) por modificação, utilizando filas de prioridade com retroatividade não-consistente.
Abstract: The retroactivity in programming is the study of a modification in a timeline for a data structure and the effects that this modification exerts throughout its existence. In general, the analysis and implementation tend to be more costly computationally, because a modification on these data structure in the past can generate a cascade effect through all the data structure timeline. The concept of retroactivity generates tools and structures that optimize the solutions facing these temporal problems. This type of data structure can be used in, for example, shortest path algorithms, security applications, and geometric problems. In this thesis, we have the theoretical subsidies about these data structures, a detailed material about the implementation of this structures, using retroactivity, and the implementation of some problems that retroactivity can be used, for example, the fully dynamic minimum spanning tree problem. For each data structure, we executed practical tests about this data retroactive data structures and a comparison between these solutions and other approaches. The tests showed that the retroactive implementations proposed by Demaine et. al (2007) [13] obtained the best results from a temporal point of view. It was proposed two algorithms which used the retroactivity concepts inside its development: the fully retroactive minimum spanning tree and the single source dynamic shortest path problem in dynamic graphs. Let m be data structure’s timeline, V(G) and A(G) the sets of vertices and edges from graph G. We reached an amortized time complexity O( √ m· lg |V(G)|) per query/update operation in the fully retroactive minimum spanning tree algorithm. The algorithm to solve the single source dynamic shortest path problem in dynamic graphs proposed by Sunita et. al [52] obtained a time complexity O(|A(G)| · lg |V(G)|) per modification using a non-oblivious retroactive priority queue.
Palavras-chave: Retroatividade
Estrutura de dados
Geometria computacional
Grafos
CNPq: CNPQ::CIÊNCIAS EXATAS E DA TERRA::CIêNCIA DA COMPUTAÇÃO
Idioma: por
País: Brasil
Editor: Universidade Federal de Itajubá
Sigla da Instituição: UNIFEI
metadata.dc.publisher.department: IESTI - Instituto de Engenharia de Sistemas e Tecnologia da Informação
metadata.dc.publisher.program: Programa de Pós-Graduação: Mestrado - Ciência e Tecnologia da Computação
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.unifei.edu.br/jspui/handle/123456789/2330
Data do documento: 9-Jun-2020
Aparece nas coleções:Dissertações

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Dissertação_2021056.pdf2.2 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.