MAC0325+5781 (2017)
Otimização Combinatória
MAC0325 é disciplina eletiva do
BCC (Bacharelado em Ciência da Computação).
MAC5781 é disciplina da pós-graduação em Ciência da Computação.
Veja o vídeo de apresentação de MAC0325 no YouTube.
A Otimização Combinatória, ou Otimização Discreta,
procura as melhores alternativas em um conjunto de possibilidades
que é finito (mas muito grande).
Em geral, isso implica em procurar a melhor combinação
dos valores inteiros de certas variáveis.
Programa
Ementa oficial
(conforme
catálogo de graduação do IME,
catálogo de graduação da USP,
e
catálogo de pós-graduação do IME):
O escopo da otimização combinatória e programação inteira.
Modelagem de vários problemas usando variáveis 0/1.
O problema do transporte.
Especialização do método simplex para redes.
Aplicações: teorema de Hall, teorema de König, teorema de Dilworth.
O problema do transporte capacitado: o método primal-dual.
Algoritmos para fluxos máximos em redes.
Fluxos de custo mínimo e circulações viáveis: o método 'out-of-kilter'.
Estudo aprofundado de poliedros de alguns problemas não-unimodulares
bem resolvidos (emparelhamentos, branchings, etc.).
Não vamos seguir essa ementa à risca pois ela está um pouco defasada.
Requisitos
Os alunos de MAC0325 e MAC5781 devem ter conhecimentos prévios de
Programação Linear,
Grafos e
Análise de Algoritmos.
Os requisitos oficiais de MAC0325 são
MAC0121 (Algoritmos e Estruturas de Dados I) e
MAC0315 (Otimização Linear).
Acredito que muitos dos alunos do BCC também já terão cursado
MAC0323 (Algoritmos e Estruturas de Dados II)
e
MAC0338 (Análise de Algoritmos).
Horário, sala, professor
As aulas serão dadas na sala B-142
B-10,
segundas-feiras às 10:02 e quartas-feiras às 8:04.
As aulas começam no dia 7/8/2017 (quarta-feira)
e terminam no dia 13/12/2017 (quarta-feira).
Para discussões, perguntas, e avisos
usaremos o Paca (Moodle).
Você deve se inscrever o quanto antes.
As aulas serão dadas por Paulo Feofiloff
(sala C-103).
Infelizmente não temos monitor.
Livros e material didático
Principais referências:
- [CCPS]
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver,
Combinatorial Optimization,
Wiley, 1998
-
P. Feofiloff,
Otimização Combinatória,
IME-USP
Referências adicionais:
-
C.H. Papadimitriou and K. Steiglitz,
Combinatorial Optimization: Algorithms and Complexity,
Prentice-Hall, 1982
-
Alexander Schrijver,
A Course in Combinatorial Optimization,
notas de aula, 2017
-
V. Chvátal,
Linear Programming,
Freeman, 1983
-
R.K. Ahuja, T.L. Magnanti and J.B. Orlin,
Network Flows: Theory, Algorithms and Applications,
Prentice-Hall, 1993
-
Alexander Schrijver,
Combinatorial Optimization: Polyhedra and Efficiency
(volumes A, B, C),
Springer, 2003
-
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
Introduction to Algorithms, 3rd edition,
MIT Press, 2009
-
P. Feofiloff,
Algoritmos para Grafos (via Sedgewick),
IME-USP
-
P. Feofiloff,
Algoritmos de Programação Linear,
IME-USP
-
P. Feofiloff,
Análise de Algoritmos,
IME-USP
-
P. Feofiloff,
Minicurso de Análise de Algoritmos,
IME-USP
-
M.H. de Carvalho et alii,
Uma Introdução Sucinta a Algoritmos de Aproximação,
IMPA,
2001
Edições anteriores de MAC0325+5781
-
2015:
Marcel de Carli Silva e Rafael Santos Coelho
-
2008: José Coelho
Exercícios e tarefas
Os exercícios, feitos durante as aulas, não valerão nota.
As tarefas, feitas fora das aulas, terão nota.
Essas tarefas podem ser feitas em grupo,
mas cada aluno deve entregar sua própria solução
e anotar nela os nomes dos outros membros do grupo.
As soluções garimpadas na rede WWW
terão nota menor que as soluções originais,
feitas por conta própria,
mesmo que estejam erradas.
Critério de avaliação
Teremos três provas e várias tarefas.
A nota final será composta por
70% da média das provas
e 30% da média das tarefas.
Entretanto,
se a média das provas ficar abaixo de 5
ou a média dos tarefas ficar abaixo de 5,
a nota final será a menor das duas.
Para os alunos de MAC5781,
as notas serão traduzidas em conceitos:
R (de 0 a 4.9),
C (de 5 a 6.9),
B (de 7 a 8.4) e
A (de 8.5 a 10).
Calendário de aulas e provas
- Aula 1: 7/8 (segunda)
- Apresentação. Regras do jogo. Esclarecimento de dúvidas.
- Questionário.
- Lista de exercícios E01.
- Estude o capítulo 1 das
minhas notas de aula. É leve e suave.
- Tarefa A, para 10/8, quinta, até as 10:00.
- Aula 2: 9/8 (quarta)
- Aula cancelada (professor tem emergência médica).
- Aula 3: 14/8 (segunda)
- Discussão da tarefa A.
- Programação Linear. Dualidade.
- Caminhos dirigidos de custo mínimo.
- Potencial viável.
- Algoritmo de Ford.
- Lista de exercícios E02.
- Aula 4: 16/8 (quarta)
- Estude o capítulo 2 das minhas notas de aula.
- Caminhos dirigidos de custo mínimo.
- Sequências de varredura dos arcos.
- Algoritmo de Ford-Bellman.
- Caminhos dirigidos mínimos para custos não-negativos.
- Tarefa B, para 21/8, segunda, até 10:00.
- Aula 5: 21/8 (segunda)
- Algoritmo de Ford-Bellman para DAGs.
- O problema do fluxo máximo.
- Estude o capítulo 3 das
minhas notas de aula.
- Tarefa C, para 28/8, segunda, até 10:00.
- Aula 6: 23/8 (quarta)
- Teorema do fluxo máximo e corte mínimo.
- Algoritmo de Ford-Fulkerson.
- Lista de exercícios E06.
- Aula 7: 28/8 (segunda)
- Algoritmo de Ford-Fulkerson.
- Aperfeiçoamento de Edmonds-Karp.
- Programas lineares para fluxo máximo e corte mínimo.
- Leia o capítulo 4 das minhas notas de aula.
- Emparelhamentos bipartidos e o teorema de König.
- Aula 8: 30/8 (quarta)
- O problema do transporte.
- Teorema de Gale.
- Teorema de Hoffman.
- Tarefa D, para 11/9, segunda, até 9:58.
- Feriado (Semana da Pátria): 4/8 (segunda)
- Feriado (Semana da Pátria): 6/9 (quarta)
- Aula 9: 11/9 (segunda)
- Fluxo mínimo de r a s.
- Discussão da tarefa D.
- Lista de exercícios E09.
- Tarefa E, para 18/9, segunda, até 9:58.
- Aula 10: 13/9 (quarta)
- Árvore de Gomory-Hu.
- Leia o capítulo 5 das minhas notas de aula.
- Prova 1: 18/9 (segunda)
- Aula 11: 20/9 (quarta)
- Teorema de Dilworth.
- Árvore de Gomory-Hu.
- Tarefa F, para 27/9, quarta, até 7:58.
- Aula 12: 25/9 (segunda)
- Fluxo viável de custo mínimo.
- Leia o capítulo 6 das notas de aula.
- Lista de exercícios E12.
- Tarefa G, para 2/10, segunda, até 7:50.
- Aula 13: 27/9 (quarta)
- Fluxo viável de custo mínimo: circuitos de aumento.
- Lista de exercícios E13.
- Aula 14: 2/10 (segunda)
- Fluxo viável de custo mínimo: simplex para redes.
- Lista de exercícios E14.
- Aula 15: 4/10 (quarta)
- Algoritmo simplex para redes de transbordo.
- Tarefa H, para 16/10, segunda, até 7:50.
- Break (Padroeira do Brasil): 9/10 (segunda)
- Break (Padroeira do Brasil): 11/10 (quarta)
- Aula 16: 16/10 (segunda)
- Algoritmo simplex para redes.
- Aula 17: 18/10 (quarta)
- Algoritmo simplex para redes.
- Prova 2: 23/10 (segunda)
- Aula 18: 25/10 (quarta)
- Emparelhamentos máximos.
- Tarefa I, para 30/10, segunda, até 7:50.
- Aula 19: 30/10 (segunda)
- Emparelhamentos máximos.
- Tarefa J, para 6/11, segunda, até 7:50.
- Aula 20: 1/11 (quarta)
- Algoritmo para emparelhamento perfeito.
- Aula 21: 6/11 (segunda)
- Algoritmo para emparelhamento máximo.
- Aula 22: 8/11 (quarta)
- Emparelhamento perfeito de custo mínimo em grafos bipartidos.
- Tarefa K, para 22/11, quarta, até 7:50.
- Break (Proclamação da República): 13/11 (segunda)
- Feriado (Proclamação da República): 15/11 (quarta)
- Feriado (Consciência Negra): 20/11 (segunda)
- Aula 23: 22/11 (quarta)
- Emparelhamento perfeito de custo mínimo.
- Tarefa L, para 27/11, segunda, até 7:50.
- Aula 24: 27/11 (segunda)
- Discussão das tarefa K e L.
- Aula 25: 29/11 (quarta)
- Poliedro dos emparelhamentos perfeitos.
- Aula 26: 4/12 (segunda)
- Poliedros, politopos, e vértices.
- Poliedro dos emparelhamentos perfeitos.
- Aula 27: 6/12 (quarta)
- Laboratório de exercícios.
- Prova 3: 11/12 (segunda)
- Prova 2-a avaliação: 14/12 (quinta)
- 10h, sala C-103
Administração
Curiosidades