PGC101-Análise de Algoritmos

EMENTA

DISCIPLINA: Análise de Algoritmos

CÓDIGO: PGC101

CARGA HORÁRIA: 90h

CRÉDITOS: 5

OBJETIVOS GERAIS DA DISCIPLINA: Introduzir as técnicas básicas de eficiência de algoritmos, com cálculo de tempo de pior caso e tempo médio. Isto é feito com a apresentação de um grande número de algoritmos que servem de ponto de partida para o desenvolvimento de novos algoritmos. Considera-se também uma introdução ao estudo comparativo dos principais métodos de computação, particularmente nos aspectos de complexidade de tempo e de espaço de problemas computacionais.

EMENTA DO PROGRAMA:

- Análise de Algoritmos –  Tempo de Execução - Notação assintótica
- Técnicas de estruturação de Algoritmos.
- Algoritmos de Ordenação, 
- Estruturas de dados elementares e avançadas
- Programação dinâmica – algoritmos gulosos
- Algoritmos de Busca em grafos.

 

DESCRIÇÃO DO PROGRAMA: 

1. Fundamentos
Algoritmos – Análise de Algoritmos  – Tempo de Execução no pior caso e caso médio  Projeto de Algoritmos
Crescimento de funções – notação assintótica
Recorrência 
Análise probabilistica e algoritmos aleatórios
 
2. Algoritmos de Ordenação
Heapsort
Quicksort
Ordenação em tempo linear
Medianas e estatísticas de ordem
 
3. Estrutura de Dados Elementares
Pilhas, filas, listas, ponteiros e objetos
Tabela Hash
Arvores binárias
Estatisticas de ordem dinâmicas
 
4. Técnicas Avançadas de Projeto e Análise
Programação dinâmica
Algoritmos Gulosos
 
5. Estruturas de Dados Avançadas
Arvores B
Heaps binomiais
Heaps de Fibonacci
Estruturas de dados para conjuntos – Algoritmos de Manipulação de Conjuntos
 
6. Algoritmos de grafos
Algoritmos elementares de grafos
Arvores espalhadas mínimas
Caminhos mais curtos – de única origem e de todos os pares
Algoritmo de Floyd-Warshall
Algoritmo de Johnson para grafos esparsos
Fluxo Máximo – Método de Ford-Fulkerson
Emparelhamento bipartido máximo
Algoritmos de push-relabel

 

BIBLIOGRAFIA:

01. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 3ª Edição,  2009.
(Edição em portugues : “Algoritmos-Teoria e Prática”, Editora Campus 2003)

02. David Harel and Yishai Feldman. Algorithmics: The Spirit of Computing, 3a Edição, Addison Wesley, 2004. 

03. Steven S. Skiena: The Algorithm Design Manual.  Springer, 2a Edição., 2008. 

04. Donald E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1.  (Series in Computer Science & Information Processing) Addison-Wesley Professional, 2011. 

05 Bernhard Korte, Jens Vygen. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics), 4a Edição, 2010.

06. Vijay V. Vazirani. Approximation Algorithms. Addison-Wesley 2001