Resenha critica e fichamento

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (982 palavras )
  • Download(s) : 0
  • Publicado : 17 de maio de 2012
Ler documento completo
Amostra do texto
AED´s III String Matching Casamento de Padrão
Professor: Ciro Meneses Santos

String Matching

O problema de localizar ocorrências de uma cadeia de caracteres em um texto.

UNIPAC –Universidade Presidente Antonio Carlos Departamento de Ciência da Computação

Introdução Conteúdo
• String Matching
– Algoritmo de Força Bruta

– Algoritmo KMP
– Algoritmo Boyer-Moore

• O problema delocalizar ocorrência duma cadeia de caracteres num texto é muito frequente. Existem muitos algoritmos com qualidades diferentes para satisfazer esta necessidades. • O problema pode ser formulado como:dado um conjunto de símbolos “” que definimos como alfabeto do Texto. Desejamos saber as ocorrências do Padrão “P” no Texto “T”. • Aplicações:
– – – – Busca na Internet Busca de palavra em textoVerificações em sequências de DNA Livros, dicionários, artigos técnicos, científicos jornalismo

e

Introdução
• • • • • • • Notações: T  Texto; P  Padrão;   Alfabeto; n  Tamanho do Texto; m Tamanho do Padrão; c  Tamanho do alfabeto;

Algoritmo Força Bruta
• Descrição:
O algoritmo força bruta consiste em verificar, em todas as posições no texto entre 0 e n-m, se uma ocorrência dopadrão existe ou não. Isto e feito deslocando o padrão sobre o texto por exatamente uma posição à direita.

• Características Principais:
– Nenhuma fase de pre-procesamento
– – – – E necessárioespaço extra para constante desloca sempre o conteúdo 1 posição à direita As comparações podem ser feitas em qualquer ordem. A complexidade do Algoritmo e O(nm).

1

Algoritmo Força Bruta
• • • •Alfabeto = {a, b, c} Texto ={abaabacab} Padrão = { a a b a } Passos: abaabacab aaba  abaabacab aaba  abaabacab aaba  Primeira tentativa ABAABAC AB
1 2

Algoritmo Força Bruta
Primeira tentativaGCAT C GC AGAGAGT AT ACAGT ACG 1 2 3 4 GCAGAGAG Em segundo tentativa GC AT C GC AGAGAGT AT ACAGT ACG 1 GCAGAGAG Terceira tentativa GCAT C GC AGAGAGT AT ACAGT ACG 1 GCAGAGAG

AA B A

Algoritmo...
tracking img