Turmas - 1º Semestre de 2022(vale 1,0 ponto) O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para quaisquer máquina de Turing M e palavra w, se M irá eventualmente parar com entrada w.
Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o algoritmo termina ou se executará indefinidamente.
Para o problema da parada,
a. Existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
b. Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
c. Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
d. Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.
e. Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.
(vale 1,0 ponto) A máquina de Turing pode ser usada como ferramenta para estudar o processo algorítmico. Assinale a alternativa CORRETA.
a. A máquina de Turing consiste de uma fita finita; um cabeçote que lê, escreve e move para direita ou esquerda; um registrador de estados e uma tabela de ações.
b. A máquina de Turing não determinística possui um poder computacional maior do que a máquina de Turing determinística.
c. O conjunto de símbolos usados pela máquina de Turing é infinito.
d. Se um problema não puder ser resolvido por uma máquina de Turing, então esse problema não poderá ser resolvido por qualquer outro sistema algorítmico.
e. A máquina de Turing com fita infinita a esquerda e a direita possui um poder computacional maior do que uma máquina de Turing cuja fita seja infinita apenas à direita.
(vale 1,0 ponto) Considere o seguinte termo do cálculo-lambda:
M = (λx. λy. x + y) 5 ((λz. z * 3) 6)
Considerando a forma normal que resulta da redução completa do termo M, assinale a alternativa CORRETA.
a. 21
b. 23
c. 27
d. 28
e. 33
(vale 1,0 ponto) O problema P versus NP é o principal problema aberto da Ciência da Computação, possuindo enorme relevância em campos que vão deste a engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via internet. Entretanto, apesar da pergunta P = NP está sem resposta desde 1971, ano em que foi formulada, é possível provar que um problema pertence à classe P. Analise as assertivas a seguir:
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.
(vale 1,0 ponto) 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.
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.
(vale 1,0 ponto) 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 {a, b} que verifique a quantidade de símbolos a's e b's presentes na entrada, aceitando as entradas cujas quantidades sejam diferentes.
Exemplos de entradas válidas: a, b, aa, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, aaba, ...
Exemplos de entradas inválidas: ε, ab, ba, aabb, abab, abba, baab, baba, bbaa, aaabbb, aababb, ...
M = ({a, b}, D, #)
(vale 1,0 ponto) 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 calcule a somatória dos n primeiros números pares.
Por exemplo, caso o valor de n seja 5, a função deverá retornar como resposta o valor 30, ou seja, 2 + 4 + 6 + 8 + 10.
Caso o valor de n seja inválido (menor ou igual a zero), a função deverá retornar como resposta o valor -1.
serie(n) = λn.(n <= 0 → -1, (n = 1 → 2, serie(n - 1) + (n * 2)))
(vale 1,0 ponto) 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 {a, b} que verifique a quantidade de símbolos a's e b's presentes na entrada, aceitando as entradas cujas quantidades sejam diferentes.
Exemplos de entradas válidas: a, b, aa, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, aaba, ...
Exemplos de entradas inválidas: ε, ab, ba, aabb, abab, abba, baab, baba, bbaa, aaabbb, aababb, ...
M = ({a, b}, {q0, q1, q2, q3, q4, q5, q6}, ∏, q0, {q5, q6}, {A, B}, β, ⊗)
Ybadoo - Soluções em Software Livre • Copyright 2009/2025 • 