CSI546 - Projeto e Análise de Algoritmos

Objetivo

Desenvolver o conteúdo programático proposto, possibilitando a compreensão de conceitos e técnicas de análise e projeto de algoritmos. Apresentar e consolidar noções de limitações das classes de algoritmos, em termos de complexidade e poder de solução de problemas.

Ementa

Crescimento assintótico de funções e notação assintótica. Técnicas de análise de complexidade de algoritmos. Técnicas de projeto de algoritmos: força bruta, incremental e divisão e conquista. Algoritmos gulosos. Programação dinâmica. Algoritmos aproximados. Provas de limite inferior. Problemas intratáveis.

Conteúdo programático

  1. Crescimento assintótico: definições, notação assintótica e propriedades.
  2. Análise de complexidade de algoritmos
  3. Técnicas de projetos de algoritmos
  4. Algoritmos guloso: exemplos e prova de corretude.
  5. Programação dinâmica.
  6. Algoritmos aproximados.
  7. Limite inferior de problemas: árvore de decisão, oráculo e estratégia do adversário e redução.
  8. Intratabilidade

Bibliografia

  1. LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3a edition. Editora Addison Wesley;
  2. CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Introduction to Algorithms. 3a edition. Editora The MIT Press;
  3. KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Editora Addison Wesley.