GoConqr hat ein neues Design! Sag uns, wie es dir gefällt.

Kostenlos registrieren

Quiz

Quiz 3-Coloring e NP-Completo

danillo-fr 8 Fragen

Quiz starten

Fragen in diesem Quiz (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?Bild zu Frage 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. ARichtig
    2. BFalsch
  3. 3Quais são as duas classes que mais são proeminentes, ou seja, que mais se destacam na Teoria da Complexidade?Bild zu Frage 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. ARichtig
    2. BFalsch
  5. 5O problema 3-Coloring:Bild zu Frage 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. ARichtig
    2. BFalsch
  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. ARichtig
    2. BFalsch

Informationen

Beschreibung
Questionário para testar o conhecimento adquirido sobre a classe de problemas NP-Completo e o problema 3-Coloring
Sprache
Português
Aufrufe
191
Bewertung
Noch keine Bewertungen
Bewerte dieses Quiz
Bewerte dieses Quiz

Feedback

Worum geht es?

Wie gefällt dir das neue Design?

Dein Eindruck