Número: 041
Enunciado:
Qual o preço a se pagar por usar o algoritmo de alinhamento que economiza espaço visto em aula:
- É necessário saber de antemão o quanto as cadeias são semelhantes.
- Só funciona se as sequências tiverem o mesmo tamanho.
- O alinhamento é aproximado, e não ótimo.
- O tempo de execução pode dobrar.
- NDA
Dada a questão, é possível reduzir as necessidades do algoritmo de forma que passe a utilizar apenas o espaço proporcional à soma dos tamanhos das sequências de entrada, não mantendo a matriz toda na memória como no método anterior. (1) Não há a necessidade em saber o quanto as cadeias comparadas são semelhantes pois, a função desse algoritmo é exatamente mostrar qual o alinhamento ótimo entre as sequências. Se, de antemão, houvesse um valor absoluto de quanto elas são semelhantes, não haveria a necessidade em executá-lo. (2) As sequencias não, necessariamente, devem ter o mesmo tamanho, visto que, para cada i de s1, deverá ser casado com s2[j]. Desta forma, o algoritmo trará à tona as pontuações ótimas entre s1[1..(i-1)] para um i fixo e um prefixo arbitrário de s2 e também entre s2[(i+1)..m] e um sufixo de s2, independente do tamanho de s1 e s2, embora, sendo m menor que n (ou vice-versa), usar colunas gasta menos espaço. (3) A função do algoritmo em questão é retornar a pontuação máxima entre s1 e s2, encontrando o alinhamento ótimo e não um alinhamento aproximado. (4) Para realizar a economia de espaço, são necessários alguns cálculos adicionais que vão determinar o alinhamento ótimo utilizando chamadas recursivas, além do método de divisão e conquista empregado neste caso. A chamada BestScore(s1(a..(i-1)], s2[c..d], prefixo) calcula em prefixo[j] a pontuação máxima entre s1[a..(i-1)] e s2[c..j] para c-1 <=j <=d e, BestScoreRev(s1[(i+1)..b], s2[c..d], sufixo) calcula em sufixo[j] a pontuação máxima entre s1[(i+1)..b] e s2[(j+1)..d] para c-1 <=j <=d. Uma análise revelou que o gasto, no máximo, será duas vezes mais tempo com estre processo em relação ao que mantinha toda a matriz na memória.
ResponderExcluirEntão, a única alternativa correta desta questão é a (d) que fala que o tempo de execução poderá dobrar.
Bom comentário, embora um pouco longo demais. No comentário sobre a alternativa (2), senti falta de uma menção ao fato de que a "diagonal" no caso de m diferente de n, assume a forma de uma "faixa". No comentário sobre a alternativa (4), senti falta de uma menção ao fato de que várias áreas têm que ser sucessivamente refeitas, pois a matriz não é mantida em sua totalidade, apenas uma ou duas linhas (ou colunas).
ResponderExcluirNo todo, nota 8,0 (oito).