Daniel Gondim - Técnicas de Análise de Algoritmos

Horário: Segundas 07h às 09h | Sextas 07h às 09h

Local: Lab. IV | B202

Objetivo:

A disciplina de Técnicas de Análise de Algoritmo tem por objetivo das aos alunos o embasamento necessário à análise da complexidade de algoritmos do ponto de vista de tempo e espaço, bem como uma visão geral dos principais paradigmas de projeto de algoritmos de tal forma que sejam capazes de identificar quando um determinado paradigma pode/deve ser aplicado ou não. Além disso, a disciplina também objetiva fornecer embasamento da teoria da complexidade de problemas computacionais.

Ementa:

Análise e Complexidade de Algoritmos:
- Medidas de Tempo e Espaço de um Algoritmo
- Notações O, Omega e Theta
- Recorrências
- Análise de Algoritmos de Ordenação
Paradigmas de Projeto de Algoritmos:
- Indução
- Recursividade
- Tentativa e Erro (backtracking)
- Divisão e Conquista
- Programação dinâmica
- Algoritmos gulosos
Problemas NP-Completos:
- Classificação de problemas computacionais
- As classes P, NP-Difícil, NP e NP-Completo
- Redutibilidade

Avaliação:

Bibliografia:

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), Ed. Campus (2002).
S. Skiena. The Algorithm Design Manual. Second Edition. Springer. (2012).
J. Kleinberg e E. Tardos, Algorithm Design, Addison Wesley, (2005).

Notas de Aulas:

Cronograma

16/11
- Dia não-letivo
19/11
- Divisão e Conquista
- Miniteste 8
23/11
- Divisão e Conquista
26/11
- Programação Dinâmica
- Miniteste 9
30/11
- Sem aula
03/12
- Programação Dinâmica
- Miniteste 10
07/12
- Algoritmos Gulosos
- Divulgação do Miniteste 12 (para ser feito em dupla - entrega dia 12/12)
10/12
- Miniteste 11
14/12
- Prova Final

Técnicas de Análise de Algoritmos - Manhã