Algoritmos paralelos realísticos para a maior subsequência comum

AUTOR(ES)

Claudia Regina Tinós Peviani

DATA DE PUBLICAÇÃO

2009

RESUMO

Neste trabalho estudou-se o problema da Maior Subsequência Comum (Longest Common Subsequence - LCS) que deseja encontrar uma subsequência comum de comprimento máximo de duas sequências. O problema LCS pode ser resolvido em tempo sequencial quadrático usando a técnica de programação dinâmica. Este trabalho consiste em estudar os algoritmos paralelos baseados nos modelos realísticos para resolver o problema LCS. Inicialmente estudou-se um algoritmo sequencial, um algoritmo paralelo no modelo PRAM e um no modelo realístico que encontra a LCS de todas as subcadeias. Fez-se uma implementação paralela realística com O(p) rodadas de comunicação usando p processadores. O resultado desta implementação não obteve speedup satisfatório, o que motivou o estudo mais teórico da paralelização do problema. Neste sentido, a partir do algoritmo PRAM descreveu-se uma solução paralela realística, usando estrutura de dados bem conhecidas como soma prefixa paralela e a técnica de pointer jumping.

ASSUNTO(S)

algoritmos paralelos dynamic programming technique técnica de programação dinâmica parallel algorithms lcs ciencia da computacao

Documentos Relacionados

• Algoritmos paralelos para o problema da mochila.
• Algoritmos Paralelos para Extensão Linear em Digrafos Planares
• Algoritmos memeticos paralelos aplicados a problemas de otimização combinatoria
• Algoritmos heuristicos e exatos para resolução do problema de sequenciamento em processadores paralelos
• Avaliação de algoritmos de ordenação em sistemas paralelos