Grátis: Leia o texto a seguir: Quanto tempo leva para executar um determinado algoritmo? Os cientistas da computação não dão a resposta em minutos ou milis... – Questões Respondidas

Método Científico

Outros

Leia o texto a seguir: Quanto tempo leva para executar um determinado algoritmo? Os cientistas da computação não dão a resposta em minutos ou milissegundos; eles a dão em relação ao número de instruções que o algoritmo tem que manipular.
Considerando as informações apresentadas, avalie as afirmacoes a seguir: I. Seja X um problema que pertence à classe NP, logo, se X é NP-Hard, então ele é NP-Completo. II. O problema de determinar se existe um ciclo em um grafo não direcionado está em P. III. Se quisermos provar que um problema X é NP-Hard, precisamos primeiramente provar que ele é um NP-Completo. É correto o que se afirma em:
I e II, apenas.
II, apenas.
III, apenas.
I e III, apenas.
II e III, apenas.

Perguntas sobre Metodologia Científica

há 5 dias

Perguntas sobre Metodologia Científica

há 5 dias

Teste_ Atividade Objetiva 3 2 tentativa

Teste_ Atividade Objetiva 3 2 tentativa

FAM

Respostas

Ed

há 5 dias

Vamos analisar cada uma das afirmações: I. Seja X um problema que pertence à classe NP, logo, se X é NP-Hard, então ele é NP-Completo. Falso. Um problema NP-Hard não precisa ser NP-Completo. Para ser NP-Completo, um problema deve ser NP-Hard e também estar em NP. II. O problema de determinar se existe um ciclo em um grafo não direcionado está em P. Verdadeiro. O problema de detectar ciclos em grafos não direcionados pode ser resolvido em tempo polinomial, portanto, está na classe P. III. Se quisermos provar que um problema X é NP-Hard, precisamos primeiramente provar que ele é um NP-Completo. Falso. Para provar que um problema é NP-Hard, não é necessário que ele seja NP-Completo. Você pode provar que um problema é NP-Hard diretamente, sem que ele seja NP-Completo. Com base nas análises: - A afirmação I é falsa. - A afirmação II é verdadeira. - A afirmação III é falsa. Portanto, a única afirmação verdadeira é a II. Assim, a alternativa correta é: II, apenas.

Essa resposta te ajudou?

0

0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Teste_ Atividade Objetiva 3 2 tentativa

Teste_ Atividade Objetiva 3 2 tentativa

FAM

Mais perguntas desse material

Observe a figura a seguir: Existe um problema S qualquer que é NP-Completo. Existem outros dois problemas Q e R que não estão em NP, e onde Q é tempo polinomial redutível a S e S é tempo polinomial redutível a R.
Considerando as informações apresentadas, assinale a opção correta.
A+
A
A- R é NP-Hard.
Q é NP-Hard.
Q e R são NP-Completo.
Q é NP-Completo.
R é NP-Completo.

Leia o texto a seguir: A complexidade de tempo refere-se a quantas etapas são necessárias para resolver um problema e como o número de etapas necessárias aumenta com o tamanho do problema. Dado um algoritmo, a Complexidade de Tempo do algoritmo é descrita como uma função assintótica que depende do tamanho de entrada do algoritmo.
Considerando as informações apresentadas, avalie as afirmações a seguir: I. De acordo com o tamanho de entrada, podemos distinguir os algoritmos em função de complexidade polinomial, os quais são chamados de eficientes. II. Existem muitos problemas computacionais impossíveis de serem resolvidos em tempo polinomial; eles são chamados de NP ou Não-Polinomial. III. Alguns problemas computacionais estão na classe NP-Hard e esses são classificados como pelo menos tão difíceis quanto os problemas mais difíceis em NP. É correto o que se afirma em:
A+
A
A- II e III, apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
II, apenas.

Leia o texto a seguir: A busca é o processo no qual um algoritmo encontra a sequência de várias etapas necessárias para resolver um determinado problema, sendo necessariamente de dois tipos: busca cega (desinformada) ou busca heurística (busca informada). Em inteligência artificial, por exemplo, uma busca informada fornece mais eficiência.
Considerando as informações apresentadas, avalie as seguintes asserções e a relação proposta entre elas. I. A busca informada pode resolver o problema além da definição da função, assim como pode encontrar a solução de forma mais eficiente. PORQUE II. Apesar de possuir conhecimento prévio, o estado meta (objetivo) pode ser alcançado usando diferentes ordens e duração das ações. A respeito dessas asserções, assinale a opção correta:
A+
A
A- Salvo em 10:04
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
As asserções I e II são ambas proposições falsas.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

Leia o texto a seguir: Dada uma grade de Sudoku incompleta (famoso jogo baseado na colocação lógica de números), desejamos saber se ela possui pelo menos uma solução válida. Qualquer solução de Sudoku proposta pode ser facilmente verificada, e o tempo para verificar uma solução cresce de forma polinomial à medida que a grade aumenta.
Qual propriedade melhor descreve a solução dessa classe de problema?
O problema de decisão Sudoku está em NP se suas soluções podem ser verificadas de forma eficiente.
O problema de decisão Sudoku é um problema categorizado como NP, o qual é um conjunto da classe P.
O problema do jogo Sudoku está na classe NP, logo, também é da classe P, uma vez que NP é uma classe de problemas dentro de P.
O Sudoku é resolvido em um tempo P, onde P é o conjunto de todos os problemas de decisão que são solucionáveis com eficiência.
O problema do jogo Sudoku está na classe de algoritmos Polinomiais, logo, são chamados de eficientes.