MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-109

Enunciado: Você está jogando um jogo online chamado Danos. Percebendo que você pode converter o mapa do jogo em um grafo com vértices representando as posições no mapa e com arestas representando as passagens entre elas, você observa que cada aresta no grafo provoca uma quantidade de danos a você no jogo. É possível ainda representar os danos causados ​​por pesos em cada aresta. Você então, usa o algoritmo de Dijkstra para encontrar o caminho de A a H, com o menor dano possível. Anote a ordem em que os vértices são removidos da fila de prioridade ao executar o algoritmo de Dijkstra.

1. A, B, D, C, F, E, G, H
2. A, B, C, D, F, E, G, H
3. A, B, D, C, E, F, G, H
4. A, B, C, D, E, F, G, H
5. NDA

Ideia original de: Lucas Miguel de Carvalho

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-108

Enunciado: Considere problemas de fluxo onde arestas possuem uma necessidade mínima de fluxo que deve ser cumprida. Por exemplo, no grafo abaixo, a aresta AB tem capacidade igual a 8 e necessidade mínima igual a 5, o que significa que o fluxo nesta aresta tem de estar entre 5 e 8.

No grafo abaixo, quais podem ser os valores de x e y, representando respectivamente a necessidade mínima e a capacidade da aresta AC, para que exista um fluxo entre a origem S e o destino T?

1. x=1 e y=3
2. x=4 e y=6
3. x=7 e y=9
4. x=10 e y=12
5. NDA

Ideia original de: Lucas Miguel de Carvalho

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-107

Enunciado: Dadas as afirmações abaixo

I. Cada linguagem em NP pode ser decidida em tempo exponencial.
II. Se uma linguagem X for reduzida a uma linguagem NP-difícil, então X  será NP-difícil.
III. Se P é igual a NP, então NP é igual a NP-completo.
IV. A seguinte linguagem está em NP: {n ∈ Naturais | n = p.q, onde p e q são números primos}.


Quantas dessas afirmações são verdadeiras ?

1. 4
2. 3
3. 2
4. 1
5. NDA

Ideia original de: Lucas Miguel de Carvalho

MO417 - Questão para prova oral

Número: 2013-106

Enunciado: Considere uma versão restrita do problema da satisfatibilidade onde as fórmulas tem até 3 literais por cláusula e podem conter no máximo k ocorrências de cada variável, onde 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 está em P
IV - O tamanho de k não interfere na complexidade do problema

 Alternativas:

1. II e III estão corretas
2. I e III estão corretas
3. Somente IV está correta
4. Somente II está correta
5. NDA

Ideia original de: Osvaldo Andrade Neto

MO417 - Questão para a prova oral

Número: 2013-105

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, quais das afirmações abaixo sobre o novo problema são verdadeiras?


I - O problema continua a ser NP-Completo.
II - O problema pertence à classe NP.
III - O problema pertence à classe co-NP.

1. Apenas a II 
2. Apenas a III 
3. I e II
4. II e III
5. N.D.A.

Ideia original de: René du Raymond Sacramento

MO417 - Questão para a prova oral

Número: 2013-104

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

I) O problema de decisão CLIQUE em grafos bipartidos está em P
II) O problema de decisão do CLIQUE em grafos planares está em P
III) O problema de decisão do CLIQUE em grafos densos, isto é, grafos onde o número de arestas é pelo menos 1/6 do quadrado do número de vértices, é NP-Completo

1. Apenas I está correta
2. Apenas II está correta
3. Apenas III está correta
4. Todas estão corretas
5. NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-103

Enunciado: Seja P a classe das linguagens decidíveis em tempo polinomial.  Considere uma linguagem L ∈ P.  Quais dos seguintes fatos sobre uma segunda linguagem M NÃO garantem que M ∈ P?

I - M pode ser reduzida polinomialmente a L.

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

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

IV - A linguagem L pode ser reduzida em tempo polinomial a M.

1. I e IV
2. II, somente.
3. II e IV.
4. IV, somente.
5. N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus

MO417- QUESTÃO PARA A PROVA ORAL

Número: 2013-102

Enunciado: Qual das seguintes alternativas não representa um problema NP-Difícil?

1. Encontrar um caminho de comprimento máximo num grafo orientado
2. Encontrar um ciclo Hamiltoniano num grafo com n vértices e n arestas
3. O problema de caixeiro viajante com presença de arestas de peso negativo, sem ciclos negativos
4. A versão de SAT que também usa a operação XOR (onde X1 XOR X2 retorna 1 se e somente se X1 e X2 forem diferentes)
5. NDA

Ideia original de: Sheila Katherine Venero Ferro

MO417 - Questão para a prova oral

Número: 2013-101

Enunciado: O problema do carteiro chinês visa encontrar um passeio fechado de peso mínimo num grafo, passando por cada aresta no mínimo uma vez. Assinale a alternativa que contém o número mínimo de arestas repetidas no grafo não direcionado abaixo, num passeio fechado passando por todas as arestas.

1. 2
2. 3
3. 4
4. 5
5. NDA

Ideia original de: Luís Guilherme Cordiolli Russi

MO417 - Questão para a prova oral

Número: 2010-120

Enunciado: Considere as afirmações abaixo:

• Se NP ≠ co-NP, então P ≠ NP.
• Se SAT ∉ co-NP, então co-NP ≠ P.
• Se SAT ∈ P, então co-NP ≠ P.
• Se SAT ∈ P, então SAT (complemento de SAT) ∈ P

Quantas delas estão corretas?

1. 1
2. 2
3. 3
4. 4
5. NDA

Ideia original de: Leonardo de Paula Rosa Piga

MO417 - Questão para a prova oral

Número: 2010-119

Enunciado: Considere as seguintes linguagens:

CAMINHO-MAIS-CURTO: {<G,u,v,k> | G é um grafo, u e v são dois vértices de G e existe um caminho de u a v com até k arestas}

CAMINHO-MAIS-LONGO: {<G,u,v,k> | G é um grafo, u e v são dois vértices de G e existe um caminho de u a v com pelo menos k arestas}

TRILHA-DE-EULER: {<G> | G é um grafo e existe uma trilha de Euler em G}

CICLO-HAMILTONIANO: {<G> | G é um grafo e existe um ciclo hamiltoniano em G}

CLIQUE: {<G,k> | G é um grafo e existe uma clique em G com pelo menos k vértices}

COBERTURA-POR-VÉRTICES: {<G,k> | G é um grafo e existe uma cobertura das arestas de G com até k vértices}

São NP-Completas:

1. CAMINHO-MAIS-CURTO, TRILHA-DE-EULER e CLIQUE
2. CLIQUE, CICLO-HAMILTONIANO e CAMINHO-MAIS-CURTO
3. COBERTURA-POR-VÉRTICES, CICLO-HAMILTONIANO e CAMINHO-MAIS-LONGO
4. TRILHA-DE-EULER, CICLO-HAMILTONIANO e CAMINHO-MAIS-LONGO
5. NDA

Ideia original de: Juliana Galvani Greghi

MO417 - Questão para a prova oral

Número: 2010-117

Enunciado: No problema de satisfabilidade de circuitos, considere as portas lógicas e o circuito apresentados abaixo.

Portas lógicas:



Circuito:


Dado que as entradas do circuito são os valores atribuídos a X₁, X₂, X₃ e X₄, qual atribuição para as entradas desse circuito faz a saída do circuito se tornar 1?

1. X₁ = 1, X₂ = 0, X₃ = 0, X₄ = 1 
2. X₁ = 1, X₂ = 0, X₃ = 1, X₄ = 1 
3. X₁ = 1, X₂ = 1, X₃ = 0, X₄ = 1 
4. X₁ = 1, X₂ = 1, X₃ = 1, X₄ = 1 
5. NDA

Ideia original de: Maikon Cismoski dos Santos

MO417 - Questão para a prova oral

Número: 2010-115

Enunciado: Dadas as seguintes afirmações, onde NPC significa NP-Completo, assinale a alternativa correta:

I. L ∈ NPC se para todo L' ∈ NP, L' ≤_p L.
II. L ≤_p L' se existe uma função f polinomial tal que x ∈ L se e somente se f(x) ∈ L'.
III. Se L" ≤_p L' e L'≤_p L, então L" ≤_p L.
IV. L’ ≤_p L para alguma L’ ∈ NPC, então L é NP-difícil.

1. Apenas uma afirmação está correta.
2. Apenas duas afirmações estão corretas.
3. Apenas três afirmações estão corretas.
4. Todas as afirmações estão corretas.
5. NDA

Ideia original de: Fábio Augusto Faria

MO417 - Questão para a prova oral

Número: 2010-114

Enunciado: Considere o circuito combinacional booleano C abaixo, composto de portas AND, OR e NOT, lembrando que as portas OR têm base curva:
Dos 8 possíveis valores de entrada para a tripla (x₁, x₂, x₃), quantos satisfazem C?

1. 0
2. 1
3. 2
4. 3
5. NDA

Ideia original de: Priscila Tiemi Maeda Saito

MO417 - Questão para a prova oral

Número: 2010-113

Enunciado: Uma forma de representar conjuntos disjuntos é utilizar florestas onde os conjuntos são representados por árvores enraizadas, com cada nó contendo um elemento e cada árvore representando um conjunto. Além disso, cada nó da árvore aponta apenas para seu pai e o nó raiz da árvore contém o elemento representante e é seu próprio pai.
Considere os algoritmos abaixo utilizados em operações de conjuntos disjuntos representados por florestas de conjuntos disjuntos. O pai de um nó x em uma árvore é dado por p[x].

MAKE-SET(x) 1 p[x] ← x 2 r[x] ← 0

UNION(x, y) 1 x ← FIND(x) 2 y ← FIND(y) 3 if x ≠ y then 4     LINK(x,y)

LINK(x, y) 1 if r[x] > r[y] then 2     p[y] ← x 3 else 4     p[x] ← y 5     if r[x] = r[y] then 6         r[y] = r[y] + 1

FIND(x) 1 if x ≠ p[x] then 2     p[x] ← FIND(p[x]) 3 return p[x]

Empregando o conceito florestas de conjuntos disjuntos, dados n=8 elementos distintos, quais dos algoritmos abaixo resulta em uma única árvore contendo os n elementos?

A 1 for i←1 to n do 2     MAKE-SET(xi) 3 for i←1 to n/2 do 4     UNION(x2i-1,x2i) 5 UNION(1, 3) 6 UNION(6, 8) 7 UNION(5, 8)

B 1 for i←1 to n do 2     MAKE-SET(xi) 3 for i←1 to n/2 do 4     UNION(x2i-1,x2i) 5 UNION(8, 2) 6 UNION(6, 5) 7 UNION(3, 4)

C 1 for i←1 to n do 2     MAKE-SET(xi) 3 for i←1 to n/2 do 4     UNION(x2i-1,x2i) 5 UNION(4, 6) 6 UNION(8, 2) 7 UNION(5, 2)

D 1 for i←1 to n do 2     MAKE-SET(xi) 3 for i←1 to n/2 do 4     UNION(x2i-1,x2i) 5 UNION(1, 4) 6 UNION(5, 7) 7 UNION(2, 4)

E NDA

Ideia original de: Maikon Cismoski dos Santos

MO417 - Questão para a prova oral

Número: 2010-112
Enunciado: Analise as sentenças a seguir e identifique a alternativa correta.

I) O número de arestas (cardinalidade) de um emparelhamento num grafo bipartido G = (V, E) é no máximo |V|/2.
II) A cardinalidade do emparelhamento máximo do grafo bipartido abaixo é igual a 5.
III) Existe um único emparelhamento máximo no grafo acima.

1. Apenas I e III estão incorretas
2. Apenas II está correta
3. Apenas II e III estão corretas
4. Todas estão corretas
5. NDA

Ideia original de: Ewerton Almeida Silva

MO417 - Questão para a prova oral

Número: 2010-110

Enunciado: Considere as classes de problemas P, NP, NP-difícil e NP-completo e os seguintes procedimentos:

I. Encontrar um algoritmo determinístico polinomial para algum problema em NP.
II. Encontrar um algoritmo determinístico polinomial para algum problema em NP-difícil.
III. Encontrar um algoritmo determinístico polinomial para algum problema em NP-completo

Para provar que P = NP:

1. Apenas os procedimentos I e II podem ser utilizados.
2. Apenas os procedimentos I e III podem ser utilizados.
3. Apenas os procedimentos II e III podem ser utilizados.
4. Todos os procedimentos podem ser utilizados.
5. NDA

Ideia original de: Marcos Vinícius Mussel Cirne

MO417 - Questão para a prova oral

Número: 2010-109

Enunciado: Königsberg era uma cidade da Prussia, situada `as margens do rio Pregel, que cortava a cidade de maneira bastante peculiar, criando duas ilhas. Sete pontes ligavam as duas ilhas entre si e ao continente. Durante muito tempo várias pessoas se perguntaram se seria possível fazer um passeio pela cidade passando por cada ponte exatamente uma vez. A figura abaixo representa de forma esquemática a cidade de Königsberg e o grafo a ela relacionado. Este problema reduz-se a:

1. encontrar uma árvore espalhada mínima num grafo
2. encontrar um caminho de peso mínimo num grafo
3. encontrar um ciclo hamiltoniano num grafo
4. encontrar um passeio euleriano num grafo
5. NDA

Ideia original de: Juliana Galvani Greghi

MO417 - Questão para a prova oral

Número: 2010-107

Enunciado: Considerando as classes de complexidade P, NP e NP-completo, bem como reduções entre os problemas de decisão A, B e C, é possível afirmar que: I. Para quaisquer dois problemas A e B, se A é da classe P e existe uma redução polinomial de B a A, então B também é da classe P
II. Se A é redutível polinomialmente a B e B é redutível polinomialmente a C, então A é redutível polinomialmente a C
III. Para quaisquer dois problemas A e B, se A é redutível polinomialmente a B, então B é redutível polinomialmente a A

1. Todas as alternativas são corretas
2. Apenas I e III são corretas
3. Apenas II e III são corretas
4. Apenas III é incorreta
5. NDA

Ideia original de: Priscila Tiemi Maeda Saito

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-100

Enunciado: Qual das seguintes declarações NÃO é correta?

1. HAM-CYCLE ∈ NP e HAM-CYCLE ∈ NPC.
2. Se L ∈ P, então L ∈ NP.
3. Seja {C_k} uma família de circuitos, onde cada C_k tem k entradas e tamanho Θ(2^k). Então verificar a satisfatibilidade do circuito C_k leva tempo polinomial no número de entradas.
4. Seja L uma linguagem e A um algoritmo que verifica L.  Então para nenhuma string x fora de L existe um certificado y tal que A(x,y)=1. 
5. NDA.

Ideia original de: Armando Faz Hernández