jun

MO417 - Questão para a prova oral

Numero:

Enunciado: Leia a seguintes afirmações e assinale a alternativa Correta

I     No problema de soma de subconjuntos(subset-sum problem).temos um conjunto finito de inteiros positivos S e um inteiro destino t > 0. Perguntamos se existe um subconjunto cujos elementos tenham a soma t.
     Adicionalmente, este problema é NP-completo

II    No problema do caixeiro-viajante (traeling-salesman problem), um vendedor deve visitar n cidades.Modelando o problema como um grafo completo com n vertices,podemos dizer que o vendedor deseja fazer uma viagem,ou um ciclo hamiltoniano,visitando cada cidade exatamente uma vez e terminando na cidade de onde partiu.
      Adicionalmente, este problema é NP-completo

III   O problema de cobertura de vertices (vertex-cover problem) é o de encontrar uma cobertura de vertices de tamano minimo num grafo dado.
       Adicionalmente, este problema é NP-completo

IV   O problema do grupo exclusivo(clique problem) é o problema de otimizacao de encontrar um grupo exclusico de tamanho maximo em um grafo.
       Adicionalmente, este problema é NP-completo

 Qual é a alternativa correta:

a) Somente I é correta

b) Somente I , II , III  são corretas

c) Somente II, IV são corretas

d) Todos são corretas

e) NDA

                                             Ideia original de: Junior Cupe Casquina