jul

MO417 - Questão para a prova oral

MO417 - Questão para a prova oral

Número:

Enunciado: Suponha que exista uma empresa de engenharia eletrônica que está muito preocupada com possíveis plágios do design de seus componentes eletrônicos.

Ela pretende iniciar um processo penal contra uma outra empresa, mas precisa de evidências do plágio. Portanto, ela decidiu contratar você para desenvolver algoritmos que lhe dê certeza disso.

Para isso, é necessário que os algoritmos resolvam os seguintes problemas, relacionados a dois designs eletrônicos (A) e (B):

• Determinar se o design (A) está ou não contido dentro do design (B).
  
• Determinar qual é o maior sub-design de (B) equivalente ao design (A).

Obs.: Os engenheiros da empresa lhe alertam sobre a possibilidade de que as peças eletrônicas podem estar distribuídas espacialmente de forma diferente em cada um dos designs.

De acordo com essas informações, assinale a alternativa correta: 

1. Os dois problemas podem ser resolvidos em tempo polinomial, se pelo menos um deles pode ser resolvido em tempo polinomial.
2. Apenas o primeiro problema pode ser resolvido em tempo polinomial.
3. Apenas o segundo problema pode ser resolvido em tempo polinomial.
4. Os dois problemas não tem solução.  
5. NDA 

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