Resenha critica e fichamento

Páginas: 4 (982 palavras) Publicado: 17 de maio de 2012
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...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • A constitucionalidade da lei maria da penha (fichamento e resenha crítica)
  • Resenha e fichamento- pedro demo- sociologia uma introdução a critica
  • Metodologia científica: o que é fichamento, resenha, resumo, sinopse, resenha crítica, esquemas
  • Conceitos sobre resumo, resenha critica, fichamento, seminário, projeto de pesquisa e citação.
  • Resenha Crítica Corrente Crítica
  • Resenha Crítica
  • Resenha critica
  • RESENHA CRÍTICA

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!