Question

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 Iimpá-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 solução do problema é obtida em tempo de ordem O(nlogn), ufilizando-se um algoritmo ótimo de ordenação.uma heurísfica para a solução do problema de coloração de grafos solucionará o problema em tempo polinomial.0 o problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas do processo, requerendo tempo de ordem polinomial para ser solucionado.a utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo entre o QUESTÃO 24Considere as seguintes tabelas de um banco de dados:1.Fornecedor (cod fornec, nome fornec, telefone,cidade, UF)2.Estado (UF, nome_estado)A expressão SQL que obtém os nomes dos estados para os quais não há fornecedores cadastrados éSELECT E.UFFROM Estado AS EWHERE E.nome estado NOT IN ( SELECT F.UFFROM Fornecedor AS F);SELECT E.nome estado FROM Estado AS E, FROMFornecedor AS F WHERE E.UF = F.UF;SELECT E.nome estado FROM Estado AS E WHERE E.UF NOT IN ( estado inicial e o final soluciona o problema em 0tempo polinomial.0 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.

#ENADE

Answer 1

A afirmativa correta é a (E), pois 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.

Para a modelagem do problema com a utilização de grafos recomenda-se o uso de grafo completo com n+1 vértices para a representação de cada uma das etapas e a etapa inicial caldeira limpa.

Em que as arestas possuem pesos que representam o custo de se passar de uma etapa para a outra. Para sair do vértice que apresenta a representação da caldeira limpa, deve-se passar todos os vértices uma única vez e retornar ao vértice caldeira limpa.

Bons estudos!