Exportar registro bibliográfico

Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala (2000)

  • Authors:
  • USP affiliated author: MONGELLI, HENRIQUE - IME
  • School: IME
  • Sigla do Departamento: MAC
  • Subjects: ARQUITETURA E ORGANIZAÇÃO DE COMPUTADORES; ARQUITETURAS E PROGRAMAÇÃO PARALELAS
  • Language: Português
  • Abstract: Dados um texto e um padrão, o problema de busca de padrões em textos consiste em determinar as posições do texto onde existe uma ocorrência do padrão. Quando o texto e padrão são cadeias de caracteres, a busca é dita unidimensional. Quando ambossão matrizes, a busca é dita ser bidimensional. Existem variações deste problema onde se permite a busca do padrão, de alguma maneira, modificado. A modificação que permitiremos ao nosso padrão é que ele possa estar escalado. Descrevemosalgoritmos seqüencias lineares para estes problemas, uni ou bidimensionais, com e sem escala, presentes na literatura. Para o caso bidimensional sem escala é apresentado, ainda, um algoritmo de tempo sublinear sob determinadas condições nasmatrizes de entrada. Para estes problemas propomos novos algoritmos paralelos, utilizando o modelo CGM (Coarse Grained Multicomputers), cujos tempos de computação local são lineares na entrada (local), consomem memória também linear e utilizamapenas uma rodada de comunicação em que são trocados, no máximo, uma quantidade também linear de dados. As condições do modelo são, assim, respeitadas. Do nosso conhecimento, não há na literatura outros algoritmos paralelos em modelos degranularidade grossa para o problema de busca unidimensional com escala e para os problemas de busca bidimensional com ou sem escala. Estes algoritmos propostos foram implementados em linguagem C, utilizando interface PVM e foram executadosnamáquina Parsytec PowerXplorer. Os resultados experimentais obtidos mostraram que as implementações tiveram ganhos significativos ao utilizar-se mais de um processador
  • Imprenta:
  • Data da defesa: 04.04.2000

  • How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      MONGELLI, Henrique; SONG, Siang Wun. Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala. 2000.Universidade de São Paulo, São Paulo, 2000.
    • APA

      Mongelli, H., & Song, S. W. (2000). Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala. Universidade de São Paulo, São Paulo.
    • NLM

      Mongelli H, Song SW. Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala. 2000 ;
    • Vancouver

      Mongelli H, Song SW. Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala. 2000 ;

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2020