Exercicios3-Solucoes

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. 
 
Estratégia: Prova por contradição. Assumimos que é decidível e que, portanto, 
existe uma MT que decide . Vamos mostrar que, usando A, podemos construir um 
Decididor para decidir , a linguagem usada no Problema da Parada (dicotomia 
Aceita/Rejeita). Como sabemos que é indecidível, então temos uma contradição 
e, portanto, o Decididor A para S não pode existir; em outras palavras S é indecidível. 
 
B = “Na entrada ⟨ ⟩, onde é um e é uma palavra: 
1. 
2. Execute A com entrada ⟨ ⟩ 
3. Se aceitar, Aceite; se rejeitar, Rejeite” 
 
 
 
 
 
 
 
 
 
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). 
 
Formulação como um problema de aceitação de linguagens: 
 
 {〈 〉 M é uma MT, p é uma palavra e M tenta mover em algum momento 
a cabeça le para a esquerda quando a mesma estiver no início da fita} 
 
Mostrando que é indecidível: 
Seguindo a mesta estratégia do exercício anterior, vamos mostrar que, usando um 
Decididor A para , podemos construir um Decididor para decidir . 
 
 
B = “Na entrada ⟨ ⟩, onde é um e é uma palavra: 
1. Converta M para M1, onde M1 primeiramente move toda a entrada uma 
posição à direita na fita e depois escreve um marcador especial na primeira 
posição da fita. M1 então simula M sobre a palavra de entrada. Sempre que o 
símbolo atual da fita for igual ao marcador significa que M tentou mover a 
cabeça le para a esquerda do primeiro símbolo da palavra de entrada. Neste 
caso, a cabeça le é movida imediatamente por M1 para o primeiro símbolo da 
palavra de entrada. Finalmente, se M Aceitar p, M1 move a cabeça le para a 
posição sob o marcador especial (que se encontra na primeira posição da fita) e 
depois é realizada uma tentativa para mover a cabeça le para a esquerda. 
2. Execute A com entrada ⟨ ⟩ 
3. Se aceitar, Aceite; se rejeitar, Rejeite” 
 
Notem que a única maneira de M1 tentar mover a cabeça le para a esquerda quando a 
mesma estiver no início da fita é se M aceitar a entrada p. 
 
 
 
 
 
 
 
 
 
 
 
3) Escreva as seguintes funções em notação : 
 
a) 
 
b) 
 
c) 
 
 
d) 
 
 
 
 
e) 
 
 
 
 
 
 
 
 
4) É verdade que 2 + 100n = O( )? Prove. 
 
É preciso encontrar valores para as contantes e tal que: 
 
 
 
Existem diversas maneiras para encontrar c e caso os mesmos existam. Uma 
sugestão que aparece no slide 37 do material sobre Complexidade é fazer um pouco 
maior que o coeficiente do termo de mais alta ordem. Neste caso, o coeficiente em 
questão é 2, então vamos fazer . Portanto, temos: 
 
 
 
 
 
Portanto, uma solução é e . 
 
 
 
5) Apresente a redução polinomial do CLIQUE para PCI. 
 
Baseiem-se nos slides 114-119 do material sobre NP-Completude. A redução 
polinomial poderá ser apresentada de maneira similar à redução apresentada no slide 
119. 
 
 
 
 
 
 
 
 
 
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. 
 
 
Temos que um certificado para o problema da Mochila é representado por um 
subconjunto do conjunto de entrada . A verificação de que representa uma 
solução para o problema consiste em realizar um somatório dos tamanhos (peso t) e 
dos valores (peso v) de cada elemento de e verificar se os valores destes somatórios 
é menor ou igual à e maior ou igual à , respectivamente. Esta verificação pode 
realização em tempo linear à quantidade de elementos em Portanto, existe um 
Verificador polinomial para o Problema da Mochila; em outras palavras, 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. 
 
Podemos mostrar que CLIQUE PSI por restrição. Para isso, basta restringirmos o 
conjunto de instâncias do PSI para instâncias onde H seja um grafo completo. Neste 
caso, G possui um subgrafo isomorfo à se e somente se G possui um clique 
formado pelos subconjunto onde . (Vejam a definição do 
problema CLIQUE no slide 114).