Índice

Introdução

Esta página contém a monografia de conclusão de curso, que versa sobre um projeto sob supervisão do Prof. Ernesto G. Birgin. O trabalho foi desenvolvido individualmente, e consiste primordialmente na análise de um problema NP-difícil a ser abordado por algoritmos de aproximação. Para tanto, diversos papers foram estudados (vide Bibliografia), e dois tipos de algoritmos foram eleitos para a implementação e teste das heurísticas discutidas: um de natureza construtiva, e outro de abordagem genética.

Uma vez que o trabalho é individual, a organização do mesmo foi naturalmente orientada por interações entre o aluno e o supervisor, desde a fase da escolha do problema, abordagens adotadas, escolha de ferramental, etc., até a implementação e análise propriamente ditas.

Para navegar nas seções desta monografia, utilize os botões ao lado, ou os links descritos nas seções a seguir.

Objetivos

Implementar e comparar a eficiência de diferentes abordagens para o problema do "Empacotamento de Círculos de Tamanho Variado em um Retângulo", ou "Problema do Corte Circular Restrito", tal como definido na página do problema. Demonstradamente NP-difícil, ele é expresso na forma de um problema de programação não-linear, para o qual foram sugeridas algumas heurísticas e os correspondentes algoritmos. O trabalho visa implementar duas destas heurísticas e fazer uma análise dos resultados obtidos, comparando as técnicas entre si.

Cronograma de Atividades para o Segundo Semestre

A estimativa inicial de prazos e expectativa de andamento do projeto, encontram-se na página do Cronograma. Neste mesmo local encontra-se uma discussão post-mortem sobre o andamento do projeto.

Metodologia, Tópicos e Teorias Estudados

Em Teoria encontram-se descritos os aspecto teóricos utilizados neste trabalho, bem como as ferramentas e técnicas utilizadas.

Atividades Realizadas

As diversas atividades que compreenderam este trabalho estão descritas na página do Cronograma. Durante sua execução, porém, foram produzidos diversos artefatos, contidos no Arquivo.

Conclusão e Análise dos Resultados Obtidos

Uma vez que este trabalho ainda está em andamento, a página correspondente à Conclusão ainda não está preenchida. Todas as outras seções também serão expandidas e complementadas por ocasião da versão final desta monografia.

Meta-Relatório: Uma Descrição da Experiência ao Realizar o Trabalho

A descrição do processo de realização deste projeto, bem como a experiência advinda dele e sua relação com o curso, estão contidos no meta-relatório sobre o projeto.

Volta para o Topo

Personal site: http://rubens.altimari.com.br
email: rubens@altimari.com.br
Atualizado em 28/02/2005