Í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:2007-1
Tabela de Conteúdos
Página descontinuada, provavelmente o material não é mais acessível.
Análise e Desenvolvimento de Algoritmos (2007/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
Professoras: 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: Terça/Quinta, 15.30-17.10, Sala NN, prédio 43425.
Consultas: Quarta, 14-16.
Detalhes: Vê o Página no PPGC.
Resultados
Materiais
Aulas
Notas de aula (Última atualização: 04/07/2007.)
| No. | Data | Tópicos | Notas | Exercícios | Leitura |
|---|---|---|---|---|---|
| 1 | 13/03 | Administrativa, Introdução. | p.1-19,A.1,A.2 | TV1,2.1 | |
| 2 | 15/03 | Notação para classes de funções. | p.A.3,19-29 | 1.1-1.6 | TV2.3 |
| 3 | 20/03 | Palestra convidada de Mauricio Resende | |||
| 4 | 22/03 | Análise de complexidade pessimista. | p.31-43 | TV3 | |
| 5 | 27/03 | Exercícios. | p.43-50 | Slides+2.2,2.3 | |
| 6 | 29/03 | Complexidade média. | A.5,p.51-58 | TV4 | |
| 7 | 03/04 | Complexidade média. | p.59-65 | 2.1-2.7 | TV4 |
| 8 | 05/04 | Métodos: Divisão e conquista. | p.119-124 | TV5.3 | |
| 9 | 10/04 | Métodos: Divisão e conquista. | p.125-129 | TV5.3 | |
| 10 | 12/04 | Métodos: Divisão e conquista. | p.130-131 | TV5.3 | |
| 11 | 17/04 | Métodos: Programação dinâmica. | p.97-101 | TV5.2 | |
| 12 | 19/04 | Métodos: Programação dinâmica. | p.102-109 | TV5.2 | |
| 13 | 24/04 | Métodos: Programação dinâmica. | p.110-118 | TV5.2 | |
| 14 | 26/04 | Métodos: Algoritmos gulosos. | p.73-83 | TV5.1 | |
| 01/05 | Feriado: Dia do Trabalho | ||||
| 15 | 03/05 | Métodos: Algoritmos gulosos. | p.84-95 | 3.1,3.2 | TV5.1 |
| 16 | 08/05 | Prova | |||
| 17 | 10/05 | Métodos: Backtracking. | p.135-141 | ||
| 15/05 | Semana acadêmica | ||||
| 17/05 | Semana acadêmica | ||||
| 18 | 22/05 | Métodos: Backtracking. | p.142-149 | ||
| 19 | 24/05 | Classes de complexidade. | |||
| 20 | 29/05 | Classes de complexidade. | |||
| 21 | 31/05 | Classes de complexidade. | |||
| 22 | 05/06 | Classes de complexidade. | |||
| 07/06 | Feriado: Corpus Cristi | ||||
| 23 | 12/06 | Métodos: Aproximação. | |||
| 24 | 14/06 | Métodos: Aproximação. | |||
| 25 | 19/06 | Métodos: Busca local. | |||
| 26 | 21/06 | Métodos: Busca local. | |||
| 27 | 26/06 | Métodos: Busca local. | |||
| 28 | 28/06 | Apresentação dos trabalhos. | |||
| 29 | 03/07 | Apresentação dos trabalhos. | |||
| 30 | 05/07 | Apresentação dos trabalhos. | |||
| 12/07 | Término oficial das aulas. |
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.
cmp155/2007-1.txt · Esta página foi modificada pela última vez em: 2010/01/18 15:45 (Edição externa)
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
