Baixe o app para aproveitar ainda mais
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
Compartilhar