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