Disciplina: Projeto e Análise de Algoritmos – BCC241 – 1/2013
Turmas: 11
Prof. Anderson Almeida Ferreira
Horário: 13h30 às 15h10
Segunda-feira e quarta-feira: Sala 207 - Pavilhão de Aulas
Ementa:
Medidas de complexidade.
Análise assintótica de complexidade.
Medidas empíricas.
Análise de algoritmos iterativos e recursivos.
Noções de teoria da complexidade.
Estratégias de projeto de algoritmos:
divisão e conquista,
método guloso,
programação dinâmica,
backtracking,
branch&bound,
probabilísticos.
Objetivos:
Ao final do curso espera-se que os alunos possuam os seguintes conhecimentos e habilidades:
Dados dois algoritmos, compará-los quanto aos diferentes critérios de desempenho, identificando o melhor
Dado um problema, identificar, entre as diversas estratégias estudadas, aquela(s) que melhor se aplica(m) e implementá-la(s)
[DPV] Algoritmos, S. Dasgupta, C. Papadimitriou, U. Varizani, McGraw-Hill, 2009. Versão gratuita em inglês disponível em (http://www.cs.berkeley.edu/~vazirani/algorithms.html).
[Silva] Projeto e Análise de Algoritmos, Elton Silva, Apostila do Curso, 2010.
[CLRS] Algoritmos: Teoria e Prática, Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Cliford Stein. 2a. edição, 2001.
Complementar
[Hrom] Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms. Jurai Hromkovi?, 2005.
[LLM] Mathematics for Computer Science, Eric Lehman, Tom Leighton, Albert Meyer, 2010. (Disponível em http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/).
[Shafer] A Pratical Introduction to Data Structures and Algorithms Analysis (C++ or Java), Clifford Shaffer, 2011 (Disponível em http://people.cs.vt.edu/~shaffer/Book/)
[BB] Fundamentals of Algorithmics, Gilles Brassard and Paul Bratley, Prentice Hall, 1996.