MO640 - Exercícios - Sobre a aula de 2008-08-26

1. No texto é dado um algoritmo recursivo para comparação global de duas seqüências que usa espaço linear. Escreva um algoritmo não recursivo para o mesmo problema, usando também espaço linear.
2. O texto apresenta um algoritmo para comparar duas seqüências de tamanho n que roda em tempo O(dn), onde d é tanto menor quanto mais semelhantes são as seqüências. O algoritmo usa várias iterações de uma rotina, chamada de KBand no texto, que determina a melhor pontuação de um alinhamento entre as seqüências dadas que não utilize mais que k pares de espaços. O parâmetro k começa em 0 e vai dobrando a cada iteração. Verdadeiro ou falso: se KBand retorna a mesma pontuação em duas iterações consecutivas, podemos dizer que esta pontuação é a similaridade entre as seqüências dadas?

MO640 Home

© 2008 João Meidanis