Page 26 - Telebrasil - Julho/Agosto 1980
P. 26
Novo teorema matemático, referente ao Algoritmo Polinomial, descoberto pelo cientista sovié
tico de 27 anos, Leonid Genrikhovich Khachiyan, está revolucionando a solução de problemas
envolvendo grande número de variáveis.
Como reporta C. R. Whitney, do New York O tema em si é importante, sendo retomado por
Times, e reproduzido no Jornal do Brasil, os Leônidas Hegenberg rio O Estado de S. Pau
especialistas acreditam que ela pode ser apli lo, quando fala sobre as limitações do computa
cada a problemas até então insolúveis, como a dor e da inteligência humana, dizendo que a si
previsão do tempo, e outros que dependem de tuação tem um paralelo na viagem espacial.
muitas e diferentes variáveis. Há quem afirme Para atingir um ponto do espaço, o viajante pre
que pode servir até na decifração de códigos se cisa realizar um movimento que requer tempo e
cretos. O método do tratam ento soviético energia. Como o tempo e a energia são fatores
oferece uma aproximação para a programação de que dispomos limitadamente, as porções
linear de computadores na solução dos chama acessíveis, no universo, também são limitadas.
dos “ problemas de viagem do vendedor’ ’. Tais Analogamente, para conhecer teoremas da ma
problemas estão entre os de mais difícil solução temática, são indispensáveis “ movimentos Mas há diversos problemas de grande impor
em matemática. Envolvem, por exemplo, a ótimos” (em um jogo matemático), que reque tância prática — digamos, determinação das
descoberta do caminho mais curto através do rem cálculos que, por sua vez, consomem raízes de um polinómio, resolução de sistemas
qual um vendedor poderia visitar numerosas ci tempo e energia. Existindo quantidades limita de equações não lineares, otimização de uma
dades sem que fosse preciso passar duas vezes das de tempo e de energia, limita-se a porção função de várias variáveis, etc., cujos custos
pela mesma cidade. acessível do universo matemático. são muito elevados. Um problema aparente
mente simples, como o da determinação do
Cada vez que uma nova cidade é acrescentada “ melhor caminho” que um vendedor deve se
ao trajeto, o problema se toma incrivelmente A potência dos computadores guir, visitando n cidades, para retornar ao
complexo. Numerosíssimas variáveis devem limita o uso dos algoritmos. ponto de partida, atinge custos proibitivos e.
ser calculadas com várias equações, usando um por exemplo, n = 100. (Em verdade, o custo
sistema de programação linear. Em um certo t computacional excede a capacidade de qual
ponto, a complexidade se torna tão grande, que Dado um sistema de duas equações lineares, quer procedimento computacional hoje exis
um computador precisaria de bilhões de anos com duas incógnitas, o processo de resolução tente).
para achar uma solução. por eliminação (devido a Gauss) requer, ao
todo, nove operações aritméticas. O processo cm resumo, numerosos problemas (de mate
de eliminação, que caracteriza um algoritmo, mática, de lógica, da área da inteligência artifi
D os egípcios até hoje a aplica-se a um número qualquer de n equações, ciai, etc.) não podem ser resolvidos porque o*
com n incógnitas. Um algoritmo é um método custos computacionais envolvidos excedem s
matemática impulsiona o
que considera os dados do problema (cm nosso potência de qualquer computador conhecido
progresso. caso, os coeficientes das incógnitas nas equa (Em verdade, há casos em que o custo excede
ções incialmentc fornecidas) e os transforma, para qualquer algoritmo que possa existir, a po
passo a passo, até a obtenção dos valores das tência dos computadores.).
Até hoje, os problemas de viagem do vende incógnitas.
dor, inclusive a escalação eficiente de tripula
ções aéreas ou equipes de enfermagem cm hos Num sistema de n equações lineares, com n in
pitais, têm sido resolvidos pelo “ método cógnitas, o número de operações requerido
simplex” , inventado por George B. Dantzig, para resolver o sistema é 2/3 n’ + 3/2 n2 - 7/
da Universidade de Stanford. Como regra, o 6 n (número esse que recebeu o nome de custo Selos do Papa
método simplex funciona, mas não oferece computacional do algoritmo). Crescendo n,
garantia de que, após um certo número de cresce, concomitantemente, o custo — que, Os cinco selos comemorativos da visita do
operações no computador, encontrará sempre aliás, cresce mais rapidamente do que n. Imple Papa foram emitidos com uma tiragem total
uma resposta. Á abordagem de Khachiyan mentando um algoritmo, para um computador, de 19 milhões de exemplares—-cincomi-
oferece um meio de dizer com certeza desde o é preciso lembrar que o custo não deve exceder lhões de cada selo de circulação nacional e
começo se o problema terá solução ou não dado o número de operações aritiméticas que o com três milhões de cada um para os de postagem
certo número de operações. putador pode realizar em um razoável intervalo para o exterior.
de tempo. Os primeiros computadores podiam
Dois matemáticos, pesquisadores em Stanford, realizar de cem a mil operações por segundo. Os selos destinam-se à circulação no Brasil
já aplicaram o método Khachiyan no aperfei Hoje, são realizadas de 10 a 100 milhões de (Papa e as catedrais de São Pedro e de
çoamento de um programa para calculador de operações aritméticas por segundo — isto é, Fortaleza), nos Estados Unidos (Papa e a ca
bolso, que solucionou problemas até então não menos de 1013 operações por dia. Usando o al tedral do Rio de Janeiro), América Latina
resolvidos pelo método simplex. Matematica goritm o gaussiano, podemos resolver, por (Papa e a catedral de Aparecida do Norte) e
mente, o método de Khachiyan Usa equações tanto, no m áxim o,.3 x IO4 equações lineares A sia e E uropa (Papa e a catedral de
para criar clipsóidcs imaginárias que encap por dia. (Até hoje, ao que parece, apenas um Brasília).
sulam a solução, ao contrário do método sim algoritm o, elaborado por V. Strassen, em »
plex, no qual a resposta é representada pelas in 1968, tem custo inferior ao algoritmo de elimi Para os filatelistas, o edital da série tem
terseções dos lados dos poliedros. À medida nação, para a resolução de sistemas de equa valor inestimável, pois foi impresso em la
que as clipsóidcs vão diminuindo, a resposta é ções lineares — mas o algoritmo gaussiano tim, língua oficial da Santa Sé.
conhecida com maior precisão. ainda é o mais comumente empregado.).