MC448 - Análise de Algoritmos I

Avaliação

Haverá três provas (P1, P2, P3) nas datas indicadas ao final deste documento. Cada prova será em classe e terá duração de 120 minutos. A média final será a média ponderada de P1, P2 e P3 com pesos iguais a 2, 3 e 4, respectivamente. Não serão ministradas provas antecipadas nem substitutivas.

Aviso: Qualquer tentativa de cola ou fraude, detetada durante uma prova ou posteriormente, acarretará nota zero naquela prova para todos os implicados, além das sansões regimentais, a critério do docente.

Tópicos Selecionados para o Exame

• Construção de algoritmos por indução
[1] - Capítulos 5
• Algoritmos de ordenação
[4] - Capítulos 1, 7 e 8 ([2] - Capítulos 2, 6 e 7)
• Limite inferior para ordenação e ordenação em tempo linear
[4] - Capítulo 9 ([2] - Capítulo 8)
• Estatísticas de Ordem
[4] - Capítulo 10 ([2] - Capítulo 9)
• Algoritmos elementares em grafos
[4] - Capítulo 23 ([2] - Capítulo 22)
• Árvore geradora mínima
[4] - Capítulo 24 ([2] - Capítulo 23)
• Caminhos Mínimos
[4] - Capítulo 25 ([2] - Capítulo 24)

Exercícios

Listas de exercícios serão atribuídas ao longo do semestre. Além de servir para maior fixação do material apresentado em classe, o conteúdo dos exercícios é considerado parte integrante do material visto e será assumido como parte da matéria coberta. Como as listas não farão parte da avaliação, suas soluções não serão coletadas. Os alunos são encorajados a resolver todos os exercícios individualmente e, só posteriormente, realizar discussão em grupo. Quaisquer dificuldades devem ser prontamente discutidas com o professor nos horários de atendimentos. Dúvidas não sanadas geram mais dúvidas.

Veja os exercícios recomendados.

Programa do Curso

• Introdução à análise de Algoritmos.
• Indução matemática.
• Complexidade de Algoritmos.
• Relações de recorrência.
• Construção de algoritmos por indução.
• Algoritmos de ordenação.
• Limite inferior para ordenação.
• Estatística de ordem.
• Estruturas de dados para conjuntos disjuntos.
• Programação Dinâmica.
• Análise amortizada.
• Algoritmos em grafos.

Referências Bibliográficas

1. [Livro-texto] U. Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
   
   As seguintes referências são equivalentes: A referência [4] é a primeira edição do livro.
   A segunda edição possui versões em inglês [3] e português [2].
   Verifique a equivalência de capítulos entre as edições.


2. [Livro-texto] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algoritmos - Teoria e Prática, 2002. Errata
3. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, McGraw-Hill, 2001.
4. T. Cormen, C. Leiserson, R. Rivest, Introduction to Algorithms , McGraw-Hill, 1990.

Outras referências recomendadas:


5. G. Brassard e P. Bratley, Algorithmics: theory and practice, Prentice-Hall, 1995.
6. N. Ziviani, Projeto de Algoritmos - 2a edição, Thomson, 2004.
7. A. Aho, J. Hopcroft, J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
8. D. E. Knuth, The Art of Computer Programming, Addison-Wesley, 1974.
9. J. L. Szwarcfiter, Grafos e Algoritmos Computacionais, Addison-Wesley, 1974.