Projeto e Análise de Algoritmos - IPRJ - 2017.1

Material das Aulas:

Listas de Exercícios:

Exercícios Extras:

Datas Importantes:

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

Notas:

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 
    • Algoritmo de Força Bruta
    • Algoritmo de Boyer-Moore
    • Tries
    • Algoritmo de Força Bruta
    • Algoritmo de Programação Dinâmica
    • Busca de Padrões em Texto
    • Maior Subsequência Comum
  • 4. Algoritmos de Ordenação
    • Bubble Sort
    • Selection Sort
    • Insertion Sort
    • Merge Sort
    • Quick Sort
    • Counting Sort
    • Radix Sort
    • Bucket Sort
    • Métodos de Ordenação
    • Métodos de Ordenação de Complexidade Linear
  • 5. Algoritmos em Grafos
    • Algoritmo de Kahn;
    • Algoritmo baseado na busca em profundidade;
    • Algoritmo de Kosaraju;
    • Algoritmo de Tarjan;
    • Algoritmo de Prim;
    • Algoritmo de Kruskal;
    • Algoritmo de Dijkstra; 
    • Busca em Profundidade e Busca Largura;
    • Ordenação Topológica;
    • Componentes Fortemente Conectados;
    • Árvores Geradoras Mínimas;
    • Distâncias Mínimas;

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.