CI1238 / INFO7070

Otimização / Tópicos Especiais I (PPGINF)

Professor: André Guedes

Horário: 3as e 5as, 17:30

Sala de aula: PA-04

Introdução a Problemas de Otimização
Problemas Computacionais e Algoritmos
- Definições e terminologia: espaço de soluções, função objetivo, soluções viáveis etc
- Máximos/mínimos locais
- Busca no espaço de soluções
- Discreta X contínua
- Combinatória X não combinatória
Programação Linear
- Introdução e Modelagem
- Conceitos fundamentais e introdução ao simplex
- Detalhes do simplex
- Dualidade e PLI
Técnicas combinatórias de algoritmos
- Enumeração;
- Backtracking;
- Branch-and-bound;
- Algoritmos gulosos;
- Programação dinâmica;

Apresentar problemas de otimização e técnicas para sua solução.

Apresentar os problemas de programação linear e inteira, o algoritmo Simplex e reduções de problemas de otimização aos problemas de programação linear e inteira
Apresentar as técnicas de programação dinâmica e o uso de algoritmos gulosos para solução de problemas computacionais.
Apresentar algoritmos para enumeração de estruturas discretas e as técnicas de "backtracking" e "branch and bound" para solução de problemas computacionais.

Duas provas e dois trabalhos práticos, envolvendo a solução algorítmica de problemas usando as técnicas vistas na disciplina, além da prova final.

Os números do tipo "[nn]" se referem a itens da bibliografia.

Exercícios (atualizado em 15/12/2020)
Introdução à Otimização
- [2], sec 1.1 e 1.2
- [3], sec 1.1
- [4], cap 1
PL: Introdução e Modelagem
- [1], sec 1.1 + cap 2, exceto 2.5 e 2.6
PL: Conceitos Fundamentais e Introdução ao Simplex
- [1], cap 4, exceto 4.3 + 5.1 + 5.5 + 5.6
PL: Detalhes do Simplex
- [1], 5.2 + 5.3 + 5.4 + 5.7 + 5.8 + 5.9
PL: Dualidade e PLI
- [1], 6.1 + 6.2 + 3.1 + 3.2 + 3.3 + 3.4
- só para PPGINF: [1], 8.2 + 8.3 (opcional para a graduação)
Enumeração / Backtracking
- [3], cap 2 e 4 (4.1 a 4.3 exceto 4.3.1)
- pré leitura recomendada: [3], sec 1.2 e 1.3
- só para PPGINF: [3], 4.5
Branch-and-bound
- [3], sec 4.6 e 4.7
Programação Dinâmica
- [3], sec 1.8
- [6], cap 15
Gulosos
- [6], cap 16
Trabalho 1 (entrega até 08/04/2024)
Exemplos para o 1o trabalho (com as entradas usadas na avaliação)
Prova 1 com gabarito (parcial)
Trabalho 2

[2] Combinatorial Optimization - Algorithms and Complexity. Papadimitriou, Steiglitz. Dover Publications. 1998.

[3] Combinatorial Algorithms - Generation, Enumeration and Search. Kreher, Stinson. CRC Press. 1999.

[5] Algorithms. S. Dasgupta, C. H. Papadimitriou e U. Vazirani. McGraw Hill. 2006

[7] The Algorithm Design Manual. Skiena. Springer, 1998.

[10] Exact exponential algorithms. F.V. Fomin e D. Kratsch. Springer Verlag, 2010.

[11] Algorithms. R. Sedgewick. Addison-Wesley, Reading, Massachusetts, 1983.

[12] Data Structures and Algorithms. A.V. Aho, J.E. Hopcroft, J.D. Ullman. Addison-Wesley, Reading, Massachusetts, 1983.

[13] Algorithms and Data Structures. N. Wirth. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989).

[14] The Art of Computer Programming vol. 1, D.E. Knuth.

[15] The Art of Computer Programming vol. 3, D.E. Knuth.

[16] The Art of Computer Programming vol. 4, D.E. Knuth.