Algoritmos de aproximação animados ---------------------------------- Aluno: José Eduardo Gaboardi de Carvalho http://www.linux.ime.usp.br/~edu/mac499/arquivos/ Planejamos estudar algoritmos de aproximação. O estudo será feito seguindo o livro de Ferreira et al [1]. Além do estudo teórico dos algoritmos, planejamos implementar alguns deles e projetar animações para essas implementações usando o sistema XTango [2]. Dentre os algoritmos que pretendemos estudar e para os quais pretendemos produzir uma animação estão o algoritmo de Graham, a 2-aproximação para o TSP métrico, o algoritmo de Jonhson para o MAXSAT e ou o algoritmo de Chvátal para cobertura de conjuntos ou o FPTAS para o problema da mochila. Eventualmente estudaremos e eventualmente implementaremos mais alguns algoritmos, como o algoritmo de Chistofides (que depende do algoritmo de Edmonds para calcular um emparelhamento perfeito de custo mínimo em um grafo) e/ou alguns algoritmos envolvendo a resolução de um programa linear. XTango é um sistema geral de animação de algoritmos de fácil uso, que não exige conhecimento de sistemas gráficos. Dado um algoritmo em C, o projeto de uma animação consiste apenas em implementar rotinas em C que correspondam a eventos da animação e da inclusão de chamadas a estas rotinas nos pontos chave do algoritmo original. As rotinas de animação utilizam o pacote de rotinas de animação do XTango, que permite criar e manipular objetos geométricos, colorir, fazer mudanças de escala e outras coisas. Os objetivos deste trabalho são adquirir uma base sólida na área de algoritmos de aproximação bem como produzir uma biblioteca animada com vários dos algoritmos de [1], que possa ser usada para fins didáticos. Cronograma tarefa maio junho julho agosto setembro outubro novembro 1 x x 2 x 3 x x 4 x x 5 x x 6 x x 7 x x Tarefas: 1. estudo inicial de algoritmos de aproximação (caps 1 e 2). 2. estudo do sistema XTango. 3. implementação do algoritmo de Graham e de uma animação para ele. 4. implementação do algoritmo de Chvátal e de uma animação para ele. 5. implementação e animação da 2-aproximação para o TSP. 6. estudo, implementação e animação do algoritmo de Jonhson. 7. escrita do trabalho. Referências [1] M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. Pina Jr., J. Soares, Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, Publicações Matemáticas do IMPA, 2001. [2] J.T. Stasko, "TANGO: A Framework and System for Algorithm Animation", IEEE Computer, Vol. 23, No. 9, September 1990, pp. 27-39. (Veja também o site http://www.cc.gatech.edu/gvu/softviz/algoanim/xtango.html.)