Um Algoritmo pode revolucionar o mundo
Autor: Pedro Luis Kantek Garcia Navarro


O fato que descreveremos a seguir é verídico, aconteceu não faz muito tempo, é uma prova cabal de que a informática veio para ficar e revolucionar o mundo.

Desde os primórdios do estudo da eletricidade, e depois da eletrônica, conhecem-se ferramentas para manusear matematicamente equações que permitam projetar, construir e testar os mais diversos circuitos e equipamentos.

Uma das melhores contribuição deve-se a Fourier, matemático Francês, que em 1820 bolou o algebrismo necessário para simplificar o tratamento usado para calcular e manusear sinais elétricos. Ele só não publicou estes resultados na época, pois os submeteu antes a 3 grandes matemáticos, e um deles (Legendre) achou que os resultados não conduziam a nada, embora os outros dois, tenham achado a teoria excelente.

Afinal, este tratamento veio a ser conhecido como Transformada de Fourier. Em última análise, ele permite transformar equações diferenciais (que realmente modelam o mundo físico) em produtos, que são aritmeticamente definidos.

O procedimento é razoavelmente simples. Uma transformação similar é conhecida por todo mundo que tem mais de 34 anos. Até 20 anos atrás, não existiam calculadoras, e todo estudante de segundo grau (antigo curso científico) estudava, conhecia e usava uma tabela de logaritmos.

O que se faz usando a transformada de Fourier, é muito parecido com o que se fazia usando logaritmos. Vejamos um esquema simplificador:


Com o conceito de transformada, o problema original se simplifica e pode mais facilmente ser resolvido. Matematicamente a transformada de Fourier de uma função genérica v(t) é igual a:


Estes símbolos não devem assustar; as transformadas estão tabeladas e é só consultar qualquer referência para achar a transformada de uma função.

Para se calcular o valor de uma integral em um computador, é necessário transformá-la em um somatório (isto é, passar do domínio contínuo para o domínio discreto). Com isto a transformada fica:



Este algoritmo tem um custo computacional proporcional a n2, ele demanda n ao quadrado multiplicações. Isto torna a fórmula inaceitável para valores de n grandes (que é o caso mais comum).

Na tabela a seguir, quantas multiplicações seriam necessárias para calcular a transformada em função do valor n.

Valor de n                      Quantidade de multiplicações
10                                    100
100                                  10.000
1.000                               1.000.000
1.000.000                       1.000.000.000.000

Segundo palavras do autor Brigham Jr, no livro The Fast Fourier Transform,”... even with a large computers, compilation of a Fourier Transform requires excessive machine time for large N”.

Nesse ponto começa a nossa história. Estamos no ano de 1965. O Presidente Lindon Johnson dos EUA tinha um comitê de aconselhamento científico. Dele faziam parte dois cientistas, Richard Garwin e John Tuckey. O primeiro precisava desesperadamente calcular muitas transformadas de Fourier com rapidez, e o segundo estava calmamente resolvendo, com papel e lápis, algumas T.F. cabeludas.

Garwin, chegou, viu e se interessou pelo assunto. Ele questionou Tuckey sobre o que este estava fazendo. Tuckey mostrou sua nova abordagem T.F. para resolver para resolver T.F.

Garwin era da área de informática, voltou logo ao centro de pesquisa da IBM em Yorktown Heighs para ter a técnica de Tuckey implementada em computador.

Achou um programador recém-contratado, que perambulava sem nada importante para fazer, e entregou a encomenda para ele. Seu nome era James Cooley e ele fez e implementou o programa. Segundo suas palavras “...achei que o projeto seria esquecido, e eu mesmo logo o esqueci.

Mas, aconteceu o contrário. Começaram a chegar requisições para obter cópias do programa, a comunidade acadêmica ficou em polvorosa, e a seguir Cooley e Tuckey publicaram hoje famoso “An algorithm for the machine calculation of complex Fourier series.”

Estava criado o algoritmo Cooley/Tuckey, também conhecido como FFT, de faz fourier transform”. Com ele o custo computacional de calcular a transformada de Fourier, caiu de n2 para N.log2 N. Vamos olhar a mesma tabela vista acima, agora para o algoritmo FFT.

Valor de n                      Quantidade de multiplicações 10 32
100                                  650
1.000                               9.800
1.000.000                       20.000.000

A Transformada de Fourier encontra aplicação em toda a moderna eletrônica. Qualquer sistema que necessite enviar e receber sinais através de meios de comunicação usa e abusa destes conceitos. Nesta definição, cabem sistemas de comunicação (rádio, TV, fax, telex, transmissão digital etc).

Além desta aplicação principal, a T.F. é usada em antenas dos mais diversos tipos, equipamentos óticos, probabilidades e processos rândomicos, física quântica (o princípio da incerteza é associado a uma T.F). problemas de contorno e muita, muita, muita coisa mais.

Não é coincidência que os anos 60/70/80 tenham visto um desenvolvimento da eletrônica que ainda está para ser compreendido e avaliado, mas que certamente é maior do que qualquer outro melhoramento importante da história humana.


Recomendar esta página via e-mail: