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