MO417 - Questão para a prova oral

Número: 2003-098

Enunciado: Assuma que você tenha um problema cujas soluções possuam um valor associado "c". Suponha que você queira achar uma solução que maximize o valor de "c". Lendo artigos sobre o assunto, você descobriu que existe um algoritmo que utiliza programação dinâmica para encontrar esta solução. O artigo onde você encontrou este algoritmo provava formalmente que o algoritmo está correto, mas você tem a impressão que um algoritmo guloso poderia ser muito mais eficitente, embora você saiba que provar a corretude do algoritmo guloso não será fácil. Você resolve  implementar ambos os algoritmos e comparar algumas soluções para ver se a abordagem gulosa não falha logo de cara. Que tipo de resultado mostraria que o guloso NÃO funciona?

A) Tanto as soluções encontradas pelos algoritmos quanto os valores de "c" para estas soluções são diferentes para uma mesma entrada.
B) Tanto as soluções encontradas pelos algoritmos quanto os valores de "c" para estas soluções são iguais para uma mesma entrada.
C) Tanto as soluções encontradas pelos algoritmos quanto os valores de "c" para estas soluções são iguais para uma mesma entrada, mas o algoritmo guloso não resolve todos os subproblemas que o algoritmo de programação dinâmica resolve.
D) As soluções encontradas pelos algoritmos podem ser diferentes, mas os valores de "c" para as soluções sempres são iguais para uma mesma entrada.
E) NDA

Ideia original de: José Augusto Amgarten Quitzau