Programação Dinâmica em Arquiteturas Paralelas: Análise da Complexidade

• Laira Vieira Toscani UFRGS
• Paulo Augusto S. Veloso PUC-Rio

DOI: https://doi.org/10.5753/sbac-pad.1988.23543

Resumo

Este trabalho parte de uma formalização da programação dinâmica e examina arquiteturas paralelas com o objetivo de melhorar a eficiência do método. É apresentada uma análise de complexidade das versões seqüencial e paralela, juntamente com alguns exemplos ilustrativos.

Referências

CASTI, J.; RICHARDSON, M. & LARSON, R. Dynamic Programming and Parallel Computers, Journal of Optimization Theory and Applications. Vol. 12, n.4, 1973.

BERTOLAZZI, P. & PIROZZI, M., Parallel Algorithms for Dynamic Programm ing Problems. Elaboratori Paralleli e Calcolo Scientifica, Roma, 1982.

TOSCANI, Laira V. & VELOSO, Paulo A.S., Especificação Formal e Análise da Complexidade da Programação Dinâmica. Porto Alegre, CPGCC da UFRGS, 1986. (RP nº 49)

HOARE, C.A.R., "Communicationg Sequential Processes", Communication of the ACM 21, pp 666-77, 1978.

TOSCANI, L.V. & VELOSO, P.A.S., A Programação Dinâmica em Arquiteturas Paralelas. (a ser publicado)

TERADA, R., Desenvolvimento de Algoritmos e Complexidade de Computação. Departamento de Informática, PUC/RJ, 1982.