Repositório UNIFEI 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
Registro completo de metadados
Campo DCValorIdioma
dc.creatorANDRADE JÚNIOR, José Wagner de-
dc.date.issued2020-06-09-
dc.identifier.urihttps://repositorio.unifei.edu.br/jspui/handle/123456789/2330-
dc.description.abstractThe 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.pt_BR
dc.description.sponsorshipAgência 1pt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal de Itajubápt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectRetroatividadept_BR
dc.subjectEstrutura de dadospt_BR
dc.subjectGeometria computacionalpt_BR
dc.subjectGrafospt_BR
dc.titleEstruturas de dados retroativas: aplicações na dinamização de algoritmospt_BR
dc.typeDissertaçãopt_BR
dc.date.available2021-03-15-
dc.date.available2021-03-15T13:04:18Z-
dc.date.accessioned2021-03-15T13:04:18Z-
dc.creator.Latteshttp://lattes.cnpq.br/84814011126713pt_BR
dc.contributor.advisor1SEABRA, Rodrigo Duarte-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/1450824752280712pt_BR
dc.description.resumoA 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.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentIESTI - Instituto de Engenharia de Sistemas e Tecnologia da Informaçãopt_BR
dc.publisher.programPrograma de Pós-Graduação: Mestrado - Ciência e Tecnologia da Computaçãopt_BR
dc.publisher.initialsUNIFEIpt_BR
dc.subject.cnpqCNPQ::CIÊNCIAS EXATAS E DA TERRA::CIêNCIA DA COMPUTAÇÃOpt_BR
dc.relation.referencesANDRADE JÚNIOR, José Wagner de. Estruturas de dados retroativas: aplicações na dinamização de algoritmos. 2020. 147 f. Dissertação (Mestrado em Ciência e Tecnologia da Computação.) – Universidade Federal de Itajubá, Itajubá, 2020.pt_BR
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.