[obm-l] Re: [obm-l] RES: [obm-l] Numeros primos - solução

["iver" <iver@xxxxxxxxxx>]

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" <edilon.silva@poli.usp.br>
To: <obm-l@mat.puc-rio.br>
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: DEOLIVEIRASOU@aol.com [mailto:DEOLIVEIRASOU@aol.com]
Enviada: dom 25/8/2002 15:15
Para: obm-l@mat.puc-rio.br
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 é <nicolau@mat.puc-rio.br>
=========================================================================