Prévia do material em texto

Unidade 5 - Computabilidade
1.Um dos modelos mais utilizados para descrever algoritmos de maneira formal é a máquina de Turing. Considere a seguinte máquina de Turing, em que Q correspondente ao conjunto de estados (q0 é o estado inicial, e qP é o estado de parada) e £ indica os símbolos que a fita pode conter (B é o símbolo de espaço em branco):
Q = { q0, q1, q2, q3, qP }
£  = { 0, 1, X, Y, B}
A função de transição é dada pela seguinte tabela de regras:
Assinale a alternativa correta a respeito do funcionamento da máquina acima considerando a entrada 0011B.
R: A. 
A máquina de Turing vai parar considerando a entrada informada, e os símbolos que estarão na fita serão XXYYB.
2.  A solução para dado problema pode ser obtida por meio da descrição de um algoritmo que o resolva. Para isso, no entanto, é fundamental que se analise a computabilidade do problema. Sobre o conceito de computabilidade, leia as assertivas a seguir.
I. Se um problema em um cenário prático é dito computável, então qualquer algoritmo que o resolva pode ser empregado.
II. Um algoritmo de complexidade O(cn) é dito intratável, já que o seu tempo de resposta é inviável para um problema prático.
III. Algoritmos que resolvem problemas incomputáveis têm complexidade de tempo inviável para situações práticas.
IV. Um algoritmo com complexidade O(n!) é menos eficiente do que qualquer algoritmo para problemas tratáveis.
Quais estão corretas?
R: B. 
II e IV.
3. Problemas incomputáveis não podem ser resolvidos por algoritmos com um número finito de passos. Marque V para verdadeiro e F para falso para as afirmações a respeito dessa categoria de problemas:
( ) Problemas que não podem ser resolvidos em uma máquina de Turing podem ser resolvidos via cálculo lambda.
( ) Se dois programas computam o mesmo resultado para qualquer entrada, então eles processam a mesma linguagem.
( ) Um problema que pode ser resolvido por um algoritmo computacional pode ser resolvido por uma máquina de Turing.
( ) A versão mais eficiente de um algoritmo pode ser obtida por meio de uma máquina de Turing com fita de tamanho infinito.
Assinale a alternativa que apresenta a sequência correta:
R: C. 
F - V - F - F.
4. O problema da parada é um tradicional exemplo de problema incomputável. Ele pode ser apresentado por duas funções, conforme descrito a seguir.
R: D. 
P, P / executar laço infinito / DECIDE_PARADA /.
5.  
Os problemas que precisam ser resolvidos computacionalmente podem ser classificados de acordo com a sua computabilidade. Assinale a alternativa correta a respeito dessa classificação de problemas.