Enunciado:
Suponha que sejam dadas n atividades, cada uma com um instante de início s_i e um instante de término f_i. As atividades encontram-se ordenadas por ordem crescente de instante de término. Deseja-se selecionar um subconjunto de tamanho máximo de atividades mutuamente compatíveis , isto é, que não se sobreponham no tempo. Considere a solução para este problema dada pela chamada RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n+1), onde fazemos f₀ igual a menos infinito e o código da função RECURSIVE-ACTIVITY-SELECTOR é dado abaixo:

RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j)
 1  m = i + 1
 2  while m < j e sm < fi
 3    do m = m + 1
 4  if m < j
 5    then return {am} U RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j)
 6    else return conjunto_vazio

Comparando este algoritmo com uma solução equivalente que utilize programação dinâmica, escolha a alternativa correta:

A) A chamada recursiva da linha 5 baseia-se em um critério de escolha de no máximo um subproblema para solucionar, ao contrário da programação dinâmica que poderia envolver a seleção de mais de um subproblema.

B) Por decidir antecipadamente o subproblema que irá resolver, a solução gulosa pode levar mais tempo que a equivalente em programação dinâmica, se os palpites forem inexatos.

C) Tal como neste exemplo, qualquer outro problema que pode ser resolvido por programação dinâmica também pode ser resolvido pela estratégia gulosa.

D) As linhas 2 e 3 tem a função de detectar subproblemas superpostos, tal como acontece na programação dinâmica.

E) NDA

Autor(a): André Santanchè