Em relação à análise de algoritmo dos problemas NP, analise as seguintes afirmacoes: Os problemas da classe NP utilizam algoritmos de verificação e...
Os problemas da classe NP utilizam algoritmos de verificação em tempo polinomial. Uma classe polinomial tem complexidade de tempo O(p(n)), em que p(n) é um polinômio e n é o tamanho da entrada. Além disso, a classe NP utiliza algoritmos não determinísticos que usam a função escolhe (X) com a complexidade de tempo O(1) e os comandos sucesso e insucesso também com a complexidade de tempo O(1).
I. A complexidade do problema do caixeiro viajante é O(c), e a solução encontrada obteve o melhor resultado.
II. A complexidade do problema de coloração de grafos é O(P(x)), uma vez que a solução do problema se dá em tempo polinomial.
III. O objetivo do problema do caixeiro viajante é percorrer a rota de menor custo, não sendo necessário analisar (n-1)! possibilidades de rota; logo, a complexidade é O(c).
IV. O problema da mochila utiliza um algoritmo não determinístico, cuja complexidade de tempo do problema é O(n), sendo n o tamanho da entrada.
A. I, II e III.
B. II e IV.
C. II e III.
D. I, III e IV.
E. I, II, III e IV.
💡 2 Respostas
Ed 
A alternativa correta é a letra C) II e III. I. A complexidade do problema do caixeiro viajante é NP-completo, ou seja, não se sabe se existe um algoritmo de tempo polinomial para resolvê-lo. Portanto, a afirmação está incorreta. II. A complexidade do problema de coloração de grafos é NP-completo, ou seja, não se sabe se existe um algoritmo de tempo polinomial para resolvê-lo. Portanto, a afirmação está incorreta. III. O objetivo do problema do caixeiro viajante é encontrar a rota de menor custo que passe por todos os vértices do grafo. A complexidade do problema é O(n!), que é exponencial. No entanto, existem algoritmos aproximados que resolvem o problema em tempo polinomial. Portanto, a afirmação está correta. IV. O problema da mochila é um problema de otimização que pode ser resolvido em tempo polinomial por meio de programação dinâmica. Portanto, a afirmação está incorreta. Assim, as afirmações corretas são II e III, e a alternativa correta é a letra C.
Rafael Andrade
Resposta correta.B.
II e IV.
A afirmação I está incorreta, pois o problema do caixeiro viajante é um problema NP (problema não determinístico polinomial), cuja complexidade é O(cn), uma vez que a melhor solução encontrada não foi provada ser a melhor solução. A afirmação II está correta, pois o problema de coloração de grafos é um problema NP (problema não determinístico polinomial), e a verificação da solução se dá em tempo polinomial; logo, a complexidade é O(P(x)). A afirmação III está incorreta, pois o objetivo do problema do caixeiro viajante é percorrer a rota de menor custo, sendo necessário analisar (n-1)! possibilidades de rota; logo, a complexidade é exponencial O(cn). A afirmação IV está correta, uma vez que o problema da mochila também é considerado um problema NP, usa um algoritmo não determinístico, e sua complexidade é O(n), sendo que n representa o tamanho da entrada.
CORRIGIDO PELO AVA
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
1 pág.
10 pág.
Compartilhar