EXERCICIO 9

Prévia do material em texto

03494 - COMPUTABILIDADE E A MÁQUINA DE TURING
	 
		
	
		1.
		A hierarquia de Chomsky representou um marco na classificação das linguagens e uma grande evolução para a computação. Acerca das características das diferentes linguagens e as respectivas máquinas reconhecedoras dessas linguagens, Aassinale a alternativa falsa.
	
	
	
	Todo Conjunto Finito é enumerável.
	
	
	O conjunto de todas as Máquinas de Turing é enumerável.
	
	
	Toda Linguagem Regular é enumerável.
	
	
	O conjunto de todas as Expressões Regulares é enumerável.
	
	
	Nenhum Conjunto Finito é enumerável.
	Data Resp.: 04/12/2023 18:30:57
		Explicação: 
Os conjuntos enumeráveis são os superconjuntos de todas as linguagens tratáveis por autômatos (no caso a máquina de Turing). Portanto, há linguagens infinitas cujas gramáticas são uma especificação finita e são enumeráreis e aceitas por Máquinas de Turing. Outo contraexemplo é o conjunto dos números naturais.
	
	
	 
		
	
		2.
		Analise as seguintes afirmativas
 
I. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão. Em um problema de localização, procura-se localizar uma certa estrutura que satisfaça um conjunto de propriedades dadas. Se as propriedades envolverem critérios de otimização, então o problema é dito de otimização.
II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-completos é aplicado somente para esse tipo de problema.
III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP podem ser resolvidos da mesma forma.
A análise permite concluir que:
	
	
	
	Apenas as afirmativas I e III estão corretas.
	
	
	Apenas a afirmativa II está correta.
	
	
	As afirmativas I, II e III estão corretas.
	
	
	Apenas as afirmativas I e II estão corretas.
	
	
	Apenas a afirmativa I está correta.
	Data Resp.: 04/12/2023 18:31:23
		Explicação: 
Em um problema de decisão, o objetivo é decidir a resposta sim ou não. Problemas de otimização envolvem critério de otimização. Afirmativa I está correta. Os problemas NP-Completos são objeto da teoria da complexidade computacional e são problemas de decisão que, até o momento, não foram reduzidos a um tempo de solução polinomial. A afirmativa II está correta. Para esse caso hipotético, por redução, implica que P=NP. Uma vez que P=NP, existem algoritmos polinomiais para todos os problemas NP e a proposição III é correta. Ocorre que não se sabe se P=NP, ainda.
	
	
	 
		
	
		3.
		Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.
I. A descoberta do cientista implica P = NP.
PORQUE
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-Completos.
A respeito dessas asserções, assinale a opção correta.
	
	
	
	A asserção I é uma proposição verdadeira e a II é uma proposição verdadeira.
	
	
	A asserção I é uma proposição falsa e a II é uma proposição verdadeira.
	
	
	As asserções I e II são proposições falsas.
	
	
	As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
	
	
	As asserções I e II são proposições verdadeiras e a II é uma justificativa correta da I.
	Data Resp.: 04/12/2023 18:31:45
		Explicação: 
Sabemos que P ⊆ NP, ou seja, P é um subconjunto de NP. Problemas NP-completos são um conjunto de problemas que podem ser reduzidos em tempo polinomial a partir de qualquer outro problema NP, mas cuja solução ainda pode ser verificada em tempo polinomial. Um problema NP-completo é pelo menos tão difícil quanto qualquer outro problema NP. Para esse caso hipotético, por redução, implica que P=NP e a asserção I é verdadeira. Uma vez que P=NP, existem algoritmos polinomiais para todos os problemas NP e a proposição II é verdadeira e uma justificativa da I.
	
	
	 
		
	
		4.
		Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo é quadrático, quanto tempo em segundos ele gastará, aproximadamente, no mesmo computador, se a entrada tiver tamanho 100?
	
	
	
	40.
	
	
	500.
	
	
	100.
	
	
	10.
	
	
	20.
	Data Resp.: 04/12/2023 18:32:22
		Explicação: 
Como o algoritmo é quadrático, podemos fazer a seguinte aproximação para o tempo de execução: T(n)=cn2, onde c é uma constante a ser determinada. Sabe-se que T(50)=10, logo c*502 = 10 segundos, então 2500c=10 e determinamos c=1/250.  A expressão de complexidade de tempo para esse algoritmo é T(n)=  (1/250) * n2. Logo, T(100) = (1/250)*1002.
T(100) = 10000/250 = 40.
	
	
	 
		
	
		5.
		Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA.
	
	
	
	A união de duas linguagens recursivas é uma linguagem recursiva.
	
	
	Todo problema que está na classe P também está na classe NP.
	
	
	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.
	
	
	Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente enumerável, então L é uma linguagem recursiva.
	
	
	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.
	Data Resp.: 04/12/2023 18:33:00
		Explicação: 
Um problema é NP completo quando está na classe NP, e todo problema NP completo conhecido pode ser reduzido a ele. O correto seria Y é redutível a X em tempo polinomial, porque, pela definição, todo problema NP-Completo poderia ser redutível a X. As demais alternativas estão corretas.
	
	
	 
		
	
		6.
		Seja uma MT T dada pelas quíntuplas:
1. (0, 1, 1, 0, D)
                2. (0, b, 1, 1, H)Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. 
Qual a função que calcula essa MT?
	
	
	
	2n +1
	
	
	2n
	
	
	2n+1
	
	
	2n -1
	
	
	2n+1 - 1
	Data Resp.: 04/12/2023 18:33:28
		Explicação: 
Esse exemplo mostra o poder de computação das MT. Deve-se começar utilizando a quíntupla 1. Enquanto a MT ler 1 na fita, escreve 1, continua no estado 0 e anda para a direita (D). Ao encontrar um branco, escreve 1, muda para o estado final 1 e para (H). A cadeia final é 1111. A cadeia inicial era 111 = 23-1, foi transformada em 1111 = 24-1. Logo a MT calcula 2n+1 - 1
	
	
	 
		
	
		7.
		O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer 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:
	
	
	
	Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas. 
	
	
	Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.
	
	
	Existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
	
	
	Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado. 
	
	
	Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
	Data Resp.: 04/12/2023 18:33:57
		Explicação: 
Não existe nenhuma máquina de Turing M que consiga decidir se vai parar ou entrar em loop infinito.O problema da parada é indecidível, portanto não existe algoritmo que o solucione.
	
	
	 
		
	
		8.
		Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro problema. Em particular, a redutibilidade pode ser usada para demonstrar que problemas são indecidíveis ou decidíveis. Nesse contexto, avalie as seguintes afirmativas:
I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução de A na presença de um método para resolver B.
II. Reduções apresentam um importante papel em classificar os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
 
Quais as afirmativas verdadeiras?
	
	
	
	I, II e III.
	
	
	III.
	
	
	I e III.
	
	
	I e II.
	
	
	II e III.
	Data Resp.: 04/12/2023 18:34:25
		Explicação: 
Na afirmativa III, se A é redutível a B e B é um problema indecidível, então A é um problema indecidível.
	
	
	 
		
	
		9.
		. Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral. Acerca de suas características principais, qual item não faz parte do diagrama mecânico da máquina de Turing?
	
	
	
	Direção de leitura..
	
	
	Pilha.
	
	
	Fita de entrada.
	
	
	Cabeça de leitura-escrita.
	
	
	Controle finito.
	Data Resp.: 04/12/2023 18:34:30
		Explicação: 
O diagrama não contempla uma pilha. Todos os outros itens podem ser visualizados na figura do diagrama mecânico.
	
	
	 
		
	
		10.
		Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase sem qualquer restrição. Dentro dessa hierarquia estão classificadas a linguagem recursiva e a linguagem recursivamente enumerável.  Acerca de suas características assinale a afirmação verdadeira.
 
	
	
	
	Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
	
	
	Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
	
	
	Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre na entrada de uma máquina de Turing.
	
	
	Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável.
	
	
	Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva.
	Data Resp.: 04/12/2023 18:35:12
		Explicação: 
As linguagens recursivas estão contidas no conjunto das linguagens recursivamente enumeráveis. Portanto, não são equivalentes. Uma linguagem recursiva é uma linguagem aceita por uma Máquina de Turing. Ambas as linguagens são aceitas por Máquinas de Turing. Quando uma linguagem é rejeitada a MT para, não entra em loop infinito.