Show simple item record

dc.contributor.authorTavares, Rui Alberto Ecke Tavarespt_BR
dc.contributor.authorDuarte Junior, Elias Procopiopt_BR
dc.contributor.otherUniversidade Federal do Paraná. Setor de Ciencias Exatas. Programa de Pós-Graduaçao em Informáticapt_BR
dc.date.accessioned2011-02-10T19:37:18Z
dc.date.available2011-02-10T19:37:18Z
dc.date.issued2011-02-10
dc.identifier.urihttp://hdl.handle.net/1884/25119
dc.description.abstractResumo: As árvores binárias são estruturas de dados utilizadas tradicionalmente para a realização de pesquisa de forma eficiente sobre um conjunto de dados. Uma árvore pode atingir grandes dimensões, bem como ser utilizada para armazenar dados em memória secundária ou distribuídos pelos nodos de uma rede de computadores. Nestes casos, é necessário definir uma estratégia eficiente para o acesso aos dados da árvore, que são organizados em páginas. Uma página é utilizada para a transferência de dados em blocos da memória secundária para a primária, além do acesso remoto em redes de computadores, por intermédio de pacotes que possuem tamanho máximo pré-fíxado. Este trabalho apresenta um algoritmo para a paginação de árvores binárias de pesquisa aplicável quando o conjunto de informações é estático, as freqüências de acesso não são conhecidas e o armazenamento é remoto ou secundário. O algoritmo visa reduzir o tempo de pesquisa aos dados armazenados na árvore binária em termos do número de páginas visitadas e do aumento da taxa de preenchimento das páginas utilizadas. Uma versão alternativa do algoritmo que visa reduzir a distância internodal nas páginas é apresentada. Observou-se que o algoritmo proposto constrói a paginação ótima quando possível, isto é, quando a árvore é completa e o número de nodos é múltiplo do tamanho da página. Além disso, propõe-se uma política eficiente para o preenchimento das páginas de uma árvore binária degenerada tendo por base a aplicação de empacotamento unidimensional na franja da árvore. A complexidade computacional do algoritmo, que depende do empacotamento unidimensional a ser utilizado, é discutida e apresentada. O algoritmo foi implementado e resultados experimentais quanto ao número de páginas visitadas e à taxa de preenchimento das páginas utilizadas, comparativos com a paginação seqüencial, valores ótimos teóricos e as árvores B, são descritos e analisados. Comparando o algoritmo proposto com as árvores B, enquanto o número de paginas visitadas por pesquisa é similar em ambas as abordagens, a taxa de preenchimento das páginas produzida pelo algoritmo proposto é mais de 30% superior à taxa obtida pelas árvores B.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.languagePortuguêspt_BR
dc.subjectTesespt_BR
dc.subjectAlgoritmospt_BR
dc.subjectArvores binariaspt_BR
dc.subjectEmpacotamento e cobertura combinatóriapt_BR
dc.titleUm algoritmo para paginaçao de árvores binárias de pesquisa utilizando empacotamento unidimensionalpt_BR
dc.typeDissertaçãopt_BR


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record