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.

Neste sentido, assinale a única alternativa que que apresenta um problema de decisão solucionável.
Escolha uma:
a.
Problema da equivalência

b.
Problema da parada da palavra vazia

c.
Problema da totalidade

d.
Conjunto dos números primos

e.
Problema da parada

2-Há uma classe de problemas ainda mais simples que os de busca. São problemas cujas instâncias admitem apenas dois tipos de solução: ‘sim’ e ‘não’.

Assinale a alternativa que apresenta corretamente o tipo de problema referido no texto.
Escolha uma:
a.
Problemas de decisão

b.
Problemas de busca

c.
Problemas da parada

d.
Problemas de otimização

e.
Problemas de Turing

3-A Teoria da computabilidade estuda, dentre outros temas, os fundamentos de vários tipos de problemas, como os de decisão, otimização e busca.

Assinale a alternativa que apresenta corretamente a definição de um problema de otimização.
Escolha uma:
a.
Nenhuma das alternativas.

b.
Problema computacional em que é necessário determinar a melhor solução possível entre todas as soluções viáveis.

c.
Problema computacional em que é necessário decidir, dado um programa monolítico arbitrário P para Norma, se a computação de P em Norma termina ou não, para a entrada p.

d.
Problema computacional em que a resposta para cada instância é sim ou não.

e.
Problema computacional que consiste em encontrar uma estrutura y em um objeto x.

4-Analise o seguinte problema:

“Dadas uma lista de cidades e as distâncias entre todas, determine a menor rota que visite todas as cidades e retorne à cidade original.”

Qual o tipo de problema caracterizado por este enunciado?
Escolha uma:
a.
Problema de parada

b.
Problema de busca

c.
Problema de otimização

d.
Problema de decisão

e.
Problema de Turing

5-A essência de um problema de ____________ é dada pela seguinte ideia: dado um programa P para uma máquina universal M, decidir se a função computada é total (ou seja, se a correspondente computação é finita).

Assinale a alternativa que preenche corretamente a lacuna.
Escolha uma:
a.
Decisão

b.
Computação

c.
Recursão

d.
Busca

e.
Otimização

6-Sobre os problemas de decisão e otimização, analise as afirmativas a seguir:

I. Problema de decisão é um tipo de problema computacional em que é necessário determinar a melhor solução possível entre todas as soluções viáveis.

II. Problema de otimização é um tipo de problema computacional em que a resposta para cada instância é sim ou não.

III. Geralmente, os problemas de decisão não são mais difíceis que os problemas de otimização.

Neste contexto, é correto o que se afirma em:
Escolha uma:
a.
I, apenas.

b.
II, apenas.

c.
I e II, apenas.

d.
I, II e III.

e.
III, apenas.

Answer 1

Resposta:

1 conjunto dos numeros primos

2 problema de decisão

3 letra b

Explicação:

Answer 2

Resposta:

1 - Conjunto dos números primos

2 - Problemas de decisão

3 - Problema computacional em que é necessário determinar a melhor solução possível entre todas as soluções viáveis.

4 - Problema de otimização

5 - Decisão

6 - III, apenas

Explicação:

Corrigido pelo AVA