042-2005

MO640 - Questão para a prova oral
Número: 042

Enunciado:

Sobre comparação de seqüências é incorreto afirmar que:

1. 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).
2. 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.
3. É 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.
4. 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.
5. nda     

Autor(a): Renato Hirata