Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala (2000)
- Authors:
- Autor USP: MONGELLI, HENRIQUE - IME
- Unidade: 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
-
ABNT
MONGELLI, Henrique. Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala. 2000. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2000. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-115206/. Acesso em: 19 abr. 2024. -
APA
Mongelli, H. (2000). Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-115206/ -
NLM
Mongelli H. Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala [Internet]. 2000 ;[citado 2024 abr. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-115206/ -
Vancouver
Mongelli H. Algoritmos CGM para busca uni e bidimensional de padrões com e sem escala [Internet]. 2000 ;[citado 2024 abr. 19 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-20210729-115206/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
