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

ota

MO417- Questão para a prova oral
Numero:

Um dos problemas de Karp, os quais foram provados pertencerem a NP-Completo, é o problema do clique máximo em um grafo não direcionado.
O clique máximo de um grafo G é o maior subgrafo, em número de vértices, os quais todos os vértices estejam conectados, ou seja o subgrafo completo com maior número de vértices de G.

Um uso do clique máximo é achar nas redes sociais, com usuários como vértices e as arestas a relação entre eles, o maior grupo, ou subgrafo, onde todos os usuários estejam conectados entre si, e assim direcionar alguns recursos como notícias e propagandas.

Sobre esse problema:

I.  O problema de se achar o clique máximo em G , no complemento de G,  é mais fácil  do que em G.
II. Seria possível encontrar um k-clique máximo de G=(V,E), ou um clique com k vértices para k <|V| , em tempo polinomial  através de buscas em grafos.
III. Se for possível enumerar todos as componentes fortemente conexas de G em tempo polinomial, o problema do clique também seria resolvido em tempo polinomial para o tamanho da entrada.
IV.  Como se trata de um problema de decisão, é possível propor um algoritmo guloso que pode encontrar pelo menos um i-clique, onde i é menor ou igual ao clique máximo.

São verdadeiras apenas:

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

Ideia original de: Otavio Augusto A. Silva

var

MO417 - Questão para a prova oral

Número:

Enunciado: Conhecemos que o problema de decisão do CLIQUE é NP-Completo. Analise as sentenças a seguir e identifique a alternativa correta.

I) O problema de decisão do CLIQUE em grafos bipartidos é NP-Completo
II) O problema de decisão do CLIQUE em grafos planares é de classe P
III) O problema de decisão do CLIQUE em grafos densos não é NP-Completo

a) Apenas I está correta
b) Apenas II está correta
c) Apenas III está correta
d) Todas estão corretas
e) NDA


Ideia original de: John Edgar Vargas Muñoz

kim

MO417 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa que contém todos os problemas NP-Completos da lista de problemas abaixo:

I - Ciclo Hamiltoniano.

II - Mochila Binária.

III - Problema da Satisfabilidade de Circuitos.

IV - Problema do Grupo Exclusivo.

(a) I, II e III.

(b) I, II e IV.
(c) II, III e V.

(d) II, IV e V.

(e) N.D.A.

Idéia original de: Kim Pontes Braga

pau

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-

Enunciado: Considere as linguagens MATCHING = {<G, k> : G é um grafo bipartido e possui um emparelhamento de cardinalidade k} e MAX-FLOW = {<G, k> : G é um grafo direcionado ponderado que possui um fluxo de valor k}. Qual/quais dos seguintes fatos não garante(m) que MATCHING ∈ P?

I - MATCHING pode ser reduzida polinomialmente a MAX-FLOW, sendo que MAX-FLOW ∈ P.

II - Existe um algoritmo A que, dado um certificado, verifica MATCHING em tempo polinomial.

III - Existe um algoritmo A' que decide MATCHING em tempo polinomial.

IV - Existe uma linguagem L ∈ P que pode ser reduzida em tempo polinomial a MATCHING.

a) I e IV

b) IV, somente.

c) II e IV.

d) II, somente.

e) N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus

mar

MO417 - Questão para a prova oral

Número:

Enunciado: Analise as seguintes afirmativas e indique a alternativa INCORRETA:

a) Um problema de decisão A que seja NP-difícil pode ser mostrado ser NP-completo exibindo um algoritmo determinista polinomial para A.
b) Apenas problemas de decisão (“sim/não”) podem ser NP-completo.
c) Problemas de otimização podem ser NP-difícil, mas geralmente, se A é um problema de decisão e B um problema de otimização, é bem possível que A é polinomialmente transformável em B.
d) A dificuldade de um problema NP-difícil não é menor do que a dificuldade de um problema
NP-completo
e) NDA

Ideia original de: Marleny Luque Carbajal

she

MO417- QUESTÃO PARA A PROVA ORAL

Número:  

Enunciado: Qual das seguintes alternativas não representa um problema NP-Completo?

a) Encontrar o caminho mais longo entre dois vértices de um grafo orientado
b) Encontrar um ciclo Hamiltoniano num grafo com |V| vértices e |V| arestas
c) O problema de caixeiro viajante com presença de arestas de peso negativo, sem ciclos negativos 
d)Um circuito no problema SAT que também use portas XOR (retorna 1 se X1 e X2 forem diferentes)
e) NDA

 Ideia original de: Sheila Katherine Venero Ferro

rap

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre o circuito lógico abaixo, qual a alternativa correta?

a) É satisfatível, tendo saída 1 para a = 0 e b = 1
b) É satisfatível, tendo saída 1 para a = 1 e b = 0
c) É satisfatível, tendo saída 1 para a = 1 e b = 1
d) Não é satisfatível.
e) NDA

Ideia original de: Raphael Azzolini

jor

MO417 - Questão para a prova oral

Número:

Enunciado: Considere os seguintes circuitos:

I.   (x1 OR x2) OR (NOT (x1 OR x2))
II.  NOT((NOT x1) OR (NOT x2))
III. NOT((NOT x1) AND (NOT x2))

Podemos usar alguns deles para reduzir o problema SAT a um problema de satisfabilidade com apenas duas portas lógicas válidas (NOT e AND/OR).

Quais deles podemos usar para provar este problema é NP-completo, e como? Suponha que já temos como validar este problema em O(n^k).

a. circuito I, substituindo a porta AND por ele
b. circuito I, substituindo a porta OR por ele
c. circuito I e II, substituindo a porta AND por I ou a porta OR por III.
d. circuito II e III, substituindo a porta AND por II ou a porta OR por III.
e. NDA

Idéia original de: Jorge Augusto Hongo

luc

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

Número:

Enunciado: Uma empresa de produtos alimentícios possui uma frota de veículos que realizam entregas por diversas cidades. Os veículos de transporte de mercadoria possuem uma capacidade limitada de carga e devem realizar entregas em diferentes cidades distribuídas em um mapa. O gerente desta empresa deseja minimizar os custos no processo de entrega de mercadorias determinando rotas que minimizem a distância total percorrida e atenda a todas as demandas das cidades do mapa. Os veículos devem partir do depósito e retornar para o mesmo e cada cidade só deve ser visitada uma vez.
A figura abaixo ilustra uma possível solução do problema:

O problema descrito acima pode ser reduzido ao:

a) Ciclo Hamiltoniano
b) Clique
c) Fluxo máximo
d) Caxeiro Viajante
e) NDA

Ideia original de: Lucas Oliveira Batista

tia

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dentre as alternativas abaixo, assinale a INCORRETA.

A) A classe de problemas NP pode ser definida como o conjunto de problemas de decisão que podem ser solucionados em tempo polinomial em uma Máquina de Turing não determinística.

B) Um problema c em NP também está em NPC se e somente se todos os outros problemas em NP podem ser transformados em p em tempo polinomial.

C) A classe de problemas P engloba todos os problemas de decisão que podem ser resolvidos por um algoritmo de tempo polinomial.

D) A classe de problemas NPC é um subconjunto dos problemas de decisão em NP de tal modo que todo problema em NP pode-se reduzir, com uma redução de tempo polinomial, a um dos problemas NPC.

E) N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

mig

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado as afirmações abaixo

I. Cada problema em NP pode ser resolvido no tempo exponencial.
II. Se houver um problema X que pode ser reduzido a um problema NP-difícil conhecido, então X deve ser NP-difícil.
III. Se P é igual a NP, então NP é igual a NP-completo.
|V. O seguinte problema está em NP: dado um número n = p.q, em que p e q são números primos de N-bits, encontre p ou q.

Quantas dessas afirmações são verdadeiras ?

(a) 1

(b) 2

(c) 3

(d) 4

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

gui

MO417 - Questão para a prova oral
 
Número:

Enunciado: Sabe-se que o problema do carteiro chinês é NP-Completo, o qual visa encontrar um passeio fechado de tamanho mínimo em grafos direcionados e não direcionados, permitindo passar por cada aresta do grafo no mínimo uma vez para retornar ao ponto de origem. Com base nessas informações, assinale a alternativa que contém o valor mínimo de arestas repetidas no grafo não direcionado abaixo, começando o passeio fechado pelo vértice 1.

 

a) 2
b) 3
c) 4
d) 5
e) NDA


Ideia original de: Luís Guilherme Cordiolli Russi

mcs

MO417 - Questão para a prova oral

Número:

Enunciado: Dado o circuito combinacional booleano C abaixo, composto pelas portas lógicas AND, OR e NOT. As entradas do circuito são os valores atribuídos a X1, X2 e X3.

Qual atribuição para as entradas desse circuito faz a saída do circuito se tornar 1?
Quantos satisfazem C, entre as 8 possíveis entradas pela tripla (X1, X2 e X3), ou seja CIRCUIT-SAT = {<C>: C é um circuito combinacional booleano capaz de satisfação}?

a) <X1 = 0, X2 = 1, X3 = 0> e Número_CIRCUIT-SAT(1) = 1
b) <X1 = 1, X2 = 1, X3 = 0> e Número_CIRCUIT-SAT(1) = 3
c) <X1 = 0, X2 = 0, X3 = 1> e Número_CIRCUIT-SAT(1) = 3
d) <X1 = 1, X2 = 0, X3 = 1> e Número_CIRCUIT-SAT(1) = 2
e) NDA

Idea Ogirinal: Marcelo Palma Salas