Proposta de Trabalho de Formatura
Tema: Algoritmos de Aproximação
Aluno: Samuel Plaça de PaulaSupervisora: Prof.ª Cristina Gomes Fernandes
Resumo da monografia a ser desenvolvida
Há uma quantidade imensa de problemas, sobretudo originários da vida real, que podem ser modelados como problemas de otimização combinatória. No entanto, dentre estes, muitos dos mais interessantes são NP-difíceis, ou seja, não podem ser resolvidos por algoritmos eficientes (isto é, de tempo polinomial) a menos que P = NP. Como em geral precisamos obter respostas em tempo razoável, uma maneira de enfrentar esse problema são os Algoritmos de Aproximação.Algoritmos de aproximação são algoritmos que, para um problema de otimização, calculam eficientemente soluções aproximadamente ótimas. Ou seja, terminam em tempo polinomial e devolvem uma solução cujo valor dista do valor ótimo no máximo em um determinado fator chamado de garantia de desempenho.
O trabalho de formatura contará com uma descrição de algumas técnicas de desenvolvimento de algoritmos de aproximação através de exemplos de algoritmos para variados problemas, tais como a cobertura mínima por conjuntos, o k-center e o caixeiro viajante (TSP). Estarão presentes algoritmos clássicos encontrados na literatura, com ênfase em um problema a ser escolhido, bem como resultados presentes em no mínimo um artigo científico sobre tal problema. Além dos algoritmos em si, o trabalho deverá apresentar também uma discussão da importância da área para a teoria da computação (via resultados de inaproximabilidade, por exemplo) e, se possível, para problemas de natureza prática.
Objetivos do trabalho
Os objetivos do trabalho são estudar a abrangência dos algoritmos de aproximação como forma de resolver problemas difíceis de otimização combinatória, entrar em contato com resultados mais recentes (e algoritmos mais sofisticados) e estudar resultados importantes (para além da resolução dos problemas em si).Para isso, estudaremos algoritmos introdutórios para alguns problemas, de modo a ter contato com variadas técnicas, e estudaremos (ao menos) um artigo científico da área, a ser escolhido.
Atividades já realizadas
Estudamos diversos algoritmos introdutórios presentes no livro de Williamson e Shmoys[1]. Realizamos um resumo do capítulo 1 desse livro, adicionando a ele comentários e demonstrações não presentes no texto original. Estudamos partes de capítulos seguintes para ver outras técnicas e problemas.Vimos técnicas que utilizam soluções fracionárias de relaxações de problemas lineares inteiros que servem como formulação alternativa do problema original. Estudamos técnicas como arredondamentos determinístico e aleatorizado de soluções de tais programas lineares relaxados, método primal-dual, algoritmos gulosos e algoritmos de busca local. Estudamos os problemas da cobertura mínima por conjuntos, problemas de escalonamento de tarefas, k-center e o TSP, entre outros. Vimos resultados de inaproximabilidade para alguns desses problemas.
O resumo feito deverá ser incrementado com outras partes do livro e, futuramente, do artigo científico. Ele poderá ser aproveitado para a monografia, principalmente no caso do artigo, em que deverá ser bastante importante a inclusão de mais explicações e demonstrações.
Cronograma de atividades
| Atividade | Junho | Julho | Agosto | Setembro | Outubro | Novembro |
| Estudo do livro de Williamson e Shmoys[1] | X | X | ||||
| Escolha de artigo científico | X | X | ||||
| Estudo de artigo científico | X | X | X | |||
| Escrita de notas sobre artigo | X | X | X | |||
| Preparação do pôster, apresentação | X | X | ||||
| Finalização e revisão da monografia | X | X | X |
Estrutura esperada da monografia
Parte objetiva:- Introdução
- Conceitos básicos: complexidade computacional, otimização, etc.
- Apresentação de técnicas gerais via cobertura mínima por conjuntos
- Comentários sobre inaproximabilidade
- Apresentação do problema principal
- Comentários sobre inaproximabilidade
- Técnicas clássicas para o problema principal
- Abordagem do artigo científico para o problema principal
- Conclusões
- Bibliografia
- Desafios e frustrações do trabalho de formatura
- Experiência pessoal no BCC
- Relação entre o trabalho de formatura e as disciplinas do BCC
- Trabalhos futuros (na mesma direção do TCC)