Análise de Algoritmos (1/04, 1/05, 2/06, 2/07, 2/13, 2/15, 2/17)

Programa da Disciplina

Objetivos:

• Desenvolver a capacidade de avaliar a complexidade e a qualidade dos algoritmos propostos para um determinado problema.
• Estudar os algoritmos básicos para as classes mais importantes de problemas tratados em computação.
• Compreender a importância da implementação e a sensibilidade do comportamento dos algoritmos nas implementações.
• Conhecer as potencialidades e as limitações do conhecimento algorítmico atual.
• Apresentar as tendências da pesquisa na área.

Ementa:

1. Problemas Algorítmicos, Correção e Eficiêcia de Algoritmos. 2. Indução Finita e Solução de Recorrências. 3. Algoritmos de Ordenação, Seleção e Mediana. 4. Estrutura de Dados: Filas, Pilhas, Heaps, Hashing, Árvores de Busca. 5. Divisão e Conquista, Programação Dinâmica e Método Guloso. 6. Algoritmos em Grafos. 7. Noções da Teoria de Complexidade: as Classes P, NP, e CoNP e Algoritmos Aproximados. 8. Tópicos Avançados.

Bibliografia:

• R. Sedgewik e K. Wayne, Algorithms. (4th ed) Pearson Education, 2011.*
• T.H. Cormen, C. Leiserson, R. Rivest e C. Stein, Introduction to Algorithms (3rd ed), MIT Press, 2009.*
• T.H. Comen, Algorithms Unlocked.  MIT Press, 2013.*
• M.T. Goodrich e R. Tamassia, Algorithm Design - Foundations, Analysis, and Internet Examples, John Wiley &Sons, 2002.(Projeto de Algoritmos - Fundamentos, Análise e Exemplos da Internet, Bookman, 2004 - Versão em Português)
• S. Baase e A. Van Gelder A., Computer Algorithms: Introduction to Design and Analysis (3rd ed), Addison-Wesley, 2000.
• U. Manber, Algorithms: A Creative Approach, Addison-Wesley, 1989.
• A.V. Aho, J.E. Hopcroft and J.F. Ullman, The design and analysis of computer algorithms, Reading: Addison-Wesley, 1974.
• M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.