Matématica

Pergunta 1

Assinale a alternativa correta:

a. Todo problema decidível apresenta solução Ο(n).

b. Todo problema decidível apresenta solução com complexidade computacional polinomial.

c. Toda Máquina de Turing com n ≥ 1 fitas pode ser reduzida a uma Máquina de Turing padrão.

d. A eliminação de fitas adicionais de uma MT não transforma o tempo de execução.

e. Todo problema decidível apresenta solução O(n!).

0 pontos
Pergunta 2

Assinale a alternativa que apresenta um problema cuja solução é polinomial.

a. A rota mais longa para se visitar n cidades de uma região.

b. A rota mais curta para se visitar n cidades de uma região.

c. A pior alocação de processos à memória de um sistema computacional.

d. A alocação ótima de processos ao microprocessador.

e. Cálculo dos zeros de um polinômio quadrático.

0 pontos
Pergunta 3

Assinale a alternativa incorreta.

a. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão.

b. Se existe uma máquina de redução de LA para LB (sobre um alfabeto Σ), então LB = LA.

c. Linguagens codificam problemas.

d. É possível reduzir o problema do ciclo hamiltoniano para o da satisfabilidade booleana.

e. A classe NP contém muitos problemas de interesse prático.

0 pontos
Pergunta 4

Assinale a alternativa correta:

a. Verificar se uma dada fórmula booleana cujas cláusulas apresentam apenas 2 literais é “satisfazível”, não é um problema NP.

b. É possível demonstrar que P ⊆ NP e NP ⊆ P.

c. Não se sabe se P = NP.

d. Se P é diferente de NP, então existem problemas na classe P que são NP – completos.

e. O algoritmo para a busca em uma árvore binária é NP – completo.