Question

1-Muitos problemas de decisão sobre máquinas universais são não solucionáveis. Na realidade, é fácil definir um problema não solucionável, e há vários exemplos. Um deles, é um problema que é uma variação do problema da parada, restringindo a entrada à palavra vazia (ou ausência de entrada).

Assinale a alternativa que apresenta corretamente o nome do problema referido no texto-base.
Escolha uma:
a.
Problema da parada total

b.
Problema da equivalência

c.
Problema da parada da palavra vazia

d.
Problema da parada vazia

e.
Problema da correspondência de Post

2-Considere o problema a seguir, sendo ele um dos mais importantes problemas não solucionáveis:

“Dada uma máquina universal M qualquer e uma palavra w qualquer sobre o alfabeto de entrada, existe um algoritmo que verifica se M para, aceitando ou rejeitando, ao processar a entrada w?”

Assinale a alternativa que apresenta corretamente o problema mencionado.
Escolha uma:
a.
Problema de otimização linear

b.
Problema de linguagem

c.
Problema de busca

d.
Problema da parada

e.
Problema de Turing

3-O conjunto de todos os problemas pode ser particionado em algumas classes. E um dos problemas de decisão mais conhecidos é chamado de problema da parada.

Assinale a alternativa que apresenta corretamente a classe de problemas a qual o problema da parada pertence.
Escolha uma:
a.
Decidíveis

b.
Não solucionáveis

c.
Computáveis

d.
Solucionáveis

e.
Irracionais

4-O problema da equivalência é um problema de ____________ que verifica a equivalência de duas máquinas universais. Este problema é ____________.

Assinale a alternativa que preenche corretamente as lacunas.
Escolha uma:
a.
decisão / não solucionável

b.
decisão / solucionável

c.
busca / parcialmente solucionável

d.
otimização / solucionável

e.
otimização / não solucionável

5-Considere o problema a seguir:

“Dada uma máquina universal M qualquer, existe um algoritmo que verifica se M para, aceitando ou rejeitando, ao processar qualquer entrada?”

Assinale a alternativa que apresenta corretamente o problema mencionado.
Escolha uma:
a.
Problema da totalidade

b.
Problema da parada da palavra vazia

c.
Problema da correspondência de Post

d.
Problema da equivalência

e.
Problema da parada

6-Com base em seu conhecimento sobre tempos polinomiais e exponenciais, considere a taxa de crescimento de polinômios que ocorrem tipicamente tais como n3 e exponenciais típicas tais como 2n.

Assinale a alternativa correta.

Escolha uma:
a.
Algoritmos de tempo exponencial 2n raramente são suficientemente rápidos para muitos propósitos.

b.
2n e n3 são tempo-polinomialmente equivalentes.

c.
Um algoritmo polinomial n3 e um exponencial 2n não apresentam diferenças em tempo de execução.

d.
Um algoritmo com tempo de execução exponencial 2n é mais rápido que um polinomial n3

e.
Um algoritmo com tempo de execução polinomial n3 é mais rápido que um exponencial 2n

7-Um conjunto S de números naturais é chamado ____________ se existe uma função recursiva parcial (também conhecida como função computável) na qual o domínio é exatamente S, significando que a função é definida se e somente se sua entrada é membro de S.

Assinale a alternativa que preenche corretamente a lacuna.
Escolha uma:
a.
recursivamente enumerável

b.
enumerável

c.
decidível

d.
recursivamente tratável

e.
computavelmente tratável

8-Qual a classe que consiste nos problemas que podem ser resolvidos em tempo polinomial (problemas tratáveis) sobre uma máquina de Turing determinística de uma única fita?
Assinale a alternativa correta.

Escolha uma:
a.
Classe P

b.
Classe NPL

c.
Classe PSPACE

d.
Classe TP

e.
Classe NP

Answer 1

Resposta:

Questão 5 -> a. Problema da totalidade

Explicação:

Corrigido pelo AVA

Answer 2

Resposta:

1

c) Problema da parada da palavra vazia

5

a) Problema da totalidade

6

e) Um algoritmo com tempo de execução polinomial n3 é mais rápido que um exponencial 2n

8

a) Classe P

Corrigido pelo AVA

Explicação: