¡GoConqr estrena diseño! Cuéntanos qué te parece.

Regístrate gratis

Test

Quiz 3-Coloring e NP-Completo

danillo-fr 8 preguntas

Hacer el test

Preguntas del test (8)

  1. 1A 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?Imagen de la pregunta 1
    1. A2 cores
    2. B3 cores
    3. C4 cores
    4. D5 cores
  2. 2Para 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?
    1. AVerdadero
    2. BFalso
  3. 3Quais são as duas classes que mais são proeminentes, ou seja, que mais se destacam na Teoria da Complexidade?Imagen de la pregunta 3
    1. AClasses P e NP
    2. BClasses P e NP-C
    3. CClasses P e Co-NP
    4. DClasses NP-C e Co-NP
  4. 4"A classe NP-Completo aborda problemas considerados mais difíceis dos contidos em NP"

    Esta afirmação está correta?
    1. AVerdadero
    2. BFalso
  5. 5O problema 3-Coloring:Imagen de la pregunta 5
    1. AÉ 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.
    2. BÉ 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.
    3. CÉ 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.
    4. DÉ 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.
  6. 6Para 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?
    1. AProblema SAT
    2. BProblema do Caixeiro Viajante
    3. CProblema 3-SAT
    4. DProblema Not-All-Equal 3-SAT
  7. 7"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?
    1. AVerdadero
    2. BFalso
  8. 8O 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".
    1. AVerdadero
    2. BFalso

Información

Descripción
Questionário para testar o conhecimento adquirido sobre a classe de problemas NP-Completo e o problema 3-Coloring
Idioma
Português
Visitas
191
Valoración
Aún sin valoraciones
Valora este test
Valora este test

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué te parece el nuevo diseño?

¿Te gusta?