Turmas - 1º Semestre de 2025
Turmas
1º Semestre de 2025

A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing, muitos anos antes de existirem os modernos computadores digitais. Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento e não à sua implementação física. Considere a Máquina de Turing M a seguir:

M = ({a, b}, {q₀, q₁, q₂, q₃}, ∏, q₀, {q₃}, ø, β, ⊗)

Qual palavra será aceita pela Máquina de Turing M?

a. abaab

b. aabab

c. abba

d. babab

e. baab

O objetivo do estudo da solucionabilidade de problemas é investigar a existência ou não de algoritmos que solucionem determinada classe de problemas, ou seja, investigar os limites da computabilidade e, consequentemente, os limites do que pode efetivamente ser implementado em um computador. Considerando as noções de solucionabilidade apresentadas, analise as assertivas que se seguem.

1. A união das classes dos Problemas Totalmente Solucionáveis com os Problemas Completamente Insolúveis é o universo de todos os problemas.
2. Para qualquer algoritmo que solucione um Problema Parcialmente Solucionável, que também é um Problema Não-Solucionável, sempre existirá uma palavra de entrada que fará com que o algoritmo fique em loop.
3. Todo Problema Computável é também considerado um Problema Solucionável.
4. Existem Problemas Não-Solucionáveis que também podem ser considerados como Problemas Parcialmente Solucionáveis.

A análise permite concluir que:

a. Apenas as assertivas I e II estão corretas.

b. Apenas as assertivas I e III estão corretas.

c. Apenas as assertivas II e III estão corretas.

d. Apenas as assertivas II e IV estão corretas.

e. Apenas as assertivas III e IV estão corretas.

R. Bird desenvolveu um formalismo para o tratamento do conceito de recursão através de definições recursivas, os quais se verifica que a Classe das Funções com Definição Recursiva é a mesma Classe das Funções Computáveis. Implemente uma função recursiva, conforme as definições recursivas de Bird, que apresente o valor aproximado da raiz quadrada de um número A, por meio de n iterações, através da sequência de aproximação x_n = (x_n-1 + A/x_n-1)/2, com x₁ = 1 e n Î À.

O número de iterações e o valor de A serão fornecidos pelo usuário, devendo ser um valor inteiro e positivo.

Por exemplo, caso o valor fornecido pelo usuário para o número de iterações seja 5 e para A seja 3, o programa deverá apresentar como resposta o valor 1,732050810, obtido pela sequência de valores

x1 = 1
x2 = (x1 + 3/x1) / 2 = 2
x3 = (x2 + 3/x2) / 2 = 1,75
x4 = (x3 + 3/x3) / 2 = 1,732142857
x5 = (x4 + 3/x4) / 2 = 1,732050810

Caso o usuário forneça um valor inválido para o número de iterações ou para A, o programa deverá apresentar como resposta o valor -1.

raiz = λn.λA.(n < 1 → -1, (A < 1 → -1, (n = 1 → 1, ((raiz(n - 1, A) + A/raiz(n - 1, A))/2))))

Autômatos com pilha diferem da definição normal de máquinas de estados finitos de duas maneiras: a) podem fazer uso da informação que está no topo da pilha para decidir qual transição deve ser efetuada e b) podem manipular a pilha ao efetuar uma transição. Autômatos com pilha escolhem uma transição analisando o símbolo atual na cadeia de entrada ou o topo da pilha, enquanto que máquinas de estados finitos convencionais apenas analisam o símbolo da cadeia de entrada. Desenvolver uma máquina com Pilhas, sobre o alfabeto {0, 1, $}, que realize a disjunção binária (operador binário OR) sobre os dois números binários fornecidos pelo usuário. O símbolo $ é utilizado como separador dos dois números binários. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({0, 1, $}, D)

O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Ciência da Computação. Em linhas gerais, deseja-se saber se todo problema cuja solução pode ser eficientemente verificada por um computador, também pode ser eficientemente obtida por um computador. Por "eficientemente" ou "eficiente" significa "em tempo polinomial".

A classe dos problemas cujas soluções podem ser eficientemente obtidas por um computador é chamada de classe P. Os algoritmos que solucionam os problemas dessa classe têm complexidade de pior caso polinomial no tamanho das suas entradas.

Para alguns problemas computacionais, não se conhece solução eficiente, isto é, não se conhece algoritmo eficiente para resolvê-los. No entanto, se para uma dada solução de um problema é possível verificá-la eficientemente, então o problema é dito estar em NP. Dessa forma, a classe de problemas para os quais suas soluções podem ser eficientemente verificadas é chamada de classe NP.

Um problema é dito ser NP-completo se pertence à classe NP e, além disso, se qualquer outro problema na classe NP pode ser eficientemente transformado nesse problema. Essa transformação eficiente envolve as entradas e saídas dos problemas.

Considerando as noções de complexidade computacional apresentadas acima, analise as assertivas que se seguem.

1. Existem problemas na classe P que não estão na classe NP.
2. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P, então A está na classe P.
3. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
4. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.

A análise permite concluir que:

a. Apenas as assertivas I e II estão corretas.

b. Apenas as assertivas I e III estão corretas.

c. Apenas as assertivas II e III estão corretas.

d. Apenas as assertivas II e IV estão corretas.

e. Apenas as assertivas III e IV estão corretas.

Considere o seguinte termo do cálculo lambda:

M = ((λw. λx.(w x))(λy.y)) z

Considerando a forma normal que resulta da redução completa do termo M, assinale a alternativa correta.

a. w

b. x

c. y

d. z

e. z z

Uma Máquina de Post, assim denominada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados de tipo fila com um símbolo auxiliar. Desenvolver uma máquina de Post, sobre o alfabeto {0, 1, 2}, que verifique se os números ternários fornecidos pelo usuário são números ternários divisíveis por 3. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({0, 1, 2}, D, #)

A Máquina de Turing consiste basicamente de três partes: uma fita, uma unidade de controle e uma função de transição. A fita é usada como um dispositivo de entrada, saída e memória. Ela é dividida em células que armazenam um símbolo de cada vez. A unidade de controle reflete o estado corrente da máquina. Possui uma unidade de leitura e gravação que pode deslocar-se para a esquerda (L) ou para a direita (R) da fita, podendo ler e/ou gravar um único símbolo em cada movimento. A função de transição comanda as leituras e gravações, o sentido de movimento da cabeça e define o estado corrente da máquina. Desenvolver uma máquina de Turing, sobre o alfabeto {0, 1, $}, que realize a conjunção binária (operador binário AND) sobre os dois números binários fornecidos pelo usuário. O símbolo $ é utilizado como separador dos dois números binários. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

Download do fonte para executar no JFLAP 7.1

M = ({0, 1, $}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₈, q₉, q₁₀, q₁₁}, ∏, q₀, {q₁₁}, {x, y}, β, ⊗)