Turmas - 2º Semestre de 2017
Turmas
2º Semestre de 2017

(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 assertivas que se seguem.

1. 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.
2. 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.
3. O conjunto de todos os problemas que param para uma dada entrada é o conjunto dos problemas parcialmente solucionáveis ou computáveis.

É correto apenas o que se afirma na(s) assertiva(s):

a. I.

b. II.

c. III.

d. I e II.

e. I e III.

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.

M = ({a, b, $}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆, q₇, q₈, q₉, q₁₀, q₁₁}, ∏, q₀, {q₉, q₁₀, q₁₁}, {A, B}, β, ⊗)

Considerando a Máquina de Turing apresentada, analise as assertivas que se seguem.

1. A máquina aceita a entrada aa$bb.
2. A máquina rejeita a entrada abb$aba.
3. A máquina aceita a entrada aab$aab.
4. A máquina rejeita a entrada abb$abb.

É 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.

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. Desenvolva uma máquina de Post, sobre o alfabeto {a, b}, que reconheça palavras que contenham a mesma quantidade de símbolos a's e b's, independentemente da ordem como os símbolos apareçam na entrada. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

(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. Desenvolva uma máquina com Pilhas, sobre o alfabeto {a, b}, que verifique se a palavra fornecida pelo usuário é uma palavra palíndroma. Palavras palíndromas são palavras que lidas da esquerda para a direita ou vice-versa possuem o mesmo significado, como por exemplo, a palavra arara ou ovo. A seguir, são apresentados alguns exemplos de entradas possíveis de serem fornecidas pelo usuário com seus respectivos resultados.

(POSCOMP, 2008) Considere o seguinte termo do cálculo-lambda:

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

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

a. (λy.z)

b. (λx.x)(λz.z)

c. (λy.(λu.λz.u))

d. (λx.λy.x)

e. (λx.(λu.λz.u).x)

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 n-ésimo termo da série de Fibonacci.

serie = λn.(n = 0 → 0, (n = 1 → 1, serie(n - 1) + serie(n - 2)))

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 da classe dos problemas Solucionáveis e dos Completamente Insolúveis é o universo de todos os problemas.
2. 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.
3. Todo problema Computável é também um problema Solucionável.
4. Alguns problemas Não-Solucionáveis são Parcialmente Solucionáveis.

É 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.

(ENADE, 2011) O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em 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.

É correto apenas o que se afirma na(s) assertiva(s):

a. I.

b. IV.

c. I e III.

d. II e III.

e. II e IV.