Lucas Peres
Quiz by , created more than 1 year ago

Quiz referente a problemas polinomiais e o problema da mochila.

30
0
0
Lucas Peres
Created by Lucas Peres over 8 years ago
Close

Knapsack Problem

Knapsack Problem

Question 1 of 7

1

Um problema é polinomial se:

Select one of the following:

  • Um algoritmo resolve problemas de polinômios

  • Um algoritmo resolve problemas em um tempo dado por um polinômio

  • Um algoritmo resolve problemas em um limite de tempo no melhor caso dado por um polinômio

  • Um algoritmo resolve problemas em um limite de tempo no pior caso dado por um polinômio

Explanation

Question 2 of 7

1

O conjunto P é o conjunto de todos os problemas polinomiais possíveis.

Select one of the following:

  • True
  • False

Explanation

Question 3 of 7

1

Um problema é NP-Completo se for:

Select one of the following:

  • NP e P ao mesmo tempo

  • NP e somente com verificação polinomial(completamente polinomial)

  • NP-difícil e P ao mesmo tempo

  • NP-difícil e NP ao mesmo tempo

Explanation

Question 4 of 7

1

Qual destas complexidades é polinomial?

Select one of the following:

  • 2^n

  • n^2 + n

  • n^n

  • n^2 + 3^n

Explanation

Question 5 of 7

1

Como se prova que um NP é um NP-Completo:

Select one of the following:

  • Redução Polinomial a partir de outro problema conhecido como NP-C.

  • Por métodos matemáticos avançados.

  • Redução Polinomial a partir de outro problema conhecido como NP.

  • Não é possivel provar.

Explanation

Question 6 of 7

1

O problema da mochila pertence a qual ou quais tipo(s) de problema?

Select one or more of the following:

  • P

  • NP

  • NP-C

  • BC

Explanation

Question 7 of 7

1

O problema da mochila é único e pertence somente aos problemas NP-C.

Select one of the following:

  • True
  • False

Explanation

Previous
Next