Ferramentas de Utilizador

Ferramentas de Site


cmp155:homepage

Análise e Desenvolvimento de Algoritmos (2012/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: 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.

Notícias

  • Nova versão da notas de aula disponível
  • Definição do projeto atualizado.

Resultados

Materiais

Aulas

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.

Avaliação

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.

Bibliografia

Locations of visitors to this page

1)
Capítulo nas notas de aula
cmp155/homepage.txt · Esta página foi modificada pela última vez em: 2012/06/27 13:10 por marcus