Aula9-Processamento de Cadeias
11 pág.

Aula9-Processamento de Cadeias


DisciplinaEstruturas de Dados I581 materiais2.532 seguidores
Pré-visualização1 página
Processamento de Cadeias 
Prof: Ekler Paulino de Mattos 
ekler.mattos@gmail.com 
CPCX/UFMS 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 Introdução 
\u2022 Cadeia: Entende-se uma sequência de elementos 
denominados caracteres. 
 
\u2022 Caracteres: são elementos escolhidos por um conjunto de 
elementos denominados alfabeto. 
 
\u2022 Ex: 011010101 é uma cadeia com alfabeto {0,1}. 
 
\u2022 Caracteres: 
\u2022 Não possuem relações estruturais entre si, a não ser a 
sua ordem sequêncial. 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 Cadeias presentes na computação (Exemplos) 
 
\u2022 Processamento de textos, palavras, códigos, 
mensagens, 
 
 
\u2022 Aplicações: tratamento computacional de dicionários, 
mensagens de correio eletrônico, sequenciamento de 
DNA (biologia computacional), criptografia entre outros. 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 Questões a serem tratadas: 
\u2022 Casamento de cadeias: Consiste verificar se a primeira 
delas contém a segunda, ou seja, se os caracteres que 
compõem a segunda cadeia aparecem sequencialmente 
também na primeira. 
\u2022 Ex: edição de textos. 
 
\u2022 Codificação de mensagens: Dada uma cadeia de 
caracteres, denominada mensagem, o problema consiste 
em codificá-la através da atribuição de códigos a seus 
caracteres, de modo a minimizar o comprimento total da 
mensagem codificada. 
\u2022 Ex: transmissão de mensagens em uma rede. 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 O Problema do Casamento de Cadeias 
\u2022 Sequência de caracteres escolhidos de um conjunto 
chamado alfabeto. O número de caracteres da cadeia 
 é o seu comprimento. 
 
\u2022 Sejam X, Y, duas cadeias de caracteres com comprimentos n, 
m, respectivamente. n >=m. 
 
\u2022 Y é uma subcadeia da X quando Y for uma subsequencia 
consecutiva de X, isto é, quando existir algum inteiro l <= n-
m, Y é sufixo, tal que 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 O Problema do Casamento de Cadeias 
\u2022 Consiste em verificar se Y é subcadeia de X. Em caso 
positivo, localizar Y em X. Diz-se, então, que houve um 
casamento de Y com X na posição l + 1. 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 O Algoritmo da Força Bruta 
\u2022 Sejam X e Y cadeias com caracteres xi e yi, 1 <= I <= n e 1 
<= j <= m, m <= n. Deseja-se verificar se Y é subcadeia de X 
e, em caso positivo, localizar Y em X. Um método bastante 
simples consiste em examinar todas as possíveis situações. 
Se Y é subcadeia de X, então Y se encontra em X, deslocado 
de l posições à esquerda. 
 
\u2022 Idéia: Consiste em comparar Y com a subcadeia de tamanho 
m de X, que se inicia no caractere , para todos os 
possíveis de l. Ou seja, l = 0, 1, \u2026, n-m. 1\uf02blx
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 O Algoritmo da Força Bruta 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
\u2022 O Algoritmo da Força Bruta 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
Lista de Exercícios 3 \u2013 L3 
Entrega: 18/11/2013 
\u2022 O Algoritmo da Força Bruta 
\u2022 Exercício 1: 
\u2022 Considerando duas cadeias de caracteres X e Y, de 
tamanhos m e n onde m>= n. Implemente o algoritmo de 
Força Bruta que: 
\u2022 A) Recupere a quantidade de ocorrências da cadeia 
 Y dentro na cadeia X. 
 
\u2022 B) Recupere as posições da cadeia Y em que foi 
encontrada a cadeia X. 
 
 
 
 
(c) Ekler Paulino de Mattos 
Processamento de cadeias 
 
 
 
 
\u2022 O Algoritmo de Knuth, Morris e Pratt. 
\u2022 Revisão do algoritmo de Força Bruta. 
http://www.youtube.com/watch?v=GVizb_fi
08E&feature=related 
http://www.youtube.com/watch?v=Zj_er99
KMb8&feature=related 
(c) Ekler Paulino de Mattos