Horário: 3as e 5as, das 8h às 10h.
Início: 13 de junho de 2017.
Repositório do código criado em sala de aula:
https://github.com/vigusmao/top_esp_otimizacao_2017_2
Problemas possíveis (entre outros):
- Minimum Cut Max Flow
- Knapsack Problem
- Bin Packing
- Traveling Salesman
- Minimum Spanning Trees and variations (e.g. Spanning Trees With Few Branches)
- Maximum Matchings / Maximum Weighted Matchings
- Edge Coloring
- Maximum Independent Set / Maximum-Weight Independent Set
- Vertex Coloring
- Vertex Covers
- Dominating Sets
Apresentações:
- 01/08 - Judismar - cobertura de vértices
- 03/08 - Bernardo K - emparelhamento m&aacu;ximo
- 08/08 - Diego - 3-SAT
- 10/08 - Alexsander - árvore de Steiner com número fixo de terminais
- 15/08 - Jamile - coloração de vértices
- 17/08 - André Carlos - coloração de arestas
- 22/08 - Benardo S - um problema original de inferência
Bibliografia sugerida:
- Alan Tucker - Applied Combinatorics
- William J. Cook / William H. Cunningham / William R. Pulleyblank / Alexander Schrijver - Combinatorial Optimization
- Alexander Schrijver - A Course in Combinatorial Optimization
- Christos Papadimitriou - Computational Complexity
- Christos Papadimitriou / K. Steiglitz - Combinatorial Optimization
- Bernhard Korte / Jens Vygen - Combinatorial Optimization: Theory and Algorithms
Conteúdo das aulas
13/06
Introdução ao curso. Abordagem prática, computacional. Relacionamento mais próximo, "completo", com cada problema. Problemas difíceis. Força bruta. Domínio restrito. Aproximação / Randomização / Parametrização.
20/06
Fluxo máximo em redes. Ford-Fulkerson.
22/06
Teorema do Fluxo Máximo / Corte Mínimo. Algoritmo de Edmonds-Karp.
27/06
Aula prática: Python; representação de grafos; busca em largura.
Código (commit parcial) feito em sala de aula no GitHub.
29/06
Implementação do Edmonds-Karp e do Ford-Fulkerson usando busca em profundidade, para comparar.
Código (commit parcial) feito em sala de aula no GitHub.
04/07
Push-relabel.
06/07
Push-relabel (continuação).
11/07
O problema da mochila. Variante 0-1 e fracionária. Gulosos que não funcionam. Idéias de força bruta (enumeração total, backtracking com poda).
13/07
O problema da carga da balsa. Como explorar simetrias, possíveis certificados de otimalidade. Repetição de subproblemas. Programação dinâmica.
18/07
Implementação de algoritmos para o problema da mochila 0-1: enumeração total de subconjuntos, backtracking.
Código (commit parcial) feito em sala de aula no GitHub.
20/07
Resolvendo o problema da mochila 0-1 via PD. Complexidade psudo-polinomial. PD top-down (recursão com memoização).
25/07
Implementação do problema da mochila por recursão (sem memoização) e via PD (bottom-up e top-down).
01/08
Apresentação do Judismar sobre cobertura de vértices.
03/08
Apresentação do Bernardo K sobre emparelhamento máximo.
08/08
Apresentação do Diego sobre 3-SAT.
10/08
Apresentação do Aleksander sobre árvores de Steiner.
15/08
Apresentação da Jamile sobre coloração de vértices.
17/08
Apresentação do André sobre coloração de arestas.
24/08
Apresentação do Bernardo S sobre um problema de otimização em mineração de dados (resultados do Enem).
29/08
Complemento da apresentação do Bernardo K: algoritmo de Edmonds para a determinação de emparelhamentos máximos.
Branch and bound: ideias básicas. Exemplo de relaxação de restrições: mochila.
