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

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

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.
Publicado
26/09/1988
TOSCANI, Laira Vieira; VELOSO, Paulo Augusto S.. Programação Dinâmica em Arquiteturas Paralelas: Análise da Complexidade. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 2. , 1988, São José dos Campos/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1988 . p. 230-235. DOI: https://doi.org/10.5753/sbac-pad.1988.23543.