Defesa de Dissertação: George Edson Albuquerque Pinto

Sex, 26 de Março de 2021 15:02 | Escrito por Alan Vital Pereira | Imprimir

Título: Otimalidade dinâmica: Um survey
Data: 29/03/2021
Horário: 09:00
Local: Videoconferência
Resumo:
Árvores Binárias de Busca (BSTs) pertencem as estruturas de dados clássicas dentro da Ciência da Computação e que, apesar de sua simplicidade, possuem muitas questões em aberto após décadas de pesquisa. A principal questão em aberto sobre BSTs é a seguinte: “Qual é a melhor Árvore Binária de Busca sobre uma sequência de buscas qualquer de elementos da árvore?”. Em 1983, Sleator e Tarjan propuseram a Árvore Splay e conjecturaram que o custo para realizar qualquer sequência de buscas S nesta BST é tão bom, assintoticamente, quanto o menor custo possível, denotado por OPT(S). Esta é a famosa conjectura da otimalidade dinâmica, onde qualquer BST que realiza qualquer sequência de buscas S com custo O(OPT(S)) é dita dinamicamente ótima. Desde que a conjectura foi proposta, houveram muitas tentativas de prová-la, mas ainda não foi provado que a Árvore Splay, ou qualquer outra BST, é dinamicamente ótima. O melhor custo conhecido é O(log log n OPT(S)) da Árvore Tango, proposta por Demaine et al., e das árvores Multi-Splay Tree e Chain-Splay Tree. Através do estudo de BSTs, Demaine et al. propuseram um modelo de pontos no plano que equivale ao problema de busca em uma BST. Este resultado é surpreendente, pois representa uma maneira visual da execução de uma BST sobre uma sequência de buscas. Finalmente, esta dissertação trata-se de um survey da literatura sobre a otimalidade dinâmica, onde reunimos os principais resultados relacionados ao problema.
Banca examinadora:
  • Prof. Dr. Victor Almeida Campos (Orientador - UFC)
  • Prof. Dr. Manoel Bezerra Campêlo Neto (Coorientador - UFC)
  • Prof. Dr. Carlos Vinícius Gomes Costa Lima (UFCA)
  • Prof. Dr. Nicolas de Almeida Martins (UNILAB)
  • Jayme Luiz Szwarcfiter (UFRJ)

Última atualização (Sex, 26 de Março de 2021 18:21)