MO417 - QUESTÃO PARA A PROVA ORAL - 1ª QUESTÃO

Número:
Enunciado: Sobre programação dinâmica assinale a alternativa correta marcando V para verdadeiro e F para falso:
( ) Ao contrário da divisão e conquista as técnicas de programação dinâmica utilizam um enfoque tabular de baixo para cima que resolve todos os subproblemas uma única vez. Este enfoque gera algoritmos mais eficientes.
 ( ) Problemas onde a divisão de um problema de tamanho n resulta em a subproblemas de tamanho n-1 geralmente nos levam a algoritmos recursivos exponenciais O(a^n). A programação dinâmica aplicada a estes problemas não gera algoritmos eficientes.
( ) A construção de um algoritmo utilizando programação dinâmica supõe quatro etapas: definição da subestrutura ótima, definição da recursividade, resolução dos subproblemas (bottom-up) e construção da solução ótima.
( ) A programação dinâmica geralmente é aplicada a problemas de otimização, quando os subproblemas são dependentes e superpostos, buscando todas as soluções ótimas para o problema.

a) V – F – V – F
b) V – V – V – F
c) F – F – F – V
d) F – V – V – F
e) NDA

Ideia original de: Lucas Oliveira Batista