UFJF - Universidade Federal de Juiz de Fora

Plano de ensino

Disciplina: DCC142 - ANÁLISE E PROJETO DE ALGORITMOS II

Créditos: 2

Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE

Ementa -Revisão
-Algoritmos para tratar problemas com alta complexidade de tempo
-Análise de algoritmos paralelos
Conteúdo 1) Revisão
Breve revisão de complexidade, dominação assintótica, notações de complexidade e classes de problemas

2) Algoritmos para tratar problemas com alta complexidade de tempo
Métodos eficientes para obter soluções aproximadas. Medida de qualidade da aproximação. Caminhamento em grafos: tentativa e erro, poda de árvores, remoção de simetrias, árvore geradora mínima, grafo de Euler, caminho de Euler. Heurísticas: algoritmos gulosos, programação dinâmica, cozimento simulado. O problema do caixeiro viajante: prova do limite inferior para uma aproximação com árvore geradora mínima, algoritmo de Christofides. O problema da mochila: aproximação por algoritmo guloso, otimização por programação dinâmica.

3) Análise de algoritmos paralelos
Problemas que necessitam de alto desempenho. Paralelismo de dados e paralelismo de controle: exemplo com o Crivo de Erastótenes. Escalabilidade de algoritmos e de arquiteturas. Taxonomia de Flynn, Speedup e a lei de Amdahl. Modelos PRAM. Algoritmos PRAM: soma de um conjunto com n elementos, soma de prefixos, coloração de grafos. Custo da computação paralela e definição de algoritmo paralelo ótimo Teorema de Brent. Modelos PRAM e a Tese da Computação Paralela. Problemas P-Completo. Projeto de algoritmos paralelos: SIMD, MIMD. Algoritmos para máquinas SIMD.
Bibliografia - AHO, A.V.; HOPCROFT, J.E.; ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison Wesley,1974.
- GAREY, M. R., JOHNSON D. S., Computer and intractability: a guide to the theory of NP-Completeness, Freeman, 1979.
- MORET, D. M. E.; SHAPIRO H. D., Algorithms from P to NP, Benjamim/Cummings Publishing Company, 1991.
- HU, T. C. Combinatorial Algorithms, Addison-Wesley, 1982.
- FRAKES; BAEZA-YATES. Information retrieval data structures and algorithms, Prentice-Hall, 1992.
Bibliografia (continuação)
Bibliografia complementar - CAMPELLO, R.; MACULAN FILHO, N. Algoritmos e Heurísticas. Editora da UFF, 1994.
Voltar