XMCO02 - Métodos Exatos - 2024s2

Informações:

• Docente: Prof. Dr. Pedro H. D. B. Hokama - IMC
• Aulas: Segundas das 19:00 até 20:40 e Quintas das 21:00 até 22:40 na sala I1123.

Noticias:

1. 18/11 - Divulgado enunciado do Trabalho Final.
2. 31/10 - Divulgado notas parciais.
3. 19/09 - Divulgado enunciado do Trabalho 02.
4. 15/09 - Divulgado enunciado do Trabalho 01.
5. 08/08 - Site da Disciplina no Ar

Aulas:

• 17/10 - Two-Phase method para encontrar uma Solução Básica Viável. Dualidade.
• 03/10 - O algoritmo Simplex. Slides
• 30/09 - Programação Linear. Slides
• 23/09 - Limitantes e método Branch-and-Bound. Slides
• 19/09 - Trabalho 01 e Revisão - Presença não obrigatória.
• 16/09 - Força bruta e Backtracking. Código feito em aula.
• 12/09 - PD - Problema de Dimensionamento de Lotes. Slides
• 09/09 - PD - Problema de Multiplicação Sequência de Matrizes. Slides
• 02/09 - SECOMP - sem aula.
• 29/08 - Programação Dinâmica. Slides
• 26/08 - Redução VERTEX-COVER para HAM-CYCLE. Slides
• 22/08 - Redução polinomial. 3-CNF-SAT para CLICK; CLICK para VERTEX-COVER. Slides
• 19/08 - Classes de Complexidade, P, NP e NP-Completo. Slides
• 12/08 - Apresentação. Exemplos de Problemas. Slides

Critérios de Avaliação:

• Tt = nota dos Trabalhos do Bimestre t.
• Pt = nota da Prova do Bimestre t.
• Nt = Tt * Pt / 10.
• M = (N1 + N2) / 2.
• Se freq < 75% o aluno reprovou-se.
• Senão, se M >= 6 o aluno aprovou-se.
• Senão, se M < 6 o aluno faz uma sub que substitui a menor entre N1 e N2.

Referências bibliográficas e Material de Apoio (em constante atualização):

• Artigos da área
• Papadimitriou, Christos H. e Kenneth Steiglitz. Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998.
• Curso Discrete Optimization no Coursera - Prof. Dr. Pascal Van Hentenryck
• Playlist de aulas do curso Introdução à Otimização Combinatória Aplicada - Prof. Dr. Mário Cesar San Felice
• Texto do curso Introdução à Otimização Combinatória - Prof. Dr. Flávio Keidi Miyazawa e Prof. Dr. Cid. C. de Souza
• Dasgupta, Papadimitriou e Vazirani. Algorithms (2006)