TRABALHO 04 TEORIA DA COMPUTAO

INTRODUO CINCIA DA
COMPUTAO - COM06850- 2012-II

CINCIA DA COMPUTAO

GRUPO 5

2012204302 Caque de Oliveira de Souza

2012204291 - Heloiza Barros DelEsposti
2012204278 - Maycown Douglas O. Miranda
2012204279 - Melissa Silva de Souza
2012204298 - Otto Freitas Quintanilha
2012204286 - Paloma Marques Nobre

Teoria da Computao
Primeiro, apresentaremos uma linguagem que chamamos linguagem
simples, a fim demostrar que o numero mnimo de instrues necessrias para
resolver qualquer problema solvel por um computador trs. Segundo,
explicaremos que outra ferramenta, chamada maquina de Turing tambm pode
resolver um problema que pode ser resolvido por nossa linguagem simples.
Terceiro, provaremos que nenhum programa pode informar se o outro para ou no
(se o programa termina ou ira executar para sempre), e essa terceira prova, mostra
por si prpria que existem problemas que no podem ser solucionado por um
computador.
- As linguagens simples:
Nessa linguagem o nico tipo de dados utilizado so nmeros inteiros no
negativos para poder demonstrar algumas ideias da teoria da computao.
Definimos linguagens do computador apenas com trs instrues:
Instruo de incremento: Aumentar de 1 o valor de certa varivel.
Imagine que um programa trabalhe com uma varivel denominada X e que se
deseje aumentar de 1 o valor dessa varivel ou seja incr(x): X = X + 1;
Instruo de decremento: Esta operao o inverso daquela
denominada incremento. Trata-se de retirar 1 do valor de uma varivel. Ento, de
modo anlogo operao de incremento tem-se decr(x): X = X - 1
Instruo de lao: Trata-se de uma tcnica que permite repetir as
mesmas instrues vrias vezes ate alcanar o valor desejado da varivel.
- A importncia da linguagem simples
Embora no seja to eficiente quanto outras linguagens sofisticadas, to
importante quanto, pois a partir dela possvel simular instrues que so
encontradas em algumas linguagens populares com apenas as trs instrues da
linguagem simples.

- Macros em linguagem simples

Macroinstruo (macro), chamamos cada simulao de macro e os
utilizamos como base para uma nova simulao.

O uso de macros facilita a

especificao de trechos repetitivos de um cdigo, que podem ser invocados pelo

programador como uma nica linha no programa. Toda macro tem um nome
especificado como o rtulo da pseudo-instruo e que ser utilizado pelo
programador para invocar a macro, e um corpo, que ser usado pelo macromontador para substituir o nome usado pelo programador pela sequncia de
instrues nele especificados. Na sua forma mais simples, uma macro
simplesmente uma abreviatura para um grupo de instrues. A forma geral de
definio de uma macro :
nome

MACRO

[argumentos]

corpo
- Entrada e sada
Na linguagem simples, meramente para provar alguns teoremas da
cincia da computao simulamos a sada assumindo que a ultima varivel utilizada
o que deveria ser impresso.

Mquina de Turing
A Mquina de Turing(MT) pode ser descrita como um modelo matemtico
do processo de computao. Sua estrutura simples proposital, uma vez que Turing
pretendia, com sua definio, chegar a um modelo que fosse universalmente aceito.
Atualmente h diversos modelos na literatura, mas que seguem o mesmo princpio.
A MT o principal modelo usado para o estudo do que ou no
computvel. De acordo com a tese de Church, todos os modelos razoveis de
procedimento so equivalentes, e a MT se revelou simples e flexvel o suficiente
para permitir todas as demonstraes dos resultados principais. Pode-se usar uma
MT como aceitador ou reconhecedor, ou ainda como a implementao de um
procedimento mais geral, que transforma uma cadeia de entrada em uma cadeia de
sada.
Uma Mquina de Turing feita de trs componentes: fita, controlador
cabeotes de leitura/gravao.
Uma definio para a Mquina de Turing pode ser: Uma mquina de
Turing M uma tupla M = < K, , , , i, F >, onde K um conjunto (finito, no
vazio) de estados, o alfabeto (finito) de smbolos da fita, o alfabeto de
smbolos de entrada, a funo de transio, i K o estado inicial, e F K o
conjunto de estados finais. A funo de transio d um mapeamento : K K
{L, R}. Quando tivermos (q, a) = (p, b, R), a MT M, quando est no estado q, e
l o smbolo a na fita, escreve o smbolo b na mesma posio em que a estava
escrito, move-se para a direita uma clula, e passa para o estado p. (Idem, para a
esquerda no caso de (q, a) = (p, b, L) ). Por simplicidade, podemos deixar alguns
valores de indefinidos, de maneira que deve ser entendida como uma funo
parcial. Atingida uma situao em que o estado , o smbolo lido a, e (q, a)
indefinido, dizemos que a mquina para. Poderamos, se desejado, definir mquinas
de Turing que sempre param quando atingem um estado final, e que nunca param
em um estado no final. Mas sempre que esta propriedade for desejada, podemos
alterar uma MT introduzindo um estado adicional, no final, do qual a mquina
nunca mais sai.

Tese de Church-Turing
J dizia a tese de Church-Turing: Se existe um algoritmo para fazer a
tarefa de manipulao de smbolos, existe uma mquina de Turing para realiza-la. A
tese consiste em tentar provar que qualquer tarefa de manipulao de smbolos,
pode ser executada em uma mquina de Turing, caso a tarefa no puder ser
calculada na mquina de Turing, a mesma no pode ser calculada. Essa tese pode
ser provada matematicamente, apesar de que nunca poder ser provada, existem
fortes argumentos em seu favor. Como por exemplo, no foi encontrado nenhum
algoritmo que no possa ser simulado utilizando uma mquina de Turing, e foi
demonstrado que todos os modelos computacionais que tm sido comprovados so
equivalentes ao modelo dessa mquina.

Numeros de Godel
Na cincia da computao, um numero sem sinal pode ser associado a cada
programa que poder ser descrito em linguagem especifica, geralmente chamado
de numero de Godel, em homenagem ao matemtico austraco Kurt Godel.
Vantagens de uso do numero de Godel: Os programas podem ser utilizados
como um nico item de dados como entrada para outros programas. A Identificao
de um programa pode ser feita por apenas uma representao de um nico numero
inteiro. O uso de numerao pode ser utilizado para provar que certos problemas
no podem ser solucionados pelo computador, mostrando que o nmero total de
problemas no mundo maior do que problemas em programas.
Vrios mtodos foram criados para numerao de programas, um modo de
transformao simples para numerar programas escritos em linguagens simples na
tabela abaixo.
Smbolo

Cdigo

Smbolo

Cdigo

Hexadecimal

Hexadecimal

Incr

Decr

while

Representao de um Programa
Ao utilizar a tabela, podemos representar qualquer programa escrito na
linguagem simples por um nico numero inteiro positivo, basta seguir algumas
etapas.
1. Substituir a partir da tabela, cada smbolo hexadecimal correspondente.
2. Interpretar o nmero hexadecimal resultante como um nmero inteiro
sem sinal.
Ex:
Qual numero de Godel para o programa incr(X)?
A soluo basta substituir cada smbolo pelo seu correspondente cdigo
hexadecimal.
Incr X (AF)16 ---- 175
A representao do programa em numero de Godel ser 175.
Interpretao de um nmero de Godel
Para interpretar um numero de Godel em um programa, basta seguir as
seguintes instrues:
1. Converta o nmero para hexadecimal
2. Interprete cada dgito hexadecimal como um smbolo utilizando a
tabela.
Ex:
Interprete 3058 como um programa.
Basta modificar o numero para hexadecimal e substituir cada dgito pelo
correspondente smbolo.
3508 (BF2)16 decr X 2 decr (X2)

O Problema da Parada
Quase todo o programa escrito de em uma linguagem de programao
envolve alguma forma de repetio, laos ou funes recursivas. Uma construo
com base em repetio pode nunca parar; ou seja, possvel que um programa seja
executado para sempre se tiver um lao infinito. A existncia desse programa
poderia economizar muito tempo dos programadores. Executar um programa sem
saber se ele ir ou no parar um trabalho muito difcil. Mas, agora j pode ser
comprovado que um tal programa no pode existir, o que um grande
desapontamento para os programadores.
O Problema da Parada No Pode Ser Resolvido
Em vez de afirmar que o programa de teste no existe, e nunca poder
existir, o cientista da computao diz: o problema da parada no solvel.
Prova: Assumimos que o programa existe, e ento, mostramos que essa
existncia cria uma contradio; portanto ela no pode existir.
Etapa 1
Assumimos que um programa, chamado teste, existe.
Etapa 2
Criamos outro programa, chamado Estranho, que composto de duas
partes: uma cpia de teste no incio, e um lao vazio.
Etapa 3
Tendo escrito o programa Estranho, testamos consigo mesmo como
entrada.

A Complexidade dos Problemas

A complexidade de um problema o consumo de tempo do melhor
algoritmo possvel para o problema. (O melhor algoritmo conhecido atualmente no
, em geral, o melhor algoritmo possvel.) claro que estamos nos referindo ao
consumo de tempo no pior caso, ou seja, ao consumo de tempo para as instncias
mais "difceis" do problema.
Problemas computacionais
Precisamos de um repertrio de exemplos. Seguem alguns:
Quadrado perfeito: Dado um nmero natural n, encontrar um nmero
natural x tal que x = n ou constatar que tal x no existe.
Equao inteira do segundo grau:

Dados nmeros inteiros a, b e c,

encontrar um nmero inteiro x tal que ax + bx + c = 0 ou constatar que tal xno

existe.
Fatorao: Dado um nmero natural n, encontrar um nmero natural p,
maior que 1 e menor que n, que seja divisor n ou constatar que tal p no existe.
Mximo divisor comum:

Encontrar o maior divisor comum de dois

nmeros naturais m e n.
Divisor comum grande: Dados nmeros naturais m, n e k, encontrar um
divisor comum de m e n que seja maior que k ou constatar que tal divisor no
existe.
Subsequncia crescente mxima:

Dada uma sequncia s1,,sn de

nmeros naturais, encontrar uma subsequncia crescente mxima de s1,,sn.

Subsequncia crescente longa:

Dada uma sequncia s1,,sn de

nmeros naturais e um nmero natural k, encontrar uma subsequncia crescente de

s1,,sn que tenha comprimento maior que k ou constatar que tal subsequncia
no existe.

Mochila: Dados nmeros naturais p1,,pn, v1,,vn e c, encontrar um

subconjunto K de {1,,n} tal que a soma dos pk para k em K no passe de c e a
soma dos vk para k em K seja mxima.
Caminho mnimo:

Dados vrtices r e s de um grafo, encontrar um

caminho de comprimento mnimo de r a s no grafo

ou

constatar que no h

caminho algum de r a s.
Caminho mximo:

Dados vrtices r e s de um grafo, encontrar um

caminho de r a s que tenha comprimento mximo ou constatar que no h caminho

algum de r a s.
Ciclo mximo: Encontrar um ciclo de comprimento mximo num grafo
dado ou constatar que o grafo no tem ciclo algum.
Ciclo hamiltoniano: Encontrar um ciclo hamiltoniano (ou seja, um ciclo
que passe por todos os vrtices) num grafo dado ou constatar que tal ciclo no
existe.
Ciclo longo:

Dado um grafo e um nmero k, encontrar um ciclo de

comprimento maior que k ou constatar que o grafo no tem tal ciclo.

Clique grande: Dado um grafo e um nmero k, encontrar uma clique com
k ou mais vrtices ou constatar que tal clique no existe.
Cobertura pequena:

Dado um grafo e um nmero k, encontrar uma

cobertura com menos que k vrtices ou constatar que tal cobertura no existe.
(Observe que h uma relao ntima entre o problema do ciclo
hamiltoniano e o problema do ciclo longo. H relaes anlogas entre vrios outros
pares de problemas.)
Algoritmos Polinomiais
Dizemos que um algoritmo resolve um dado problema se, ao receber
qualquer instncia do problema, devolve uma soluo da instncia ou diz que a
instncia no tem soluo.

Um algoritmo que resolve um dado problema polinomial se o seu

consumo de tempo no pior caso limitado por uma funo polinomial dos tamanhos
das instncias do problema.
polinomial, por exemplo, todo algoritmo que consome no mximo
100N4 + 300N2 + 5000

unidades de tempo, sendo N o tamanho da instncia.

Tambm polinomial todo algoritmo que consome no mximo 200N9 log N

unidades de tempo, por exemplo (pois 200N9 log N < 200N10).
Algoritmos polinomiais so considerados rpidos (ainda que seja difcil
aceitar como rpido um algoritmo que consome tempo proporcional a N500, por
exemplo). Algoritmos no polinomiais como, por exemplo, os que consomem
tempo proporcional a 2N so considerados inaceitavelmente lentos (ainda que
possam ser teis para valores muito modestos de N).
Problemas Polinomiais e a Classe P
Um problema computacional polinomial se existe um algoritmo
polinomial para o problema. Problemas desse tipo so considerados tratveis do
ponto de vista computacional.
Exemplos de problemas polinomiais: o problema da equao do segundo
grau, o problema do mximo divisor comum, o problema do caminho mnimo,
oproblema da subsequncia crescente mxima.
A classe P de problemas o conjunto de todos os problemas polinomiais.
[A rigor, esta definio est incorreta, pois a classe P contm apenas os problemas
polinomiais de deciso.]
Um problema no polinomial se nenhum algoritmo polinomial resolve o
problema.

(Cuidado:

no se trata de problemas para os quais algoritmos

polinomiais no so conhecidos atualmente, pois tais algoritmos podem vir a ser

descobertos

no

futuro.)

computacionalmente intratveis.

Problemas

desse

tipo

so

considerados

A Classe NP de Problemas
O status de muitos problemas desconhecido:
problema polinomial ou no.

no se sabe se o

Diante disso, uma boa ideia investigar a

complexidade relativa dos problemas. Trata-se de verificar se um dado problema Y

computacionalmente mais fcil ou mais difcil que um outro problema X (talvez mais
bem-conhecido). Antes que isso possa ser feito, entretanto, preciso restringir um
pouco o universo dos problemas sob estudo.
Quais problemas devemos considerar "razoveis"?

Diremos que um

problema "razovel" se fcil reconhecer uma soluo do problema quando se

est diante de uma. Mais precisamente, um problema computacional X "razovel"
se toda instncia I de X satisfaz a seguinte condio:
possvel verificar, em tempo polinomial, se uma suposta soluo da
instncia I , de fato, uma soluo de I.
Muitos dos problemas mencionados acima so "razoveis". Considere os
seguintes exemplos:
fcil verificar se um dado inteiro x satisfaz a equao ax + bx + c = 0.
Essa verificao consome tempo limitado por um polinmio no tamanhosda instncia
(a,b,c) pois o valor absoluto de qualquer soluo x da equao no maior que o
produto (|a|+1)(|b|+1)(|c|+1). Portanto, oproblema da equao do segundo grau
"razovel".
fcil verificar se um dado nmero natural p divide n.

Ademais, a

verificao consome tempo polinomial no tamanho da instncia pois todo divisor de

n menor que n. Portanto, o problema da fatorao "razovel".
O problema do ciclo longo "razovel" pois fcil verificar, em tempo
polinomial, se um dado objeto um ciclo no grafo e tem comprimento maior que k.
O problema do ciclo hamiltoniano "razovel" pois fcil verificar, em
tempo polinomial, se um dado objeto um ciclo no grafo e passa por todos os
vrtices do grafo.

O conjunto de todos os problemas "razoveis" (essencialmente) igual

classe NP de problemas. [Cuidado: "NP" no abreviatura de "no polinomial" mas
sim de "nondeterministic polynomial".]
(A rigor, no correto confundir o conjunto dos problemas "razoveis"
com classe NP. A questo que o conceito de soluo que serve de base para a
ideia de problema "razovel" no suficientemente preciso.

Considere, por

exemplo, o problema do ciclo mximo. Por um lado, parece que deveramos aceitar
o problema como "razovel" uma vez que o problema do ciclo longo "razovel".
Por outro lado, o problema no parece "razovel" pois no est claro como verificar
se um dado ciclo mximo, ou seja, se no existe ciclo mais longo. Para contornar
essas dificuldades, preciso restringir nossa ateno a problemas "de deciso" e
trocar o conceito de "soluo" pelo de "certificado".)
A Questo "P = NP?"
No difcil entender que a classe NP inclui a classe P, ou seja, que todo
problema polinomial "razovel".

O bom senso sugere que P apenas uma

pequena parte de NP. Surpreendentemente, ningum conseguiu ainda encontrar

um problema de NP que comprovadamente no esteja em P, isto , um problema
"razovel" para o qual comprovadamente no existe algoritmo polinomial.
Esta situao abre caminho para a suspeita de que talvez P seja igual a
NP .

A maioria dos especialistas no acredita nessa possibilidade, entretanto. [O

Instituto Clay de Matemtica oferece um prmio de um milho de dlares pela

soluo da questo "P=NP?".]
A pergunta "P = NP?" por ser reformulada assim: " verdade que todo
problema cujas solues podem ser conferidas por um algoritmo polinomial pode
tambm ser resolvido por um algoritmo polinomial?"
Complexidade Relativa de Problemas
Podemos agora dizer algo sobre a complexidade relativa de problemas
em NP. Um problema Y no mais difcil que um outro problema X se Y for um
"subproblema", ou "caso particular", de X. Exemplos:

O problema do quadrado perfeito no mais difcil que o problema da

equao do segundo grau.
O problema do ciclo hamiltoniano no mais difcil que o problema do
ciclo longo.
O problema da cobertura pequena de um grafo no mais difcil que o
problema da clique grande. (Por que?)
Para explicar um pouco melhor o conceito, diremos que um problema Y
no mais difcil que um problema X se qualquer algoritmo polinomial para X pode
ser transformado num algoritmo polinomial para Y. O algoritmo para Y tem trs
etapas: primeiro, qualquer instncia J de Y transformada, em tempo polinomial,
numa instncia "equivalente" I de X; depois, a instncia I submetida ao algoritmo
polinomial para X, que produz uma soluo S; finalmente, S transformada, em
tempo polinomial, numa soluo T de J.

Assim, se X est em P e Y no mais

difcil que X ento Y tambm est em P.

Problemas Completos em Np
Um problema X completo em NP, ou NP-completo, se X est em NP e
todos os demais problemas em NP no so mais difceis que X.
A existncia de problemas completos em NP um fato surpreendente e
fundamental. O fato foi demonstrado, por volta de 1970, por S. Cook e L. Levin
(independentemente).
Para mostrar que P = NP basta encontrar um algoritmo polinomial para
um nico problema NP-completo.

Portanto, os problemas NP-completos so os

mais "difceis" de NP.

Por exemplo, so NP-completos os problemas (de deciso derivados dos)
seguintes:

ciclo

pequena,mochila.

hamiltoniano,

ciclo

longo,

clique

grande,

cobertura

Uma lista com centenas de outros problemas NP-completos

pode ser encontrada no livro de Garey e Johnson.

Apndice: Certificados de Inexistncia de Soluo

Nossa tentativa grosseira de definir a classe NP de problemas, trouxe
baila uma questo importante. Muitos problemas tm instncias que no admitem
soluo. Como possvel "provar" ou "certificar" que uma dada instncia de um
problema no admite soluo? No estamos tratando aqui de como descobrirque
uma dada instncia no tem soluo, mas apenas de, uma vez descoberta a
inexistncia de soluo, como tornar este fato "evidente".
Para muitos problemas, existem certificados naturais e elegantes para a
inexistncia de soluo. (Todos consistem em trocar um "no existe x" por um
"existe y" apropriado.) Eis alguns exemplos:
Problema do quadrado perfeito: Para mostrar que um nmero natural n
no um quadrado perfeito, basta exibir um nmero natural k tal quek < n < (k+1).
Um tal k um certificado de inexistncia de soluo.
Problema da equao do segundo grau: Para mostrar que no existe um
inteiro x tal que ax + bx + c = 0, basta verificar que (1) b4ac no um quadrado
perfeito, ou

(2) b4ac um quadrado perfeito mas nem (b4ac) + b nem

(b4ac) b so divisveis por 2a.

Assim, um certificado de inexistncia de

soluo consiste em certificados para as condies (1) ou (2).

Problema do divisor comum grande: Para mostrar que no existe divisor
comum de m e n que seja maior que k suficiente exibir nmeros inteiros (no
necessariamente positivos) x e y tais que 0 < xm+yn k. Como qualquer divisor
comum de m e n tambm divisor de xm+yn, conclumos que todo divisor comum
de m e n menor ou igual a k. Assim, o par x,y um certificado da inexistncia de
divisor comum grande. Todas as instncias sem soluo tm um tal certificado. (O
algoritmo de Euclides calcula o certificado ao mesmo tempo que calcula um mximo
divisor comum.)
Problema da fatorao: Existe um certificado muito interessante para as
instncia do problema que no tm soluo, mas no tenho condies descrever o
certificado aqui.

Problema da subsequncia crescente longa:

Suponha dada uma

cobertura por subsequncias estritamente decrescentes de uma sequncia

s1,,snde nmeros naturais. Se a cobertura consiste em k sequncias ento claro
que nenhuma subsequncia crescente de s1,,sn pode ter comprimento maior que
k. Assim, uma cobertura pequena por subsequncias estritamente decrescentes
um certificado de inexistncia de subsequncia crescente longa.
instncias sem soluo tm uma tal cobertura.

Todas as

(O algoritmo que calcula uma

subsequncia crescente mxima pode ser adaptado para determinar tambm um

cobertura mnima.)
Problema do caminho mnimo:

Seja R um conjunto de vrtices que

contm o vrtice r mas no contm o vrtice s. Suponha ainda que nenhuma aresta
liga um vrtice de R a um vrtice fora de R. Se um tal R existe, claro que no
existe caminho de r a s. Assim, um tal R um certificado de inexistncia de soluo
para a instncia em discusso. (Toda instncia sem soluo tem um tal certificado.)
Cada um desses exemplos mostra que o correspondente problema est
na classe coNP.

Referncias Bibliogrficas
[1] FOROUZAN, Behrouz; MOSHARRAF, Firouz. Fundamentos da Cincia da
Computao, traduo da 2 edio internacional.
[2] http://www.ime.usp.br