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

lau

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: O problema do ciclo de Hamiltoniano (HAM-CYCLE) e o problema do caixeiro viajante (TSP) são bastantes conhecidos da teoria de NP-completude. Sabendo que HAM-CYCLE é NP-completo e que TSP é NP, para provar que TSP é NP-completo, basta mostrar que TSP é NP-difícil apresentando uma redução polinomial do HAM-CYCLE para o TSP. Quantas arestas são necessárias adicionar ao grafo abaixo para realizar tal redução? 

 

 

Observação: o grafo acima apresenta HAM-CYCLE.

1. 1
2. 3  
3. 10
4. 12
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

jul

MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número:

Enunciado: Suponha que exista uma empresa de engenharia eletrônica que está muito preocupada com possíveis plágios do design de seus componentes eletrônicos.

Ela pretende iniciar um processo penal contra uma outra empresa, mas precisa de evidências do plágio. Portanto, ela decidiu contratar você para desenvolver algoritmos que lhe dê certeza disso.

Para isso, é necessário que os algoritmos resolvam os seguintes problemas, relacionados a dois designs eletrônicos (A) e (B):

• Determinar se o design (A) está ou não contido dentro do design (B).
  
• Determinar qual é o maior sub-design de (B) equivalente ao design (A).

Obs.: Os engenheiros da empresa lhe alertam sobre a possibilidade de que as peças eletrônicas podem estar distribuídas espacialmente de forma diferente em cada um dos designs.

De acordo com essas informações, assinale a alternativa correta: 

1. Os dois problemas podem ser resolvidos em tempo polinomial, se pelo menos um deles pode ser resolvido em tempo polinomial.
2. Apenas o primeiro problema pode ser resolvido em tempo polinomial.
3. Apenas o segundo problema pode ser resolvido em tempo polinomial.
4. Os dois problemas não tem solução.  
5. NDA 

Ideia original de: Julián Esteban Gutiérrez Posada

wal

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considere o seguinte problema como o Problema do Carteiro Idoso: deseja-se encontrar o menor circuito (a soma dos pesos de arestas seja mínimo), cuja origem é a posição inicial do carteiro, passando exatamente 1 vez em cada residência. A figura abaixo ilustra o problema, onde o carteiro e cada residência são nós de um grafo não orientado ponderado.

 

 

Dada a definição informal do problema, é correto afirmar que:

 

a. Este problema é da classe NPC, pois é possível associá-lo ao problema de encontrar um circuito de Euler.

b. Este problema é da classe P, pois é possível resolvê-lo aplicando o algoritmo de Prim.

c. Este problema é da classe NPC, pois é possível associá-lo ao problema de encontrar um ciclo Hamiltoniano.

d. Este problema é da classe P, pois é possível resolvê-lo aplicando o algoritmo de Dijkstra.

e. NDA

 

Ideia Original: Wallace Felipe Francisco Cardoso

dav

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Sobre ciclos e caminhos hamiltonianos, é incorreto afirmar:

1. Quando removida uma aresta de um ciclo hamiltoniano sempre se obtém um caminho hamiltoniano
2. Não há ciclos hamiltonianos em grafos bipartidos com número ímpar de vértices
3. Se os vértices de início e fim de um caminho hamiltoniano forem adjacentes é possível obter um ciclo hamiltoniano
4. O numero de diferentes ciclos hamiltonianos num grafo não-direcionado completo com n vértices é  (n − 1)! / 2
5. NDA

Ideia original de: Daniel Vidal

2013-06-14

car

MO417 - Questão para a prova oral

Número:

Enunciado: Leia as seguintes afirmações:

I.- Uma forma de provar que um problema é NP-completo, é fazer-lhe uma redução ate um problema de decisão.
II.- O fechamento da estrela de Kleene de uma linguagem L é a linguagem L*= L¹ U L² U L³ U ...
III.- A classe NP tem problemas que som certificados por um algoritmo que corre em tempo polinomial.

Escolha a alternativa correta.

a) I y II são verdadeiras.
b) Apenas III e verdadeira.
c) II e III não são falsas.
d) I, II e III são verdadeiras.
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales

arm

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Qual das seguintes declarações não é correta?

1. HAM-CYCLE ∈ NP e HAM-CYCLE ∈ NPC.
2. Seja L um linguagem e x uma seqüência binaria, então para toda x∉L, não existe um certificado y tal que A(x,y)=1, onde A é um algoritmo que verifica L.
3. Se L∈P, entao L∈NP.
4. Seja C um circuito de k entradas e tamanho θ(2^k), entao verificar a satisfatibilidade do circuito leva tempo polinomial ao numero de entradas.
5. NDA.

Ideia original de: Armando Faz Hernández

fab

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: O grafo abaixo representa o fluxo em uma rede de capacidade infinita para todas as arestas. Qual dos seguintes pares de vértices NÃO respeitam a propriedade de conservação do fluxo?

A) b, c
B) d, e
C) b, d
D) c, e
E) NDA

Ideia original de: Fabrício Matheus Gonçalves

jac

MO417 - Questão para a prova oral

Número:

Enunciado: Sabendo que dado um problema A e B podemos reduzir A a B se é possível converter a entrada de A para a entrada de B, resolver o problema B e converter a saída de B para o problema A. Isto é, podemos solucionar o problema A através de B. Então sobre a noção de redução e sobre as classes P e NP podemos afirmar que:

a) P ⊂ NP.
b) Um problema pertence à classe NP se seu problema de decisão é tratável.
c) Se B é um problema pertencente à classe P e podemos reduzir A a B então A também pertence à classe P.
d) Se B é um problema pertencente à classe NP e podemos reduzir A a B então A também pertence à classe NP.
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

jho

MO417 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa correta:

1.)Se um problema P1 se reduz a um problema P2 en tempo polinomial, então P2 é NP 
2.)Se um algoritmo verifica um problema P1 em tempo polinomial, então P1 é NP
3.)Se um algoritmo verifica um problema P1, então P1 é NP-Completo
4.)Se qualquer problema NP-difícil pode ser reducido a B em tempo polinomial, então P = NP
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga

ali

MO417 - Questão para a prova oral

Número:

Enunciado: Marque a alternativa que contém as arestas que fazem parte do menor corte (S,T) "minimum cut (S,T)" do grafo de fluxo abaixo. Lembrando que pelo teorema de Max-flow Min-Cut (Ford-Fulkerson, 1956), em qualquer grafo o valor do fluxo máximo é igual a capacidade do menor corte.

a) SA, AB, AT
b) SA, SB, SC
c) AB, BD, CD
d) AT, DT, BT
e) NDA

Ideia original de: Alisson Linhares de Carvalho

daf

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Assinale a alternativa correta:

a) A classificação de problemas em "Problemas de Decisão" e "Problemas de Otimização" é, de certa forma, equivalente à classificação em "Problemas NP" e "Problemas NP-Completos", já que os "Problemas de Decisão" são NP e os problemas de otimização são NP-completos.
b) Seja A um problema de otimização e B um problema de decisão relacionado a A, então se A pertence a NP-Completo implica que B pertence a NP-Completo.
c) Seja A um problem de complexidade desconhecida e seja B um problema NP-Completo. Se encontrarmos uma redução de tempo polinomial que transforma instâncias de A em instâncias de B, então provamos que A também é um problema NP-Completo.
d) Seja A um problema da classe NP e B um problema da classe NP-Completo. Se conseguirmos provar que A não pode ser resolvido em tempo polinomial, então garantiremos que B também não pode.
e) N.D.A

Ideia original de: Danielle Furtado dos Santos Dias

acs

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado os algoritmos A₁ que decide a linguagem L₁ e A₂ que decide a linguagem L₂ e L₁, L₂ ⊆ {0,1}* podemos afirmar que:

1. Se L₁ ≤p L₂, então A₁ tem o mesmo tempo assintótico que A₂
2. Se  L₁ ≤p L₂ então L₁ ∈ NP implica L₂  ∈ P
3. Seja T(x) o tempo do algoritmo x, se T(A₁) = O(T(A₂))  e T(A₂) é polinomial então L₁ ≤p L₂
4. Se L₁ ∈ P e A₁ também decidir L₂ então L₂ ∈ NP
5. NDA

Ideia original de: Anderson Carlos Sousa e Santos

eds

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

Enunciado: Dada uma linguagem L, sua decisão sobre um algoritmo A depende de:

1  A linguagem L ser um mapeamento binário da instância do problema.

2  Da aceitação da Linguagem L pelo algoritmo A.
3  Da não aceitação do complemento da Linguagem L .

a. Todas as afirmações estão corretas
b. Somente a afirmação 1 é correta.
c. Somente a afirmação 2 é correta.
d. Somente as  afirmações 2 e 3 são corretas.
e. NDA

Ideia original de: Edson Riberto Bollis

eri

MO417 - Questão para a prova oral

Número:

Enunciado:

I – Se um problema X pode ser reduzido a um outro problema Y, então, certamente, X é tão difícil quanto Y.

II – Seja X um problema tal que X ∈ Ω(n²). Se X pode ser reduzido a um outro problema Y, então, certamente, haverá um algoritmo A, com tempo de execução Ω(n²), para resolver Y.

III – Os problema de cobertura de vértices e caminho mais longo pertencem a classe NP-Completo.

IV – Se P = NP, então, para todo problema de decisão X, X ∈ NP-Completo.

De acordo com as afirmações acima, marque a alternativa correta:

a)      As afirmativas I e II estão corretas.

b)      As afirmativas II e III estão corretas.

c)      Apenas a afirmativa III está correta.

d)     As afirmativas III e IV estão corretas.

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato

ade

MO417 - QUESTÃO PARA A PROVA ORAL


Número:


Enunciado: Dada as seguintes afirmações abaixo, assinale a alternativa correta.

I. Se A é redutível em tempo polinomial a B e B é redutível em tempo polinomial a C, então A é redutível em tempo polinomial a C.

II. Cobertura de Vértice, Clique e Ciclo Hamiltoniano são problemas da classe NP-Completo.

III. Se A é redutível polinomialmente a B e se B ∈ P, então A ∈ P.

a) Somente I e II estão corretas
b) Somente I e III estão corretas
c) Somente II e III estão corretas
d) Todas estão corretas
e) NDA



Ideia original de: Ademar Takeo Akabane

dam

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Um programador propôs a seguinte rotina para transformar um grafo G em um de seus possíveis ciclos hamiltonianos (CH), ou retornar nulo caso não haja um.

HAM-CICLO(G):
  se VERIFICA-HAM-CICLO(G) == falso
      retorna NULO;

  para cada aresta (u, v) de G
      REMOVE-ELEMENTO(v, G.adj[u]);       // elimina aresta (u, v)

  se VERIFICA-HAM-CICLO(G) == falso   // G deixou de possuir um CH?
  ADICIONA-ELEMENTO(v, G.adj[u]);  // recupera aresta (u, v)

   retorna G;

Admitindo-se que as operações REMOVE-ELEMENTO e ADICIONA-ELEMENTO têm complexidade Θ(1) em relação ao tamanho de G.adj[u], e que a operação VERIFICA-HAM-CICLO(G) decide se o grafo G possui ou não um ciclo hamiltoniano, considere as seguintes afirmações:

I) O problema resolvido pela rotina HAM-CICLO é da classe NP. 

II) O problema resolvido pela rotina VERIFICA-HAM-CICLO é da classe NP.

III) Se comprovado que o problema resolvido pela rotina VERIFICA-HAM-CICLO pertence à classe P de problemas, então HAM-CICLO poderá ser executado em tempo polinomial, com relação ao tamanho do grafo de entrada.
IV) VERIFICA-HAM-CICLO resolve um problema de decisão e, por isto, certamente pertence à classe P. Já HAM-CICLO diz respeito a um problema de otimização, que talvez pertença à classe P, se um dia comprovar-se que P = NP.

Escolha a alternativa verdadeira:

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

Ideia original de: Daniel Henriques Moreira

hil

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: O vértice D do grafo abaixo representa uma distribuidora de bebidas, e os demais vértices representam as cidades que um certo caminhoneiro precisará visitar. Ele deve partir da distribuidora e visitar cada cidade exatamente uma vez, retornando para a distribuidora ao final do percurso. As arestas do grafo representam as únicas conexões pelas quais o caminhoneiro pode viajar. Este conjunto de conexões, entretanto, não permite que ele realize o percurso completo sem repetir alguma cidade.

A inclusão de uma única aresta no grafo já seria suficiente para que o caminhoneiro pudesse visitar todos as cidades exatamente uma vez, voltando para a distribuidora ao final. Qual alternativa possui apenas arestas que, se incluídas individualmente no grafo, resolveriam o problema?

1. (B, I), (A, H), (D, F)
2. (D, J), (B, H), (F, A)
3. (A, G), (H, C), (J, B)
4. (C, F), (G, E), (B, I)
5. N. D. A.

Ideia original de: Hilário Seibel Júnior