MO640 - Questão para a prova oral
Número: 042
Enunciado:
Sobre comparação de seqüências é incorreto afirmar
que:
- Para
não se penalizar espaços iniciais
na comparação semi-global, deve-se na matriz de programação dinâmica, inicializar com zeros a 1ª linha e/ou 1ª coluna, dependendo
de qual seqüência se considera (1ª,2ª ou ambas).
- Se
duas seqüências são similares, então os melhores alinhamentos terão seus
caminhos próximos à diagonal principal na matriz de programação dinâmica.
- É
conhecido algoritmo de comparação de seqüências de complexidade de tempo O(nm) (onde n,m são os comprimentos
das seqüências) que penaliza menos um bloco de k espaços consecutivos do que
k espaços isolados.
- No
algoritmo que utiliza espaço linear para comparação de seqüências, a técnica
de “divisão e conquista” é utilizada para se preencher o vetor de pontuações.
- nda
Autor(a): Renato Hirata