Árvores binárias de busca e a Conjectura da Otimalidade Dinâmica (2024)
- Authors:
- Autor USP: BRAGA, BRUNO ARMOND - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: ESTRUTURAS DE DADOS; ALGORITMOS E ESTRUTURAS DE DADOS
- Keywords: Conjectura otimalidade dinâmica; Árvores binárias de busca; Árvores splay; Data structures; Dynamic optimality conjecture; Binary search trees; Splay trees
- Agências de fomento:
- Language: Português
- Abstract: Árvores binárias de busca são estruturas elementares na ciência da computação e sua eficiente capacidade de responder perguntas sobre um conjunto faz com quem elas sejam muito utilizadas e estudadas. Apesar desse vasto estudo, há questões primordiais em aberto sobre o custo ótimo de algoritmos de busca em ABBs para sequências de acesso arbitrárias. Nesse trabalho cobriremos a conjectura da otimalidade dinâmica que diz que árvores splays são assintoticamente tão eficientes quanto qualquer outra árvore para qualquer sequência de acessos. Além disso, cobriremos uma visão geométrica de buscas que é muito útil para caracterizar o custo ótimo e veremos como conseguir delimitar inferiormente custos de sequências de acesso a partir das delimitações da alternância e do funil. Por fim, veremos uma redução que mostra que o problema de múltiplas buscas em árvores binárias de busca é NP-completo.
- Imprenta:
-
ABNT
BRAGA, Bruno Armond. Árvores binárias de busca e a Conjectura da Otimalidade Dinâmica. 2024. Trabalho de Conclusão de Curso (Graduação) – Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, 2024. Disponível em: https://bdta.abcd.usp.br/directbitstream/1fbe1376-da43-43c5-a93b-a3f445a54224/3244194.pdf. Acesso em: 19 maio 2025. -
APA
Braga, B. A. (2024). Árvores binárias de busca e a Conjectura da Otimalidade Dinâmica (Trabalho de Conclusão de Curso (Graduação). Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo. Recuperado de https://bdta.abcd.usp.br/directbitstream/1fbe1376-da43-43c5-a93b-a3f445a54224/3244194.pdf -
NLM
Braga BA. Árvores binárias de busca e a Conjectura da Otimalidade Dinâmica [Internet]. 2024 ;[citado 2025 maio 19 ] Available from: https://bdta.abcd.usp.br/directbitstream/1fbe1376-da43-43c5-a93b-a3f445a54224/3244194.pdf -
Vancouver
Braga BA. Árvores binárias de busca e a Conjectura da Otimalidade Dinâmica [Internet]. 2024 ;[citado 2025 maio 19 ] Available from: https://bdta.abcd.usp.br/directbitstream/1fbe1376-da43-43c5-a93b-a3f445a54224/3244194.pdf
Download do texto completo
| Tipo | Nome | Link | |
|---|---|---|---|
 |
3244194.pdf | Direct link |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
