Turmas - 1º Semestre de 2019
Turmas
1º Semestre de 2019

(POSCOMP, 2017) Em relação a computabilidade de problemas, analise as alternativas a seguir, assinalando V, se verdadeiras, ou F, se falsas.

( ) Segundo a Tese de Church, a capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer modelo de computação.

( ) Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente, X é redutível em tempo polinomial para qualquer outro problema Y na classe NP.

( ) Todo problema que está na classe P também está na classe NP.

( ) Dado que exista um problema NP-completo com solução em tempo polinomial, então todos os problemas em NP terão soluções em tempo polinomial.

A ordem correta de preenchimento dos parênteses, de cima para baixo, é:

a. V – V – V – V

b. V – V – V – F

c. V – V – F – V

d. V – F – V – V

e. F – V – V – V

Considere o seguinte termo do cálculo lambda:

M = (((λf.λx.λy.(x)(f)y)p)q)r

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

a. p q r

b. p r q

c. r p q

d. q r p

e. q p r

(Diverio, 2000) 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. Em relação ao estudo da solucionabilidade de problemas, analise as alternativas a seguir, assinalando V, se verdadeiras, ou F, se falsas.

( ) A união das Classes dos Problemas Parcialmente Solucionáveis e dos Completamente Insolúveis é o Universo de Todos os Problemas.

( ) A Classe dos Problemas Parcialmente Solucionáveis contém propriamente a Classe dos Problemas Não-Solucionáveis e parte da Classe dos Problemas Solucionáveis.

( ) Não existem problemas não-solucionáveis que possuem solução parcial.

( ) Todo problema solucionável é parcialmente solucionável.

A ordem correta de preenchimento dos parênteses, de cima para baixo, é:

a. F – F – V – V

b. V – F – F – V

c. V – V – F – F

d. F – V – F – V

e. V – F – V – F

(POSCOMP, 2008) Em relação ao estudo das máquinas universais, em especial, a Máquina de Turing, analise as alternativas a seguir, assinalando V, se verdadeiras, ou F, se falsas.

( ) Existe uma Máquina de Turing U que simula qualquer outra Máquina de Turing M sobre qualquer entrada para M.

( ) A Tese de Church afirma que o conceito informal de procedimento efetivo é capturado pelo conceito formal da Máquina de Turing.

( ) Existe uma Máquina de Turing T que, dada qualquer Máquina de Turing M e qualquer entrada w para M, T determina, em um número finito de passos, se M pará para a entrada w ou não.

( ) Toda Máquina de Turing com N ≥ 1 fitas pode ser reduzida para uma Máquina de Turing padrão.

A ordem correta de preenchimento dos parênteses, de cima para baixo, é:

a. V – V – V – V

b. V – V – V – F

c. V – V – F – V

d. V – F – V – V

e. F – V – V – V

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 o valor da exponenciação de uma base qualquer por um expoente positivo qualquer, ou seja, B^E.

power(b, e) = λb.λe.(e = 0 → 1, b * power(b, e - 1)))

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 verifique se os números binários fornecidos pelo usuário são números binários pares. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({0, 1}, {q₀, q₁, q₂}, ∏, q₀, {q₂}, ∅, β, ⊗)

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 {1}. Suponha que as palavras de entrada são números naturais representados em unário, onde, por exemplo, 3 é denotado por 111, 4 é denotado por 1111, e assim por diante. A máquina deve aceitar os naturais pares e rejeitar os naturais ímpares. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({1}, D, #)

(Diverio, 2000) 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, que concatene duas palavras sobre o alfabeto {a, b, $}. O símbolo $ é utilizado como separador das duas palavras. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

M = ({a, b, $}, D)