Exercícios de Teoria da Computação

Prévia do material em texto

Universidade Federal de Lavras 
Departamento de Ciência da Computação 
2
o
 semestre de 2011 
 
 
GCC108 – Teoria da Computação 
Professor Responsável: Leonardo Andrade Ribeiro 
 
 
Avaliação: Exercícios 3 
Data: 01.12.2011 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
 
 
 
 
1) Seja {〈 〉 }. Mostre que S é indecidível. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2) Considere o problema de testar se uma Máquina de Turing sobre uma entrada 
tenta em algum momento mover a cabeça le para a esquerda quando a cabeça le já 
está no início da fita. Formule este problema como um problema de aceitação de 
linguagem e mostre que o mesmo é indecidível. 
 
(Observação: Estamos adotando a convenção de que a fita apenas se expande da 
esquerda para a direita. Neste contexto, se uma transição indicar movimentação para a 
esquerda e cabeça le se encontra sobre o primeiro símbolo da fita, então a cabeça irá 
permanecer no mesmo lugar) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3) Escreva as seguintes funções em notação : 
 
a) 
 
b) 
 
c) 
 
 
d) 
 
 
 
 
e) 
 
 
 
 
 
 
 
 
4) É verdade que 2 + 100n = O( )? Prove. 
 
 
 
 
 
5) Apresente a redução polinomial do CLIQUE para PCI. 
 
 
 
 
 
 
 
 
 
 
 
6) Considere a prova de NP-Completude do PCbV. Apresente o grafo formado pelos 
Componentes 1, 2, 3 para a seguinte expressão 3FNC: 
 
 ̅̅ ̅ ̅̅ ̅ ̅̅ ̅ ̅̅ ̅ 
 
 
 
 
 
 
 
 
 
 
 
 
 
7) Prove que o problema da Mochila está em NP. 
 
 
 
 
 
 
 
 
8) Considere o problema dos subgrafos isomoformos (PSI): 
 
Instância genérica: Dois grafos, e . 
 
Questão: Existe um grafo isomorfo à em G? Em outras palavras, existe um 
subconjunto e um subconjunto tal que | | | | | | | | , e existe 
uma função 1-1 satisfazendo { } se e somente se { } ? 
 
Dica: Mostre que CLIQUE PSI.