Aluno: Felipe Castro de Noronha
Supervisora: Profª. Drª. Cristina Gomes Fernandes
Tema: Link-cut trees e aplicações em estruturas de dados retroativas
A ideia deste trabalho é a realização de um estudo sobre estruturas de dados retroativas, que permitem modificações e consultas não somente no presente, mas também no passado. Em linhas gerais, podemos dividir este trabalho em três partes principais.
A primeira delas seria o estudo e implementação de uma estrutura de dados chamada link-cut tree, que nos permite manter uma floresta dinâmica, realizando ligações e separações de árvores. Essa estrutura servirá como base para as implementações retroativas a seguir.
Inicialmente, estudaremos a versão retroativa da estrutura de dados union-find, usada para manipular uma coleção de conjuntos disjuntos. A ideia é que possamos realizar a união entre dois conjuntos da coleção em qualquer instante de tempo, assim como consultar se dois elementos faziam parte do mesmo conjunto em um certo instante.
Em seguida, estudaremos a versão retroativa do problema da árvore geradora mínima (minimum spanning tree) de um grafo. Nele, podemos realizar modificações na estrutura do grafo e consultar a sua árvore geradora mínima a qualquer momento.
A realização do trabalho pode ser dividida nas seguintes atividades:
A seguir, temos o cronograma aproximado para a realização das atividades acima, os quadros marcados em verde sinalizam o que já foi realizado.
Atividade | Mar | Abr | Mai | Jun | Jul | Ago | Set | Out | Nov | Dez |
---|---|---|---|---|---|---|---|---|---|---|
Estudo e implementação da link-cut tree | X | |||||||||
Escrita do capítulo sobre link-cut tree | X | X | ||||||||
Estudo e implementação do union-find retroativo | X | |||||||||
Escrita do capítulo sobre union-find retroativo | X | X | ||||||||
Implementação da versão retroativa do problema de minimum spanning tree | X | X | ||||||||
Estudo e escrita de capítulo sobre a técnica de square root decomposition | X | |||||||||
Escrita do capítulo sobre a versão retroativa do problema de minimum spanning tree | X | X | X | X | ||||||
Caso haja tempo, estudo e implementação de outro problema relacionado ao trabalho | X | X | X | X | ||||||
Escrita da introdução e resumo da monografia, assim como preparação de poster e/ou apresentação | X | X | X |
Estruturas de dados retroativas permitem a realização de operações que afetam não somente o estado atual da estrutura, mas também em qualquer um de seus estados passados. Além disso, uma link-cut tree é uma estrutura de dados que permite a manutenção de uma floresta de árvores enraizadas com peso nas arestas, e onde os nós de cada árvore possuem um número arbitrário de filhos. Tal estrutura é muito utilizada como base para o desenvolvimento de estruturas de dados retroativas, e neste trabalho estudaremos as versões retroativas dos problemas de union-find e floresta geradora mínima. Para isso, implementamos essas estruturas em \texttt{C++} e descrevemos as ideias por trás de seus funcionamentos. Ademais, apresentamos uma melhoria da solução originalmente apresentada para a floresta geradora mínima retroativa, que retira limitações sem piorar sua performance.
felipe.castro.noronha at usp.br
Instituto de Matemática e Estatística
Universidade de São Paulo