Questão das aulas do dia 01/04 e 03/04 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: A principal diferença entre Programação Dinâmica e algoritmos de Divisão e Conquista é:

a) A Divisão e Conquista é mais eficiente quando todos os subproblemas são dependentes.
b) As soluções parcias em Programação Dinâmica são armazenadas e em Divisão e Conquista não.
c) A Programação Dinâmica é mais eficiente quando os subproblemas são independentes.
d) A Programação Dinâmica é mais adequada quando há sobreposições de subproblemas.
e) NDA

Ideia original de: Lucas Miguel de Carvalho

Questão das aulas do dia 01/04 e 03/04 - 2ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Vamos considerar o problema de encontrar a Cadeia Comum mais Longa (LCS) , definindo  como LCS(A,B) a Cadeia Comum mais Longa entre as strings A e B.

Por exemplo, se considerarmos A={ALFABETO} e B={HABITAT} e os subproblemas A'={ALFA} e B'={HABI}, então podemos afirmar que:

a) LCS(A',B') + LCS(A-A',B-B') = LCS(A,B)
b) LCS(A',B') + LCS(A-A',B-B') ≠ LCS(A,B)
c) Não existe Cadeia Comum mais Longa entre os subproblemas A' e B'.
d) Só existe uma Cadeia Comum mais Longa entre A e B, ou seja, LCS(A,B) é única.
e) NDA.

Ideia original de: Lucas Miguel de Carvalho