Pergunta 1
0,5 em 0,5 pontos

Assinale a alternativa que representa um problema NP-Completo:

Resposta Selecionada:
E.
Problema do ciclo hamiltoniano.
Respostas:
a.
Satisfabilidade booleana-2.

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

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, deseja-se armazená-las no menor número possível de contêineres, todos de mesmo tamanho é um problema da classe P.
IV – Sabe-se 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
0,5 em 0,5 pontos

Em uma determinada edificação, em que o esquema de segurança é crucial, deseja-se cobrir todas as áreas de circulação e ao mesmo tempo minimizar o número de pontos de monitoração. Sabe-se 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 de pontos de monitoração de forma