Análise de Algoritmos

Análise de Algoritmos
Segunda Lista de Exercı́cios
Reconhecimento de padrões em palavras e programação dinâmica
30 de maio de 2008
Prof. Mauricio Ayala-Rincón
Entrega: 14 de maio de 2008 (100%) - Grupos de cinco pessõas
Será disponibilizado um gabarito da lista, depois do dia 14 de maio
Listas entregues entre 15 e 19 de maio de 2008: 50%
Listas entregues após 19 de maio de 2008: 0%
Estágiario de docência: Daniel Lima Ventura: ventura at mat dot unb dot br
Reconhecimento de Padrões em Palavras
1. Demonstre que a computação da função de erro ou falha, denotada por f , para o
algoritmo de Knuth-Morris-Pratt (KMP) fornecida na aula é correta. I. e., que o F
computado coincide com a f definida. Lembre-se de que a definição dada e o algoritmo de cálculo sugerido desta, são objetos diferentes e por isso não necessáriamente
coincidentes.
Sejam P, Q palavras sobre uma alfabeto Σ. Se |P | = m, denotamos os seus sı́mbolos
como P = p1 p2 . . . pm . Pk , para k = 0..m, denota o prefixo k-ésimo de P . Assim, P0 =
λ, a palavra vazia, e Pk = p1 p2 . . . pk , para qualquer k = 1..m. Usa-se a notação Q @ P
e Q A P para denotar que Q é prefixo de P e que Q é sufixo de P , respectivamente.
Definição(Função de erro ou falha de KMP) Seja P uma palavra sobre um
alfabeto Σ com |P | = m. A função de erro de Knuth-Morris-Pratt para P , f :
{1, . . . m} → {0, . . . m}, define-se da seguinte maneira
f (i) =
(
0
se i = 1
máximo({|Q| + 1 | Q A Pi−1 e Q @ Pi−1 e pi 6= p|Q|+1 } ∪ {0}) se i > 0
Observe que dados um P com |P | = m e algum i = 1..m, se não existe Q tal que
Q A Pi−1 e Q @ Pi−1 e pi 6= p|Q|+1 , então o primeiro conjunto na segunda linha da
definição de f é considerado vazio e f (i) é definido como 0.
1
Algoritmo(Cálculo da função de erro ou falha de KMP)
Entrada:
PadrAo P com m sImbolos
SaIda: FunCAo de erro ou falha de KMP F para P
i := 1, j := 0;
F[i] := 0;
while (i<m) do
while (j>0) e (P[i] != P[j])
j := F[j];
i++;
j++;
if (P[i] = P[j]) then F[i] := F[j];
else F[i] := j;
2. Forneça a função de erro de KMP para os seguintes padrões: AAAB, ABABBABABBAB, ABABBABABBABBABABBAB.
3. Explique como modificar a função de erro de KMP para tratar a busca de todas as
ocorrências de um padrão num texto.
4. Forneça a função matchjump do algoritmo de Boyer-Moore (BM) para os seguintes
padrões: AAAB, ABABBABABBAB, ABABBABABBABBABABBAB.
5. Explique como modificar a função matchjump de BM para tratar a busca de todas as
ocorrências de um padrão num texto.
6. Opcional. Implemente na linguagem C o algoritmo de Boyer-Moore para reconhecimento de padrões em palavras.
Compare o comportamento do algoritmo de Knuth-Morris-Pratt (uma implementação
deste encontra-se na página http://www.mat.unb.br/∼ayala/academics.html no
arquivo “match KMP.c” na seção desta disciplina) e sua implementação do algoritmo
de Boyer-Moore com palavras em alfabetos binário e inglês.
Apresentar:
• Especificação do problema e explicação do método de solução.
• Descrição e análise da complexidade dos algoritmos implementados.
• Definição e justificação das estruturas de dados usadas na implementação.
• Descrição da implementação no mesmo listado.
• Referências.
7. Explique quando é mais apropriado o uso do algoritmo de KMP e quando o do algoritmo de BM no reconhecimento de padrões. Explique as ventagens do método de
reconhecimento de padrões baseado nas árvores de sufixos.
2
Programação Dinâmica
8. Multiplicação ótima de sequências de matrizes.
(a) Demonstre que o número de operações aritméticas necessárias para calcular diretamente a relação de recurrência
M (i, j) = mini≤k≤j−1 [M (i, k) + M (k + 1, j) + di−1 dk dj ], para 1 ≤ i < j ≤ n,
M (i, i) = 0,
resultante do tratamento puramente recursivo ao problema da fatoração ótima de
multiplicação de sequências de matrizes, é de ordem exponencial; i. e., tem um
lı́mite inferior exponencial em n.
(b) Explique passo a passo o funcionamento do algoritmo dinâmico para ordem ótima
de multiplicação de sequências de matrizes, para matrizes A1 , A2 , A3 , A4 de dimensões
20 × 2, 2 × 15, 15 × 40, 40 × 4,
respectivamente.
(c) Sejam A1 , A2 , . . . , An matrizes de dimensões d0 × d1 , d1 × d2 , . . . , dn−1 × dn , respectivamente. Análise a seguinte técnica voraz para o problema de ordem ótima
de multiplicação de sequências de matrizes:
em cada passo, selecione a dimensão restante maior (entre d1 , . . . , dn−1 ) e
multiplique as duas matrizes adjacentes eliminando tal dimensão.
- Qual é a ordem do algoritmo correspondente a tal técnica?
- Encontre um exemplo para o qual tal técnica voraz não funciona.
Ajuda: aplique a técnica sugerida ao exemplo anterior.
(d) Na página http://www.mat.unb.br/∼ayala/academics.html no arquivo “matmultseq.c” na seção desta disciplina, encontra-se uma implementação na linguagem C deste método. Inclua uma função para imprimir simbolicamente a
sequência ótima de multiplicação.
9. Na página http://www.mat.unb.br/∼ayala/academics.html, na seção desta disciplina no arquivo “arvore binaria otima dinamica.c”, encontra-se uma implementação
na linguagem C da solução dinâmica do problema de construção de árvores binárias
de consulta ótimas para chaves com probabilidade de busca. Utilize a bibliografia da
disciplina para formular o problema e a solução dinâmica deste.
10. Sejam u = u1 . . . un e v = v1 . . . vm palavras no alfabeto {0, 1}. u é uma subsequência
de v se existem 1 ≤ s1 < s2 < · · · < sn ≤ m, tais que ui = vsi , 1 ≤ i ≤ n.
Dadas duas sequências x e y, u é uma subsequência comum de x e y, se u é uma
subsequência de x e também de y.
Seja:
3
maxcom(x, y) = max{ |u| | u é uma subsequência comum de x e y}
(a) Sejam x, y ∈ {0, 1}∗ , δ, σ ∈ {0, 1}.
Descreva maxcom(xδ, yσ) em termos de
maxcom(xδ, y),
maxcom(x, yσ) e
maxcom(x, y).
(b) Desenhe um algoritmo O(n2 ) para calcular maxcom(x, y), onde |x| = |y| = n.
Ajuda: use técnicas de programação dinâmica.
(c) Modifique seu algoritmo de tal forma que no cálculo de maxcom(x, y) sejam geradas as subsequências correspondientes de x e y.
11. O reconhecimento aproximado de padrões em palavras é uma generalização do problema
de reconhecimento de padrões em palavras. O problema pode-se estabelecer da seguinte
maneira:
dadas palavras padrão e texto, p e t, respectivamente, sobre um alfabeto Σ, com
|p| = m > 0 e |t| = n > 0 e dado um inteiro k ≥ 0, encontrar subpalavras s de t
tais que a distância de edição entre s e p, d(s, p), é menor ou igual que k.
A distância de edição entre duas palavras x e y é o custo total mı́nimo possı́vel de
uma sequência de passos de edição para converter x em y. Denotando com a palavra
vazia, em cada passo de edição aplica-se uma regra de reescrita da forma:
• a → , a ∈ Σ (eliminação);
• → a, a ∈ Σ (inserção);
• a → b, a, b ∈ Σ (substitução).
Diz-se que a palavra x é uma k-aproximação de y, se se pode converter x em y em k
passos de edição. Por exemplo, existe uma ocorrência 1-aproximada do padrão abb na
primeira posição do texto abcdbdb e uma ocorrência 2-aproximada na quarta posição,
como se ilustra no seguinte esquema.
a b b
a b b
↓
↓
↓
a b c d b d b
O mecanismo de solução mais “popular” do problema de reconhecimento aproximado
de padrões é baseado em técnicas de programação dinâmica e tem complexidade O(nm).
Sejam p = p1 . . . pm e t = t1 . . . tn um padrão e um texto, respectivamente. Basicamente
o método consiste em construir uma m + 1 × n + 1-tabela D tal que para 0 ≤ i ≤ m,
4
0 ≤ j ≤ n, D[i, j] é a mı́nima distância de edição de p1 . . . pi à subpalavra do texto
que termina em tj . Existem aproximações do padrão com distância de edição ≤ k
terminando em tj se e solamente se D[m, j] ≤ k. A tabela se constroi segundo as
seguintes regras:
• D[0, j] = 0, 0 ≤ j ≤ n;
• D[i, 0] = i, 0 ≤ i ≤ m;
• D[i, j] = mı́nimo entre:
– D[i − 1, j] + 1,
– D[i − 1, j − 1] + se pi = tj então 0 se não 1,
– D[i, j − 1] + 1,
1 ≤ j ≤ n, 1 ≤ i ≤ m.
Note que D[i, j] depende unicamente de D[i − 1, j], D[i − 1, j − 1] e D[i, j − 1] o que
permite construir a tabela coluna por coluna e fila por fila em ordem ascendente.
Considere, por exemplo, a tabela construida para p = cab, t = abcabdab:
0
c 1
a 2
b 3
a
0
1
1
2
b
0
1
2
1
c
0
0
1
2
a
0
1
0
1
b
0
1
1
0
d
0
1
2
1
a
0
1
1
2
b
0
1
2
1
(a) Descreva em detalhe o algoritmo sugerido usando técnicas de programação dinâmica.
(b) Indique com precisão como pode ser usada a tabela gerada pelo anterior algoritmo
para produzir as “aproximações do padrão” achadas.
12. Considere o problema de soma de subconjuntos: dado um conjunto de inteiros positivos
S = {s1 , . . . , sn } e um inteiro positivo C, determinar se existe um subconjunto S 0 de
S tal que
X
si = C
si ∈S 0
Uma solução dinâmica do problema consiste em construir uma tabela M de tamanho
(n + 1) × (C + 1), tal que M [i, j] = 1 se existe um subconjunto de {s1 , . . . , si } com
soma j e se não existe M [i, j] = 0.
Note que a tabela pode ser construida coluna por coluna ascendentemente usando o
fato de que um subconjunto de {s1 , . . . , si } soma j sse
• algum subconjunto S 0 de {s1 , . . . , si−1 } soma j ou
• se algum subconjunto S 0 de {s1 , . . . , si−1 } soma j − si (sempre que j − si ≥ 0).
Neste caso o conjunto S 0 ∪ {si } soma j.
5
Assim, para determinar se o valor de M [i, j] é 1 basta verificar se
• M [i − 1, j] = 1 ou
• M [i − 1, j − si ] = 1 (j − si ≥ 0).
Como exemplo considere a tabela para S = {3, 2, 4} e C = 7:
0
1
3 1
2 1
4 1
1
0
0
0
0
2
0
0
1
1
3
0
1
1
1
4
0
0
0
1
5
0
0
1
1
6
0
0
0
1
7
0
0
0
1
Observe que para todo 0 ≤ i ≤ 3, M [i, 0] = 1 e para todo 1 ≤ j ≤ 7, M [0, j] = 0, já
que o conjunto vazio soma 0.
(a) Descreva o algoritmo para construir M .
(b) Calcule a complexidade do algoritmo dinâmico sugerido em termos do tamanho
da entrada.
Ajuda: Não é preciso desenvolver a primeira parte para calcular a complexidade.
A complexidade não se deve expressar como θ(n × C) devido a que o tamanho da
entrada do problema é n + 1, os n inteiros do conjunto S e o inteiro C!
6