MC548 - Projeto e Análise de Algoritmos II - 2012
Prof. Flávio Keidi Miyazawa

Informações sobre a disciplina


 Docente da Disciplina
Ementa da disciplina
 Avaliação
 Aulas e Atendimento
 Datas Importantes
 Listas de Exercícios
 Bibliografia
   Um livro de exercícios disponível na internet: Problems on Algorithms, by Ian Parberry.
Projeto
Notas
Transparências

• Aula 01 - Introdução
• Aula 02 - Reduções entre Problemas
• Aula 03 - Reduções e Tranferência de Cotas
• Aula 04 - Reduções e Programação Linear 1
• Aula 05 - Reduções e Programação Linear 2
• Aula 06 - Problemas de Decisão, Codificação, Linguagens
• Aula 07 - Certificado, Verificação, Classes NP e NP-Completo
• Aula 08 - Reduções de NP-Completude 1
• Aula 09 - Reduções de NP-Completude 2
• Aula 10 - Reduções de NP-Completude 3
• Aula 11 - Reduções de NP-Completude 4
• Aula 12 - Mais sobre classes de complexidade
• Aula 13 - Heustísticas Construtivas e Busca Local
• Aula 14 - Metropolis, Simulated Annealing e Busca Tabu
• Aula 15 - Algoritmos Genéticos, GRASP e Path Relinking
• Aula 16 - Backtracking
• Aula 17 (3 aulas) - Programação Linear Inteira
• Aula Gurobi- Problemas Mochila e TSP+Lemon
• Aula 18 - Algoritmos de Aproximação: Aproximação Absoluta
• Aula 19 - Algoritmos de Aproximação: Fator de Aproximação
• Aula 20 - Algoritmos de Aproximação: Esquema de Aproximação / Problema da Mochila
• Aula 21 - Algoritmos de Aproximação: Arredondamento de programas lineares

 News:

• Problemas de 1 Milhão de dólares

Docente da Disciplina

Docente: Flávio Keidi Miyazawa
Sala: IC-30

Ementa

Reduções entre problemas. Programação Linear. Classes de Problemas. Tratamento de Problemas NP-difíceis.

Avaliação da Disciplina

Turma MC548-A e alunos cursando como Aproveitamento de Estudos
A avaliação da turma MC548-A e dos alunos cursando como Aproveitamento de Estudos será feita através de três provas P1,  P2 e P3 e um Trabalho T (implementação e texto), um exame E. A avaliação A será calculada através da fórmula:
A=(3.P1+4.P2+4.P3+4.T) / 15
Se A>=5.0, a nota final NF é calculada como:NF=A
Caso contrário, se A<5.0, então a nota final NF é calculada como: NF=(A+E)/2

Turma MC548-# (Turma Especial)
A avaliação da disciplina será feita através de três provas P1,  P2 e P3 e um exame E. A avaliação A será calculada através da fórmula:
A=(3.P1+4.P2+4.P3) / 11
Se A>=5.0, a nota final NF é calculada como:NF=A
Caso contrário, se A<5.0, então a nota final NF é calculada como: NF=(A+E)/2.

Alunos da turma especial que desejarem serem avaliados incluindo projeto/trabalho, poderão fazê-lo, porém devem fazer o pedido por escrito e assinado ao docente da disciplina, até um semana após a divulgação do projeto. Será da responsabilidade do aluno se informar quanto aos detalhes do projeto passados em aula. A avaliação neste caso será como feita na turma normal.

Aulas e Atendimento:

As aulas serão na sala CB08, das 8hs as 10hs, segundas-feiras e quartas-feiras.

O atendimento do professor será nas segundas-feiras das 13 as 14hs. Para atendimento, os alunos deverão chegar as 13hs e não havendo alunos, o atendimento estará finalizado. Não haverá atendimento na aula anterior a uma prova.

O atendimento do PED Pedro Henrique del Bianco Hokama será nas terças-feiras as 18hs na sala IC-322. Para atendimento, os alunos deverão chegar as 18hs e não havendo alunos, o atendimento estará finalizado.

Datas

Data da prova P1: 3 de Setembro de 2012.
Data da prova P2: 8 de Outubro de 2012.
Data da prova P3: 21 de Novembro de 2012.

Projeto/Trabalho: 19 de Novembro as 9hs da manhã.
Data do exame E : 10 de Dezembro de 2012.

Listas de Exercícios

Lista de reduções

Lista de Classes de Complexidade e Reduções de NP-Completude

Lista de Exatos e Aproximados

Projeto

Enunciado.
Exemplo: SCPsolver.tgz (Códigos base para o projeto)

Example of a Branch and Cut Algorithm using GUROBI and LEMON

Simple TSP Solver implementation for didactic purposes, using LEMON/COIN-OR and the integer programming solver GUROBI (GUROBI is free for academic institutions/purposes).

Bibliografia

T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduction to Algorithms, MIT Press, Third edition, 2009.

U. Manber, Algorithms: A Creative Approach, Addison-Wesley, 1989.

J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2005.

N. Ziviani,  Projeto de Algoritmos, Thompson, segunda edição, 2004.

M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. Pina Jr., J. Soares, Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, 23o Colóquio Brasileiro de Matemática, 2001 (errata). M.R. Cerioli, P. Feofiloff, C.G. Fernandes, F.K. Miyazawa (Eds.). Há exemplares do livro na biblioteca do IMECC.

A. Aho, J. Hopcroft, J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.


Ian Parberry and William Gasarch, Problems on Algorithms, 2002. Disponível na internet.

Horowitz e Sahni. Fundamentals of Computer Algorithms. Computer Science Press.

Christos H. Papadimitriou e Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity.

M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005. Errata da Primeira impressão, Segunda impressão. Este é o livro texto do curso de Algoritmos Probabilísticos.

V. Vazirani. Approximation Algorithms. 2001. Springer-Verlag. Eis uma versão disponível, mas incompleta. Este é o principal livro para quem deseja aprender mais sobre esta abordagem.