ATC_TrabalhoP1_Gustavo-mouraria-CC7P36_D7725I6

Prévia do material em texto

Bacharelado em Ciência da Computação
Aspectos Teóricos da Computação 
Trabalho P1
	Nome.: Gustavo De Mouraria Pereira 
	RA: D7725I6
As questões que se seguem constituem o trabalho a nota P1 da disciplina.
O valor de cada questão é 0.5 ponto. Assim sendo a nota máxima para o trabalho é 5.0
DATA DE ENTREGA: 10 DE MAIO. APÓS ESTA DATA NÃO SERAO ACEITOS TRABALHOS PARA A Composição DA Média FINAL.
Questão 1 (0.5 ponto) - Sabe-se que a  máquina de Turing, é  definida formalmente como uma quíntupla MT = (Q, A, , g, q0, >, b, F), onde:
· Q é o conjunto finito não vazio de estados.
· A é o alfabeto de entrada, formado por um conjunto não vazio de símbolos.
· é o conjunto finito e não vazio de símbolos que podem ser lidos e/ou escritos na fita de trabalho. A.
· q0Q é o estado inicial.
· F  Q é o conjunto de estados finais.
Assinale a alternativa correta sobre a Máquina de Turing MT:
a) O cursor de acesso à fita de trabalho de uma máquina de Turing pode se deslocar apenas à direita.
b) Apresenta a fita de trabalho limitada à direita.
c) Sempre, para qualquer que seja o conteúdo da fita de entrada e qualquer que seja a função de transição.
d) Apresenta um conjunto ilimitado de estados.
e) A Fita de trabalho de uma MT é passível de ser lida e escrita.
Resposta: e) A Fita de trabalho de uma MT é passível de ser lida e escrita.
Questão 2(0.5 ponto) Considere a seguinte tabela, que representa a operação de uma máquina de Turing:
	estado
	Símbolo lido na fita
	Símbolo gravado na fita
	Direção
	Próximo estado
	q0
	
	
	direita
	q0
	q0
	x
	x
	direita
	q1
	q0
	y
	x
	direita
	q0
	q0
	b
	b
	direita
	q0
	q1
	x
	y
	direita
	q0
	q1
	y
	y
	esquerda
	q0
 
Considere ainda, a seguinte configuração inicial de reconhecimento:
 
	
	b
	y
	x
	b
	
	 
	 
	 
	 
	q0
	 
	 
	 
	 
A última fita de entrada é:
a) 
	
	b
	x
	x
	b
	 
	 
	 
	
	 
	 
	 
	 
	q0
	 
b) 
	
	b
	y
	y
	b
	
	 
	 
	 
	 
	qf
	 
	 
	 
	 
 
c) 
	
	b
	y
	x
	b
	 
	 
	 
	
	 
	 
	 
	 
	q1
	 
d) 
 
	
	b
	x
	x
	b
	 
	 
	 
	 
	
	 
	 
	 
	 
	q1
e) O processamento não para.
Resposta: d) 
	
	b
	y
	x
	b
	 
	 
	 
	
	 
	 
	 
	 
	q1
	 
Questão 3 (0.5 ponto)- Considere a seguinte tabela, que representa a operação de uma máquina de Turing:
	estado
	Símbolo lido na fita
	Símbolo gravado na fita
	Direção
	Próximo estado
	q0
	
	
	direita
	q0
	q0
	x
	x
	direita
	q1
	q0
	y
	x
	direita
	q0
	q0
	b
	b
	direita
	q0
	q1
	x
	y
	direita
	q0
	q1
	y
	y
	esquerda
	q0
 
Considere ainda, a seguinte configuração inicial de reconhecimento:
 
	
	b
	x
	y
	b
	
	 
	 
	 
	 
	q0
	 
	 
	 
	 
A última fita de entrada é:
a) 
	
	b
	x
	x
	b
	 
	 
	 
	
	 
	 
	 
	 
	q0
	 
b) 
	
	b
	y
	y
	b
	
	 
	 
	 
	 
	qf
	 
	 
	 
	 
c) 
	
	b
	x
	y
	b
	 
	 
	 
	
	 
	 
	 
	 
	q1
	 
d) 
	
	b
	x
	y
	b
	 
	 
	 
	 
	
	 
	 
	 
	 
	q1
e) O processamento não para, efetuando ciclos.
Resposta: e) O processamento não para, efetuando ciclos.
Questão 4: (0.5 ponto) A Hipótese de Turing-Church sugere:
a)  Que à Máquina de Turing devem ser adicionadas duas ou mais pilhas de forma que o seu poder computacional de expressar algoritmos seja menos restritivo;
b) Que se a máquina de Turing fosse multidimensional seu poder computacional de expressar algoritmos seria menos restritivo;
c) Que à Máquina de Turing devem ser adicionados múltiplos cabeçotes de leitura e gravação sobre a mesma fita, de forma que o seu poder computacional de expressar algoritmos seja menos restritivo;
d) Que se a máquina de Turing fosse multidimensional seu poder computacional de expressar algoritmos seria muito restritivo;
e) Qualquer outra forma de expressar algoritmos terá no máximo a mesma capacidade computacional da Máquina de Turing;
Resposta: e) Qualquer outra forma de expressar algoritmos terá no máximo a mesma capacidade computacional da Máquina de Turing;
Questão 5 (0.5 ponto) Considere a seguinte definição: “Dada uma Máquina Universal M qualquer e uma palavra w qualquer sobre o alfabeto de entrada, existe um algoritmo que verifique se M para, aceitando ou rejeitando, ao processar a entrada w?”. Trata-se da definição do problema conhecido como:
 
a) Problema da Análise Lexicográfica;
b) Problema das Máquinas Universais;
c) Problema das Entradas;
d) Problema da Parada;
e) Problema da Auto-Aplicação;
Resposta: d) Problema de Parada
Questão 6 (0.5 ponto) Assinale a alternativa que diz respeito a um problema que apresenta desempenho polinomial:
a) problema do Caixeiro Viajante.
b) Problema do Clique.
c) Problema dos Conjuntos Independentes
d) Detecção de um ciclo  Hamiltoniano em um Grafo
e) Detecção de um caminho Euleriano em um Grafo;
Resposta: e) Detecção de um caminho Euleriano em um Grafo;
Questão 7 (0.5 ponto) Considere o grafo G=(V, A, g), onde:
V = {1, 2, 3, 4, 5, 6, 7, 8} são os vértices
A = {a, b, c, d, e}
g(a) = 2-6
g(b) = 4-3
g(c) = 2 – 3
g(d) = 1-4
g(e) = 1-2
g(f) = 5-6
g(g) = 5- 8
g(h)=8-7
g(i)= 6-7
g(j) = 7-3
g(k) = 8-4
 
Sejam ainda, as seguintes afirmações:
I -  O grafo apresenta um caminho de Euler, pois apresenta um número par de nós ímpares;
II – O grafo apresenta um ciclo Hamiltoniano, pois apresenta um número par de nós ímpares
III – Este grafo apresenta 8 vértices e desta forma um programa que verifique se existe um caminho Hamiltoniano deverá efetuar em uma situação de pior caso 8! cálculos.
IV – Este grafo apresenta 6 nós ímpares e portanto não apresenta um Caminho de Euler.
a) I, II, III e IV;
b) Apenas III e IV;
c) Apenas I e II;
d) Apenas I e III;
e) Apenas II e IV;
Resposta: b) Apenas III e IV;
Questão 8 (0.5 ponto) Assinale a alternativa correta:
a) Verificar se uma dada fórmula booleana cujas cláusulas apresentam apenas 2 literais é “satisfazível, é um problema NP.
b) É possível demonstrar que P  NP e NP   P.
c) Não se sabe se P = NP;
d) Se P é diferente de NP, então existem problemas na classe P que são NP-completos.
e) O algoritmo para a busca em uma árvore binária é NP-completo;
Resposta: a) Verificar se uma dada fórmula booleana cujas cláusulas apresentam apenas 2 literais é “satisfazível, é um problema NP
Questão 9 (0.5 ponto) Assinale a alternativa que representa um problema NP-Completo:
a) Satisfabilidade booleana-2;
b) Problema da parada;
c) Detecção universal do loop completo;
d) Problema do Ciclo de Euler;
e) Problema do Ciclo Hamiltoniano
Resposta: a) Satisfabilidade booleana-2;
Questão 10(0.5 ponto) Em uma determinada edificação, onde o esquema de segurança é crucial, deseja-se cobrir todas as áreas de circulação e ao mesmo tempo minimizar o número de pontos de monitoração. Sabe-se que o número de salas deste lugar é 30 e o número de corredores é 15. A fim de se obter exatamente o menor número de pontos de monitoração de forma a cobrir todos os corredores, deveriam ser realizados cálculos de complexidade:
a) fatorial;
b) quadrática;
c) linear
d) logarítmica;
e) cúbica;
Resposta: a) fatorial
Respostas
1. Resposta: e) A Fita de trabalho de uma MT é passível de ser lida e escrita.
2. Resposta: d) 
	
	b
	y
	x
	b
	 
	 
	 
	
	 
	 
	 
	 
	q1
	 
3. Resposta: e) O processamento não para, efetuando ciclos.
4. Resposta: e) Qualquer outra forma de expressar algoritmos terá no máximo a mesma capacidade computacional da Máquina de Turing;
5. Resposta: d) Problema de Parada
6. Resposta: e) Detecção de um caminho Euleriano em um Grafo;
7. Resposta: b) Apenas III e IV;
8. Resposta: a) Verificar se uma dada fórmula booleana cujas cláusulas apresentam apenas 2 literais é “satisfazível, é um problema NP
9. Resposta: a) Satisfabilidade booleana-2;
10. Resposta: a) fatorial