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 LinearGrafos  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:

Referências adicionais:

Edições anteriores de MAC0325+5781

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

Outros assuntos:   Projeto de Algoritmos em C  |  Estruturas de Dados  |  Literate Programming & CWEB  |  Exercícios de Teoria dos Grafos  |  Uma Introdução Sucinta à Teoria dos Grafos  |  Otimização Combinatória  |  Digrafos  |  Minicurso de Análise de Algoritmos  |  Análise de Algoritmos  |  O que é uma prova?  |  Algoritmos para Grafos via Sedgewick  |  Algoritmos de Programação Linear  |  Uma Introdução Sucinta a Algoritmos de Aproximação