Índice
-
- INF 5010: Otimização combinatória
- INF 5016: Algoritmos avançados
- INF 5023: Técnicas de busca heurística.
Ferramentas de Utilizador
Barra Lateral
cmp155:2010-1
Tabela de Conteúdos
Análise e Desenvolvimento de Algoritmos (2010/1)
Somebody once asked John Hopcroft about the problem of P and NP. He answered: “On Tuesdays, I try to prove that they are equal, on the rest of the week - that they are different.” I believe that he has reduced the time to try to show that they are equal to Sunday afternoons.
Informações gerais
Professores: Luciana Buriol, Marcus Ritt
Carga horária: 60 h (em 30 aulas de 2h)
Créditos: 4
Súmula: Complexidade de algoritmos. Cálculo de complexidade. Métodos básicos de construção de algoritmos. Classes de complexidade. Algoritmos aproximativos.
Horário/Sala: Seg/Qua 13.30, Sala 116, prédio 43425.
Consultas: Seg 15.30.
Detalhes: Ver a página no PPGC.
Notícias
- 8/3/2010: Primeiro dia de aula.
Resultados
Materiais
- Notas de aula (atualizado dia 2/7/2010).
- Definição do segundo trabalho prático
Aulas
| No. | Data | Tópicos | Notas | Exercícios | Leitura |
|---|---|---|---|---|---|
| 1 | 08/03 | Administrativa, Introdução. | p.1-19,A.1,A.2 | TV1,2.1 | |
| 2 | 10/03 | Notação para classes de funções. | p.A.3,19-29 | 1.1-1.6 | TV2.3 |
| 3 | 15/03 | Análise de complexidade pessimista. | p.31-48 | ||
| 4 | 17/03 | Análise de complexidade pessimista. | p.31-48 | 2.1-2.4 | TV3 |
| 5 | 22/03 | Complexidade média. | A.5,p.48-58 | TV4 | |
| 6 | 24/03 | Complexidade média. | p.59-67 | 2.1-2.7 | TV4 |
| 7 | 29/03 | Métodos: Divisão e conquista. | p.111-118 | TV5.3 | |
| 8 | 31/03 | Métodos: Divisão e conquista. | p.119-120 | TV5.3 | |
| 9 | 05/04 | Métodos: Divisão e conquista. | p.121-125 | TV5.3 | |
| 10 | 07/04 | Métodos: Programação dinâmica. | p.93-95,100-101,106-112 | TV5.2 | |
| 11 | 12/04 | Métodos: Programação dinâmica. | p.95-99,106-113 | TV5.2 | |
| 12 | 14/04 | Métodos: Programação dinâmica. | p.104-105 | TV5.2 | |
| 13 | 19/04 | Métodos: Algoritmos gulosos. | p.73-83 | TV5.1 | |
| 21/04 | Feriado: Tiradentes | ||||
| 14 | 26/04 | Métodos: Algoritmos gulosos. | p.84-92 | 3.1,3.2 | TV5.1 |
| 15 | 28/04 | Classes de complexidade. | p.179-189 | TV7.1,7.2, AB 1 | |
| 16 | 03/05 | Classes de complexidade. | p.189-206 | TV7.3, AB 2,3 | |
| 17 | 05/05 | Classes de complexidade. | p.207-218 | EC | |
| 18 | 10/05 | Prova | P, S | ||
| 19 | 12/05 | Métodos: Backtracking e Branch&Bound | p.137-151 | ||
| 20 | 17/05 | Métodos: Algoritmos randomizados. | |||
| 21 | 19/05 | Métodos: Algoritmos randomizados. | |||
| 24/05 | Semana academica | ||||
| 26/05 | Semana academica | ||||
| 22 | 31/05 | Métodos: Fluxos em redes. | |||
| 23 | 02/06 | Métodos: Fluxos em redes. | |||
| 24 | 07/06 | Métodos: Emparelhamentos. | |||
| 25 | 09/06 | Métodos: Emparelhamentos. | |||
| 26 | 14/06 | Métodos: Aproximação. | p.151-170 | A3.1.1-3,A2.1.1 | |
| 27 | 16/06 | Métodos: Aproximação. | p.151-170 | ||
| 28 | 21/06 | Apresentação dos trabalhos. | |||
| 29 | 23/06 | Apresentação dos trabalhos. | |||
| 30 | 28/06 | Apresentação dos trabalhos. | |||
| 07/07 | Prova de recuperação. | ||||
| 17/07 | Término oficial das aulas. |
Livros: TV=Toscani/Veloso. A=Ausiello, AB=Arora/Barak.
Bibliografia
- Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 2nd edition, 2001.
- Michael R. Garey and David S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. Freeman, 1979.
- E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1984.
- Laira Vieira Toscani and Paula A. S. Veloso. Complexidade de Algoritmos. Editora Sagra Luzzatto, 2a edition, 2005.
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation – Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999.
- Bernhard H. Korte and Jens Vygen. Combinatorial optimization theory and algorithms. Springer, 4th edition, 2008. INF 65.012.122 K85c.
- Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, dover edition, 1982.
- Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.
- S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algoritmos. McGraw-Hill, 2009.
cmp155/2010-1.txt · Esta página foi modificada pela última vez em: 2010/10/28 13:29 por marcus
Ferramentas de Página
Excepto menção em contrário, o conteúdo neste wiki está sob a seguinte licença: CC Attribution-Noncommercial-Share Alike 4.0 International
