O que talvez não seja muito óbvio é que, apesar de usar apenas processamento mecânico, a máquina de diferenças é um computador digital (ela possui um clock, dado pela rotação de um eixo interno, e executa uma adição com carry a cada quatro rotações). Já os computadores analógicos podem ser bem mais bizarros, como o computador de sabão do post anterior.
Computadores analógicos possuem uma vantagem sobre os digitais: não estão presos aos mesmos limites computacionais. É bastante simples construir, por exemplo, um circuito, utilizando amplificadores operacionais, que resolva equações diferenciais complexas em tempo bem inferior a um computador digital (embora o processo prejudique a precisão).
Um exemplo mais curioso é o problema da ordenação de um conjunto de números. É possível demonstrar que um computador digital, usando como elemento básico de computação a comparação de dois valores, não pode ser melhor que O(n log n) (essa demostração está em qualquer livro básico de algoritmos, como o Cormen). Mas os computadores analógicos não tem essa restrição, sendo que existe até mesmo um algoritmo que resolve em O(1)!
Uma implementação simples desse algoritmo é com ábacos: primeiro você dispõe os números que você quer ordenar na base unária, como estão os números 2, 4, 1, 3, 3 na figura abaixo:
Depois, basta levantar o ábaco e deixar a gravidade fazer seu serviço:
Como o Bead Sort usa operações analógicas, não dá pra analisar de verdade a complexidade computacional dele. Quando fazemos análises de big-oh, queremos saber quantos passos o algoritmo leva pra terminar, e o Bead Sort tem só um passo (levantar o ábaco), sendo que nesse aspecto ele é O(1) mesmo. Mas intuitivamente, o que queremos quando fazemos análise de complexidade é descobrir como o tempo de execução varia com o tamanho da entrada. Desse ponto de vista, a complexidade é O(sqrt(n)), se você considerar o tempo que uma bolinha leva pra ser puxada pela gravidade (no vácuo), ou então O(n), se você levar em conta que a bolinha vai atingir uma velocidade terminal devido à resistência do ar.
No excelente livro "The Armchair Universe", do A. K. Dewdney (fora de catálogo há um tempão, mas tive a sorte de trombar com ele baratinho na Livraria Triângulo), há dois capítulos com um monte de exemplos de computação analógica. Entre eles, está a... ordenação spaghetti!
ResponderExcluirTem a ordenação por panquecas também, que inclusive foi tema de um paper escrito pelo Bill Gates :)
ResponderExcluirO principal problema dessas computadores de valvulas são os BUGS, e nao os de programação!
ResponderExcluirVc lembra de quando as formigas invadiam videos cassetes?
era real aquele lance?
Ah, esse computador do Babbage não é com válvulas, é com engrenagens! Se entrasse algum bug, ele seria esmagado :)
ResponderExcluirO lance das formigas procede sim, quando você vai soldar uma placa de circuito impresso, você usa uma substância chamada fluxo pra ficar mais fácil, e até onde eu lembro, formigas gostam de fluxo.
Faala, Ricibit!! Gostaria de sugerir um artigo sobre computação analógica, vi agora a pouco algo interessante sobre ordenação analógica nesse link aqui:
ResponderExcluirhttp://hrl.harvard.edu/analog/ ... T+!!
Uia, parece bacana mesmo.
ResponderExcluir