Í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:2008-1
Tabela de Conteúdos
Página descontinuada, provavelmente o material não é mais acessível.
Análise e Desenvolvimento de Algoritmos (2008/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-15.10, Sala 107, prédio 43425.
Consultas: Ad hoc.
Detalhes: Vê o Página no PPGC.
Notícias
- Nova data da prova 1: 07/05
- Prova antiga com solução para preparação disponível!
Materiais
- Página da disciplina em 2007/1
Aulas
| No. | Data | Tópicos | Notas | Exercícios | Leitura |
|---|---|---|---|---|---|
| 1 | 10/03 | Administrativa, Introdução. | p.1-19,A.1,A.2 | TV1,2.1 | |
| 2 | 12/03 | Notação para classes de funções. | p.A.3,19-29 | 1.1-1.6 | TV2.3 |
| 3 | 17/03 | Análise de complexidade pessimista. | p.31-48 | ||
| 4 | 19/03 | Análise de complexidade pessimista. | p.31-48 | 2.1-2.4 | TV3 |
| 5 | 24/03 | Complexidade média. | A.5,p.48-58 | TV4 | |
| 6 | 26/03 | Complexidade média. | p.59-67 | 2.1-2.7 | TV4 |
| 7 | 31/03 | Métodos: Divisão e conquista. | p.111-118 | T1 | TV5.3 |
| 8 | 02/04 | Métodos: Divisão e conquista. | p.119-120 | TV5.3 | |
| 9 | 07/04 | Métodos: Divisão e conquista. | p.121-125 | E1, S1 | TV5.3 |
| 10 | 09/04 | Métodos: Programação dinâmica. | p.93-95,100-101,106-112 | TV5.2 | |
| 11 | 14/04 | Métodos: Programação dinâmica. | p.95-99,106-113 | TV5.2 | |
| 12 | 16/04 | Métodos: Programação dinâmica. | p.104-105 | TV5.2 | |
| 21/04 | Feriado: Tiradentes | ||||
| 13 | 23/04 | Métodos: Algoritmos gulosos. | p.73-83 | E2,S2 | TV5.1 |
| 14 | 28/04 | Métodos: Algoritmos gulosos. | p.84-92 | 3.1,3.2 | TV5.1 |
| 15 | 30/04 | Métodos: Backtracking. | Artigo | ||
| 16 | 05/05 | Métodos: Backtracking. | p.137-151 | ||
| 17 | 07/05 | Prova | P, S | ||
| 18 | 12/05 | Classes de complexidade. | p.171-180 | TV7.1,7.2 | |
| 19 | 14/05 | Classes de complexidade. | TV7.3 | ||
| 20 | 19/05 | Classes de complexidade. | p.181-198 | ||
| 21 | 21/05 | Classes de complexidade. | p.199-208 | ||
| 26/05 | Semana academica | ||||
| 28/05 | Semana academica | ||||
| 22 | 02/06 | Métodos: Aproximação. | p.151-170 | A3.1.1-3,A2.1.1 | |
| 23 | 04/06 | Métodos: Aproximação. | p.151-170 | ||
| 24 | 09/06 | Métodos: Aproximação. | p.151-170 | ||
| 25 | 11/06 | Métodos: Busca local. | |||
| 26 | 16/06 | Métodos: Busca local. | |||
| 27 | 18/06 | Métodos: Busca local. | |||
| 23/06 | Sem aula | ||||
| 25/06 | Sem aula | ||||
| 28 | 30/06 | Apresentação dos trabalhos. | |||
| 29 | 02/07 | Apresentação dos trabalhos. | |||
| 30 | 07/07 | Apresentação dos trabalhos. | |||
| 10/07 | Término oficial das aulas. |
Livros: TV=Toscani/Veloso. A=Ausiello.
Bibliografia
- 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.
cmp155/2008-1.txt · Esta página foi modificada pela última vez em: 2010/03/08 11:28 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
