• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2019.tde-24092019-181655
Document
Auteur
Nom complet
Yan Soares Couto
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2019
Directeur
Jury
Fernandes, Cristina Gomes (Président)
Franco, Álvaro Junior Pereira
Stolfi, Jorge
Titre en portugais
Estrutura de dados persistentes
Mots-clés en portugais
Árvores rubro-negras
Estruturas de dados
Localização de ponto
Persistência
Resumé en portugais
Estruturas de dados (EDs) permitem operações de acesso e de modificação; operações de acesso apenas consultam um ou mais campos de uma ED, enquanto operações de modificação podem alterar os campos da estrutura. Dizemos que, ao realizar uma operação de modificação, criamos uma nova versão da ED. Uma ED é parcialmente persistente se permite apenas operações de acesso a versões anteriores e modificação apenas na versão mais nova, e totalmente persistente se também permite operações de modificação em todas as versões. Esta dissertação apresenta a descrição e implementação de uma versão total ou parcialmente persistente de várias estruturas: pilhas, filas, deques e árvores rubro-negras. Também são discutidas técnicas gerais para tornar persistentes certas classes de estruturas de dados. Por fim, é apresentada uma solução ao problema de localização de ponto, que usa uma árvore de busca binária persistente.
Titre en anglais
Persistent data structures
Mots-clés en anglais
Data structures
Persistence
Point location
Red-black trees
Resumé en anglais
Data structures (DSs) allow access and update operations; access operations only allow accessing the value of one or more fields of the DS, while update operations allow modifying the fields of the structure. We say that, whenever an update operation is done, a new version of the DS is created. A DS is partially persistent if it allows access operations to previous versions of the structure and update operations only on the newest version, and totally persistent if it also allows update operations on all versions. This dissertation presents the description and implementation of totally or partially persistent versions of several data structures: stacks, queues, deques, and red-black trees. General techniques to make certain classes of DSs persistent are also discussed. At last, a solution to the point location problem, using a persistent binary search tree, is presented.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
main.pdf (763.96 Kbytes)
Date de Publication
2019-09-25
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.