Ciência de Dados - Teoria de Grafos e Complexidade

O que é um grafo G.V; E/?

• Conjunto infinito V e um conjunto E de pares não ordenados de elementos distintos de V

• Conjunto finito não vazio V e um conjunto E de pares não ordenados de elementos distintos de V

• Conjunto finito não vazio V e um conjunto E de pares ordenados de elementos distintos de V

• Conjunto infinito V e um conjunto E de pares ordenados de elementos distintos de V

O que é considerado um grafo trivial?

• Quando jE j D 0

• Quando jV j D 1

• Quando jV j D 0

• Quando jE j D 1

O que é o grau de um vértice v em um grafo G.V; E/?

• O número de vértices adjacentes a v

• O número de arestas adjacentes a v

• O número de arestas incidentes a v

• O número de vértices incidentes a v

O que é uma cláusula em uma expressão booleana?

• Uma expressão cujos operadores são conjunções ou disjunções

• Uma expressão cujos operandos são literais

• Uma disjunção de literais

• Uma conjunção de literais

O que é o problema de satisfatibilidade (SAT)?

• Verificar se uma expressão booleana é inválida

• Verificar se uma expressão booleana é satisfatível

• Verificar se uma expressão booleana é insatisfatível

• Verificar se uma expressão booleana é válida

O que é o problema 3-SAT?

• Uma restrição do problema SAT onde todas as cláusulas possuem no máximo três literais

• Uma restrição do problema SAT onde todas as cláusulas possuem no máximo dois literais

• Uma restrição do problema SAT onde todas as cláusulas possuem no máximo quatro literais

• Uma restrição do problema SAT onde todas as cláusulas possuem no máximo cinco literais

O que é um problema NP-difícil?

• Um problema que é mais difícil do que um problema NP-completo

• Um problema que é mais simples do que um problema NP-completo

• Um problema que pode ser resolvido em tempo polinomial

• Um problema que não importa se satisfaz a condição (i) da definição de NP-completo

O que é a forma normal conjuntiva (FNC) em uma expressão booleana?

• Uma expressão que possui apenas operadores de conjunção

• Uma expressão que possui apenas operadores de disjunção

• Uma expressão que é uma conjunção de cláusulas

• Uma expressão que é uma disjunção de cláusulas

O que é um grafo regular de grau r?

• Um grafo onde todos os vértices possuem graus diferentes

• Um grafo onde todos os vértices possuem o mesmo grau r

• Um grafo onde todos os vértices possuem grau 1

• Um grafo onde todos os vértices possuem grau 0

O que é o problema 2-SAT?

• Uma restrição do problema 3-SAT onde cada cláusula possui no máximo dois literais

• Uma restrição do problema 3-SAT onde cada cláusula possui no máximo três literais

• Uma restrição do problema 3-SAT onde cada cláusula possui no máximo quatro literais

• Uma restrição do problema 3-SAT onde cada cláusula possui no máximo cinco literais