GA-026 Algoritmos I

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

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, inversão de matrizes;

Avaliação. Consistirá de listas semanais de exercícios, de um trabalho e de uma prova.

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

  • 24/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]
  • 26/09: Classes de crescimento assintótico de funções, projeto de algoritmos com a técnica de dividir-para-conquistar, Mergesort. [PDF]
  • 03/10: Classes de crescimento assintótico de funções, introdução ao Quicksort. [PDF]
  • 08/10: Quicksort, equações de recorrência: método da substituição. [PDF]
  • 10/10: Resolução de problemas.
  • 17/10: Demonstração Teorema Mestre.
  • 22/10: Demonstração Teorema Mestre, Heaps. [PDF]
  • 24/10: Heapsort
  • 29/10: Correção Heapsort, multiplicação de matrizes (algoritmo convencional e por divisão e conquista), introdução ao algoritmo de Strassen.
  • 05/11: Reunião para definição dos temas dos trabalhos.
  • 07/11: Algoritmo de Strassen, limite inferior para ordenação por comparação.
  • 12/11: Árvores de busca binárias: definição, percorrimento em ordem, busca.
  • 14/11: Árvores de busca binárias: busca iterativa, máximo, mínimo, sucessor, inserção, remoção.
  • 19/11: Algoritmos multiprocessados: multiprocessamento dinâmico
  • 21/11: Algoritmos multiprocessados: modelo de execução
  • 26/11: Algoritmos multiprocessados: medidas de desempenho
  • 03/12: Algoritmos multiprocessados: escalonamento
  • 05/12: Algoritmos multiprocessados: análise de algoritmos multiprocessados.
  • 10/12: Apresentações:
    • 15:00: Antonio Lacerda Jr.
    • 15:15: Gustavo Bezerra
    • 15:30: Douglas Machado
    • 15:45: Elaine Bernine
    • 16:00: Emanuelle Paixão
    • 16:15: Mateus Oliveira
  • 12/12: Apresentações:
    • 15:00: Natanael Bento
    • 15:15: Raquel Mattoso
    • 15:30: Renato Borseti
    • 15:45: Matheus Silva
    • 16:00: Afrânio Gonçalves
    • 16:15: Ismael Ledoino
  • 17/12: 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.