Data: 25/02/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Um Survey sobre a Conjectura da Otimalidade Dinâmica
Palestrante: Victor Campos (UFC)


Resumo: Uma busca por um valor no modelo BST consiste em visitar o nó com chave buscada em uma árvore binária de busca ao começar pela raiz da árvore, sendo possível saltar entre nós adjacentes e realizar rotações. Dado uma sequência de buscas S, denotamos por OPT(S) os menor custo para se buscar sequencialmente pelos elementos de S por um algoritmo no modelo BST. A Conjectura da Otimalidade Dinâmica diz que existe um algoritmo online com custo O(OPT(S) + n), onde n é o número de nós da árvore.

Vamos apresentar um survey sobre esta conjectura com foco no ponto de vista do modelo geométrico. O modelo geométrico mostra uma equivalência entre algoritmos no modelo BST e um problema sobre grafos grid chamado de superconjunto arboreamente satisfeito. Nesta visão, a conjectura da otimalidade dinâmica consiste em achar um algoritmo O(1)-aproximativo para o superconjunto arboreamente satisfeito.

Apresentaremos uma classe de árvores binárias de busca balanceadas que implementam uma árvore split no modelo BST. As árvores split são necessárias para mostrar a equivalência entre o problema do superconjunto arboreamente satisfeito e a versão online da conjectura.

O survey sobre o problema foi realizado em conjunto com George Pinto e a classe de árvores balanceadas foi realizado em conjunto com Ricardo Corrêa.