MC548 - Projeto e Análise de Algoritmos II - 2011
Informações sobre a disciplina
Prof. Flávio Keidi Miyazawa
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:

Docente: Flávio Keidi
Miyazawa
Sala: IC-30
Ementa
Avaliação
da Disciplina
Turma MC548-A
Turma MC548-# (Turma Especial)
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
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.
