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

["Edilon Ribeiro da Silva" <edilon.silva@xxxxxxxxxxx>]

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

winmail.dat