Mestre

Nenhum trabalho por enquanto.

Subcadeia comum maxima ´
Definic¸ao: Subcadeia ˜
Dada uma cadeia S = a1 ...an, dizemos que S
= b1 ...bp e´ uma subcadeia de S se existem p ´ındices i(j) satisfazendo:
(a) i(j) ∈ {1,...,n} para todo j ∈ {1,...,p};
(b) i(j) < i(j +1) para todo j ∈ {1,...,p −1};
(c) bj = ai(j) para todo j ∈ {1,...,p}.
Exemplo: S = ABCDEFG e S
= ADFG.
Problema da Subcadeia Comum Maxima ´
Dadas duas cadeias de caracteres X e Y de um alfabeto Σ, determinar a maior subcadeia comum de X e Y
C. de Souza, C. da Silva, O. Lee, P. de Rezende, G. Pimentel, F. Miyazawa MC448 — P.A.A. ISubcadeia comum maxima (cont.) ´
E um problema de otimizac ´ ¸ao. ˜ Sera que tem subestrutura ´ otima? ´
Notac¸ao: ˜ Seja S uma cadeia de tamanho n. Para todo i = 1,...,n, o prefixo de tamanho i de S sera denotado ´ por Si.
Exemplo: Para S = ABCDEFG, S2 = AB e S4 = ABCD.
Definic¸ao: ˜ c[i,j] e o tamanho da subcadeia comum ´ maxima dos pre ´ fixos Xi e Yj. Logo, se |X| = m e |Y| = n, c[m,n] e o valor ´ otimo. ´
C. de Souza, C. da Silva, O. Lee, P. de Rezende, G. Pimentel, F. Miyazawa MC448 — P.A.A. ISubcadeia comum maxima (cont.) ´
Teorema (subestrutura otima): ´ Seja Z = z1 ...zk a subcadeia comum maxima de ´ X = x1 ...xm e
Y = y1 ...yn, denotado por Z = SCM(X,Y).
1 Se xm = yn entao˜ zk = xm = yn e Zk−1 = SCM(Xm−1,Yn−1).
2 Se xm = yn entao˜ zk = xm implica que Z = SCM(Xm−1,Y).
3 Se xm = yn entao˜ zk = yn implica que Z = SCM(X,Yn−1).
Formula de Recorr ´ encia: ˆ c[i,j] =



0 se i = 0 ou j = 0 c[i −1,j −1] +1 se i,j > 0 e xi = yj max{c[i −1,j],c[i,j −1]} se i,j > 0 e xi = yj
C. de Souza, C. da Silva, O. Lee, P. de Rezende, G. Pimentel, F. Miyazawa MC448 — P.A.A.