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.).
   21   22   23   24   25   26   27   28   29   30   31