Quiz 3-Coloring e NP-Completo

danillo-fr
Quiz by danillo-fr, updated more than 1 year ago
danillo-fr
Created by danillo-fr about 6 years ago
99
0

Description

Questionário para testar o conhecimento adquirido sobre a classe de problemas NP-Completo e o problema 3-Coloring

Resource summary

Question 1

Question
A coloração de mapas também é um problema da classe NP-Completo. A representação de mapas pode ser através de grafos planares, sendo os vértices os países ou estados e as arestas a ligação entre eles. Uma das principais regras é que um grafo do tipo mapa não pode ter cruzamento de arestas. Desta forma, qual é o número mínimo de cores para colorir o mapa do Brasil, de forma que nenhum estado vizinho tenha uma cor igual?
Answer
  • 2 cores
  • 3 cores
  • 4 cores
  • 5 cores

Question 2

Question
Para que um problema seja da classe NP-Completo, as seguintes características devem ser respeitadas: 1) Estar em NP; 2) Para toda linguagem A ∈ NP, A é redutível a L, onde L é o problema que desejamos provar ser NP-c. Esta afirmação está correta?
Answer
  • True
  • False

Question 3

Question
Quais são as duas classes que mais são proeminentes, ou seja, que mais se destacam na Teoria da Complexidade?
Answer
  • Classes P e NP
  • Classes P e NP-C
  • Classes P e Co-NP
  • Classes NP-C e Co-NP

Question 4

Question
"A classe NP-Completo aborda problemas considerados mais difíceis dos contidos em NP" Esta afirmação está correta?
Answer
  • True
  • False

Question 5

Question
O problema 3-Coloring:
Answer
  • É um problema da classe NP-completo cujo objetivo é, dado um grafo G(V,E), verificar se um grafo é colorível com 3 cores diferentes de modo que não haja vértices adjacentes com as mesmas cores.
  • É um problema da classe NP-completo cujo objetivo é, dado um grafo G(V,E), colorir as arestas com 3 cores diferentes de modo que não haja arestas cruzando entre si.
  • É um problema da classe NP-completo cujo objetivo é, dado um grafo G(V,E), colorir 3 vértices e 3 arestas com 3 cores diferentes de modo que não haja vértices e arestas das mesmas cores.
  • É um problema da classe NP-completo cujo objetivo é, dado um grafo G(V,E), colorir os vértices com 3 cores diferentes de modo que duas ou mais arestas não estejam saindo de um mesmo vértice.

Question 6

Question
Para provar que o problema 3-Coloring pertence à classe de problemas NP-Completo, foi realizado a redução do problema, que é uma das condições exigidas. Para qual dos problemas abaixo o problema 3-Coloring foi reduzido?
Answer
  • Problema SAT
  • Problema do Caixeiro Viajante
  • Problema 3-SAT
  • Problema Not-All-Equal 3-SAT

Question 7

Question
"Os problemas da classe P são problemas que são decidíveis em tempo polinomial, enquanto que os problemas da classe NP são problemas em que a solução pode ser verificada em um tempo polinomial." Essa afirmação está correta?
Answer
  • True
  • False

Question 8

Question
O professor da Universidade de Londres, Augustus De Morgan, foi o primeiro matemático a receber a conjectura de que "é possível colorir todo e qualquer mapa com 4 cores". À partir dessa conjectura, surge o "Teorema das Quatros Cores".
Answer
  • True
  • False
Show full summary Hide full summary

Similar

Romeo and Juliet essay
Tambo234
GCSE Chemistry C2 topic notes
imogen.shiels
Cell Organelles and Functions
Melinda Colby
Of Mice and Men - Themes
Hafsa A
Input Devices
Jess Peason
An Inspector Calls: Mrs Sybil Birling
Rattan Bhorjee
Of Mice and Men Characters - Key essay points
Lilac Potato
Physics 1A - Energy
Zaki Rizvi
Maths GCSE - What to revise!
livvy_hurrell
New GCSE history content
Sarah Egan
Specific Topic 7.2 Timber
T Andrews