Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos térmicos e químicos

ENADE 2014 - QUESTÃO 22

Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos térmicos e químicos para ficar pronto. Cada uma das n etapas de tratamento é realizada uma única vez na mesma caldeira.

Além do custo próprio de cada etapa do tratamento, existe o custo de se passar de uma etapa para outra, uma vez que, dependendo da sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la para evitar a reação entre os produtos químicos utilizados. Assuma que o processo de fabricação inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a sequência de tratamentos que possibilite fabricar o produto com o menor custo total. Nessa situação, conclui-se que

A) a solução do problema é obtida em tempo de ordem O(nlogn), utilizando-se um algoritmo ótimo de ordenação.

B) uma heurística para a solução do problema de coloração de grafos solucionará o problema em tempo polinomial.

C) o problemas e reduz a encontrar a árvore geradora mínima para o conjunto de etapas do processo, requerendo tempo de ordem polinomial para ser solucionado.

D) a utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo entre o estado inicial e o final soluciona o problema em tempo polinomial.

E) qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade de tempo não-polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.

RESOLUÇÃO:

Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

GABARITO:

E) qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade de tempo não-polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.

QUESTÃO DISPONÍVEL EM:

- Prova Ciências da Computação ENADE 2014 com Gabarito