Logo Passei Direto
Buscar

Matemática Computacional

Colégio Objetivo
O problema de decisão representa qualquer problema com resposta “sim ou não”, além de ser utilizado para decidir se determinado elemento de um universo pertence a um conjunto específico.
Sobre o problema de decisão, é correto afirmar que:
A) em um problema de decisão, um algoritmo é utilizado sempre com uma entrada genérica, considerando uma linguagem específica e retornando como resultado uma saída que aponte se a sentença é verdadeira ou falsa.
B) o termo alemão Entscheidungsproblem pode ser utilizado para se referir ao “problema de decisão”, que considera respostas decimais quando corresponde à computabilidade, explicando numericamente como resolver os problemas.
C) existem problemas de decisão não solucionáveis, cujo principal define o detector universal de loops, em que o algoritmo nunca chega a uma decisão precisa e o algoritmo continua sendo executado.
D) a equivalência de compiladores é um fator determinante, afirmando que é possível usar a linguagem livre para criar um algoritmo geral para comparar dois compiladores.
E) existem diversos métodos que podem ser utilizados para determinar a decidibilidade de um problema, portanto definir a primalidade de um conjunto de números é um exemplo de problema decídivel.
User badge image
Estudando com Questões

há 12 meses

User badge image
Estudando com Questões

há 12 meses

tema 5 1 - Decidibilidade
34 pág.

tema 5 1 - Decidibilidade

UNICARIOCA

Respostas

User badge image

Ed Verified user icon

há 12 meses

Vamos analisar cada uma das alternativas em relação ao problema de decisão: A) em um problema de decisão, um algoritmo é utilizado sempre com uma entrada genérica, considerando uma linguagem específica e retornando como resultado uma saída que aponte se a sentença é verdadeira ou falsa. - Esta afirmação é verdadeira, pois um problema de decisão realmente envolve um algoritmo que recebe uma entrada e retorna uma resposta de "sim" ou "não". B) o termo alemão Entscheidungsproblem pode ser utilizado para se referir ao “problema de decisão”, que considera respostas decimais quando corresponde à computabilidade, explicando numericamente como resolver os problemas. - Esta afirmação é incorreta, pois o Entscheidungsproblem se refere a problemas de decisão que têm respostas binárias (sim ou não), e não a respostas decimais. C) existem problemas de decisão não solucionáveis, cujo principal define o detector universal de loops, em que o algoritmo nunca chega a uma decisão precisa e o algoritmo continua sendo executado. - Esta afirmação é verdadeira, pois existem problemas de decisão que são indecidíveis, como o problema da parada (halting problem), onde não é possível determinar se um algoritmo irá parar ou não. D) a equivalência de compiladores é um fator determinante, afirmando que é possível usar a linguagem livre para criar um algoritmo geral para comparar dois compiladores. - Esta afirmação não está diretamente relacionada ao problema de decisão e é um conceito diferente. E) existem diversos métodos que podem ser utilizados para determinar a decidibilidade de um problema, portanto definir a primalidade de um conjunto de números é um exemplo de problema decídivel. - Esta afirmação é verdadeira, pois a primalidade é um problema decidível, mas não é a única característica do problema de decisão. Analisando as alternativas, as mais corretas são A e C. No entanto, a alternativa C é mais específica sobre a natureza dos problemas de decisão, mencionando a indecidibilidade, que é um aspecto importante. Portanto, a alternativa correta é: C) existem problemas de decisão não solucionáveis, cujo principal define o detector universal de loops, em que o algoritmo nunca chega a uma decisão precisa e o algoritmo continua sendo executado.

Essa resposta te ajudou?

0
Dislike0
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

tema 5 1 - Decidibilidade
34 pág.

tema 5 1 - Decidibilidade

UNICARIOCA

Mais perguntas desse material

A máquina de Turing (MT) pode ser utilizada para resolver diversos problemas, empregando uma técnica específica para determinar quais serão as decisões tomadas, visando a um resultado e determinando uma solução para cada caso. Além disso, a tese de Church-Turing pode ser definida como o uso de máquinas para reconhecimento de linguagens. Assim, se um problema de decisão tem solução, existe uma máquina de Turing que o soluciona. E se, por exemplo, não existir uma linguagem que seja uma solução para um problema de decisão, esse problema de decisão é insolúvel.
A partir do cenário apresentado, os desafios propostos em relação à MT criada são:
a) Após a implementação da MT, é necessário definir qual a relação entre a decidibilidade e a computação para o exemplo proposto.
b) Sabendo que o algoritmo apresentado também apresenta o poder de decisão, você precisa explicar aos alunos o conceito da MT utilizada em um problema de decisão e a maneira como deve ser aplicado. É necessário identificar de que forma o programa seria capaz de reconhecer que o problema é insolúvel?

Um exemplo simples de problema de decisão é descobrir se um número pertencente a um determinado conjunto é ou não é primo. O problema é definido a partir do seguinte questionamento: “Dado um número inteiro x, esse x é um número primo?”. A resposta para essa pergunta pode ser “sim” ou “não” e depende dos valores que a variável x assume em cada instância do problema.
Qual é a resposta gerada na saída para a entrada definida pelo número 7?
a) sim
b) não

O conceito de problema de decisão, conhecido em alemão como Entscheidungsproblem, foi proposto por David Hilbert, em 1928. Hilbert queria encontrar um procedimento mecânico (ou algoritmo) para verificar se uma determinada fórmula na lógica de predicados de primeira ordem seria válida ou não. Church e Turing provaram que tal algoritmo não existe.
O que Hilbert queria encontrar em relação ao problema de decisão?
a) Um algoritmo para verificar a validade de fórmulas.
b) Um modelo de cálculo.
c) Uma máquina de Turing.
d) Um problema insolúvel.

A partir do formalismo da MT, são definidas as classes de linguagens apresentadas a seguir (MENEZES, 2011; DIVERIO; MENEZES, 2011; HOPCROFT; MOTWANI; ULLMAN, 2002; SIPSER, 2007).
Qual é a definição de linguagem recursiva?

O problema da parada foi definido considerando-se as propriedades de uma máquina universal de Turing M e uma palavra w qualquer.
Qual é a linguagem associada ao problema da parada?

De acordo com Diverio e Menezes (2011), o problema de equivalência de MTs é utilizado para decidir se duas máquinas reconhecem a mesma linguagem.
Qual é a linguagem que traduz o problema da equivalência?

Quando se considera um problema de decisão, a indecidibilidade significa apenas que o sistema dedutivo específico em consideração não pode provar a autenticidade ou a falsidade da sentença.
Sobre a indecidibilidade, é correto afirmar que:
A) é uma ação que se refere a um problema de decisão, em que se pode determinar a correlação em um conjunto de fórmulas, validando-as com eficácia.
B) quando existe um algoritmo capaz de decidir um resultado, por exemplo, no problema da coprimalidade, considera-se que um problema é indecidível, caracterizando, assim, a indecidibilidade.
C) as sentenças indecidíveis podem ser descritas como um número infinito de ações aplicadas a sentenças e problemas de decisão, e essas ações e problemas nem sempre podem ser resolvidos por decisões computáveis.
D) quando um problema de decisão é indecidível, há um sistema formal consistente e eficaz para provar “sim para A” ou “não para A” para cada questão.

A importância histórica do problema da parada reside no fato de que foi um dos primeiros problemas a serem provados indecidíveis descobertos, definindo se, a partir da entrada informada, o programa terminaria ou rodaria infinitamente.
Considere as seguintes afirmações e classifique-as como verdadeiras (V) ou falsas (F):
( ) Uma consequência da indecidibilidade do problema da parada é que é impossível ter um algoritmo geral para determinar se determinada frase está certa ou errada.
( ) Se a máquina de Turing não puder resolver o problema de parada, nenhum outro sistema de algoritmo será capaz de definir uma solução para o mesmo problema.
( ) O problema de parada é decidível, uma vez que a máquina de Turing sempre permite que ele tenha um fim e não se torne infinito por falta de uma solução para qualquer problema.
( ) A redução (o princípio da redução) é uma técnica que transforma um problema em outro, diminuindo sua complexidade. Contudo, ainda não é aplicável para interromper problemas.
( ) O problema da parada é um problema de decisão sobre os atributos de um programa de computador, como o fato de todos os programas que podem ser escritos em uma linguagem de programação geral serem equivalentes a máquinas de Turing.
A) V – V – F – F – F.
B) V – V – V – F – V.
C) F – V – F – F – F.
D) F – V – F – F – V.
E) V – V – F – F – V.

Se houver um problema que uma máquina de Turing não consiga resolver, nenhum algoritmo pode aplicar a solução. Essa conclusão parte do conceito de decidibilidade da máquina de Turing e promove a pesquisa e a determinação de problemas solucionáveis.
Considere as seguintes afirmações sobre computabilidade e decidibilidade.
I. Existem problemas que são insolúveis na visão computacional, já que os computadores são limitados e nem sempre capazes de resolver problemas comuns.
II. Decidibilidade é uma definição para um caso particular de computabilidade, quando a função somente pode atribuir dois valores possíveis à saída quando ela recebe alguma entrada.
III. Apesar de o problema da parada ser o principal quando falamos de decidibilidade, existem outras variações, como o problema da parada da palavra vazia, em que uma entrada sempre é recebida, mas nem sempre se tem como resultado uma saída válida.
IV. Linguagens são utilizadas na decidibilidade e definem como as máquinas expressam e resolvem problemas usando algoritmos por meio de uma série de etapas capazes de determinar as ações necessárias.
V. O problema de totalidade é um problema de decisão que pode ser do tipo verdadeiro ou falso, verificando a equivalência entre duas máquinas universais.
A) I, II e IV.
B) I, II e V.
C) II, III e IV.
D) II, IV e V.
E) I e II, apenas.

Mais conteúdos dessa disciplina