IPRJ - Projeto e Análise de Algoritmos (2016.1) PDF Print E-mail

Material das Aulas:

Listas de Exercícios:

Exercícios Extras:

Códigos:

Datas Importantes:

  • 20/10: Prova Teórica (P1) sobre complexidade de algoritmos, técnicas de projeto de algoritmos e algoritmos de processamento de texto;
  • 12/12: Prova Teórica (P2) sobre algoritmos de ordenação e algoritmos em grafos;
  • 19/12: Prova Final (PF) envolvendo todo o conteúdo do curso;

Notas:

  • Notas (Atualizado em: 19/12 às 14h)

Programa do Curso:

  • 1. Complexidade de Algoritmos
    • Algoritmos
    • Eficácia vs Eficiência
    • Complexidade de Algoritmos
    • Análise Assintótica
  • 2. Técnicas de Projeto de Algoritmos
    • Força Bruta/Busca Completa/Backtracking
    • Divisão e Conquista
    • Método Guloso
    • Programação Dinâmica
  • 3. Algoritmos de Processamento de Texto 
    • Busca de Padrões em Texto
      • Algoritmo de Força Bruta
      • Algoritmo de Boyer-Moore
      • Tries
    • Maior Subsequência Comum
      • Algoritmo de Força Bruta
      • Algoritmo de Programação Dinâmica
  • 4. Algoritmos de Ordenação
    • Métodos de Ordenação
      • Bubble Sort
      • Selection Sort
      • Insertion Sort
      • Merge Sort
      • Quick Sort
    • Métodos de Ordenação de Complexidade Linear
      • Counting Sort
      • Radix Sort
      • Bucket Sort
  • 5. Algoritmos em Grafos
    • Busca em Profundidade e Busca Largura;
    • Ordenação Topológica;
      • Algoritmo de Kahn;
      • Algoritmo baseado na busca em profundidade;
    • Componentes Fortemente Conectados;
      • Algoritmo de Kosaraju;
      • Algoritmo de Tarjan;
    • Árvores Geradoras Mínimas;
      • Algoritmo de Prim;
      • Algoritmo de Kruskal;
    • Distâncias Mínimas;
      • Algoritmo de Dijkstra; 


Bibliografia Principal:

Cormen, Leiserson, Rivest e Stein. Algoritmos – Teoria e Prática, 2ª. Edição, Editora Campus, 2002.

Halim e Halim. Competitive Programming, 3rd Edition, 2003.

Levitin. Introduction to the Design and Analysis of Algorithms, 3rd Edition, 2011.