• Login
    View Item 
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    •   DSpace Home
    • BIBLIOTECA DIGITAL: Teses & Dissertações
    • 40001016034P5 Programa de Pós-Graduação em Informática
    • Dissertações
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

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

    Thumbnail
    View/Open
    D - TAVARES, RUI ALBERTO ECKE.pdf (5.482Mb)
    Date
    2011-02-10
    Author
    Tavares, Rui Alberto Ecke Tavares
    Duarte Junior, Elias Procopio
    Metadata
    Show full item record
    Subject
    Teses
    Algoritmos
    Arvores binarias
    Empacotamento e cobertura combinatória
    xmlui.dri2xhtml.METS-1.0.item-type
    Dissertação
    Abstract
    Resumo: 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.
    URI
    http://hdl.handle.net/1884/25119
    Collections
    • Dissertações [471]

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_typeThis CollectionBy Issue DateAuthorsTitlesSubjectsxmlui.ArtifactBrowser.Navigation.browse_type

    My Account

    LoginRegister

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV