MC658 - Projeto e Análise de Algoritmos III

A partir de 2014

 

Pré-­requisitos: MC558

Ementa:

Tratamento de Problemas NP-difíceis.

Programa:

1. Classes de Problemas

- A hierarquia de Complexidade. As classes P, NP, NP-completo e NP-difícil

- Noção de completude e o Teorema de Cook

- Problemas e reduções fundamentais em NP-completude

- Outras classes de problemas: co-NP, PSPACE, problemas indecidíveis (Problema da Parada)

2. Algoritmos exatos
 
- Algoritmos pseudo-polinomiais para o problema da mochila
 
- Algoritmos de backtracking. Sugestões de exemplos:
  • - Coloração de grafos
  • - Soma de subconjuntos
- Algoritmos de branch-and-bound. Sugestão de exemplo: problema da mochila
 
- Programação Linear Inteira como uma ferramenta para resolver problemas NP-difíceis
 
3. Algoritmos aproximados
 
- Definições básicas: aproximação absoluta, fator de aproximação
 
- Aproximação Absoluta. Sugestão de exemplos:
  • - Armazenagem de arquivos em 2 discos
  • - Coloração de grafos planares
- Inaproximabilidade em aproximação absoluta. Sugestão de exemplos:
  • - Problema da Mochila
  • - Clique Máxima.
- Fator de aproximação. Sugestão de exemplos:
  • - Cobertura de Vértices
  • - TSP métrico
  • - Cobertura por Conjuntos
  • - Escalonamento de Tarefas
  • - Bin packing
- Inaproximabilidade em fator de aproximação. Sugestão de exemplo: TSP
 
- Esquemas de aproximação polinomial. Sugestão de exemplo:
  • - Problema da Mochila usando Programação Dinâmica
- Uso de PL no desenvolvimento de algoritmos aproximados. Sugestão de exemplos:
  • - Cobertura por Vértices
  • - Cobertura por Conjuntos
  • - Max-Sat
4. Algoritmos heurísticos
 
- Definições básicas: algoritmos construtivos e algoritmos de busca local
 
- Algoritmos construtivos gulosos. Sugestão de exemplo:
  • - Cobertura por vértices
  • - Algoritmos de busca local. Sugestão de Exemplos:
  • - 2-opt (ou duas trocas) para o TSP
  • - Troca simples para corte máximo
- Meta-heurísticas. Sugestões de exemplos:
  • - GRASP
  • - Busca Tabu
  • - Simulated Annealing
  • - Algoritmos Genéticos

Bibliografia:

1 - T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algoritmos - Teoria e Prática, 3ª. edição, Editora Campus, 2012
2 - Jon Kleinberg e Éva Tardos. Algorithm Design, 1ª. edição, Pearson/Addison-Wesley, 2006
3 - U. Manber. Introduction to Algorithms, 1ª. edição, Addison-Wesley, 1989
4 - 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, 23º Colóquio Brasileiro de Matemática, 2001
5 - V. V. Vazirani. Approximation Algorithms, 1ª. edição, Springer, 2002
6 - D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms, 1ª. edição, Cambridge University Press, 2011
7 - L. A. Wolsey. Integer Programming, 1ª. edição, Wiley, 1998
8 - C. H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity, Dover Books, 1998