3952230
Beschreibung
Quiz von danillo-fr, aktualisiert more than 1 year ago
|
Erstellt von danillo-fr
vor etwa 9 Jahre
|
|
Frage 1
Frage
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?
Antworten
-
2 cores
-
3 cores
-
4 cores
-
5 cores
Frage 2
Frage
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?
Antworten
- True
- False
Frage 3
Frage
Quais são as duas classes que mais são proeminentes, ou seja, que mais se destacam na Teoria da Complexidade?
Antworten
-
Classes P e NP
-
Classes P e NP-C
-
Classes P e Co-NP
-
Classes NP-C e Co-NP
Frage 4
Frage
"A classe NP-Completo aborda problemas considerados mais difíceis dos contidos em NP"
Esta afirmação está correta?
Antworten
- True
- False
Frage 5
Antworten
-
É 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.
Frage 6
Frage
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?
Antworten
-
Problema SAT
-
Problema do Caixeiro Viajante
-
Problema 3-SAT
-
Problema Not-All-Equal 3-SAT
Frage 7
Frage
"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?
Antworten
- True
- False
Frage 8
Frage
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".
Antworten
- True
- False
Möchten Sie mit GoConqr kostenlos Ihre eigenen Quiz erstellen? eigenen Mehr erfahren.