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

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

MO417 - 1ª QUESTÃO PARA A PROVA ORAL

Número:
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 mínimo s-t, 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 - 2ª QUESTÃO PARA A PROVA ORAL

Número:
Enunciado: Sobre o método de Ford-Fulkerson e suas implementações podemos afirmar:

I) Em uma rede de fluxo, um corte (S,T) é definido como um corte em que a origem "s" e o sorvedor "t" encontram-se em conjuntos diferentes.
II) Em uma rede de fluxo, o fluxo máximo com origem "s" e sorvedor "t" é igual a capacidade do corte máximo (S,T)
III) O algoritmo de Edmonds-Karp tem complexidade O(VE²), pois utiliza a busca em largura O(VE) para calcular caminhos aumentantes.
IV) Em uma rede de fluxo G com origem "s" e sorvedor "t", se existe um caminho de "s" até "t" sobre a rede residual Gf então o fluxo em G não é máximo.

a) I, III e IV são verdadeiras
b) II e III são verdadeiras
c) III e IV são verdadeiras
d) I e IV são verdadeiras
e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considerando os algoritmos de Bellman-Ford, Dag-Shortest-Paths ou Dijkstra, analise os grafos abaixo e indique quais destes algoritmos podem ser utilizados para encontrar um caminho mais curto a partir do vértice s.

 Grafo 1:

Grafo 2:

Grafo 3:

a) Grafo 1: Dijkstra e Dag-Shortest-Paths. Grafo 2: Bellman-Ford e Dijkstra. Grafo 3: Dag-Shortest-Paths e Bellman-Ford

b) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

c) Grafo 1: Nenhum dos algoritmos. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford e Dijkstra

d) Grafo 1: Bellman-Ford. Grafo 2: Bellman-Ford e Dag-Shortest-Paths. Grafo 3: Bellman-Ford, Dag-Shortest-Paths e Dijkstra

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417-QUESTÃO PARA A PROVA ORAL -1ª QUESTÃO

Número:

Enunciado: Quais das arestas devem ser removidas do grafo abaixo para que seja possível obter uma ordenação topológica?

a) 9 e 3

b) 8 e 5

c) 1 e 10

d) 9 e 1

e) NDA

Ideia original de: Lucas Oliveira Batista

MO417 - QUESTÃO PARA A PROVA ORAL - 2ª QUESTÃO

Número:

Enunciado: Marque a alternativa que NÃO corresponde a uma possível “breadth-first tree”, construída pela busca em largura com origem no vértice 1 sobre o grafo abaixo:

a)                                                                                b)

                                              

                

 c)                                                                              d)

e) NDA

Ideia original de: Lucas Oliveira Batista