Questões sobre Complexidade de Algoritmos: junho 2013

sábado, 15 de junho de 2013

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.

A, B, D, C, F, E, G, H
A, B, C, D, F, E, G, H
A, B, D, C, E, F, G, H
A, B, C, D, E, F, G, H
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?

x=1 e y=3
x=4 e y=6
x=7 e y=9
x=10 e y=12
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 ?

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:

II e III estão corretas
I e III estão corretas
Somente IV está correta
Somente II está correta
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.

Apenas a II
Apenas a III
I e II
II e III
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

Apenas I está correta
Apenas II está correta
Apenas III está correta
Todas estão corretas
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.

I e IV
II, somente.
II e IV.
IV, somente.
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?

Encontrar um caminho de comprimento máximo num grafo orientado
Encontrar um ciclo Hamiltoniano num grafo com n vértices e n arestas
O problema de caixeiro viajante com presença de arestas de peso negativo, sem ciclos negativos
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)
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.

Ideia original de: Luís Guilherme Cordiolli Russi

quinta-feira, 13 de junho de 2013

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?

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:

CAMINHO-MAIS-CURTO, TRILHA-DE-EULER e CLIQUE
CLIQUE, CICLO-HAMILTONIANO e CAMINHO-MAIS-CURTO
COBERTURA-POR-VÉRTICES, CICLO-HAMILTONIANO e CAMINHO-MAIS-LONGO
TRILHA-DE-EULER, CICLO-HAMILTONIANO e CAMINHO-MAIS-LONGO
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?

X_₁ = 1, X_₂ = 0, X_₃ = 0, X_₄ = 1
X_₁ = 1, X_₂ = 0, X_₃ = 1, X_₄ = 1
X_₁ = 1, X_₂ = 1, X_₃ = 0, X_₄ = 1
X_₁ = 1, X_₂ = 1, X_₃ = 1, X_₄ = 1
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.

Apenas uma afirmação está correta.
Apenas duas afirmações estão corretas.
Apenas três afirmações estão corretas.
Todas as afirmações estão corretas.
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?

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(x_i)
3 for i←1 to n/2 do
4 UNION(x_2i-1,x_2i)
5 UNION(1, 3)
6 UNION(6, 8)
7 UNION(5, 8)

B

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

C

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

D

1 for i←1 to n do
2 MAKE-SET(x_i)
3 for i←1 to n/2 do
4 UNION(x_2i-1,x_2i)
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.

Apenas I e III estão incorretas
Apenas II está correta
Apenas II e III estão corretas
Todas estão corretas
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:

Apenas os procedimentos I e II podem ser utilizados.
Apenas os procedimentos I e III podem ser utilizados.
Apenas os procedimentos II e III podem ser utilizados.
Todos os procedimentos podem ser utilizados.
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:

encontrar uma árvore espalhada mínima num grafo
encontrar um caminho de peso mínimo num grafo
encontrar um ciclo hamiltoniano num grafo
encontrar um passeio euleriano num grafo
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

Todas as alternativas são corretas
Apenas I e III são corretas
Apenas II e III são corretas
Apenas III é incorreta
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?

HAM-CYCLE ∈ NP e HAM-CYCLE ∈ NPC.
Se L ∈ P, então L ∈ NP.
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.
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.
NDA.

Ideia original de: Armando Faz Hernández

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-099

Enunciado: O grafo abaixo representa um fluxo entre a origma a e o destino f em uma rede de capacidade infinita para todas as arestas. Qual alternativa contém um par de vértices onde NENHUM respeita a propriedade de conservação do fluxo?

b, c
b, d
c, e
d, e
NDA

Ideia original de: Fabrício Matheus Gonçalves

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-098

Enunciado: Assinale a alternativa correta, sabendo que NPC significa NP-completo:

A classe NP contém apenas linguagens, enquanto que a classe NPC contém apenas problemas de otimização.
Seja A uma linguagem da classe NP e B uma linguagem da classe NPC. Se conseguirmos provar que A não pode ser decidida em tempo polinomial, então garantiremos que B também não pode.
Seja A uma linguagem em NPC e B uma linguagem qualquer. Se encontrarmos uma redução de tempo polinomial que transforma instâncias de A em instâncias de B, então provamos que B também está em NPC.
Seja P um problema de otimização. Considere as linguagens:
A = {<p,k> | p é uma instância de P com solução ≤ k}
B = {<p,k> | p é uma instância de P com solução ≥ k}
Então, A ∈ NPC implica em B ∈ NPC.
N.D.A

Ideia original de: Danielle Furtado dos Santos Dias

quarta-feira, 12 de junho de 2013

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-097

Enunciado: Dadas duas linguagens L₁, L₂ ⊆ {0,1}*, e dois algoritmos: A₁ que decide a linguagem L₁ e A₂ que decide a linguagem L₂, e denotando por T(X) a função que dá a complexidade de pior caso do algoritmo X, podemos afirmar que:

Se L₁ ≤p L₂, então T(A₁) = O(T(A₂))
Se L₁ ≤p L₂, então L₁ ∈ NP implica L₂ ∈ P
Se T(A₁) = Ω(T(A₂)) e A₂ roda em tempo polinomial então L₁ ≤p L₂
Se L₁ ∈ P e A₁ também decidir L₂, então L₂ ∈ NP
NDA

Ideia original de: Anderson Carlos Sousa e Santos

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-096

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?

(B, I), (A, H), (D, F)
(D, J), (B, H), (F, A)
(A, G), (H, C), (J, B)
(C, F), (G, E), (B, I)
N. D. A.

Ideia original de: Hilário Seibel Júnior

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-095

Enunciado: Baseado na seguinte matriz de adjacências, que representa um grafo bipartido, analise as seguintes afirmações e assinale a alternativa correta:

I) O emparelhamento máximo deste grafo tem cardinalidade igual a 5.
II) As arestas (E, L) e (D, I) fazem parte de um mesmo emparelhamento máximo.
III) Este grafo possui apenas 2 emparelhamentos máximos diferentes.

Somente uma das afirmações é verdadeira.
Apenas as afirmações I e II estão corretas.
Apenas as afirmações II e III estão corretas.
Todas as afirmações estão corretas.
NDA

Ideia original de: Anderson Coelho Weller

terça-feira, 11 de junho de 2013

MO417 - Questão para a prova oral

Número: 2013-094

Enunciado: Dadas as matrizes predecessoras gerada pela execução do algoritmo de Floyd-Warshall sobre um grafo orientado, indique qual o caminho mais curto com origem no vértice 3 e destino no vértice 1.

3→1
3→2→1
3→2→4→1
3→4→2→1
NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

domingo, 9 de junho de 2013

MO417 - Questão para a prova oral

Número: 2010-106

Enunciado: Suponha que foi provado que qualquer algoritmo que decide uma certa linguagem A roda em tempo Ω(n lg n), e suponha que conhecemos uma redução de A para a linguagem B que leva tempo O(n). Aqui n sempre se refere ao tamanho da entrada.

Podemos então afirmar que:

Certamente existe um algoritmo para decidir B que é o(n lg n).
Qualquer algoritmo que decide A certamente também decide B.
Se existir um algoritmo para decidir a linguagem B, certamente roda em tempo Ω(n lg n)
Se provarmos que qualquer algoritmo para decidir B roda em tempo Ω(n²), então qualquer algoritmo para decidir A também rodará em tempo Ω(n²).
NDA

Ideia original de: Pedro Henrique Del Bianco Hokama

MO417 - Questão para a prova oral

Número: 2010-105

Enunciado: Considere as seguintes afirmações sobre classes de complexidade:

NP-Completo ⊆ NP.
NP ⊆ NP-Completo.
P ⊆ NP-Completo.
P ⊆ NP.

Em junho de 2010, quantas das relações acima podiam ser afirmadas com certeza absoluta?

Ideia original de: Anderson Francisco Talon

MO417 - Questão para a prova oral

Número: 2009-168

Enunciado: Dadas as linguagens abaixo:

I - {<G,v,k> | G é um grafo orientado, v é um vértice de G e existe um caminho mínimo em G com pelo menos k arestas partindo de v}
II - {<G,k> | G é um grafo orientado e existe um caminho em G com pelo menos k arestas}
III - {<G> | G é um grafo orientado conexo e existe uma tour de Euler em G}
IV - {<G> | G é um grafo orientado com n vértices e existe um ciclo envolvendo no mínimo n-1 vértices de G}
V - {<F> | F é uma fórmula booleana em 2-CNF satisfatível}

Quais delas são NP-completas?

I, IV e V
II e IV
II e III
II, III e V
NDA

Ideia original de: José Vieira Maciel Borges

MO417 - Questão para a prova oral

Número: 2009-167

Enunciado: A notação A ≤ B entre linguagens significa que A reduz-se polinomialmente a B, ou seja, A é no máximo tão difícil quanto B, a menos de computações polinomiais. Além disso, a notação A ≤ C, onde C é uma classe, significa que A reduz-se polinomialmente a todas as linguagens em C. Uma definição análoga vale para C ≤ A.
Com base nessas definições, considere as seguintes afirmações:

I) Se A ≤ P e A ≤ B, então B ≤ P.
II) Se A ≤ B e B ≤ P, então A ≤ P.
III) Se A ≤ NP, B ≤ NPC e A puder ser decidida em tempo polinomial, então B também o será.

Escolha a opção correta sobre essas afirmações:

Apenas I é verdadeira.
Apenas II é verdadeira.
Apenas III é verdadeira.
I, II e III são verdadeiras.
NDA

Ideia original de: Fábio de Souza Azevedo

MO417 - Questão para a prova oral

Número: 2003-189

Enunciado: Assinale a alternativa que nao poderia representar uma relacao entre classes de problemas computacionais:

Ideia original de: Ivan Brunetto

MO417 - Questão para a prova oral

Número: 2003-186

Enunciado: Suponha que a linguagem A seja NP-difícil. Suponha também que, recentemente, descobriu-se que uma linguagem B, que é NP-completa, pode ser reduzida em tempo polinomial a A. Com base nestas duas informações, podemos afirmar que:

Qualquer linguagem NP-completa pode ser reduzida a A em tempo polinomial, logo, A também é NP-completa.
Qualquer linguagem NP-completa pode ser reduzida a A em tempo polinomial, logo, P = NP.
A será NP-completa somente se houver um algoritmo que a decida em tempo polinomial.
Pode haver linguagens NP-completas que não se reduzem a A em tempo polinomial.
NDA

Ideia original de: José Augusto Amgarten Quitzau

MO417 - Questão para a prova oral

Número: 2003-185

Enunciado: Sobre NP-Completude, qual a alternativa incorreta?

Uma linguagem NP-difícil pode ser também uma linguagem NP-completa.
A classe de complexidade co-NP é definida como o conjunto de linguagens cujo complemento é NP-completa.
Saber se P=NP é um problema em aberto, bem como saber se P = NP ∩ co-NP.
SAT é NP-completa.
NDA

Ideia original de: Augusto Jun Devegili

MO417 - Questão para a prova oral

Número: 2003-181

Enunciado: Assinale a alternativa CORRETA:

Se uma linguagem é NP-Difícil mas não está em NP, então esta linguagem é NP-Completa.
Se uma linguagem pertencente a NP puder ser reduzida a uma outra linguagem A em tempo polinomial, então A é NP-completa.
Se uma linguagem NP-difícil qualquer puder ser decidida em tempo polinomial, então TODAS as linguagens pertencentes a NP podem ser decididas em tempo polinomial.
Para mostrar que uma linguagem A é NP-Difícil, basta reduzir ALGUMA linguagem em NP, para A.
E) NDA

Ideia original de: Ricardo Luís Lachi

MO417 - Questão para a prova oral

Número: 2003-179

Enunciado: Com relação aos problemas NP-completos, assinale a alternativa INCORRETA:

A classe P consiste nos problemas que podem ser resolvidos em tempo polinomial.
A classe NP consiste nos problemas que são "verificáveis" em tempo polinomial.
Nem todo problema em P está em NP.
Um bom exemplo de problema NP-completo é determinar se um grafo orientado tem um ciclo hamiltoniano.
NDA.

Ideia original de: Eduardo Akira Yonekura

MO417 - Questão para a prova oral

Número: 2003-175

Enunciado: Dentre as alternativas abaixo assinale a INCORRETA a respeito de como se lidar com problemas NP-completos do ponto de vista prático:

Tentar encontrar um algoritmo que ache uma resposta, que pode não ser ótima, mas tem alguma garantia de ser próxima da solução ótima.
Tentar encontrar um algoritmo que funciona bem na média, mas não necessariamente para todos os casos (na prática o algoritmo atenderá muitos casos satisfatoriamente).
Verificar se não é possível restringi-lo (por exemplo, ao invés de considerar tanto grafos orientados quanto não orientados, restringe-se o problema a grafos orientados), de forma que uma solução para este problema restrito possa ser calculada em tempo polinomial.
Procurar uma redução do problema para um outro problema para o qual já se sabe calcular uma resposta em tempo polinomial.
NDA.

Ideia original de: Ricardo Luís Lachi

MO417 - Questão para a prova oral

Número: 2003-174

Enunciado: Relacione as propriedades abaixo aos problemas:

1 - Problemas de otimização
2 - Problemas de decisão

(   ) ordenação
(   ) caminho mais curto em grafos
(   ) caminho em grafos com no máximo k arestas
(   ) arvore espalhada minima
(   ) mochila 0-1
(   ) ciclo euleriano em grafos

1 2 2 1 2 1
1 1 1 2 1 2
1 1 2 1 1 2
2 1 2 1 1 2
NDA

Ideia original de: Ivan Brunetto

MO417 - Questão para a prova oral

Número: 2003-172

Enunciado: Sobre problemas NP-Completos é correto afirmar que:

Um problema que pode ser resolvido em tempo polinomial em um certo modelo de computação jamais pode ser resolvido em tempo polinomial em outro modelo.
Os problemas de decisão não permitem o uso de mecanismos da teoria de linguagens formais.
O adjetivo "NP-Completo" se aplica somente a problemas de otimização.
São problemas cuja complexidade é desconhecida.
N.D.A.

Ideia original de: Daniele Constant Guimarães

MO417 - Questão para a prova oral

Número: 2013-093

Enunciado: Dada a seguinte rede de fluxo G abaixo com origem s e destino t :

Assinale a alternativa correta:

Existe um único fluxo máximo
O fluxo máximo em G é 9
O fluxo máximo em G é 11
O fluxo máximo em G é 15
NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-092

Enunciado: Dadas as listas de adjacência abaixo para uma rede de fluxo entre s e t, quantas são as partições S e T que fornecem cortes de menor capacidade e qual o fluxo máximo? Considere o número entre parênteses como a capacidade da aresta que vai de um vértice até o seu adjacente.

s → a(10) → b(15) → f(7)

a → c(5)

b → d(6) → e(15)

c → f(7)

d → f(15)

e → d(9) → g(20)

f → t(10)

g → t(19)

1 corte mínimo; |fluxo máximo| = 27
1 corte mínimo; |fluxo máximo| = 25
2 cortes mínimos; |fluxo máximo| =27
3 cortes mínimos; |fluxo máximo| = 25
N.D.A.

Ideia original de: Paulo Henrique Hack de Jesus

MO417 - QUESTÃO PARA PROVA ORAL

Número: 2013-091

Enunciado: Na rede abaixo, considere o problema do fluxo máximo, onde o nó S é a origem e o nó T é o sorvedouro. Partindo do fluxo nulo, suponha que foi empurrada a maior quantidade possível de fluxo ao longo do caminho aumentante S → V3 → V2 → T e, logo após, também foi enviado o máximo fluxo possível ao longo do caminho aumentante S → V2 → V1 → T.

Marque a alternativa correta contendo capacidades de arestas no grafo residual neste momento.

c_f(S,V2) = 2, c_f(V2,S) = 5, c_f(V1,T) = 5, c_f(T,V3) = 10;
c_f(S,V3) = 7, c_f(V3,S) = 8, c_f(V2,T) = 2, c_f(T,V1) = 5;
c_f(V3,T) = 5, c_f(T,V2) = 8, c_f(V1,V2) = 5, c_f(S,V1) = 5;
c_f(V2,V1) = 0, c_f(V3,V2) = 0, c_f(V1,S) = 0, c_f(V2,V3) = 5;
NDA.

Ideia original de: Laurindo de Sousa Britto Neto

sábado, 8 de junho de 2013

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-090

Enunciado: Uma empresa tem sua fábrica (onde os produtos são produzidos) localizada na cidade S e seu centro de distribuição (onde os produtos são armazenados para serem distribuídos) localizado na cidade T. Segundo o grafo abaixo, que mostra as rodovias que conectam as diversas cidades (vértices) e o número máximo de caminhões que podem trafegar por cada rodovia (arestas e seus pesos), qual é o número máximo de caminhões que a empresa pode enviar para o seu centro de distribuição?

11
12
13
14
N.D.A.

Ideia original de: Tiago Pedroso da Cruz de Andrade

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-089

Enunciado: Dada a rede de fluxo abaixo com origem "s" e sorvedor "t", determine o valor do fluxo, o fluxo máximo e o corte s-t m[inimo, respectivamente.

a) 15 , 21 , ({s,a,b,c,d,e} {t})
b) 15 , 23 , ({a,b,c,d,e} {s,t})
c) 15 , 21 , ({s,a,b,c,d} {e,t})
d) 23 , 23 , ({s,a,b,c} {d,e,t})
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-088

Enunciado: Considere a rede de fluxo mostrada abaixo, onde todas as arestas são bidirecionais e seus pesos estão representados em Megabytes/segundo.

Deseja-se transmitir um arquivo de 10626 Megabytes do computador Origem até o servidor Destino. Supondo que as transmissões utilizam o fluxo máximo permitido pela rede, é correto afirmar que:

O arquivo todo será transmitido em 462 segundos.
O arquivo todo será transmitido em 483 segundos.
O arquivo todo será transmitido em 506 segundos.
Não é possível transmitir completamente o arquivo em menos de 10 minutos.
NDA

Ideia original de: Wallace Felipe Francisco Cardoso

MO417 - Questão para a prova oral

Número: 2013-087

Enunciado: Suponha que na cidade de Paulina existe uma fabrica de produtos eletrônicos que são distribuídos para cidades vizinhas por diferentes fornecedores. Cada fornecedor é representado por um arco no grafo G e sua capacidade de distribuição é dada pelo peso do arco.

O grafo G´ representa o projeto para a criação de um novo fornecedor entre as cidades de Piracibaca e Itu com uma capacidade de distribuição de 5 unidades.

De acordo com essas informações, e supondo que o total distribuído a São Paulo correponde ao valor do fluxo máximo desde Paulínia no grafo, avalie as seguintes afirmações e assinale a alternativa correta:

I. No projeto original (Grafo G), o número de unidades entregues em São Paulo é maior do que 7.

II. Com o novo fornecedor (Grafo G´), o número de unidades entregues em São Paulo passará a ser maior do que 7.

III. O número de unidades entregues em São Paulo não será afetado pelo novo fornecedor.

IV. A implementação do novo projeto só aumentaria em 2 unidades a quantidade de produtos entregues em São Paulo.

Somente I , II são corretas
Somente I, II, III são corretas
Somente II , III são corretas
Somente II, IV são corretas
NDA

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

sexta-feira, 7 de junho de 2013

MO417 - Questão para a prova oral

Número: 2013-086

Enunciado: Dado o seguinte grafo orientado com pesos nas arestas:

E o resultado de calcular os pesos dos caminhos mínimos de até 4 arestas entre todos os pares de vértices:

Quais são os valores da tabela que faltam?

U = 7, V = 2, W = 1, X = -4, Y = 3, Z = 6
U = 7, V = 5, W = -3, X = -2, Y = 6, Z = -4
U = -7, V = -4, W = -4, X = -1, Y = -6, Z = 4
U = 7, V = 4, W = 4, X = 1, Y = 6, Z = -4
NDA.

Ideia original de: Carlos Eduardo Alfaro Morales

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-085

Enunciado: Qual a diferença entre o custo da árvore espalhada mínima e o custo total das arestas da árvore de caminhos mínimos a partir do vértice A até todos os outros vértices do grafo abaixo?

Ideia original de: Fabrício Matheus Gonçalves

MO417 - Questão para a prova oral

Número: 2013-084

Enunciado: Marque a alternativa correta para o grafo abaixo.

O “menor custo” entre o vértice B e o vértice F é 4.
O “menor custo” entre o vértice B e o vértice E é 6.
O “menor custo” entre o vértice A e o vértice F é 7.
O “menor custo” entre o vértice A e o vértice E é 7.
N.D.A.

Ideia original de: Erick Aguiar Donato

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-083

Enunciado: Em um famoso título de video game, o herói deve percorrer um reinado para salvar sua princesa, presa em um castelo. Para expressar o progresso da personagem durante a aventura, é disponibilizado um mapa semelhante ao da figura abaixo, mas com uma extensão maior. Nele, cada ponto indicado com uma "moeda" é uma fase, e o herói avança pelos caminhos a partir do ponto inicial (START), podendo escolher uma próxima fase sempre que vencer a atual.

Sabendo que todas as fases têm a mesma dificuldade e duram praticamente o mesmo tempo, um garoto deseja terminar o jogo da forma mais rápida possível, para que ainda lhe sobre tempo para estudar.

Nesta situação, as seguintes estratégias foram consideradas para planejar a mínima sequência de fases que se precisa jogar, do ponto inicial (START) até o castelo:
I) Aplicar busca em largura a partir do ponto inicial.
II) Aplicar busca em profundidade a partir do ponto inicial.
III) Aplicar o algoritmo de Prim a partir do ponto inicial.
IV) Aplicar o algoritmo de Dijkstra a partir do ponto inicial.

Escolha a alternativa que lista TODAS as estratégias que podem ser usadas, individualmente, com sucesso, na resolução do problema:

I, II, III, IV.
Apenas I, II e IV.
Apenas I, III e IV.
Apenas I e IV.
N.D.A.

Ideia original de: Daniel Henriques Moreira

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-082

Enunciado: A matriz de peso abaixo, representa o grafo G=( V, E) acíclico orientado ponderado. Em cada célula dessa matriz, representada pela linha u e coluna v, é armazenado o peso w da aresta (u,v). Um peso infinito (∞) significa que (u,v) ∉ E.

\	_R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

Denotamos por δ(u, v) o caminho mais curto a partir do vértice u até o vértice v no grafo. Assinale a alternativa correta:

δ( R, S) = 1
δ( R, U) = 1
δ( R, V) = -2
δ( T, V) = 0
NDA

Ideia original de: Ademar Takeo Akabane

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-081

Enunciado: O mapa abaixo apresenta uma parte do Backbone de Internet no Brasil e ao lado é apresentada a lista de adjacências entre os roteadores, com os seus respectivos custos de envio em um determinado momento.
Assumindo que roteamento dos dados é feito apenas através do protocolo OSPF (Open Shortest Path First), que é uma implementação do algoritmo de Dijkstra, qual seria o caminho percorrido pelos dados enviados do Rio Grande do Sul (RS) para a Bahia (BA)?

RS, PR, SP, MG, BA
RS, PR, SP, RJ, ES, BA
RS, SC, SP, RJ, DF, MG, BA
RS, SC, SP, MG, DF, RJ, ES, BA
NDA

Ideia original de: Anderson Coelho Weller

MO417 - Questão para a prova oral

Número: 2013-080

Enunciado: Um professor de Complexidade de Algoritmos pediu para os alunos construírem caminhos mínimos a partir de um vértice de origem s até todos os outros vértices do grafo, mas adicionou a seguinte restrição: "Caso haja mais de um caminho mínimo (com mesmo peso total) do vértice de origem até um certo vértice v, deve-se optar por um caminho mínimo contendo o menor número de arestas". Um dos alunos decidiu simplesmente executar o algoritmo de Dijkstra, sem nenhuma adaptação, mantendo inclusive a função de relaxamento original, mostrada a seguir:

RELAX (u, v, w)
if v.d > u.d + w(u,v)
v.d = u.d + w(u,v)
v.π = u

Para quais valores de a, b, c, d e e no grafo abaixo o aluno encontraria o resultado esperado pelo professor (partindo do vértice 1)?

a = 4, b = 7, c = 2, d = 1, e = 2.
a = 4, b = 7, c = 4, d = 3, e = 2.
a = 7, b = 4, c = 1, d = 1, e = 3.
a = 7, b = 5, c = 2, d = 1, e = 1.
N. D. A.

Ideia original de: Hilário Seibel Júnior

quinta-feira, 6 de junho de 2013

MO417 - Questão para a prova oral

Número: 2010-104

Enunciado: O algoritmo de Johnson computa as distâncias mínimas (os custos dos menores caminhos) entre quaisquer pares de vértices de um grafo. Se o grafo possui ciclos negativos, não há caminhos mínimos definidos para determinados pares de vértices e o algoritmo retorna esta informação. Caso contrário, tais distâncias são calculadas empregando algoritmos eficientes. Para tal, um procedimento inicial modifica os pesos das arestas do grafo para que elas tenham valores não-negativos.
Sejam u e v um par de vértices do grafo passado como entrada. Para um caminho P entre eles, denote por W(P) seu custo no grafo original e por W'(P) seu custo quando se emprega a nova função de custo. Considere as afirmações a seguir:

Para dois caminhos P e Q entre u e v, W(P) - W(Q) = W'(P) - W'(Q)
Se W(P) é não negativo, então W(P) = W'(P)
Se W(P) é não positivo, então W'(P) ≥ 0
Se W(P) > 0 então W'(P) > 0

Quantas destas afirmações estão corretas?

Ideia original de: Daniel Cason

MO417 - Questão para a prova oral

Número: 2010-102

Enunciado: No problema de fluxo máximo, considere um fluxo de rede G = (V, E) sendo o grafo orientado ilustrado abaixo, em que cada aresta (u,v) ∈ E tem uma capacidade não negativa c(u,v) ≥ 0. O vértice s é a origem e o vértice t é o sorvedouro.

Um corte (S,T) de fluxo de rede G = (V, E) é uma partição de V em S e T = V - S tal que s ∈ S e t ∈ T. Um corte mínimo de uma rede é um corte cuja capacidade é mínima dentre todos os cortes da rede. Qual das alternativas abaixo representa um corte mínimo em G? Em cada caso, defina T = V - S.

S = { s, v1, v2, v3 }
S = { s, v1, v2, v4 }
S = { s, v1, v2, v3, v4 }
S = { s, v1, v2, v3, v4, v6 }
NDA

Ideia original de: Maikon Cismoski dos Santos

MO417 - Questão para a prova oral

Número: 2010-099

Enunciado: Observe a figura a seguir que representa três cortes distintos em uma rede de fluxo de s a t. Os cortes são representados pelos segmentos de reta A, B e C. Em cada caso, os vértices à esquerda e à direita do segmento formam os dois conjuntos do corte.

Marque a alternativa incorreta.

A capacidade do corte A é 29 = 16 + 13.
A capacidade do corte B é 17 = 12 + 14 - 9.
A capacidade do corte C é 24 = 20 + 4.
O fluxo líquido pelo corte B é 19 = 12 + 11 - 4.
NDA

Ideia original de: Anderson Francisco Talon

MO417 - Questão para a prova oral

Número: 2010-097

Enunciado: Dada a rede de fluxo a seguir, com os valores dos fluxos (se existirem) e das capacidades apresentados em cada aresta, considere o corte (S, T), onde S = {s, v₁, v₂} e T = {v₃, v₄, t}. Qual das alternativas apresenta os valores correspondentes ao fluxo por esse corte e à capacidade do corte, respectivamente?

13 e 25
19 e 25
18 e 28
23 e 28
NDA

Ideia original de: Priscila Tiemi Maeda Saito

MO417 - Questão para a prova oral

Número: 2010-096

Enunciado: A empresa Belo Leite S/A tem um rebanho de gado leiteiro capaz de produzir 1000 litros de leite por dia (s). Este leite é enviado às unidades processadoras (v1, v2 e v3), em seguida, às unidades distribuidoras (v4 e v5), e a partir daí, para a central de vendas dos produtos Belo Leite (t). A produção, hoje em dia, está abaixo da capacidade, pois a diretoria da empresa teme o desperdício de matéria-prima. Através da análise da rede de fluxo abaixo, onde cada aresta está rotulada com "fluxo/capacidade", o que você poderia afirmar sobre o aumento da produção da empresa:

Não há como aumentar a produção, uma vez que a aresta s a v2 já está saturada.

A produção pode ser aumentada em 300 litros, a soma das capacidades residuais de v4 a t e de v5 a t.

A produção pode ser aumentada em 80 litros enviados de s a v1 e em 130 litros enviados de s a v3, ajustando os fluxos através das demais arestas de v1 e v3 até t.

A produção pode ser aumentada em 250 litros, sendo 150 litros a mais entre s e v3 e de 100 litros a mais entre s e v1, com ajuste das demais arestas até t.

Ideia original de: Juliana Galvani Greghi

MO417 - Questão para a prova oral

Número: 2009-158

Enunciado: Sobre o algoritmo de Edmonds-Karp para fluxos máximos em redes de fluxo, é INCORRETO afirmar que:

É idêntico ao algoritmo básico de Ford-Fulkerson, exceto pela forma como encontra os caminhos aumentantes;
Ao contrário do algoritmo básico de Ford-Fulkerson, não pode ser usado para emparelhamentos bipartidos máximos;
Ele sempre seleciona o próximo caminho aumentante dentre os caminhos que possuem capacidade residual e número mínimo de arestas;
Sua complexidade para grafos densos é O(V⁵)
NDA

Ideia original de: Fernando José Vieira da Silva

MO417 - Questão para a prova oral

Número: 2009-156

Enunciado: Dado um grafo não-orientado G = (V, E), com V = {v₁, v₂, v₃, v₄, v₅, v₆} e E = {e₁, e₂, e₃, e₄, e₅, e₆}, onde e₁ = (v₁, v₄), e₂ = (v₁, v₅), e₃ = (v₂, v₅), e₄ = (v₂, v₆), e₅ = (v₃, v₆), e₆ = (v₃, v₄), qual dos seguintes subconjutos de E é um emparelhamento?

{e₁, e₃, e₆}
{e₁, e₄, e₅}
{e₂, e₃, e₅}
{e₂, e₄, e₆}
NDA

Ideia original de: Milton Aparecido Soares Junior

MO417 - Questão para a prova oral

Número: 2009-155

Enunciado: Abaixo é apresentada uma rede de fluxo G = (V,E) com suas respectivas capacidades e fluxos nas arestas, fazendo uso da notação "fluxo/capacidade", ou apenas "capacidade" quando não há fluxo. Faz-se, então, um corte ({s, v3, v4}, {v1, v2, t}) na rede de fluxo dada. O fluxo através do corte e sua capacidade são, respectivamente:

23 e 31
23 e 50
31 e 31
31 e 50
NDA

Ideia original de: Jonathas Campi Costa

MO417 - Questão para a prova oral

Número: 2009-154

Enunciado: Considere a imagem abaixo

A intenção da figura é representar um fluxo numa rede de capacidade infinita para todas as arestas. Entretanto, nota-se que o vértice v3 não está obedecendo a propriedade da conservação do fluxo. Dadas as sugestões para tornar a figura acima um fluxo válido, assinale a alternativa que compreende todas as que funcionam.

I - f(v4, v3) = 7; f(v4, t) = 4
II - f(v4, v3) = 7; f(v3, t) = 14
III - f(v3, t) = 14

I e II
I e III
I, II e III
II e III
NDA

Ideia original de: José Vieira Maciel Borges

MO417 - Questão para a prova oral

Número: 2003-162

Enunciado: Uma rede de fluxo pode modelar diversos problemas encontrados na vida real, às vezes com algumas adaptações. Suponha que desejamos modelar o seguinte problema. Uma fábrica (origem) produz pães e deve transportá-los para um distribuidor (destino). No entanto, a capacidade de produção da fábrica é limitada e pode ser inferior ao fluxo de valor máximo proporcionado pela rede de transporte.
Dado um grafo G=(V,E) representando a rede de transporte entre a fábrica (s) e o distribuidor (t), como podemos modificar G, resultando numa nova rede G', de modo o fluxo de valor máximo em G' não ultrapasse a limitação p de produção da fábrica?

A) Acrescenta-se uma aresta (s,t) com capacidade c(s,t) = p.
B) Para todas as arestas (i,j) de G tais que c(i,j) > p, modifica-se c(i,j) = p em G'.
C) Cria-se um novo vétice s' que será a nova origem e uma aresta (s',s) com capacidade c(s',s) = p.
D) Para qualquer aresta (s, i), define-se c(s,i) = p em G'.
E) NDA

Ideia original de: André Santanchè

quarta-feira, 5 de junho de 2013

MO417 - Questão para a prova oral

Número: 2010-093

Enunciado: Considere o grafo orientado ponderado a seguir. Qual das alternativas é falsa, dado que o algoritmo de Dijkstra foi usado para calcular os caminhos mínimos com origem em A, usando o algoritmo de relaxação abaixo, onde "d" é a estimativa de distância mantida pelo algoritmo, "w" dá os pesos das arestas, e "pai" indica o predecessor de cada vértice?

RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2    then d[v] ← d[u] + w(u, v)
3         pai[v] ← u

O caminho mínimo de A até I passa por B
O caminho mínimo de A até G passa por F
O predecessor de E é C
G não é predecessor de nenhum vértice
NDA

Ideia original de: Greice Martins de Freitas

MO417 - Questão para a prova oral

Número: 2010-090

Enunciado: Dado o grafo orientado ponderado G = (V,E) a seguir, assinale a alternativa INCORRETA.

Se x = 4 e y = 7, então o caminho mínimo entre o vértice A e D é: A, B, C e D.
Se x ≥ 0, y ≥ 0 e x ≥ y, então o caminho mínimo entre o vértice A e D é: A, B, E e D.
Suponha que o peso da aresta (A,E) seja reduzido para 1 e que y ≥ 0 e x ≥ 7, então o caminho mínimo entre o vértice A e D será: A, E e D.
Se x ≥ y + 3, então o caminho mínimo entre o vértice B e D será: B, E e D.
NDA.

Ideia original de: Thiago Augusto Lopes Genez

MO417 - Questão para a prova oral

Número: 2010-089

Enunciado: Considere o grafo G abaixo:

Em qual das alternativas estão todas as arestas que pertencem à árvore de caminhos mínimos com origem no vértice a? Suponha que a árvore é construída relaxando-se todas as arestas saindo de cada vértice, sendo os vértices tomados numa ordem topológica de G.

(a,c) (a,b) (a,e) (b,d) (d,f).
(a,c) (a,b) (a,e) (b,f) (c,d).
(a,c) (a,e) (e,b) (b,d) (d,f).
(a,c) (a,e) (e,b) (b,f) (c,d).
NDA

Ideia original de: Fábio Augusto Faria

MO417 - Questão para a prova oral

Número: 2010-088

Enunciado: Considere os algoritmos de Bellman-Ford, Caminhos Mínimos para Grafos Acíclicos Direcionados (utilizando ordenação topológica) e o de Dijkstra. Considere também dois tipos de grafos direcionados, conforme listados abaixo:

G₁: acíclico, contendo somente arestas negativas.
G₂: contém apenas arestas positivas e pelo menos um ciclo.

Desejamos agora passar G₁ e G₂ como entrada para cada um dos algoritmos citados acima, com o intuito de resolver o problema de encontrar todos os caminhos mínimos entre um dado vértice de origem e todos os outros vértices. Quantos desses algoritmos irão resolver corretamente esse problema, para cada um dos respectivos grafos?

1, 1.
1, 2.
2, 1.
2, 2.
NDA

Ideia original de: Marcos Vinícius Mussel Cirne

MO417 - Questão para a prova oral

Número: 2010-087

Enunciado: Considere o grafo G = (V, E) acíclico orientado ponderado representado pela matriz de pesos abaixo. Armazenamos na linha u e coluna v o peso w da aresta (u,v). Quando (u,v) ∉ E, temos w = ∞ na matriz.

	A	B	C	D	E
A	∞	1	-2	∞	-3
B	∞	∞	3	-2	∞
C	∞	∞	∞	-2	-2
D	∞	∞	∞	∞	-1
E	∞	∞	∞	∞	∞

Denotando por δ(u, v) a distância entre u e v no grafo, qual das alternativas abaixo está incorreta?

δ(A, C) = -2
δ(B, D) = -2
δ(C, E) = -3
δ(A, E) = -4
NDA

Ideia original de: Maikon Cismoski dos Santos

MO417 - Questão para a prova oral

Número: 2010-086

Enunciado: Considere o algoritmo de Dijkstra para resolver o problema de caminhos mínimos de origem s no grafo G=(V,E) apresentado abaixo. Assinale a alternativa que apresenta a seqüência em que os vértices do grafo são retirados da fila de prioridade mínima utilizada pelo algoritmo.

{s, d, a, b, c}
{s, d, a, c, b}
{s, d, c, b, a}
{s, d, c, a, b}
NDA

Ideia original de: Priscila Tiemi Maeda Saito

MO417 - Questão para a prova oral

Número: 2010-084

Enunciado: Observe o grafo orientado ponderado a seguir e assinale a alternativa correta.

Não haverá ciclos negativos se x + y ≥ 0.
Haverá ciclos negativos se w + x + z < 0.
Não haverá ciclos negativos se w + z ≥ x ≥ -y.
Haverá ciclos negativos se w < 0, z < 0 e x < 0
NDA.

Ideia original de: Thiago Augusto Lopes Genez

MO417 - Questão para a prova oral

Número: 2010-083

Enunciado: Seja G=(V, E, w) um grafo orientado e ponderado, sendo w a função que associa um peso a cada aresta. Denote por δ(u,v) a distância, isto é, o peso de um caminho de peso mínimo entre u e v, se houver, ou ∞ caso contrário, Suponha que G é inicializado com d[v] ← ∞ e π[v] ← NIL para todos os vértices, a seguir fazemos d[s] ← 0, e que o único meio pelo qual d e o subgrafo de predecessores são mudados é através de alguma sequência de passos de relaxamento, usando a rotina RELAX abaixo. Com relação às propriedades de caminhos mínimos e relaxamento, qual das alternativas é INCORRETA:

RELAX(u, v, w)
    if d[v] > d[u] + w(u,v) then
        d[v] ← d[u] + w(u,v)
        π[v] ← u

Para todo (u,v) ∈ E, temos δ(s,v) < δ(s,u) + w(u,v)
d[v] ≥ δ(s,v), para todo v ∈ V
Se não existe caminho de s até v, então d[v] = δ(s,v) = ∞
Quando d[v] = δ(s,v) para todo v ∈ V, o subgrafo de predecessores é uma árvore de caminhos mínimos com raiz em s.
NDA

Ideia original de: Alexandre Toshio Hirata

MO417 - Questão para a prova oral

Número: 2010-082

Enunciado: Seja G = (V, E) um grafo com pesos nas arestas. Considere as seguintes afirmações:

I. Seja M uma árvore geradora mínima de G. O caminho mínimo em M entre qualquer par de vértices s e t é também um caminho mínimo em G.
II. Seja P um caminho mínimo entre dois vértices s e t de G. Se incrementarmos os pesos de cada aresta de G em uma unidade, P continuará sendo um caminho mínimo de s a t.
III. Na execução do algoritmo de Bellman-Ford, após relaxar |V| - 1 vezes todas as arestas de G, ele verifica se existe um ciclo negativo em G em tempo O(|V|).

Assinale a alternativa correta:

Apenas as afirmações I e II são falsas.
Apenas as afirmações I e III são falsas.
Apenas as afirmações II e III são falsas.
Todas as afirmações são falsas.
NDA

Ideia original de: Marcos Vinícius Mussel Cirne

MO417 - Questão para a prova oral

Número: 2010-081

Enunciado: No algoritmo de Bellman-Ford, uma rodada de relaxações em todas as arestas é executada exatamente V-1 vezes, onde V é o número de arestas no grafo. Considere um algoritmo que execute apenas n rodadas de relaxação, para n < V-1. O que pode-se dizer sobre ele?

Que qualquer distância envolvendo um número de arestas menor ou igual a n será corretamente calculada.
Que qualquer caminho mínimo de peso menor ou igual a n será encontrado.
Que qualquer caminho mínimo envolvendo um número de arestas menor ou igual a n será encontrado.
Que, se na última rodada (a de número n) ainda ocorreram atualizações, então há um ciclo negativo que envolve até n arestas.
NDA

Ideia original de: Alexandre Tachard Passos

MO417 - Questão para a prova oral

Número: 2010-080

Enunciado: Seja G = (V, E, ω), um grafo orientado ponderado, onde ω é uma função que associa um peso a cada aresta do grafo. Considere o seguinte algoritmo para determinar caminhos mínimos de fonte única s em G:

Construa G' = (V, E, ω'), onde ω' (uv) = ω (uv) + |min(0,W)| para toda aresta uv de E, sendo W = min_{uv ∈ E} ω (uv).
Rode o algoritmo de Dijkstra para caminhos mínimos de fonte única em G' com origem s, obtendo caminhos mínimos P(s,u) e distâncias δ' (s,v) para todo v ∈ V.
Retorne δ (s,v) = δ' (s,v) - |P(s,v)|.|min(0,W)|, onde |P(s,v)| é o número de arestas do caminho P(s,v).

Sobre este algoritmo, é possível afirmar que:

A complexidade do algoritmo acima é O(|V|.|E|).
Cada caminho P(s,v) é um caminho entre s e v em G com custo δ (s,v), porém este caminho poderá não ser mínimo, mesmo que G não possua ciclos negativos.
Para qualquer grafo G, o valor δ (s,v) é o peso de um caminho mínimo entre s e v.
Se o grafo G possui ciclos negativos, G' também terá ciclos negativos.
NDA

Ideia original de: Daniel Cason

\	_R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

	A	B	C	D	E
A	∞	1	-2	∞	-3
B	∞	∞	3	-2	∞
C	∞	∞	∞	-2	-2
D	∞	∞	∞	∞	-1
E	∞	∞	∞	∞	∞

\	_R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

	A	B	C	D	E
A	∞	1	-2	∞	-3
B	∞	∞	3	-2	∞
C	∞	∞	∞	-2	-2
D	∞	∞	∞	∞	-1
E	∞	∞	∞	∞	∞

\	_R	S	T	U	V
R	∞	1	2	∞	-1
S	∞	∞	∞	-3	-1
T	∞	-2	∞	-1	∞
U	∞	∞	∞	∞	1
V	∞	∞	∞	∞	∞

	A	B	C	D	E
A	∞	1	-2	∞	-3
B	∞	∞	3	-2	∞
C	∞	∞	∞	-2	-2
D	∞	∞	∞	∞	-1
E	∞	∞	∞	∞	∞