Análise e Técnicas de Algoritmos

 

Jorge César Abrantes de Figueiredo

 

Período: 2003.2


Veja a sua situação de faltas aqui.
Veja o quadro de notas aqui.


Horário: Q103 e X123

Sala:  Auditório Mário Hattori

 

Ementa: Análise de Complexidade de algoritmos. Análise Assintótica. Divisão-e-conquista. Problemas de otimização. Algoritmos gulosos. Programaçao dinâmica. Backtracking. Problemas NP-Completos. Aplicações. 

 

Objetivos: Curso voltado para o estudo de técnicas e análise de algoritmos. Em especial, o curso contemplará várias técnicas de criação de algoritmos, o estudo da complexidade computacional de algoritmos, além de vários exemplos de algoritmos para a solução de problemas importantes e comumente encontrados na prática.

 

Formato do Curso: O Curso terá a duração de 60 horas (4 créditos), compreendendo 33 aulas. Como ocorre com várias disciplinas deste período, o curso contempla duas aulas semanais: uma de 3 horas de duração (quarta), e a outra de uma hora de duração (sexta). Na aula da quarta-feira, faremos um intervalo de 15 minutos.

 

Avaliação: A avaliação constará de 6 exames parciais (mini-provas). A nota final é a média aritmética das notas das mini-provas. Cada aluno pode deixar duas provas para a reposição (uma dentre as duas primeiras mini-provas e mais uma dentre as quatro mini-provas restantes). Não existe a figura de reposição da menor nota. As datas dos exames de avaliação já estão definidas:

 

 

Planejamento das Aulas: O curso está dividido em três partes. A primeira parte enfatiza os fundamentos e conceitos básicos de algoritmos. A segunda parte contempla técnicas avançadas de projeto e análise de algoritmos. A última parte é dedicada a aplicações de algoritmos, bem como ao estudo dos problemas NP-Completos. O detalhamento do programa é o seguinte:

 

Aulas
 Data
 Assunto
 Observação
1-2
 19/11/2003
21/11/2003
  • Apresentação do curso.
  • Motivação e introdução informal à análise de algoritmos.
  • Corretude de algoritmos recursivos
  • Corretude de algoritmos não-recursivos
3-4
 26/11/2003
28/11/2003
  • Análise de complexidade  de algoritmos.
  • Análise assintótica.
  • Análise de algoritmos simples.
  • Relação de recorrência
5
 03/12/2003
  • Análise de algoritmos recursivos
  • Revisão
6
 05/12/2003
  • Prova 1
7-8
 10/12/2003
12/12/2003
  • Divisão-e-conquista.
  • Multiplicação de inteiros grandes.
  • Multiplicação de matrizes.
9
 17/12/2003
  • Análise de algoritmos de ordenação.
  • Ordenação por comparação.
  • Ordenação em tempo linear.
  • Revisão
10
 19/12/2003
  • Prova 2
11
 24/12/2003
  • Reposição
12
 04/02/2004
  • Problemas de otimização
  • Método Guloso: conceitos básicos, cálculo do trôco, problema da mochila, código de Huffman
  • Método Guloso (ps, pdf)
  • Lista de Exercício 5 (ps, pdf)
13
 06/02/2004
  • Método Guloso: mais exemplos
14
 11/02/2004
  • Programação Dinâmica: Conceitos básicos e eexemplos introdutórios. Mochila binária.
15
 13/02/2004
  • Multiplicação de matrizes com PD
16
 18/02/2004
  • Mais exemplos de PD: maior subsequência comum, edit distance
  • Aula de dúvidas
17
 20/02/2004
  • Prova 3
18
 03/03/2004
  • Algoritmos de Grafos
19
 05/03/2004
  • Algoritmos de grafos
  • Backtracking
20
 10/03/2004
  • Backtracking 
  • Branch-and-Bound
21
 12/03/2004
  • Branch-and-bound
22
 17/03/2004
  • Prova 4
23
 31/03/2004
  • Prova 5
24
 02/04/2004
  • Reconhecimento de Padrão
  • Material Reonhecimento de padrão (html, pdf)
25
 07/04/2004
  • NP-completude
26
 14/04/2004
  • Prova 6
27
 16/04/2004
  • Prova de reposição
28
 21/04/2004
  • Prova final


Bibliografia: