MO417 - Questão para a prova oral

Número:

Enunciado : De acordo com as afirmações abaixo sobre Programação Dinâmica, marque a alternativa correta:

I – A Programação Dinâmica poderá ser aplicada sempre que um problema apresentar uma subestrutura ótima.

II – O problema do Caminho Mais Longo Não-Ponderado poderá ser resolvido adequadamente através da Programação Dinâmica.

III – O algoritmo de Programação Dinâmica que soluciona o problema Árvores de Pesquisa Binária Ótimas utiliza um vetor auxiliar W para armazenar a soma das probabilidades na subárvore com as chaves k_i , .. , k_j , onde 1 <= i <= j <= "Nº de nós". Caso este vetor W não seja utilizado, o tempo de execução do algoritmo Θ(n³) não será alterado.

a)      Apenas a afirmativa I está correta.

b)      As afirmativas I e II estão corretas.

c)       Apenas a afirmativa III está correta.

d)     Todas as afirmações estão erradas.

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato