Trabalho de Formatura Supervisionado

Grafos estão certamente entre os assuntos mais estudados na computação. Em especial, na programação competitiva é comum nos depararmos com problemas que envolvem encontrar o ancestral em comum mais próximos entre dois vértices de uma árvore. Neste trabalho abordo o tema com viés educacional, com o objetivo de produzir um material didático sobre o assunto. Algoritmos para resolver este problema de forma eficiente são demonstrados, sempre com códigos e suas devidas demonstrações.

Durante toda a graduação participei do grupo de extensão que se dedica à Maratona de Programação, o MaratonUSP. A maioria dos membros do grupo escreveram seus trabalhos de conclusão de curso sobre seus assuntos preferidos vistos nos estudos. Aprendi bastante com eles, como por exemplo programação dinâmica e algoritmos em redes de fluxo. Assim, decidi me aprofundar num tema que sempre achei interessante, além de poder possivelmente ajudar novos maratonistas a aprenderem um importante assunto da programação competitiva.

Após a finalização da monografia, lecionei uma aula sobre as diferentes técnicas para obtenção do ancestral comum mais próximo. Tudo que foi falado durante a aula pode ser conferido na monografia final de forma mais detalhada. Para assistir o vídeo clique aqui. Para acessar os slides utilizados na aula clique aqui.