1. Repositório Institucional - Universidade Federal de Uberlândia
  2. Faculdade de Computação (FACOM)
  3. TCC - Ciência da Computação
Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/33566
Full metadata record
DC FieldValueLanguage
dc.creatorOliveira, Gustavo Nunes de-
dc.date.accessioned2021-11-29T11:42:20Z-
dc.date.available2021-11-29T11:42:20Z-
dc.date.issued2021-11-03-
dc.identifier.citationOLIVEIRA, Gustavo Nunes de. Avaliação experimental de estruturas de dados compactas na construção de grafos temporais compactos. 2021. 45 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) – Universidade Federal de Uberlândia, Uberlândia, 2021.pt_BR
dc.identifier.urihttps://repositorio.ufu.br/handle/123456789/33566-
dc.languageporpt_BR
dc.publisherUniversidade Federal de Uberlândiapt_BR
dc.rightsAcesso Abertopt_BR
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
dc.subjectEstruturas de dadospt_BR
dc.subjectGrafopt_BR
dc.subjectTemporalpt_BR
dc.subjectCompactopt_BR
dc.subjectExperimentalpt_BR
dc.titleAvaliação experimental de estruturas de dados compactas na construção de grafos temporais compactospt_BR
dc.typeTrabalho de Conclusão de Cursopt_BR
dc.contributor.advisor1Albertini, Marcelo Keese-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/1404596833493304pt_BR
dc.contributor.referee1Razente, Humberto Luiz-
dc.contributor.referee1Latteshttp://lattes.cnpq.br/4700164571979002pt_BR
dc.contributor.referee2Louza, Felipe Alves da-
dc.contributor.referee2Latteshttp://lattes.cnpq.br/7042349168112978pt_BR
dc.description.degreenameTrabalho de Conclusão de Curso (Graduação)pt_BR
dc.description.resumoCom o aumento na geração de dados causado pelos avanços tecnológicos das últimas dé- cadas, é crucial que seja possível armazenar e manipular tais dados em memória principal por meio de estruturas de dados que armazenam as informações de forma eficiente. Diversas estruturas de dados foram criadas para representar grafos temporais utilizando estruturas de dados compactas, visando alcançar uma diminuição no uso de memória mantendo o desempenho em tempo para realizar consultas no grafo. Dentre as estruturas de dados para grafos temporais analisadas neste trabalho estão as listas de adjacência tradicionais, assim como as estruturas Adjacency Log of Events (EveLog) (CARO; RO- DRÍGUEZ; BRISABOA, 2015), Time-Interval Log Per Edge (EdgeLog) (XUAN; FER- REIRA; JARRY, 2003) e Compact Adjacency Sequence (CAS) (CARO; RODRÍGUEZ; BRISABOA, 2015), que utilizam representações compactas de arrays e bitvectors, assim como wavelet trees para sua construção. Devido à escassez de referências de implementações das estruturas de grafos temporais compactos analisadas neste trabalho, as mesmas foram implementadas sem um referencial prático, baseadas apenas nas suas respectivas propostas teóricas. Foi utilizado no projeto o paradigma de orientação a objetos, assim como testes unitários para garantir que as operações foram implementadas de maneira correta. Além disso, toda a implementação foi feita pensando em obter um bom desempenho, de forma modularizada, clara e de fácil manutenção. Após a implementação das estruturas de dados analisadas no trabalho utilizando as téc- nicas escolhidas, foram executados experimentos para analisar a eficiência do uso de me- mória e tempo médio por consulta para cada estrutura de grafos temporais, utilizando geradores de grafos temporais aleatórios para gerar os dados de entrada para os testes. Os experimentos mostraram um resultado inferior das implementações de estruturas de grafos temporais compactos em relação à abordagem utilizando listas de adjacência tradi- cionais, tanto em uso de memória quanto em desempenho por operação, o que indica que as implementações feitas neste projeto não conseguiram alcançar na prática o resultado previsto pelas estruturas teoricamente. Entretanto, ainda que os resultados obtidos não satisfizeram o que era proposto teorica- mente, as implementações feitas podem servir como referencial para trabalhos futuros, para buscar alcançar o que foi proposto de forma teórica na prática ou analisar estruturas semelhantes que não fizeram parte do escopo deste trabalho.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.courseCiência da Computaçãopt_BR
dc.sizeorduration45pt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAOpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO::ENGENHARIA DE SOFTWAREpt_BR
dc.orcid.putcode103955495-
Appears in Collections:TCC - Ciência da Computação

Files in This Item:
File Description SizeFormat 
AvaliaçãoExperimentalEstruturas.pdf3.93 MBAdobe PDFThumbnail
View/Open
Show simple item record


This item is licensed under a Creative Commons License Creative Commons