A classe de estruturas de dados retroativas introduz uma maneira de controlar o histórico de operações realizadas sobre determinada estrutura de dados, modificando sua implementação tradicional para incluir a associação de cada operação a um instante de tempo e a possibilidade de incluir ou excluir operações no passado. O primeiro estudo sobre esse paradigma foi produzido por Demaine, Iacono e Langerman, que elaboraram um artigo apresentando a definição formal de retroatividade, uma extensa demonstração sobre a não existência de um método genérico para converter qualquer estrutura em uma versão retroativa, e provaram que as seguintes estruturas possuem versão retroativa eficiente: fila, fila dupla, union-find e fila de prioridades. Este trabalho pretende produzir um texto introdutório para apresentar esse tipo de estrutura e as técnicas envolvidas.
A escolha do tema de estudo foi algo que me preocupou bastante de início. Particularmente eu me interesso bastante pelas áreas de inteligência artificial, lógica, estruturas de dados e análise de algoritmos. Apesar do trabalho de conclusão ser um projeto maior, precisaria escolher uma delas para me aprofundar. Foi uma feliz surpresa quando a professora Cristina me apresentou o tema de retroatividade, que acabou sendo meu tema final.
Além de já abranger muitos aspectos que eu esperava estudar, esse tema tem potencial de se expandir e se combinar com outras áreas que tenho interesse, o que me motiva a estender meus estudos para além da graduação. Quando comecei a desenvolver o trabalho, tive medo de que os três anos de curso que ficaram atrás de mim fossem insuficientes para sustentar um trabalho mais extenso e profundo. E ao longo do processo, fui percebendo que estava me dando menos crédito do que merecia.
A construção deste trabalho passou por alguns estágios: leitura e estudo de conceitos, implementação das estruturas estudadas e redação de um texto com aspecto mais didático.
O artigo principal usado como referência não descreve em muitos detalhes a implementação, e para suprir essa escassez de detalhes, foram necessárias reuniões periódicas para discussão e estudo com minha orientadora. O desenvolvimento do código foi afetado por essa carência de descrição, muitas vezes tentava uma estratégia que precisava ser repensada porque algo que não havia ficado claro antes.
Por fim, a descrição da implementação não foi uma tarefa simples, foi difícil criar um fluxo didático de informação que transmita as ideias por trás de cada estrutura. Espero que este trabalho seja de boa utilidade para aqueles que não conheçam do assunto e gostariam de começar por um texto mais acessível.