IPRJ - Projeto e Análise de Algoritmos (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
- 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;
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.
Semestres Anteriores:
|