http://www.umcs.maine.edu/~chaitin/
Esse � o link para a pagina do criador da Algorithm Information Theory, um
dos grandes matematicos vivos. Vale a pena dar um olhada : )
abra�os
----- Original Message -----
From: "Edilon Ribeiro da Silva" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Sunday, August 25, 2002 5:13 PM
Subject: [obm-l] RES: [obm-l] Numeros primos - solu��o
Caro Crom,
---------------------------------------------------------------------------
Existem problemas de decis�o bem definidos que n�o podem ser resolvidos
por algoritmos. Podemos, portanto, classificar todos os problemas
computacionais em duas categorias: aqueles que podem ser resolvidos por
algoritmos e aqueles que n�o podem. Com os grandes avan�os da tecnologia da
computa��o das �ltimas d�cadas, � razo�vel esperar que todos os problemas do
primeiro tipo possam ser resolvidos de uma maneira satisfat�ria.
Infelizmente, a pr�tica da computa��o revela que muitos problemas, apesar de
sol�veis a princ�pio, n�o podem ser resolvidos em qualquer sentido pr�tico
por computadores devido �s excessiva exig�ncias de tempo.
Suponha, por exemplo, que sua tarefa � escalonar a visita de um caixeiro
viajante a 10 escrit�rios regionais. Voc� recebe um mapa com as 10 cidades e
as dist�ncias em kil�metros e lhe pedem para produzir um intiner�rio que
minimiza a dist�ncia total percorrida. Esse �, claramente, o tipo de tarefa
em que voc� utilizaria um computador para resolver. E, de um ponto de vista
te�rico, o problema � certamente sol�vel. Se h� n cidades para visitar, o
n�mero de itiner�rios poss�veis � finito - para ser presciso (n-1)!.
Portanto, pode-se facilmente conceder um algoritmo que sistematicamente
examina todos os intiner�rios a fim de localizar o mais curto.
Mas ainda h� um mal-estar com rela��o a esse algoritmo. H� muitas
viagens a serem examinadas. Para nosso modesto problema de 10 cidades,
ter�amos de examinar 9! = 362.880 itinar�rios. Com alguma paci�ncia, isso
pode ser realizado por um computador, mas e se tiv�ssemos 40 cidades a
visitar? O n�mero de itiner�rios seria agora gigantesco: 39!, o que � mais
que 10^45. Mesmo que pud�ssemos examinar 10^15 viagens por segundo - um
passo que � muito r�pido mesmo para o mais poderoso supercomputador
existente ou projetado - o tempo exigido para completar esse c�lculo seria
v�rios bilh�es de ciclo de vida do universo!
Evidentemente, o fato de um problema ser sol�vel na teoria n�o
imediatamente implica que ele possa ser resolvido de maneira realista na
pr�tica. A quest�o �: quais algoritmos devemos considerar como praticamente
vi�vel?
Como o exemplo do PROBLEMA DO CAIXEIRO VIAJANTE revela, o par�metro
limitador � o tempo ou n�mero de passos exigidos pelo algoritmo em um
entrada. O algoritmo (n-1)! para o problema do caixeiro viajante foi
demasiado irreal simplemente por causa do excessivo crescimento exponencial
de suas exig�ncias de tempo (� f�cil ver que a fun��o (n-1)! cresce ainda
mais r�pido que 2^n). Em contraste, um algoritmo com uma taxa de crescimento
polinomial seria obviamente muito mais atraente.
Parece que, a fim de capturar a no��o de "algotitmo praticamente
vi�vel", devemos limitar nossos dispositivos computacionais para somente
executar um n�mero de passo que � limitado por um polin�mio no comprimento
de entrada [da� a import�ncia da descoberta dos cientistas da Computa��o
indianos]. A classe de todas as linguagens polinomialmente decid�veis �
denotada por P [P do ingl�s polinomial] e a classe de todas as linguagens
que n�o pertecem a P � denotada por NP [NP do ingl�s no-polinomial]. Isso
justifica o t�tulo do artigo dos cientistas: PRIMES IN P.
Em que medida a classe P captura a no��o intuitiva de "problema
satisfatoriamente vi�vel"? Com que amplitude se aceita a tese de que
algoritmos polinomiais s�o precisamente ou empiricamente vi�veis? � razo�vel
dizer que, embora seja a �nica proposta s�ria nessa �rea, ela pode ser
desafiada em v�rios terrenos. Por exemplo, pode-se argumentar que um
algoritmo com exig�ncias de tempo n^100 ou mesmo (10^100)n^2, n�o �
"praticamente vi�vel", embora tenha um tempo polinomial. Al�m disso, um
algoritmo com exig�ncias de tempo n^(log(log(n)) pode ser considerado
perfeitamente vi�vel na pr�tica, a despeito do fato de que seu crescimento
n�o � limitado por qualquer polin�mio. O argumento emp�rico em defesa de
nossa tese � que tais limites extremos de tempo, embora teoricamente
poss�veis, raramente ocorrem na pr�tica: algoritmos polinomiais, que surgem
em pr�ticas computacionais, geralmente t�m pequenos expoentes e coeficientes
costantes agrad�veis, enquanto algoritmos n�o polinomiais s�o em geral
exponenciais e, portanto, de utliza��o bastante limitada na pr�tica.
De acordo com o documento "Primes in P", os autores apresentam um
algoritmo que decide se um dado n�mero n � primo ou composto [dei uma lida
r�pida] com uma complexidade computacional O([log(n)]^6), podendo
futuramente chegar a O([log(n)]^3), desde que se prove a conjectura de
Bhattacharjee-Pandey.
---------------------------------------------------------------------------
Notas:
1) Este texto acima foi, essencialmente, retirado do cap�tulo 6, se��es
6.1 e 6.2, do livro ELEMENTOS DE TEORIA DA COMPUTA��O [Trad. Edson
Furmankiewicz] de Harry R. Lewis e Christos H. Papadimitriou, 2� Edi��o,
Bookman, Porto Alegre, 2000.
2) Os acr�scimos e as supress�es por mim feitas objetivaram apenas
tornar a leitura mais adequada aos prop�sitos da mensagem.
3) Citem sempre a refer�ncia, qualquer que seja o texto. Respeitem os
direitos autorais.
---------------------------------------------------------------------------
Obrigado,
Edilon Ribeiro
-----Mensagem original-----
De: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]
Enviada: dom 25/8/2002 15:15
Para: [EMAIL PROTECTED]
Cc:
Assunto: Re: [obm-l] Numeros primos - solu��o
O que significa: " Em tempo polinomial ", como foi citado no texto sobre a
f�rmula dos matem�ticos hindus, para numeros primos????
Um abra�o
Crom
=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista � <[EMAIL PROTECTED]>
=========================================================================
