Algoritmos Paralelos para Casamento de Cadeias
Autores
3329 |
163,1507
|
|
3330 |
163,1507
|
Informações:
Publicações do PESC
Este trabalho trata de algoritmos paralelos para resolver o problema denominado Casamento de Cadeias (String-Matching) . Trata-se de um caso particular do problema de Casamento de Padrões (pattern-matching), que resume-se em procurar, num dado tipo de estrutura, um padrão, com o qual um subconjunto da estrutura se identifica.
Em particular, trata do caso em que tanto o padrão quanto a estrutura são cadeias de símbolos pertencentes a algum alfabeto.
São descritos os principais algoritmos paralelos para este problema, contidos na literatura. Descreve-se também o modelo de computação paralela para o qual todos esses algoritmos foram desenvolvidos, além dos limites inferiores para o problema.
Um dos algoritmos paralelos apresentados é modificado, no sentido de se obter a mesma complexidade num modelo mais fraco de computação paralela.
Porém, o algoritmo resultante funciona apenas para alguns casos especiais, contendo restrições sobre os tamanhos do alfabeto e do padrão.
Além disso, descreve-se brevemente os mais importantes algoritmos sequenciais para o problema.
This thesis is concerned with the parallel algorithms that solve the string-matching problem. This problem is an example of the pattern-matching problem, which consists in searching for a pattern within a given structure. The case we are interested is the one in which both the pattern and the structure are strings of symbols that belong to a given alphabet.
In the work it is described the main parallel algorithms that solve the problem in the literature. It is also presented the parallel computing model to which a11 this algorithms were developed, as well as the lower bounds for the above problem.
One of the parallel algorithms presented is modified, with the objective of obtaining the same complexity in a weaker parallel computing model. However, this algorithm works only for special cases containing restrictions about the pattern and alphabet lengths.
Furthermore, it is described briefly the most import ant sequential algorithms for the problem.