Enunciado:
Dado o seguinte algoritmo que calcula o menor número de multiplicações escalares para uma Multiplicação de Cadeias de Matrizes:

LowCost(p, i, j)
 1  if i == j then
 2    return 0
 3  else
 4    low = MAX_VALUE
 5    for k = i to j-1 do
 6      costa = LowCost(p, i, k)
 7      costb = LowCost(p, k+1, j)
 8      cost = costa + costb + (p[i-1]*p[k]*p[j])
 9      if cost < low then
10        low = cost
11    return low
(p = dimensões das matrizes, i = matriz inicial cálculo, j = matriz final cálculo)

Qual das observações abaixo sobre o algoritmo caracteriza um comportamento de problemas superpostos, que permite a otimização do mesmo:

A) O algoritmo combina duas características: é recursivo e possui uma repetição.

B) Todo algoritmo que possui duas chamadas recursivas (como nas linhas 6 e 7) tem problemas superpostos.

C) Sempre que qualquer algoritmo recursivo realiza cálculo com um vetor, há repetição de subproblemas.

D) As chamadas recursivas das linhas 6 e 7 retornam sempre o mesmo resultado para um dado valor de p, i e j, além disto, chamadas recursivas com o mesmo valor para p, i e j acontecem com freqüência, ocasionando repetição do mesmo processo de cálculo.

E) NDA

Autor(a): André Santanchè