MC548 - Projeto e Análise de Algoritmos II - 2011
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
Lista de discussão no Google Groups
 Bibliografia
   Veja um excelente 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 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

 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
A avaliação da turma MC548-A 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+3.T) / 14
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, 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 CB09, das 8hs as 10hs, segundas-feiras e quartas-feiras.

O atendimento do professor será após as aulas. Não haverá atendimento na aula anterior a uma prova.

O atendimento do PED Carlos Andrade () será nas quintas-feiras das 18 as 19hs na sala 363 do IC3,5.

Datas

Data da prova P1: 31 de Agosto de 2011.
Data da prova P2: 17 de Outubro de 2011 na sala PB16.
Data da prova P3:30 de Novembro de 2011 nas salas IC-351 e IC352.

Projeto: Prazo de pelo menos 1 mês após entrega do enunciado.
Data do exame E : 12 de Dezembro de 2011.

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: exemplo.tgz
Instâncias: instancias.tgz

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.