Turmas - 2º Semestre de 2019
Turmas
2º Semestre de 2019

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:

1. É possível provar que um problema pertence à classe P apresentando uma Máquina de Turing Determinística de tempo polinomial que decida o problema.
2. É possível provar que um problema pertence à classe P apresentando uma redução de tempo polinomial deste problema para outro que sabidamente pertence à classe P.
3. É possível provar que um problema pertence à classe P apresentando uma Máquina de Turing Não Determinística de tempo polinomial que decida o problema.
4. É possível provar que um problema pertence à classe P apresentando uma redução de tempo polinomial deste problema para outro que sabidamente pertence à classe NP-completo.

É correto apenas o que se afirma nas assertivas:

a. I e II.

b. I e III.

c. II e III.

d. II e IV.

e. III e IV.

Considere o seguinte termo do cálculo-lambda:

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

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

a. x

b. y

c. z

d. w

e. w w

(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 da classe dos problemas Solucionáveis e dos Completamente Insolúveis é o universo de todos os problemas.

( ) Para qualquer algoritmo que solucione um problema Parcialmente Solucionável que é Não-Solucionável, sempre existe pelo menos uma palavra de entrada que faz com que o algoritmo fique em loop.

( ) Todo problema Computável é também um problema Solucionável.

( ) Alguns problemas Não-Solucionáveis são Parcialmente Solucionáveis.

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, 2007) Computabilidade é a habilidade de resolver problemas de forma efetiva, sendo um tópico chave para o campo da Teoria da Computação dentro da Ciência da Computação. A computabilidade de um problema é intimamente ligada à existência de um algoritmo para resolver o problema. Os modelos mais estudados da computabilidade são as Máquinas de Turing e as funções recursivas, os quais têm poderes computacionais equivalentes. Considerando as noções de computabilidade apresentadas, analise as alternativas a seguir, assinalando V, se verdadeiras, ou F, se falsas.

( ) Uma linguagem L é aceita por uma Máquina de Turing não determinística com k fitas, m dimensões, n cabeçotes de leitura e gravação por fita se, e somente se, ela é aceita por uma Máquina de Turing determinística com uma fita infinita em apenas um sentido e um cabeçote de leitura e gravação.

( ) Uma função é parcialmente computável se, e somente se, ela pode ser obtida a partir de funções iniciais (por exemplo, sucessor, zero e projeção) por um número finito de aplicações de composição, recursão primitiva e minimalização.

( ) O conjunto de todos os problemas que param para uma dada entrada é o conjunto dos problemas parcialmente solucionáveis ou computáveis.

( ) Máquinas com Pilhas são máquinas universais que manipulam símbolos em um conjunto de n pilhas, com n > 0.

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

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, 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}, {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 {0, 1} que realize a divisão inteira dos números binários fornecidos pelo usuário por 2. 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, #)

(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, 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.

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

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 retorne o fatorial do número fornecido pelo usuário. Caso o usuário informe um número inválido, a função recursiva deverá retornar -1.

fat(n) = λn.(n < 0 → -1, (n = 0 → 1, n * fat(n - 1)))