• principal
• ensino
• titulação
• links

SME0216 - tópicos de otimização combinatória (graduação) e

SME5826 - tópicos em otimização (pós-graduação) (02/2015)

ATENÇÃO: A entrega do trabalho final (escrito) foi adiada para dia 25 de novembro (quarta-feira), no início da aula.

ATENÇÃO: A aula do dia 15 de outubro será na sala 3-009 e terá início às 13h30min.

Material das aulas sobre análise de algoritmos, elaborado pelo Prof. Paulo Feofiloff (IME-USP).

Material da aula sobre complexidade computacional.

Material da aula sobre problemas NP-completos.

Material da aula sobre algoritmos de aproximação.

Material da aula sobre algoritmo de aproximação para o problema de cobertura mínima.

Material da aula sobre algoritmos de aproximação para o problema da mochila.

Material da aula sobre algoritmos de aproximação para o problema do caixeiro viajante.

Material da aula sobre algoritmos de aproximação usando método primal.

Material da aula sobre algoritmos de aproximação usando método dual.

Material da aula sobre algoritmos de aproximação usando método primal-dual.

Material da aula sobre algoritmo de aproximação para o problema da transversal mínima.

Material da aula sobre algoritmo de aproximação para o problema da floresta de Steiner.

Material da aula sobre inaproximabilidade.

Enunciado do trabalho final.

Slides da apresentação do grupo 1, sobre o problema de strip packing.

Slides da apresentação do grupo 2, sobre o problema de bin packing unidimensional.

Slides da apresentação do grupo 3, sobre o problema de coloração de soma mínima.

Slides da apresentação do grupo 4, sobre o problema de localização de instalações.

Slides da apresentação do grupo 5, sobre o problema de 3-coloração.

Aulas:

- Quartas-feiras, das 8h10min às 9h50min, sala 5-002 (ICMC).

- Quintas-feiras, das 14h20min às 16h, sala 3-009 (ICMC).

Bibliografia:

- P. Feofiloff. "Minicurso de Análise de Algoritmos" (disponível aqui).

- S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani. "Algorithms", McGraw-Hill Education, 1a edição, 2006 (disponível aqui).

- 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. Piña Jr., J. A. R. Soares, Y. Wakabayashi. "Uma introdução sucinta a Algoritmos de Aproximação (disponível aqui).

voltar para ensino.

última atualização: 04/12/2015