Análise e Projeto de Algoritmos

Prévia do material em texto

MAT A52 - Análise e Projeto de Algoritmos 
1. Apresentação do curso 
 Ementa da Disciplina 
• Analise de complexidade de algoritmos 
• Técnicas de projeto de algoritmos 
• Algoritmos de classificação interna 
• Algoritmos envolvendo sequências e conjuntos 
• Algoritmos probabilísticos 
• Algoritmos geométricos 
• Noções de algoritmos paralelos 
• Noções de NP-completude 
 
 Programa da Disciplina 
1. Introdução ao curso, conceitos iniciais 
2. Analise de algoritmos (notação assintótica, técnicas de resolução de recorrência, 
primeiros algoritmos de ordenação de sequencias) 
3. Dividir para conquistar (diversos problemas, suas solucoes e respectivas analises) 
4. Considerações adicionais sobre ordenação de sequencias (limite teórico e ordenação 
em tempo linear) 
5. Programação dinâmica (diversos problemas e soluções) 
6. Algoritmos gulosos 
7. Algoritmos baseados em enumeração e retrocesso (backtracking e branchand 
bound) 
8. Algoritmos geométricos 
9. Noções de algoritmos paralelos 
10. Complexidade de problemas (noções de NP-completude) 
Bibliografia 
• Existem diversos livros que cobrem o assunto do curso 
• Muito material encontra-se disponível na Internet 
– Recomenda-se cautela ao consultar fontes na Internet! 
Curso preparado com base em... 
Referencias 
 
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to 
Algorithms. The MIT Press, 2nd edition, 2003. 
[2] S. Dasgupta, C. Papadimitrious, and U. Vazirani. Algorithms. McGraw-Hill, 1st edition, 2008. 
[3] Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 3rd edition, 
1989. 
[4] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of N P- 
Completeness. W.H.Freeman and Company, 1979. 
[5] Donald D. Knuth. The Art of Computer Programming: Sorting and Searching. Addison-
Wesley, 3rd edition, 1973.