fab

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Considere o problema de encontrar a rota máxima do topo até a base de um triangulo usando apenas elementos adjacentes,  x+y+d+c seria uma rota possível no triangulo:

x

y   z

a   d   e

b   c   f   g

NÃO seria correto afirmar para um triângulo com n elementos:

A) Existe um algorítimo O(2^(h-1)) que usa forca bruta para calcular todas as possíveis somas, onde h é a altura do triângulo.
B) a = a + max(b, c) seria parte da estratégia para resolver o problema usando programação dinâmica bottom-up.
C) f = f + max(d, e) seria parte da estratégia para resolver o problema usando programação dinâmica top down.
D) A estratégia bottom-up tem complexidade assintótica menor que a estratégia top-down.
E) NDA

Ideia original de: Fabrício Matheus Gonçalves