Texto completo
| |
| Autor(es): |
Yan Soares Couto
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | São Paulo. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Data de defesa: | 2019-01-08 |
| Membros da banca: |
Cristina Gomes Fernandes;
Álvaro Junior Pereira Franco;
Jorge Stolfi
|
| Orientador: | Cristina Gomes Fernandes |
| Resumo | |
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. (AU) | |
| Processo FAPESP: | 17/05481-8 - Estruturas de dados avançadas |
| Beneficiário: | Yan Soares Couto |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |