Resumo

O problema do Ancestral de Nível consiste em preprocessar uma árvore enraizada T para então responder consultas AN(u, d), que pedem o ancestral do nó u com profundidade d. Vários algoritmos com diferentes complexidades já foram propostos, porém existem poucos estudos comparativos e implementações disponíveis, principalmente em português. Neste trabalho, foram implementados e comparados quatro algoritmos, levando em consideração árvores com diferentes formatos para analisar na prática o comportamento de cada um conforme o fator de ramificação varia, indo além da análise tradicional de complexidade de tempo e espaço no pior caso. Os resultados obtidos estão de acordo com o que era esperado pela análise teórica mas além disso, foi possível observar que algoritmos simples podem ser implementados de maneiras que, dependendo das características da árvore de entrada, pode-se obter performances suficientes, o que leva à reforçar o quão importante é conhecer a aplicação em questão para poder tomar a melhor decisão quanto a qual algoritmo implementar, balanceando questões como uso de memória, dificuldade de implementação e manutenção do código e eficiência.

Ferramentas

A linguagem C++ foi utilizada para a implementação de todos os algoritmos, para a geração dos testes de benchmarks e a biblioteca Catch2 foi usada para a criação de testes de unidade em C++. Para analisar os resultados e plotar os gráficos presentes na monografia, foi utilizado Python e matplotlib. Para compilar os programas e testes, foi utilizada a ferramenta CMake.

Cronograma

Parte Subjetiva

Uma das minhas motivações ao querer fazer esse trabalho era fazer uma ponte entre um tópico mais teórico e a prática, coisa que muitas vezes durante a graduação nós não damos muita atenção, fazendo por exemplo apenas uma análise de pior caso dos algoritmos e não se atentando ao seu comportamento em casos mais gerais, considerando os trade-offs que costumam surgir ao comparar um algoritmo mais simples com outro mais complexo. Sinto que este objetivo foi cumprido e todo o processo de implementação e benchmarks foi bastante satisfatório.