UNIDADE 2 ASPECTOS TEORICOS DA COMPUTA O Trabalhos de Pesquisa Rildonacademic
1775 palavras
8 páginas
27/04/2015UNIDADE 2 ASPECTOS TEORICOS DA COMPUTA O Trabalhos de Pesquisa Rildonacademic
Pergunta 1 0,5 em 0,5 pontos
Assinale a alternativa que representa um problema NPCompleto:
Resposta Selecionada:
E.
Problema do ciclo hamiltoniano.
Respostas:
a.
Satisfabilidade booleana2.
b.
Problema da parada.
c.
Detecção universal do loop completo.
d.
Problema do ciclo de Euler. e.
Problema do ciclo hamiltoniano.
Pergunta 2
0,5 em 0,5 pontos
data:text/html;charset=utf8,%3Csection%20id%3D%22pf_text_1%22%20style%3D%22boxsizing%3A%20borderbox%3B%20display%3A%20block%3…
1/11
27/04/2015
UNIDADE 2 ASPECTOS TEORICOS DA COMPUTA O Trabalhos de Pesquisa Rildonacademic
Considere as seguintes afirmações
I Encontrar o maior subconjunto C de vértices, tal que todos os pares de vértices distintos, formados a partir dos elementos do conjunto C, sejam adjacentes (ou seja, são interligados por uma aresta) é um problema da classe NP.
II Verificar se uma dada fórmula booleana, tal que todas as cláusulas apresentem apenas 2 elementos, é satisfatória é um problema NP.
III Dado um conjunto de caixas de dimensões distintas, desejase armazenálas no menor número possível de contêineres, todos de mesmo tamanho é um problema da classe P.
IV – Sabese que P ≠ NP.
Resposta Selecionada:
D.
Apenas I Respostas:
a.
Apenas I, II e III
b.
Apenas I, II e IV
c.
Apenas I e IV
d.
Apenas I e.
Apenas IV
Pergunta 3 data:text/html;charset=utf8,%3Csection%20id%3D%22pf_text_1%22%20style%3D%22boxsizing%3A%20borderbox%3B%20display%3A%20block%3… 2/11
27/04/2015
UNIDADE 2 ASPECTOS TEORICOS DA COMPUTA O Trabalhos de Pesquisa Rildonacademic
0,5 em 0,5 pontos
Em uma determinada edificação, em que o esquema de segurança é crucial, desejase cobrir todas as áreas de circulação e ao mesmo tempo minimizar o número de pontos de monitoração. Sabese que o número de salas deste lugar é 30 e o número de corredores é 15. A fim de se obter exatamente o menor número