Um algoritmo para paginaçao de árvores binárias de pesquisa utilizando empacotamento unidimensional

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciencias Exatas. Programa de Pós-Graduaçao em Informática-
Autor(es): dc.creatorTavares, Rui Alberto Ecke Tavares-
Autor(es): dc.creatorDuarte Junior, Elias Procopio-
Data de aceite: dc.date.accessioned2019-08-22T00:44:38Z-
Data de disponibilização: dc.date.available2019-08-22T00:44:38Z-
Data de envio: dc.date.issued2011-02-10-
Data de envio: dc.date.issued2011-02-10-
Data de envio: dc.date.issued2011-02-10-
Fonte completa do material: dc.identifierhttp://hdl.handle.net/1884/25119-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/25119-
Descrição: dc.descriptionResumo: 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.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Palavras-chave: dc.subjectTeses-
Palavras-chave: dc.subjectAlgoritmos-
Palavras-chave: dc.subjectArvores binarias-
Palavras-chave: dc.subjectEmpacotamento e cobertura combinatória-
Título: dc.titleUm algoritmo para paginaçao de árvores binárias de pesquisa utilizando empacotamento unidimensional-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.