MAC-499 - Trabalho de formatura


	MAC-499 - Trabalho de formatura Dados gerais Aluno: José Eduardo Gaboardi de Carvalho Número USP: 3132729 E-mail: edu@linux.ime.usp.br Orientadora: Cristina Gomes Fernandes Tipo de trabalho: projeto Introdução O projeto consistiu no estudo e implementação de alguns algoritmos de aproximação, e animações para os mesmos. Os algoritmos de aproximação geram aproximações de boa qualidade para problemas de otimização combinatória de elevada dificuldade computacional, em que não se conhece nenhuma maneira de se calcular uma solução ótima em tempo limitado por uma função polinomial do tamanho da entrada do problema. Diversos destes problemas são NP-difíceis, de forma que se existe alguma maneira de se calcular uma solução ótima em tempo polinomial, então P = NP. As animações criadas têm a finalidade de mostrar como funcionam os algoritmos internamente. Espera-se que possam ser utilizadas com fins didáticos, facilitando o entendimento dos passos que os algoritmos seguem para gerar a aproximação desejada. Para gerar tais animações, foi utilizado o sistema gráfico de animação de algoritmos XTANGO (X-window Transition-based ANimation GeneratiOn). Atividades propostas Foi proposto inicialmente o projeto e animação de quatro algoritmos: o algoritmo de Graham para um problema de escalonamento, 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 FPTAS para o problema da mochila. Foram estudados os seguintes algoritmos: Algoritmo de Graham O algoritmo de escalonamento de Graham é uma aproximação para o problema de escalonamento de tarefas em máquinas. Dadas m máquinas idênticas e n tarefas com tempo de execução pré-determinado, encontrar uma atribuição das tarefas às máquinas que minimize o tempo máximo de operação de qualquer uma das máquinas. O algoritmo de Graham é o primeiro algoritmo de aproximação de que se tem notícia. Ele tem uma razão de aproximação de 2, ou seja, o custo da solução encontrada não é superior ao dobro do custo de uma solução ótima, onde o custo, nesse caso, é o tempo máximo que uma máquina terá de funcionar. O algoritmo segue uma estratégia simples, alocando uma a uma cada tarefa à máquina com menor custo acumulado. Não é necessário ter conhecimento prévio do tempo de execução das tarefas, mas caso isso aconteça, a razão de aproximação do algoritmo cai para 4/3, simplesmente ordenando-se as tarefas em ordem não-crescente de tempo de execução, antes de iniciar a atribuição das tarefas às máquinas. Neste projeto, foi implementada apenas a 2-aproximação do algoritmo de Graham para escalonamento. Algoritmo de Chvátal O algoritmo de Chvátal para cobertura de conjuntos é uma aproximação para o problema de encontrar, em uma coleção de conjuntos, cada um com um custo associado, uma cobertura de um conjunto finito E dado, com custo total mínimo. Esse custo total é a soma do custo de cada um dos conjuntos utilizados na cobertura do conjunto E. Este algoritmo seleciona conjuntos para cobrir E de acordo com o custo relativo de cada um, calculado de acordo com a razão entre o custo do conjunto e o total de elementos de E ainda não cobertos por conjuntos previamente selecionados para a cobertura. A razão de aproximação deste algoritmo é o número harmônico , onde n := \|E\|. A razão não é constante, mas essa é a melhor razão de aproximação possível (a menos de um fator constante), se . Algoritmo de Rosenkrantz, Stearns e Lewis Este é um algoritmo de aproximação para o problema do caixeiro viajante métrico. O problema consiste em achar, em um grafo completo com custos nas arestas, um circuito hamiltoniano de custo mínimo. Nesta versão do problema do caixeiro viajante, além de o grafo ter de ser completo, é necessário que os custos c_ij associados a pares ij de vértices obedeçam a desigualdade triangular, ou seja, c_ik <= c_ij + c_jk, para quaisquer três vértices i, j e k. Este algoritmo tem uma razão de aproximação de 2, e consiste no seguinte. Inicialmente acha-se uma árvore geradora de custo mínimo no grafo. Em seguida, duplica-se cada uma das arestas presentes na árvore, e a partir daí constrói-se um ciclo euleriano. Através da seleção de uma subseqüência maximal, sem vértices repetidos, das arestas do ciclo gerador achado anteriormente, constói-se o circuito hamiltoniano procurado, com custo não superior ao dobro do custo ótimo. O algoritmo de Christofides é um outro algoritmo para o problema, com razão de aproximação de 3/2. É mais complicado que o primeiro, pois em vez de duplicar as arestas da árvore geradora achada, adiciona arestas de um emparelhamento perfeito, através do algoritmo de Edmonds. Algoritmo de Johnson O algoritmo de Johnson é um algoritmo de aproximação probabílistico para o problema da satisfatibilidade máxima. O problema consiste em, dada uma fórmula booleana em CNF, achar uma valoração de variáveis booleanas de forma a satisfazer o maior número possível de cláusulas booleanas da fórmula. O algoritmo é muito simples. Ele simplesmente atribui uma valoração aleatória às variáveis booleanas, ignorando as cláusulas da fórmula dada. Este algoritmo é uma aproximação probabilística de razão 0,5, o que quer dizer que o número esperado de cláusulas satisfeitas é pelo menos metade do número de cláusulas satisfeitas por uma atribuição ótima. Atividades realizadas No primeiro semestre de 2002, foram implementados os algoritmos de Graham e Chvátal, inicialmente sem as animações, devido a dificuldades surgidas durante a instalação do sistema XTANGO. Juntamente com a implementação desses primeiros dois algoritmos, fui me familiarizando com o sistema XTANGO (apesar de este ainda não estar funcionando) através da leitura de sua documentação, e leitura do código fonte dos exemplos que vêm juntamente com o pacote. No segundo semestre, já com o sistema XTANGO instalado, foram feitas as animações dos dois algoritmos já prontos, com algumas pequenas modificações no código fonte dos mesmos, para facilitar a criação das imagens a serem animadas, de forma eficiente e com um código fácil de ser entendido. O próximo programa iniciado foi o do algoritmo de aproximação para o problema do caixeiro viajante métrico. Este, o mais complexo dos quatro algoritmos propostos, tomou muito tempo, e infelizmente ainda apresenta problemas que impossibilitam a exibição da sua animação. O último dos quatro algoritmos propostos, o probabilístico de Johnson, foi feito sem maiores complicações de implementação. Os algoritmos implementados e funcionando podem ser vistos a partir da página de MAC-499, no endereço http://www.linux.ime.usp.br/~edu/mac499/. Lá encontram-se também alguns pequenos arquivos de exemplo para teste dos algoritmos, e instruções de como gerar instâncias diferentes em arquivos de entrada. Ferramentas e bibliografia utilizadas O sistema XTANGO utilizado foi criado para permitir que seus usuários possam animar algoritmos e programas facilmente, sem ter que escrever nenhum código de baixo nível para rotinas gráficas. É um sistema de fácil uso e rápido aprendizado, e apesar de sua simplicidade, seus tipos de dados e funções permitem gerar animações que facilitam bastante o entendimento dos algoritmos animados. O sistema roda em X-windows, em máquinas com sistema operacional Linux ou similar, e foi escrito em linguagem C. Os algoritmos e programas gerados também são escritos em linguagem C. São colocadas chamadas às rotinas gráficas de animação em pontos chave do algoritmo, de forma que o algoritmo original não tenha muitas chamadas a rotinas gráficas, o que acabaria poluindo o programa original. Assim, foram criados arquivos separados para código fonte dos algoritmos e para as animações dos mesmos, tornando clara a separação de rotinas gráficas e rotinas do algoritmo de aproximação. Para o desenvolvimento dos programas dos algoritmos de aproximação foi utilizada bibliografia sobre algoritmos de aproximação, juntamente com livros de estruturas de dados e algoritmos, a fim de criar programas enxutos, que fossem fáceis de ser entendidos e modificados quando necessário. A bibliografia utilizada foi a seguinte: Uma Introdução Sucinta a Algoritmos de Aproximação, Cristina G. Fernandes, Flávio K. Miyazawa, Márcia Cerioli, Paulo Feofiloff (editores). Impa, 2001. Este livro sobre algoritmos de aproximação, do 23º Colóquio Brasileiro de Matemática, descreve os algoritmos de aproximação utilizados, contendo demonstrações das razões de aproximação de cada um deles. XTANGO Algorithm Animation Designer's Package, John T. Stasko, Doug Hayes. College of Computing, Georgia Institute of Technology, 1992. Juntamente com o livro de algoritmos de aproximação, o sistema XTANGO e sua documentação formam a principal base utilizada para desenvolvimento do projeto. C Padrão ANSI, Brian W. Kernighan, Dennis M. Ritchie. Campus, 1990. Este livro foi utilizado unicamente para esclarecimento de dúvidas com relação à linguagem de programação utilizada. Algorithms in C, Robert Sedgewick. Addison-Wesley, 1998. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. The MIT Press, 1990. Estes dois últimos livros foram utilizados para desenvolvimento dos algoritmos da forma mais simples possível, através das estruturas de dados descritas nos mesmos. O livro Introduction to Algorithms contém também um capítulo sobre algoritmos de aproximação, que foi utilizado como auxílio no desenvolvimento do código fonte dos algoritmos. Aplicação dos conhecimentos adquiridos no BCC Diversas disciplinas oferecidas no curso do BCC foram-me úteis no desenvolvimento deste projeto. Dentre elas, as mais importantes foram as relacionadas a programação e algoritmos: MAC-110 - Introdução à Computação Nesta matéria tive um primeiro contato com a linguagem C, da qual tinha apenas poucas noções. MAC-122 - Princípios de Desenvolvimento de Algoritmos Esta foi a primeira disciplina em que começamos a fazer uma análise de complexidade de algoritmos, simples e baseada em intuição, e aprendemos algumas estruturas de dados. MAC-221 - Laboratório de Programação, e MAC - 242 - Laboratório de Programação II Estas duas matérias ajudaram a adquirir prática com programação, aprendendo pequenos "truques" a serem usados num programa, sem entrar porém em aspectos muito teóricos. MAC-323 - Estruturas de Dados A disciplina de estruturas de dados teve muito em comum com a de MAC-122, porém foi mais formal na descrição das estruturas de dados e na análise dos algoritmos que as utilizam. Foram vistas também algumas estruturas mais complicadas que não havíamos visto no curso de MAC-122. MAC-328 - Algoritmos em Grafos Esta disciplina é fundamental para o desenvolvimento de qualquer programa que utilize manipulação de grafos. MAC-338 - Análise de Algoritmos Análise de algoritmos é a última, e mais completa disciplina que trata de análise de diversos tipos de algoritmos. Nela, aprendi a teoria que tornou possível o entendimento dos algoritmos de aproximação, sua análise, e seu propósito. Além das disciplinas citadas, muitas outras contribuíram de alguma forma para o desenvolvimento deste projeto. Desde FLC-474, Língua Portuguesa, que contribuiu para a escrita deste texto, até disciplinas mais ligadas à matemática, que acabam ajudando na análise dos algoritmos, trazendo uma maior facilidade no entendimento de textos abstratos. Desafios e frustrações Como todo projeto ou EP feito durante esses quatro anos do curso de computação, este apresentou algumas dificuldades. Antes da escolha do projeto, sempre há aquela dúvida sobre o que fazer no trabalho de conclusão do curso. A primeira proposta que me interessou foi sobre a implementação de algoritmos de aproximação em grafos. Tratava-se do problema de Steiner, em que se deseja uma árvore de custo mínimo que contenha os vértices de um grafo que pertencem a um conjunto R dado. O custo é a soma do custo que é atribuído às arestas do grafo que fizerem parte da árvore calculada. Acabei não ficando com este projeto, e a orientadora sugeriu-me duas outras opções. Uma era sobre algoritmos de aproximação primal-dual, e a outra é este projeto de animação de algoritmos de aproximação. Após definir o que seria feito, comecei a ler os capítulos sobre algoritmos de aproximação do livro Uma Introdução Sucinta a Algoritmos de Aproximação. A biblioteca gráfica escolhida foi a XTANGO, própria para animação de algoritmos. Havia uma outra chamada Polka, mais recente que a XTANGO, mas por ela ser usada em linguagem C++, com que tenho menor familiaridade que a linguagem C, acabei decidindo por utilizar o pacote XTANGO. A primeira dificuldade um pouco maior, além da falta de tempo devido às outras disciplinas e outras atividades, foi a instalação do XTANGO. Estava com dificuldades de instalá-la, devido a algumas configurações no arquivo Makefile de instalação necessitarem de mudanças. Em casa eu não conseguia instalá-la, e na rede Linux do IME o administrador que ficou responsável pela instalação estava tendo o mesmo problema. Após diversas tentativas, um dos administradores conseguiu modificar o que era necessário, e seguindo os mesmos passos, finalmente consegui instalar a biblioteca em meu próprio computador. Já no segundo semestre, com a biblioteca instalada e dois algoritmos já implementados, não houve muitas dificuldades na implementação das animações dos mesmos. O mais complicado é criar uma forma de visualizar o algoritmo que seja clara, já que às vezes é muito mais difícil fazer algo claro no computador que com a utilização de lápis e papel. Além disso, a falta de tempo mais uma vez atrapalhou um pouco, mas nada que atrasasse demais o projeto, já que ainda estávamos no início do semestre, quando não há muitas provas e trabalhos das demais disciplinas. O terceiro algoritmo foi o mais complicado. Por ser mais longo e envolver a utilização de grafos, este tomou-me muito tempo, e ainda contém problemas que não permitem executá-lo corretamente. Havia sido proposta uma troca do último algoritmo, de Johnson, por um outro algoritmo de aproximação para o problema do caixeiro viajante métrico. Mas se o primeiro já estava dando muito trabalho, o segundo seria pior, por utilizar algoritmos mais complicados. Diante da dificuldade com o algoritmo em grafos, comecei a implementar o último dos quatro, que era mais simples e não teria grandes problemas. Realmente sua implementação não tomou muito tempo, e novamente o mais difícil relacionado à implementação foi criar uma forma de visualizar o algoritmo. No final de semestre, quando estava implementando o algoritmo de Johnson, mal tinha tempo para dedicar ao trabalho de formatura, devido à enorme sobrecarga de trabalho que geralmente ocorre nos finais de semestre. Havia trabalhos em todas as disciplinas que eu estava fazendo, sendo dois deles muito grandes, de longe mais complicados que este projeto de formatura. Infelizmente não consegui corrigir os últimos problemas em um dos algoritmos a tempo da apresentação do trabalho e da escrita deste texto. Só agora, ao final de inúmeros trabalhos entregues e provas feitas, é que terei tempo disponível para concluir a última das animações, algo que pretendo fazer tão logo seja possível. Conclusão Este foi um projeto muito interessante, em que pude aprender um pouco sobre algoritmos de aproximação, algo que não vi durante esses quatro anos de curso. A prática de programação sempre foi algo de que gostei, e com a exibição em gráficos do que o algoritmo faz, os programas tornam-se mais interessantes do que já são, porque podemos realmente ver o que está acontecendo, além de saber o que está sendo feito internamente. Isso geralmente não ocorre nas outras disciplinas, em que vemos simplesmente os programas receberem diversos dados de entrada, e exibir algo que ele diz que é a resposta. Uma exceção é o curso de Geometria Computacional, outro curso de que gostei muito, pelo mesmo motivo que gostei deste projeto. Além de ser interessante pela forma como é feito, o projeto mostrou-me diversos algoritmos úteis, que se não resolvem, pelo menos aproximam uma solução para problemas que eu conhecia antes mesmo de entrar na faculdade. Não apenas os algoritmos implementados me chamaram a atenção, mas também outros que estão presentes no livro de algoritmos de aproximação utilizado. Finalmente, considero este um projeto importante por reunir diversos conhecimentos e técnicas aprendidos durante o curso, com o intuito de criar um programa que sem dúvida alguma é mais interessante que muitos dos EP's em que se estuda isoladamente cada assunto visto em aula. Se fosse possível fazer isso em todos os trabalhos do curso de computação, certamente o interesse dos alunos no desenvolvimento dos trabalhos seria maior. Como não é possível fazer isso sempre, fico feliz em poder ter passado por isto neste projeto.