Título: Um estudo sobre a otimalidade dinâmica de BSTs

Data: 26/04/2019

Horário: 13:00h

Local: Hall do Centro de Ciências - Bloco 902

Resumo:

Neste trabalho apresentaremos um problema clássico de árvores binária de busca de buscar ou, do inglês, Binary Search Tree – BST, que é buscar por uma sequência de chaves em uma BST e é permitido reestruturar a árvore depois de cada busca. Apesar de décadas de pesquisa, uma questão fundamental sobre as BSTs permanece sem solução: qual é a "melhor estrutura BST”? Um algoritmo BST é offline se a sequência de buscas é conhecida a princípio e é online se as buscas são conhecidas incrementalmente. Um algoritmo BST online é f(n)-competitivo se seu desempenho é limitado por uma função f(n) do desempenho do algoritmo ótimo offline. Dizemos que um algoritmo BST A é dinamicamente ótimo se dada uma sequência de buscas S, A é O(1)-competitivo. Sleator e Tarjan apresentaram a árvore Splay e conjecturaram que essa árvore é dinamicamente ótima. No entanto, ainda não foi provado que árvores Splay, ou qualquer outra BST, é dinamicamente ótima. Alguns limitantes para OPT(S) foram propostos. Lucas propôs um algoritmo BST offline guloso para encontrar um limite superior, e conjeturou que seu algoritmo fornece uma aproximação de fator constante para OPT(S). Recentemente foram apresentadas as árvores Tango e Multisplay, que são ln ln n-competitiva.

Banca:

• Prof. Dr. Victor Almeida Campos (MDCC/UFC - Orientador)
• Prof.ª Dr.ª Cláudia Linhares Sales (MDCC/UFC)
• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC)