Seminário de Teoria da Computação


   Programação Dinâmica Paralela para resolver o 
 Problema de Edição de Strings no Modelo BSP/CGM

           Edson Norberto Caceres

         Sexta-feira, 4 de abril de 2003
          Auditório do IC (IC1), 13:00hs


Resumo:

Na palestra apresentaremos um algoritmo paralelo de "granularidade
grossa" para resolver o problema da edição de strings para uma string
A e todas as substrings de um uma string C.  O algoritmo é baseado
numa estratégia de computar todos os caminhos de maior peso em um
grafo grid com peso nas arestas. O algoritmo requer log p
rodadas/superpassos de comunicação e (n^2/p) log m computação local,
onde p é o número de processadores, p^2 <= m <= n.


ps: Informações sobre seminários anteriores e inscrições/remoções no
link: www.dcc.unicamp.br/~fkm/seminarios/