ENADE 2023: Dada uma sequência de caracteres S = s1, s2, ..., sn, uma subsequência de S é dada pela remoção de zero ou mais caracteres de S

ENADE 2023: Dada uma sequência de caracteres S = s1, s2, ..., sn, uma subsequência de S é dada pela remoção de zero ou mais caracteres de S

ENADE 2023: Dada uma sequência de caracteres S = s1, s2, ..., sn, uma subsequência de S é dada pela remoção de zero ou mais caracteres de S. Formalmente, a sequência X = x1, x2, ..., xk é subsequência de S se existe uma sequência crescente de índices i1, ..., ik de S, tal que xj = Sij para todo j = 1, 2, ..., k. Define-se, também, um prefixo da sequência S com comprimento i para i = 0, ..., n, como Si = s1, s2, ..., si.

O problema da Subsequência Comum Mais Longa (LCS) e suas variações, definido a seguir, pode ser utilizado em análise de textos e em bioinformática. O problema da LCS pressupõe duas sequências de caracteres A = a1, a2, ..., an e B = b1, b2, ..., bm, de comprimentos n e m, respectivamente. Dadas essas duas sequências, é preciso encontrar uma sequência de maior comprimento possível que seja, simultaneamente, subsequência de A e de B.

A partir dessas informações, considere que Z = z1, z2, ..., zk seja uma LCS das sequências A e B. Em relação ao problema da LCS, avalie as afirmações a seguir

I. Se an = bm, então zk = an, zk = bm e Zk-1 é uma LCS de An-1 e Bm-1.

II. Se an ≠ bm e zk ≠ an, então Z é uma LCS de An-1 e B.

III. Seja lcs(i,j) o comprimento da LCS entre Ai e Bj. Para i, j > 0, se ai ≠ bj, entãolcs(i,j) = min{lcs(i, j-1), lcs(i-1, j)}.

IV. Seja lcs(i,j) o comprimento da LCS entre Ai e Bj. Para i, j > 0, se ai = bj, então lcs(i,j) = lcs(i-1,j-1)+1.

É correto apenas o que se afirma em

A) I e III.

B) I e IV.

C) II e III.

D) I, II e IV.

E) II, III e IV.

RESOLUÇÃO:

Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

GABARITO:

D) I, II e IV.

PRÓXIMA QUESTÃO:

- ENADE 2023: Vetores de tamanho dinâmico são muito utilizados como estruturas de dados para armazenar listas etabelas de dispersão (tabelas hash).

QUESTÃO DISPONÍVEL EM:

- Prova Engenharia da Computação ENADE 2023 com Gabarito