Índice
-
- INF05010: Otimização combinatória
- INF05016/CMP 588: Algoritmos avançados
- CMP612: Algorithms
- CMP268: Técnicas de busca heurística
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.
Professores: 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 111.
Consultas: Seg 15.30-17.00.
Detalhes: Ver a página no PPGC.
No. | Data | Tópicos | Cap.1) | Exercícios | Soluções | Leitura |
---|---|---|---|---|---|---|
1 | 05/03 | Administrativa, Introdução. Notação assintótica. | 1,2 | E1 | S1 | KT1-3 |
2 | 07/03 | Notação assintótica. Análise de complexidade. | 1,2 | KT1-3 | ||
3 | 12/03 | Divisão e conquista. | 6 | KT5 | ||
4 | 14/03 | Divisão e conquista. | 6 | KT5 | ||
5 | 19/03 | Divisão e conquista. | 6 | E2 | S2 | KT5 |
6 | 21/03 | Algoritmos gulosos. | 4 | KT4 | ||
7 | 26/03 | Algoritmos gulosos. | 4 | KT4 | ||
8 | 28/03 | Algoritmos gulosos. | 4 | E3 | S3 | KT4 |
9 | 02/04 | Programação dinâmica. | 5 | KT6 | ||
10 | 04/04 | Programação dinâmica. | 5 | KT6 | ||
11 | 09/04 | Programação dinâmica. | 5 | KT6 | ||
12 | 11/04 | Backtracking, Branch-and-bound. | 7 | E4 | S4 | |
13 | 16/04 | Backtracking, Branch-and-bound. | 7 | |||
14 | 18/04 | Fluxos em redes (aula a distância). | 14.1 | KT7 | ||
15 | 23/04 | Fluxos em redes. | 14.1 | KT7 | ||
16 | 25/04 | Fluxos em redes. | 14.1 | KT7 | ||
17 | 30/04 | Emparelhamentos. | 14.2 | |||
18 | 02/05 | Emparelhamentos. | 14.2 | |||
19 | 07/05 | Emparelhamentos. | 14.2 | |||
20 | 09/05 | Algoritmos randomizados. | E5 | S5 | KT13 | |
21 | 14/05 | Algoritmos randomizados. | KT13 | |||
22 | 16/05 | Algoritmos randomizados. | KT13 | |||
21/05 | Semana academica | |||||
23/05 | Semana academica | |||||
23 | 28/05 | Algoritmos randomizados. | 15 | KT13 | ||
24 | 30/05 | Teoria da complexidade. | 16-19 | KT8, | ||
25 | 04/06 | Teoria da complexidade. | 16-19 | KT8,9 | ||
26 | 06/06 | Teoria da complexidade. | 16-19 | E6 | S6 | KT8,9 |
27 | 11/06 | Apresentação dos trabalhos. | ||||
28 | 13/06 | Apresentação dos trabalhos. | ||||
29 | 18/06 | Apresentação dos trabalhos. | ||||
30 | 25/06 | Prova | P | SP | ||
27/06 | Prova de recuperação. | |||||
14/07 | Término oficial das aulas. |
Livros: TV=Toscani/Veloso. A=Ausiello, KT=Kleinberg/Tardos.
A nota final é composto pela nota obtido na solução dos exercícios (1/3), a nota do projeto (1/3) e a nota da prova (1/3). Informações sobre o projeto: aqui.