Atividade Objetiva 3 - Complexidade de Algoritmos - NOTA 1.0 de 1.0

Prévia do material em texto

Atividade 3
Iniciado: 9 out em 17:22
Instruções do teste
Importante:
Caso você esteja realizando a atividade através do aplicativo "Canvas Student", é necessário que
você clique em "FAZER O QUESTIONÁRIO", no final da página.
0,2 ptsPergunta 1
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 afirmações 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:
III, apenas.
I e II, apenas.
I e III, apenas.
II, apenas.
II e III, apenas.
0,2 ptsPergunta 2
A+
A
A-
NOTA: 1.0 de 1.0
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.
R é NP-Completo.
Q é NP-Completo.
Q e R são NP-Completo.
R é NP-Hard.
Q é NP-Hard.
0,2 ptsPergunta 3
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:
A+
A
A-
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:
II, apenas.
II e III, apenas.
I e III, apenas.
III, apenas.
I e II, apenas.
0,2 ptsPergunta 4
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 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 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 de algoritmos Polinomiais, logo, são
chamados de eficientes.
A+
A
A-
Salvo em 11:10 
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.
0,2 ptsPergunta 5
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 asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa
da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
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.
Enviar teste
A+
A
A-