Publicidade
Publicidade
05/09/2002
-
14h34
da Folha de S.Paulo
Um número natural é chamado de primo se tem exatamente dois divisores: 1 e ele mesmo. O fascínio que os números primos exercem sobre o homem é quase tão antigo quanto a própria história da matemática. Euclides (325-265 a.C.) demonstrou que existem infinitos números primos.
Eratóstenes (276-194 d.C.), por sua vez, propôs um método para encontrar números primos conhecido como crivo de Eratóstenes. Apesar de ser bastante simples elaborar um programa de computador que use esse método para encontrar números primos até um certo número natural N, o tempo de operação para executá-lo cresceria exponencialmente com o tamanho de N.
Para compreender o que isso significa, imagine um programa de computador cujo tempo de execução seja dado pela exponencial 2N. Executando esse programa para N=1.000 em um computador que realize uma operação a cada milésimo de segundo, a resposta final só seria obtida em 10284 anos, o que é 10274 vezes maior que a idade do universo.
Em geral, problemas cujo tempo de execução é exponencial são de difícil, quando não impossível, tratamento computacional e recebem o nome de problemas NP. Se, por ouro lado, um problema pode ser executado em tempo polinomial com N, ele recebe o nome de problema P e pode ser tratado de forma eficiente por computadores. Por exemplo, se o tempo de execução de um programa fosse dado polinomialmente por N2, encontraríamos sua solução em pouco mais de 16 minutos no computador descrito acima para N=1.000.
Na incansável busca dos cientistas por transformar problemas NP em problemas P, cuja resolução por computador é mais viável, a novidade, divulgada recentemente pela revista "New Scientist", vem da Índia. Três pesquisadores desse país desenvolveram um programa de tempo polinomial para verificar se um número é primo ou não, problema até então considerado como NP. Ainda não se sabe ao certo o impacto da demonstração, mas o fato é que, mais uma vez, os indianos demonstram ao mundo a força e a tradição de sua pesquisa na área de computação e matemática.
José Luiz Pastore Mello é professor da Faculdade de Educação da USP
Leia a reportagem da "New Scientist" no site www.uol.com.br/inovacao/ultimas/ult762u636.shl
Leia mais:
História: A conquista do norte mexicano
Atualidades: Alca, nova versão da Doutrina Monroe
Geografia: Os significados das siglas e o vestibular
Física: O afastamento das galáxias
Português: Pronome átono nem sempre é complemento verbal
Matemática: Descoberta sobre números primos
JOSÉ LUIZ PASTORE MELLOda Folha de S.Paulo
Um número natural é chamado de primo se tem exatamente dois divisores: 1 e ele mesmo. O fascínio que os números primos exercem sobre o homem é quase tão antigo quanto a própria história da matemática. Euclides (325-265 a.C.) demonstrou que existem infinitos números primos.
Eratóstenes (276-194 d.C.), por sua vez, propôs um método para encontrar números primos conhecido como crivo de Eratóstenes. Apesar de ser bastante simples elaborar um programa de computador que use esse método para encontrar números primos até um certo número natural N, o tempo de operação para executá-lo cresceria exponencialmente com o tamanho de N.
Para compreender o que isso significa, imagine um programa de computador cujo tempo de execução seja dado pela exponencial 2N. Executando esse programa para N=1.000 em um computador que realize uma operação a cada milésimo de segundo, a resposta final só seria obtida em 10284 anos, o que é 10274 vezes maior que a idade do universo.
Em geral, problemas cujo tempo de execução é exponencial são de difícil, quando não impossível, tratamento computacional e recebem o nome de problemas NP. Se, por ouro lado, um problema pode ser executado em tempo polinomial com N, ele recebe o nome de problema P e pode ser tratado de forma eficiente por computadores. Por exemplo, se o tempo de execução de um programa fosse dado polinomialmente por N2, encontraríamos sua solução em pouco mais de 16 minutos no computador descrito acima para N=1.000.
Na incansável busca dos cientistas por transformar problemas NP em problemas P, cuja resolução por computador é mais viável, a novidade, divulgada recentemente pela revista "New Scientist", vem da Índia. Três pesquisadores desse país desenvolveram um programa de tempo polinomial para verificar se um número é primo ou não, problema até então considerado como NP. Ainda não se sabe ao certo o impacto da demonstração, mas o fato é que, mais uma vez, os indianos demonstram ao mundo a força e a tradição de sua pesquisa na área de computação e matemática.
José Luiz Pastore Mello é professor da Faculdade de Educação da USP
Leia a reportagem da "New Scientist" no site www.uol.com.br/inovacao/ultimas/ult762u636.shl
Leia mais:
Publicidade
As Últimas que Você não Leu
Publicidade
+ LidasÍndice
- Avaliação reprova 226 faculdades do país pelo 4º ano consecutivo
- Dilma aprova lei que troca dívidas de universidades por bolsas
- Notas das melhores escolas paulistas despencam em exame; veja
- Universidades de SP divulgam calendário dos vestibulares 2013
- Mercadante diz que não há margem para reajuste maior aos docentes
+ Comentadas
- Câmara sinaliza absolvição de deputados envolvidos com Cachoeira
- Alunos com bônus por raça repetem mais na Unicamp
+ EnviadasÍndice
