Of.: S-6 T:04 L:00 HS:04 SL:04 C:04

Pre-Req.: MC538

Ementa:

Projeto e análise de algoritmos paralelos. Complexidade computacional paralela

Programa:

1. Modelos de computação paralela. O modelo PRAM e suas variações.
2. Técnicas básicas: árvores balanceadas, salto de apontadores, divisão e conquista, quebra de simetria.
3. Algoritmos para listas e árvores
4. Algoritmos para busac e ordenação.
5. Algoritmos para problemas em grafos
6. Algoritmos para problemas em outras áreas
7. Complexidade computacional paralela. P-completude e a classe NC.

Bibliografia:

J. Jájá. An Introduction to Parallel Algoritms. Addison-Wesley, 1992

J. Smith. The design and analysis of parallel algoritms. Oxford University Press, 1992

R. Greenlaw, H. J. Hoover and W. Ruzzo. Limits to Parallel Computation: P-completeness Theory. Oxford Univertsity Press, 1995