Lista 2 de exercícios de Análise de Algoritmos (Com gabarito)

Prévia do material em texto

Ana´lise de Algoritmos
Segunda Lista de Exerc´ıcios
Reconhecimento de padro˜es em palavras e programac¸a˜o dinaˆmica
30 de maio de 2008
Prof. Mauricio Ayala-Rinco´n
Entrega: 14 de maio de 2008 (100%) - Grupos de cinco pesso˜as
Sera´ disponibilizado um gabarito da lista, depois do dia 14 de maio
Listas entregues entre 15 e 19 de maio de 2008: 50%
Listas entregues apo´s 19 de maio de 2008: 0%
Esta´giario de doceˆncia: Daniel Lima Ventura: ventura at mat dot unb dot br
Reconhecimento de Padro˜es em Palavras
1. Demonstre que a computac¸a˜o da func¸a˜o de erro ou falha, denotada por f , para o
algoritmo de Knuth-Morris-Pratt (KMP) fornecida na aula e´ correta. I. e., que o F
computado coincide com a f definida. Lembre-se de que a definic¸a˜o dada e o algo-
ritmo de ca´lculo sugerido desta, sa˜o objetos diferentes e por isso na˜o necessa´riamente
coincidentes.
Sejam P, Q palavras sobre uma alfabeto Σ. Se |P | = m, denotamos os seus s´ımbolos
como P = p1p2 . . . pm. Pk, para k = 0..m, denota o prefixo k-e´simo de P . Assim, P0 =
λ, a palavra vazia, e Pk = p1p2 . . . pk, para qualquer k = 1..m. Usa-se a notac¸a˜o Q @ P
e Q A P para denotar que Q e´ prefixo de P e que Q e´ sufixo de P , respectivamente.
Definic¸a˜o(Func¸a˜o de erro ou falha de KMP) Seja P uma palavra sobre um
alfabeto Σ com |P | = m. A func¸a˜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
ma´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 na˜o existe Q tal que
Q A Pi−1 e Q @ Pi−1 e pi 6= p|Q|+1, enta˜o o primeiro conjunto na segunda linha da
definic¸a˜o de f e´ considerado vazio e f(i) e´ definido como 0.
1
Algoritmo(Ca´lculo da func¸a˜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. Fornec¸a a func¸a˜o de erro de KMP para os seguintes padro˜es: AAAB, ABABBABAB-
BAB, ABABBABABBABBABABBAB.
3. Explique como modificar a func¸a˜o de erro de KMP para tratar a busca de todas as
ocorreˆncias de um padra˜o num texto.
4. Fornec¸a a func¸a˜o matchjump do algoritmo de Boyer-Moore (BM) para os seguintes
padro˜es: AAAB, ABABBABABBAB, ABABBABABBABBABABBAB.
5. Explique como modificar a func¸a˜o matchjump de BM para tratar a busca de todas as
ocorreˆncias de um padra˜o num texto.
6. Opcional. Implemente na linguagem C o algoritmo de Boyer-Moore para reconheci-
mento de padro˜es em palavras.
Compare o comportamento do algoritmo de Knuth-Morris-Pratt (uma implementac¸a˜o
deste encontra-se na pa´gina http://www.mat.unb.br/∼ayala/academics.html no
arquivo “match KMP.c” na sec¸a˜o desta disciplina) e sua implementac¸a˜o do algoritmo
de Boyer-Moore com palavras em alfabetos bina´rio e ingleˆs.
Apresentar:
• Especificac¸a˜o do problema e explicac¸a˜o do me´todo de soluc¸a˜o.
• Descric¸a˜o e ana´lise da complexidade dos algoritmos implementados.
• Definic¸a˜o e justificac¸a˜o das estruturas de dados usadas na implementac¸a˜o.
• Descric¸a˜o da implementac¸a˜o no mesmo listado.
• Refereˆncias.
7. Explique quando e´ mais apropriado o uso do algoritmo de KMP e quando o do al-
goritmo de BM no reconhecimento de padro˜es. Explique as ventagens do me´todo de
reconhecimento de padro˜es baseado nas a´rvores de sufixos.
2
Programac¸a˜o Dinaˆmica
8. Multiplicac¸a˜o o´tima de sequeˆncias de matrizes.
(a) Demonstre que o nu´mero de operac¸o˜es aritme´ticas necessa´rias para calcular dire-
tamente a relac¸a˜o de recurreˆncia
M(i, j) = mini≤k≤j−1[M(i, k) + M(k + 1, j) + di−1dkdj], para 1 ≤ i < j ≤ n,
M(i, i) = 0,
resultante do tratamento puramente recursivo ao problema da fatorac¸a˜o o´tima de
multiplicac¸a˜o de sequeˆncias de matrizes, e´ de ordem exponencial; i. e., tem um
l´ımite inferior exponencial em n.
(b) Explique passo a passo o funcionamento do algoritmo dinaˆmico para ordem o´tima
de multiplicac¸a˜o de sequeˆncias de matrizes, para matrizes A1, A2, A3, A4 de di-
menso˜es
20× 2, 2× 15, 15× 40, 40× 4,
respectivamente.
(c) Sejam A1, A2, . . . , An matrizes de dimenso˜es d0 × d1, d1 × d2, . . . , dn−1 × dn, re-
spectivamente. Ana´lise a seguinte te´cnica voraz para o problema de ordem o´tima
de multiplicac¸a˜o de sequeˆncias de matrizes:
em cada passo, selecione a dimensa˜o restante maior (entre d1, . . . , dn−1) e
multiplique as duas matrizes adjacentes eliminando tal dimensa˜o.
- Qual e´ a ordem do algoritmo correspondente a tal te´cnica?
- Encontre um exemplo para o qual tal te´cnica voraz na˜o funciona.
Ajuda: aplique a te´cnica sugerida ao exemplo anterior.
(d) Na pa´gina http://www.mat.unb.br/∼ayala/academics.html no arquivo “mat-
multseq.c” na sec¸a˜o desta disciplina, encontra-se uma implementac¸a˜o na lin-
guagem C deste me´todo. Inclua uma func¸a˜o para imprimir simbolicamente a
sequeˆncia o´tima de multiplicac¸a˜o.
9. Na pa´gina http://www.mat.unb.br/∼ayala/academics.html, na sec¸a˜o desta disci-
plina no arquivo “arvore binaria otima dinamica.c”, encontra-se uma implementac¸a˜o
na linguagem C da soluc¸a˜o dinaˆmica do problema de construc¸a˜o de a´rvores bina´rias
de consulta o´timas para chaves com probabilidade de busca. Utilize a bibliografia da
disciplina para formular o problema e a soluc¸a˜o dinaˆmica deste.
10. Sejam u = u1 . . . un e v = v1 . . . vm palavras no alfabeto {0, 1}. u e´ uma subsequeˆncia
de v se existem 1 ≤ s1 < s2 < · · · < sn ≤ m, tais que ui = vsi , 1 ≤ i ≤ n.
Dadas duas sequeˆncias x e y, u e´ uma subsequeˆncia comum de x e y, se u e´ uma
subsequeˆncia de x e tambe´m de y.
Seja:
3
maxcom(x, y) = max{ |u| | u e´ uma subsequeˆ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 te´cnicas de programac¸a˜o dinaˆmica.
(c) Modifique seu algoritmo de tal forma que no ca´lculo de maxcom(x, y) sejam ger-
adas as subsequeˆncias correspondientes de x e y.
11. O reconhecimento aproximado de padro˜es em palavras e´ uma generalizac¸a˜o do problema
de reconhecimento de padro˜es em palavras. O problema pode-se estabelecer da seguinte
maneira:
dadas palavras padra˜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 distaˆncia de edic¸a˜o entre s e p, d(s, p), e´ menor ou igual que k.
A distaˆncia de edic¸a˜o entre duas palavras x e y e´ o custo total mı´nimo poss´ıvel de
uma sequeˆncia de passos de edic¸a˜o para converter x em y. Denotando com � a palavra
vazia, em cada passo de edic¸a˜o aplica-se uma regra de reescrita da forma:
• a → �, a ∈ Σ (eliminac¸a˜o);
• � → a, a ∈ Σ (inserc¸a˜o);
• a → b, a, b ∈ Σ (substituc¸a˜o).
Diz-se que a palavra x e´ uma k-aproximac¸a˜o de y, se se pode converter x em y em k
passos de edic¸a˜o. Por exemplo, existe uma ocorreˆncia 1-aproximada do padra˜o abb na
primeira posic¸a˜o do texto abcdbdb e uma ocorreˆncia 2-aproximada na quarta posic¸a˜o,
como se ilustra no seguinte esquema.
a b b a b � b
↓ ↓ ↓
a b � c d b d b
O mecanismo de soluc¸a˜o mais “popular” do problema de reconhecimento aproximado
de padro˜es e´ baseado em te´cnicas de programac¸a˜o dinaˆmica e tem complexidade O(nm).
Sejam p = p1 . . . pm e t = t1 . . . tn um padra˜o e um texto, respectivamente. Basicamente
o me´todo consiste em construir uma m + 1× n + 1-tabela D tal que para 0 ≤ i ≤ m,
4
0 ≤ j ≤ n, D[i, j] e´ a mı´nima distaˆncia de edic¸a˜o de p1 . . . pi a` subpalavra do texto
que termina em tj. Existem aproximac¸o˜es do padra˜ocom distaˆncia de edic¸a˜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 enta˜o 0 se na˜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:
a b c a b d a b
0 0 0 0 0 0 0 0 0
c 1 1 1 0 1 1 1 1 1
a 2 1 2 1 0 1 2 1 2
b 3 2 1 2 1 0 1 2 1
(a) Descreva em detalhe o algoritmo sugerido usando te´cnicas de programac¸a˜o dinaˆmi-
ca.
(b) Indique com precisa˜o como pode ser usada a tabela gerada pelo anterior algoritmo
para produzir as “aproximac¸o˜es do padra˜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
′ de
S tal que ∑
si∈S′
si = C
Uma soluc¸a˜o dinaˆ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 na˜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 ′ de {s1, . . . , si−1} soma j ou
• se algum subconjunto S ′ de {s1, . . . , si−1} soma j − si (sempre que j − si ≥ 0).
Neste caso o conjunto S ′ ∪ {si} soma j.
5
Assim, para determinar se o valor de M [i, j] e´ 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 2 3 4 5 6 7
1 0 0 0 0 0 0 0
3 1 0 0 1 0 0 0 0
2 1 0 1 1 0 1 0 0
4 1 0 1 1 1 1 1 1
Observe que para todo 0 ≤ i ≤ 3, M [i, 0] = 1 e para todo 1 ≤ j ≤ 7, M [0, j] = 0, ja´
que o conjunto vazio soma 0.
(a) Descreva o algoritmo para construir M .
(b) Calcule a complexidade do algoritmo dinaˆmico sugerido em termos do tamanho
da entrada.
Ajuda: Na˜o e´ preciso desenvolver a primeira parte para calcular a complexidade.
A complexidade na˜o se deve expressar como θ(n× C) devido a que o tamanho da
entrada do problema e´ n + 1, os n inteiros do conjunto S e o inteiro C!
6
Ana´lise de Algoritmos
Segunda Lista de Exerc´ıcios
Reconhecimento de Padro˜es em Palavras
1. Induc¸a˜o em i.
BI: Para i = 1, f(i) = 0 e F [i] := 0. Na primeira iterac¸a˜o com while, j = 0.
Enta˜o o segundo while na˜o sera´ executado. Portanto, ao incrementar os ı´ndices i
e j tem-se que j < i e λ=P0=
max
P1. Observe que em ambos os casos pi = pj e pi 6= pj
tem-se que F [2] = f(2).
PI: Suponha que F [l] = f(l), ∀l ≤ i e, no in´ıcio do while mais externo, 0 < j < i e
Pj−1=
max
Pi−1. O primeiro passo sera´ provar que ao incrementar os ı´ndices i e j tem-se
a invariante 0 < j < i e Pj−1=
max
Pi−1.
Se pi 6= pj, enta˜o gera-se uma sequeˆncia j=j1, j2, . . . , jr atrave´s da iterac¸a˜o com
o segundo while, onde, por hipo´tese de induc¸a˜o, jr = 0 ou Pjl−1 = Pj(l−1)−1 e
pjl 6= pj(l−1), ∀1 < l ≤ r e pjr = pi. Observe que, por hipo´tese de induc¸a˜o,
Pj−1=
max
Pi−1. Suponha que Pm=
max
Pi para algum m > jr. Enta˜o jl < m < jl−1
para algum 1 < l < r. Assim, Pjl−1 = Pm−1 = Pj(l−1)−1 e pm = pi 6= pj(l−1) .
Isso contradiz a maximalidade de f(j(l−1)) = jl com essas propriedades, dada pela
definic¸a˜o da func¸a˜o f . Portanto, Pjr=
max
Pi. Assim, ao sair do while, j = jr < i.
Apo´s o incremento de i e j tem-se a invariante. A prova para jr = 0 e´ ana´loga.
Se pi = pj, enta˜o de Pj−1=
max
Pi−1 tem-se que Pj=
max
Pi. Assim, apo´s o incremento de i
e j obte´m-se a invariante.
Observe que o valor de j (que nesse ponto e´ igual a j+1) na˜o e´ alterado no restante
do co´digo, antes do in´ıcio da pro´xima iterac¸a˜o. Agora basta provar que as u´ltimas
linhas do co´digo atribuem o valor correto para F [i+1].
Se pi+1 6= pj+1, enta˜o F [i+ 1] = j + 1 e de Pj=
max
Pi tem-se que f(i+ 1) = j + 1.
Se pi+1 = pj+1, enta˜o F [i+ 1] = F [j + 1]
HI
=f(j + 1). Suponha que f(j + 1) = r+ 1.
Enta˜o, pela definic¸a˜o da func¸a˜o f , r e´ o maior valor tal que Pr = Pj e pr+1 6= pj+1.
Logo Pr = Pi e pr+1 6= pi+1. Suponha que f(i + 1) = l + 1 > r + 1. Tem-se
que l 6= j, pois, pela definic¸a˜o de f , pl+1 6= pi+1. Suponha que l > j. Enta˜o
Pl = Pi, mas Pj=
max
Pi. Contradic¸a˜o. Se l < j, enta˜o, como Pj = Pi, Pl = Pj e
pl+1 6= pi+1 = pj+1. Mas r e´ maximal com essa propriedade. Contradic¸a˜o. Logo,
f(i+ 1) = r+ 1 = f(j + 1). Portanto, para f(j + 1) > 0, F [i+ 1] = f(i+ 1). Para
f(j + 1) = 0 a prova e´ ana´loga.
2. AAAB
i 1 2 3 4
F [i] 0 0 0 3
ABABBABABBAB
1
i 1 2 3 4 5 6 7 8 9 10 11 12
F [i] 0 1 0 1 3 0 1 0 1 3 0 1
ABABBABABBABBABABBAB
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
F [i] 0 1 0 1 3 0 1 0 1 3 0 1 8 0 1 0 1 3 0 0
3. A ide´ia e´ incluir uma regra para o estado correspondente a ter encontrado o padra˜o
no texto. Assim, basta incluir um caracter que na˜o faz parte do alfabeto na posic¸a˜o
m + 1, onde |P | = m, e permitir mais uma iterac¸a˜o do loop mais externo do
algoritmo (while).
calcule_erro_KMP()
{
int i=1, j=0;
padrao[m+1]=’#’;
erro_KMP[i]=0;
while (i<=m)
{
while (j>0 && padrao[i] != padrao[j]) j=erro_KMP[j];
i++;
j++;
if (padrao[i]==padrao[j]) erro_KMP[i]=erro_KMP[j];
else erro_KMP[i]=j;
}
}
4. AAAB
i 1 2 3 4
mJ [i] 7 6 5 1
ABABBABABBAB
i 1 2 3 4 5 6 7 8 9 10 11 12
mJ [i] 16 15 14 13 12 16 15 14 6 12 3 1
ABABBABABBABBABABBAB
i 1 2 3 4 5 6 7 8 9 10
mJ [i] 32 31 30 29 28 27 26 25 19 23
i 11 12 13 14 15 16 17 18 19 20
mJ [i] 22 21 20 11 23 22 6 20 3 1
2
5. Analogamente a mudanc¸a realizada no algoritmo KMP para tratar todas as ocor-
reˆncias do padra˜o no texto, precisa-se incluir um estado para tratar o caso no qual
o padra˜o e´ encontrado. Para isso, basta incluir na posica˜o 0 um caracter que na˜o
fac¸a parte do alfabeto que compo˜em o texto. Assim, para um padra˜o P qualquer
de comprimento m teria-se um valor mJ [0] dando a informac¸a˜o de qual salto seria
apropriado, de acordo com o algoritmo BM, apo´s encontrar uma ocorre˜ncia de P.
6. Opcional
7. O algoritmo KMP tem um bom desempenho para alfabetos com poucos caracteres,
como o bina´rio por exemplo, enquanto o algortimo BM se destaca para busca de
padro˜es em linguagem natural onde o pada˜o tem comprimento maior ou igual a 5
(veja 5.3[Baa88]). Essa diferenc¸a se deve ao fato da pre-computac¸a˜o do BM na˜o
compensar para tais alfabetos, pois a chance de haver um padra˜o onde na˜o aparec¸a
algum desses caracteres e´ mı´nima.
Programac¸a˜o Dinaˆmica
8. (a) Seja #o(n) o nu´mero de operaco˜es aritme´ticas para determinar a fatorac¸a˜o
o´tima de multiplicac¸a˜o de uma sequeˆncia de n matrizes. Observe que #o(2) =
4 e #o(1) = 0. Suponha que #o(i) ≥ 2i, para todo 1 < i < n. Note que
#o(n) = 2
∑n−1
i=1 #o(i). Portanto,
T (n) = 2
n−1∑
i=1
#o(i) = 2
n−1∑
i=2
#o(i)
≥ 2
n−1∑
i=2
2i (IH)
= 2
(
2n − 1− 3)
= 23(2n−2 − 1)
≥ 2n, paran > 2
Portanto, T (n) ∈ Ω(2n)
(b) Duas matrizes Mn×n e factorn×n sa˜o inicializadas, onde n e´ o comprimento da
sequeˆncia de matrizes. O primeiro passo do algoritmo e´ preencher a diagonal
M [i, i] com 0’s. Os passos seguinte sera˜o calcular para cada diagonal acima
da diagonal principal o valor de M [i, j]. Esse valor representa o nu´mero o´timo
de operac¸o˜es para fazer a multiplicac¸a˜o das matrizes Ai, · · · , Aj. NA matriz
factor sa˜o guardados os valores de k tal que o nu´mero o´timo e´ atingido.
Para a primeira diagonal teremos i variando de 1 ate´ n − 1 onde, para cada
i, j = i + 1. Como essa diferenc¸aentre i e j representa uma multiplicac¸a˜o
entre duas matrizes, tem-se trivialmente que M [1, 2] = 600 e factor[1, 2] = 1,
M [2, 3] = 1200 e factor[2, 3] = 2, M [3, 4] = 2400 e factor[3, 4] = 3. Assim,
ao final da computac¸a˜o para diagonal = 1 tem-se que
3
M =

0 600 − −
− 0 1200 −
− − 0 2400
− − − 0
 factor =

− 1 − −
− − 2 −
− − − 3
− − − −

Para diagonal = 2, teremos i variando de 1 ate´ 2. Como exemplo, para i igual
a 1 tem-se que j = 3. Assim
M [1, 3] = min1≤k≤3(M [1, k] +M [k+1, j] + 800dk)
Observe que para calcular esse valor, apenas valores de M [i, j] ja´ calcula-
dos anteriormente sa˜o utilizados. Assim, M [1, 3] = 2800 e factor[1, 3] = 1.
Analogamente tem-se que M [2, 4] = 1520 e factor[2, 4] = 3. Finalmente,
para diagonal = 3, temos que M [1, 4] = 1680 e factor[1, 4] = 1. Ao final da
computac¸a˜o tem-se enta˜o
M =

0 600 2800 1680
− 0 1200 1520
− − 0 2400
− − − 0
 factor =

− 1 1 1
− − 2 3
− − − 3
− − − −

(c) O algoritmo so´ e´ aplicado para um nu´mero n de matrizes maior ou igual a 3,
onde para n = 3 uma comparaca˜o e´ feita entre d1 e d2 para determinar qual e´
a maior. Assim,
T (n) =
n∑
i=3
(i− 2) =
n−2∑
i=1
i
=
1
2
(n− 2)(n− 1)
=
n2
2
− 3
2
n+ 1
Portanto, T (n) ∈ Θ(n2).
Seja A1, A2A3, A4 a sequeˆncia de matrizes apresentada em (b). Pelo algoritmo
com a te´cnica voraz teria-se a ordem de multiplicac¸a˜o representada por A1 ∗
(A2 ∗ (A3 ∗ A4)), com o nu´mero de operac¸o˜es de (15 · 40 · 4) + (2 · 15 · 4) +
(20 · 2 · 4) = 2680. Por (b) sabe-se que a fatorac¸a˜o o´tima e´ representada por
A1 ∗ ((A2 ∗ A3) ∗ A4), com 1680 operac¸o˜es.
(d) showOrder(int l, int m){
int k;
if (l == m)
printf("A%d", l);
else
{
4
k = factor[l][m];
printf("(");
showOrder(l,k);
printf("*");
showOrder(k+1, m);
printf(")");
}
}
Veja algoritmo 6.2 em [Baa88].
9.
10. (a)
maxcom(xδ, yσ) =
{
maxcom(x, y) + 1, se δ = σ
max
(
maxcom(xδ, y),maxcom(x, yσ)
)
, c.c.
(b)
BEGIN
FOR (i=1,i<=n,i++)
{
IF (x[i] == y[1])
M[i,1] = 1;
ELSE
M[i,1] = 0;
}
FOR (j=1,j<=n,j++)
{
IF (x[1] == y[j])
M[1,j] = 1;
ELSE
M[1,j] = 0;
}
FOR (i=2,i<=n,i++)
{
FOR (j=2,j<=n,j++)
{
IF (x[i] == y[j])
M[i,j] = M[i-1,j-1] + 1;
ELSE
M[i,j] = max(M[i-1,j],M[i,j-1]);
5
}
}
END.
Tem-se n comparac¸o˜es para cada um dos dois primeiros FOR’s . Assim,
T (n) = 2n+
n∑
i=2
n∑
j=2
2 = 2n+ 2(n− 1)2 < 2n+ 2n2
Portanto, T (n) ∈ O(n2).
(c)
MostraSubSeq()
{
i,j= n;
k = M[i,j];
WHILE (k>0)
{
IF (M[i,j] == M[i-1,j])
i--;
ELSE IF (M[i,j] == M[i,j-1])
j--;
ELSE
{
PX[k] = i;
PY[k] = j;
i--;
j--;
k--;
}
}
k = M[n,n];
PRINT "Um subsequencia maximal comum a x e y:"
FOR (i=0,i<=k,i++)
PRINT "x PX[i]";
6
FOR (i=0,i<=k,i++)
PRINT "y PY[i]";
}
11. (a)
BEGIN
FOR (i=0,i<=m,i++)
D[i,0] = i;
FOR (j=1,j<=n,j++)
D[0,j] = 0;
FOR (i=1,i<=m,i++)
{
FOR (j=1,j<=n,j++)
{
k = D[i-1,j-1];
IF (P[i] != T[j])
k++;
l = min(D[i-1,j],D[i,j-1]) +1;
D[i,j] = min(k,l);
}
}
END.
(b)
12. (a) BEGIN
FOR (i=0,i<=n,i++)
M[i,0] = 1;
FOR (j=1,j<=C,j++)
M[0,j] = 0;
FOR (i=1,i<=n,i++)
{
FOR (j=1,j<=C,j++)
{
k = S[i];
7
IF ( (j-k >= 0 AND M[i-1,j-k] == 1) OR M[i-1,j] == 1)
M[i,j] = 1;
ELSE
M[i,j] = 0;
}
}
END.
(b)
8
	lista2_20080430
	gabaritoL2