Cortesia de ensinounivates
Dez algoritmos que abalaram o mundo
«Quando o matemático islâmico Muhammad al-Khwarizmi publicou, na primeira metade do século IX, a sua obra Hisab al-jabr wa'l muqabalah, não podia imaginar que quer o seu nome quer o seu livro seriam imortalizados durante milénios pelos então bárbaros do Ocidente.
O seu livro sintetizava o conhecimento sobre a resolução analítica de equações, apresentava a fórmula resolvente do segundo grau e introduzia um formalismo matemático avançado e o sistema de numeração árabe que hoje usamos. A partir de al-Khwarizmi, o termo al-jabr tornou-se sinónimo de resolver equações (Álgebra). E o nome de al-Khwarizmi deu, por outro lado, origem a algarismo para designar cada um dos dígitos da numeração árabe - e algoritmo - o termo moderno que designa um procedimento sistemático para resolver problemas matemáticos.
Cortesia de fernandoquadro
Se vivesse nos nossos dias, al-Khwarizmi decerto ficari a apaixonado pelo número especial da revista Computing in Science and Engineering de Janeiro de 2000. Jack Dongarra, da Universidade do Tennessee, e Francis Sullivan, do Institute for Defense Analysis, elaboraram um trabalho notável:
- a lista dos dez algoritmos com maior influência no desenvolvimento e na prática da ciência e da engenharia no século XX. Em suma, o Top Ten dos algoritmos do século XX.
Eis então, por ordem cronológica, os dez algoritmos que abalaram o Mundo.
1. O Método de Monte Carlo (Metropolis, Ulam e von Neumann, 1946). O matemático polaco Stan Ulam estava no hospital a recuperar de um esgotamento provocado pelo esforço de guerra (Ulam tinha feito parte do Projecto Manhattan, que em Los Alamos desenvolveu a bomba atómica). Para se entreter, tentou calcular a probabilidade de obter uma mão perfeita no jogo de cartas Solitário. Como o problema é difícil, teve a ideia de aproximar essa probabilidade simulando a distribuição de cartas e observando a frequência relativa.
2. O Método do Simplex (George Dantzig, l941). Na sequência da II Guerra Mundial e em vésperas da guerra da Coreia, o planeamento da logística militar estava na ordem do dia. Como optimizar uma função objectivo (minimizar custos de transporte de tropas, por exemplo) em face de restrições lineares?
3. Métodos iterativos de subespaços de Krylov (Hestenes, Lanczos e Stiefel, 1950). A resolução de sistemas de equações lineares é, pelo menos desde Gauss, um problema de extrema importância para aplicações científicas. O próprio Gauss criou o primeiro método verdadeiramente eficiente, a eliminação, que continua hoje a ser ensinado nas nossas universidades.
4. Métodos de decomposição para cálculos matriciais (Householder, l951).As operações matriciais constituem a maior parte do trabalho de análise numérica em problemas científicos e técnicos. Torna-se assim da maior importância conceber métodos que permitam realizar todo o tipo de cálculos matriciais da forma mais eficiente possível.
5. O compilador de Fortran (Backus, 1957). A criação do Fortran foi descrita como o acontecimento singular mais importante na história da programação de computadores. Por impossível que nos possa parecer hoje, antes do aparecimento do compilador de Fortran a programação de um computador era feita directamente em código máquina ou assembler por vezes mesmo ajustando interruptores no hardware! A revolução conceptual das linguagens de alto nível e o abrir de portas da era da informação deu-se com o Fortran.
Cortesia d eleonardomiranda777
6. O algoritmo QR (Francis, 1959-1961). A determinação de valores próprios é o problema mais importante, do ponto de vista das aplicações científicas e tecnológicas, do cálculo matricial. Os métodos básicos de Álgebra Linear, embora resolvam o problema, tornam-se impraticáveis quando as matrizes têm ordem superior, digamos, a 10. Por outro lado, são extremamente instáveis do ponto de vista numérico.
7. Quicksort (Tony Hoare, 1962). Em face dos problemas anteriores, o problema da ordenação parece quase pateticamente mundano. Dada uma lista de N objectos, como ordená-los de forma eficiente? A questão muda de figura se pensarmos na omnipresença deste problema; é raro ele não se colocar! O algoritmo Quicksort para a ordenação utiliza uma estratégia desarmantemente simples, chamada «dividir pata reinar».
8. A tranformada rápida de Fourier, FFT (Cooley e Tukey, 1965). Este é, provavelmente, o algoritmo do século. Com um pequeno artigo de cinco páginas, An algorithm for the machine calculation of complex Fourier series, Cooley e Tukey entraram para a História. O problema é simples de descrever. Calcular transformadas discretas de Fourier. Este problema é omnipresente na ciência e tecnologia actuais, no processamento de sinais ou na Física Matemática.
9. A detecção de relações inteiras (Ferguson e Forcade, 1977). Durante muito tempo, os cientistas sonharam com um método que lhes permitisse reconhecer uma constante numérica a partir da equação que ela satisfaz. Esse sonho foi realizado com o algoritmo das relações inteiras. Uma relação inteira é um algoritmo que, dados n números reais, constrói uma relação linear inteira entre eles (se existir), ou prova que ela não existe dentro de certos limites.
10. O algoritmo rápido multipolar (Greengard e Rokhlin, 1987). Até há pouco tempo era impraticável simular o comportamento de agregados de N partículas em interacção gravitacional ou electrostática, a não ser para N muito baixo. Sendo necessário entrar em conta com todos os pares de interacções, a simulação de um agregado de N partículas exige o cálculo de O(N2) (leia-se N ao quadrado) interacções.
Cortesia de vidageek
Estes são os dez algoritmos que, na opinião de Dongarra e Sullivan, mudaram o mundo. Merece um pouco de atenção, no entanto, compreender porque é que os algoritmos mudam o mundo, e porque é que eles são muito mais do que esperteza aplicada ou uma questão de eficiência na utilizaçáo de recursos.
O século XXI promete trazer a computação quântica, que provavelmente nos obrigará a fundir Teoria da Computação, Física e Lógica. Ainda antes de existirem computadores quânticos existem já algoritmos quânticos, como os da factorização de inteiros de Peter Shor, à espera deles». In Ciência Aberta, Gradiva Publicações, Jorge Buescu, 225100/2005.
Cortesia de Ciência Aberta/JDACT
