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. 
 q0Q é 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