jun

MO417 - Questão para a prova oral

Numero:

Enunciado: Considere o seguinte pseudocódigo. Assinale a alternativa CORRETA.

PSEUDOCODIGO-1 (p , n)

1    let r [ 0 .. n ] and s [ 0 .. n ] be new arrays

2    r [ 0 ] = 0

3    for j = 1 to n
4          q = - ∞
5          for i = 1 to j

6                    if q < p [ i ] +r [ j - i ]

7                          q = p [ i ] + r [ j - i ]

8                          s [ j ] = i

9          r [ j ] = q

8    return r and s

I         O PSEUDOCODIGO-1 cria um arranjo s [ 0 .. n ] onde guarda os resultados dos subproblemas.

II    Dynamic Programming e Divide-and-conquer solucionam problemas combinando as soluciones dos subproblemas, além  Dynamic Programming é tipicamente aplicado nos problemas de otimização.
 
III    Quando desenvolvemos algoritmos de programação dinâmica, nós seguimos uma sequência de quatro passos, além nós podemos omitir o passo numero quatro somente se necessitamos de uma solução ótima e não da solução por sim mesma.
 
IV     Diz-se que um problema mostra uma Optimal Substructure quando Otimal Solutions de um problema incorpora Optimal Solutions dos subproblemas relacionados, os quais nós podemos resolver independentemente.
  

Qual é a alternativa correta:

a) Somente I e III são corretas.
b) Somente II e IV são corretas.
c) Somente II e III são corretas.
d) Somente II, III e IV são corretas
e) NDA
 
                                          Ideia original de: Junior Cupe Casquina