Pré-Req: MA327 MC448

Ementa

Redução entre problemas. Complexidade computacional. Classes de problemas. Problemas NP-completos. Tratamento de Problemas NP-difíceis.

Programa

Conteúdo

Tópicos de cobertura obrigatória:

1. Reduções entre problemas

- Para obtenção de cotas superiores

- Para obtenção de cotas inferiores

2. Programação Linear

- Formulação de problemas como PLs, enfatizando que isso é redução

- Apresentação resumida do algoritmo SIMPLEX e de sua complexidade.
  Citar que PL pode ser resolvido em tempo polinomial usando os   algoritmos  de   pontos interiores.

- Dualidade em programação linear

3. Classes de Problemas

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

- A noção de completude e o Teorema de Cook (em alto nível apenas)

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

- Resumir outras classes, além de NP: co-NP, PSPACE, problemas indecidíveis (dar o problema da PARADA em alto nível)

4. Tratamento de Problemas NP-difíceis

- Algoritmos exatos:
            * os algoritmos pseudo-polinomiais para o problema da mochila (tanto o que tem complexidade em função da capacidade da mochila quanto o que tem complexidade como função dos custos dos itens)
            * algoritmos de backtracking para enumeração de todas as soluções de um problema.

Sugestões de exemplos:
               coloração de grafos e sum of subsets

            * algoritmos de branch-and-bound: exemplo do problema da mochila.
            * Programação Linear Inteira como uma ferramenta para resolver problemas NP-difíceis: conceitos básicos de modelagem em PLI, incluindo uso de variáveis binárias e explicação resumida do método de resolução usando PL e branch-and-bound

- Algoritmos aproximados:
            * Definições básicas: aproximação absoluta, fator de aproximação.
            * Aproximação Absoluta.
               Sugestões (pelo menos 1 exemplo): armazenagem de arquivos em 2 discos e coloração de grafos planares.
               Inaproximabilidade em aproximação absoluta (pelo menos 1 exemplo): Sugestão: Problema da Mochila e Clique.
            * Fator de aproximação.
               Sugestões de exemplos (pelo menos 2 exemplos, sendo 1 deles com fator não constante): Cobertura de Vértices,
               TSP métrico, Cobertura por Conjuntos (guloso), Escalonamento de Tarefas, bin packing
               Inaproximabilidade em fator de aproximação. Sugestão: TSP genérico.
            * Esquemas de aproximação polinomial. Sugestões: Problema da Mochila usando Programação Dinâmica
            * Uso de PL no desenvolvimento de algoritmos aproximados. Sugestões: Cobertura de Vértices, Cobertura por Conjuntos, Max-Sat

- Algoritmos heurísticos:
            * Definições básicas: algoritmos construtivos e algoritmos de busca local
            * Algoritmos construtivos gulosos: mostrar exemplos (a escolha do docente) e caso onde é arbitrariamente ruim (exemplo, cobertura de vértices)
            * Algoritmos de busca local: mostrar exemplos (a escolha do docente). Sugestões:
               2-opt (ou duas trocas) para o TSP, troca simples para corte máximo.
            * Meta-heurísticas: definir o conceito e dar exemplos a escolha do docente.
               Sugestões: Pelo menos 2 dentre GRASP, Tabu Search, Simulated Annealing, Algoritmos Genéticos. 

- Projeto computacional: pequeno ou médio porte, comparando pelo menos 2 técnicas dentre algoritmos exatos, aproximados e heurísticos para um problema NP-difícil a escolha do docente. 

 Tópicos opcionais à escolha do docente:

 - Reduções e complexidade de Memória: o Teorema de Savitch (em alto nível)

- Relaxações lagrangeanas

- Programação por Restrições

- Outros Tópicos em Busca Local: Equilíbrio de Nash, Aproximação

 

Bibliografia

 

1. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), Ed. Campus (2002).

2. J. Kleinberg e E. Tardos, Algorithm Design, Addison Wesley, (2005).

3. U. Manber, Algorithms: A Creative Approach, Addison-Wesley (1989).

4. C. H. Papadimitriou e K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc. (1982).

5. E. Horowitz e S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 1978.

6. H.R. Lewis e C.H. Papadimitriou, Elementos de Teoria da Computação, Bookman. 2a edição (2000).

7. M. Garey e D. Johnson, Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman (1979).