CSI546 - Projeto e Análise de Algoritmos
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
- Crescimento assintótico: definições, notação assintótica e propriedades.
- Análise de complexidade de algoritmos
- Técnicas de projetos de algoritmos
- Algoritmos guloso: exemplos e prova de corretude.
- Programação dinâmica.
- Algoritmos aproximados.
- Limite inferior de problemas: árvore de decisão, oráculo e estratégia do adversário e redução.
- Intratabilidade
Bibliografia
- LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3a edition. Editora Addison Wesley;
- CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Introduction to Algorithms. 3a edition. Editora The MIT Press;
- KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Editora Addison Wesley.