dam2

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sabendo que a linguagem CAIXEIRO_VIAJANTE(G), capaz de computar uma solução para o problema do caixeiro viajante sobre um grafo G, é NP-completa, um programador propôs o seguinte relaxamento:

Dado um grafo com V vértices, em vez de se calcular a solução ótima, que é obter o ciclo hamiltoniano cujo caminho é o de menor tamanho, uma solução muito boa seria utilizar N caixeiros e fazê-los resolver o problema para apenas V/N vértices do grafo original, assegurando-se de que não haja caixeiros compartilhando vértices.

Uma linguagem auxiliar útil a este relaxamento poderia ser do formato CAIXEIRO_PARCIAL(G, N). Neste sentido, o uso CAIXEIRO_PARCIAL(G, 7), por exemplo, retornaria um ciclo para um caixeiro viajante, que passa por apenas 1/7 dos vértices de G.

Dado tal cenário, considere as seguintes afirmações:

(I) A linguagem CAIXEIRO_PARCIAL(G, N) também é NP-completa.

(II) Para verificar se a linguagem CAIXEIRO_PARCIAL(G, N) é NP-completa, basta reduzi-la à linguagem CAIXEIRO_VIAJANTE(G).

(III) A linguagem CAIXEIRO_PARCIAL(G, N) é certamente NP.

(IV) Com a disponibilidade de processadores multicore e da programação multithread, pode ser que o relaxamento proposto seja computado em tempo polinomial, desde que se paralelize a computação dos N caixeiros.

Escolha a alternativa CORRETA:

1. Todas as afirmações são verdadeiras.
2. Apenas a afirmação III é verdadeira.
3. Apenas as afirmações I, II e III são verdadeiras.
4. Apenas as afirmações I e III são verdadeiras.
5. N.D.A.

Ideia original de: Daniel Henriques Moreira

luc2

MO 417 - QUESTÃO PARA A PROVA ORAL 2ª QUESTÃO

Número:

Enunciado: Sabendo que SAT é NP-Completo e que existem funções polinomiais f(n) e g(n) que possibilitam a redução de SAT ao CLIQUE transformando a entrada de SAT em uma entrada para CLIQUE e transformando o resultado de CLIQUE para o resultado de SAT. É INCORRETO afirmar que:

a) A redução de SAT ao CLIQUE prova que CLIQUE é pelo menos NP-difícil.

b) Se soubessemos que a cota inferior de SAT é omega(h(n)) podemos afirmar que a cota inferior de CLIQUE é igual a cota inferior de SAT, omega(h(n)) apenas se f(n)+h(n)=o(h(n)).

c) Se soubessemos que CLIQUE tem cota superior O(h(n)) podemos afirmar que SAT tem cota inferior O(h(n)).

d) Se soubessemos que CLIQUE tem cota superior O(h(n)) podemos afirmar que SAT tem cota superior O(h(n)) apenas se f(n)+h(n)=o(h(n)).

e) NDA

Definições:

Cota superior: Dado um problema, se conhecemos um algoritmo que resolve tal problema em um modelo computacional em tempo T(n) então T(n) é a cota superior do problema.

Cota inferior: Dado um problema e um modelo computacional, a cota inferior do problema expressa a eficiência mínima para qualquer algoritmo que possa resolver o problema neste modelo computacional. Por exemplo, problemas de ordenação por comparação tem cota inferior = tetha(nlgn).

Ideia original de: Lucas Oliveira Batista

osv

MO417 - Questão para prova oral

June 14th, 2013 · osvaldo · Exercises (MO417) No comments

Número:
Enunciado: Considere uma versão restrita do problema da satisfabilidade onde as fórmulas podem conter no máximo k ocorrências de cada variável e que k é fixo. Analise as afirmações abaixo e assinale a alternativa correta.
I - Somente para k > 3 o problema é NP-COMPLETO
II - Para k >= 3 o problema é NP-COMPLETO
III - Para K <= 2 o problema pode ser resolvido em tempo polinomial
IV - O tamanho de K não interfere na classificação do problema
Alternativas:
a) Somente I está correta
b) Somente IV está correta
c) II e III estão corretas
d) Somente II está correta
e) NDA
Idéia original de: Osvaldo Andrade Neto

ren

MO417 - Questão para a prova oral

Número:

Enunciado: O problema da soma de um subconjunto é definido como: dado um conjunto S finito de inteiros positivos e um alvo t também inteiro positivo, deseja-se saber se há um subconjunto de S cuja a soma é igual ao alvo t. Esse problema é NP-Completo. Uma definição dele é dada abaixo e, como padrão, os dados de entrada são codificados em binário.

 

SUBSET-SUM = {(S,t) : existe um subconjunto S' ⊆ S tal que t = ∑[n ∈ S'] n}  

Se restringirmos o conjunto S para apenas poder conter inteiros que são potências de 2, qual das afirmações abaixo sobre o novo problema é verdadeira?

 

 I  - O problema continua a ser NP-Completo.

II  - O problema pertence à classe NP.

III - O problema pertence à classe co-NP.

a)  I e II
b)  Apenas a II
c)  Apenas a III
d)  II e III
e)  N.D.A.

Ideia original de:  René du Raymond Sacramento

tha

MO417 - Questão para a prova oral

Número:

Enunciado: Vários departamentos policiais de uma cidade precisam se comunicar sobre ocorrências e para isso foi estabelecida uma rede interligando-os. A comunicação deve ser feita de forma a atender o requisito de que uma mesma ocorrência passe por todos os departamentos uma única vez, partindo sempre do departamento A. A rede estabelecida e representada pelo grafo abaixo ainda não cumpre esse requisito de comunicação. 

Identifique primeiro uma nova conexão que deve ser criada para atender o requisito de comunicação. Em seguida, identifique outra conexão de forma que não só esse requisito seja atendido, como a informação retorne ao departamento de origem A para que este saiba que todos os departamentos receberam com sucesso a informação da ocorrência. 

Qual alternativa contém respectivamente a primeira e a segunda conexão válida para atender o exigido acima?

A) (C,E) e (G,H)

B) (D,G) e (D,F)

C) (D,F) e (E,H)

D) (E,F) e (D,H)

E) N.D.A

Ideia original de: Thaís Harumi Ussami

jai

MO417 - QUESTÃO PARA A PROVA ORAL
Número:
Qual é a sequencia correta de passos de um procedimento para provar que uma linguagem L é NP-completo e NP-difícil respectivamente.

1) Escolher uma linguagem L' que seja NP-completa.
2) Descrever um algoritmo que compute uma função F:L'->L, tal que cada instancia x∈{0,1}* de L', F(x)∈L.
3) Provar que o algoritmo computa F em tempo polinomial cada instância.
4) Provar L ∈ NP.
5) Provar que a função F satisfaze x∈L' se e só sem F(x)∈L para todo x∈{0,1}*.

A sequencia correta é:
a. (4,1,2,5,3) e (4,2,5,3)
b. (4,1,2,5,3) e (1,2,5,3)
c. (1,2,3,4,5) e (1,2,3,5)
d. (4,1,2,5) e (4,2,5,3)
e. DNA.

Ideia original de: Vladimir Jaime Rocca Layza

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