GA-026 Algoritmos I (Parte 1)

Programa de Pós-Graduação de Modelagem Computacional, P4/2018
Laboratório Nacional de Computação Científica
Professores: Luiz Gadelha
Horário e local: 3ª e 5ª de 15:00 às 16:30h, Sala 6

Ementa.

  • Fundamentos matemáticos: Indução, recursão;
  • Análise assintótica;
  • Ordenação: inserção, seleção, quicksort, mergesort, heapsort, radix sort;
  • Busca: sequencial, binária, hashing, árvores binárias de busca, árvores balanceadas;
  • Grafos: caminhos mínimos, algoritmo de Dijkstra, algoritmo guloso; programação dinâmica;
  • Sistemas de Equações Algébricas Lineares;
  • Números Aleatórios.

Avaliação da parte 1 do curso (50%). Consistirá de listas semanais de exercícios e de uma prova.

A nota será baseada nas listas semanais de exercícios (20%) e na prova (30%).

  • 25/09: Apresentação dos objetivos, ementa e forma de avaliação do curso. Introdução a algoritmos; ordenação por inserção e sua complexidade. [PDF]
  • 27/09: Prova de correção por indução, correção da ordenação por inserção.
  • 02/10: Divisão e conquista: mergesort e sua análise de complexidade.
  • 04/10: Crescimento de funções e notações para crescimento assintótico.
  • 09/10: Divisão e conquista: algortimo de Strassen para multiplicação de matrizes.
  • 16/10: Relações de recorrência: técnica de substituição, árvores de recursão.
  • 18/10: Relações de recorrência: Teorema Mestre.
  • 23/10: Ordenação: Heapsort.
  • 25/10: Ordenação: Quicksort.
  • 07/10: Prova.
  • Cormen, T., Leiserson, C., Rivest, R., Stein, C. (2009). Introduction to Algorithms. MIT Press.
  • Aho, A., Hopcroft, J., Ullman, J. (1983). Data Structures and Algorithms. Addison-Wesley.