Novo algoritmo revoluciona a fórmula “X / log (X)” até agora aceite pelos cientistas de computadores e pode abrir caminho a novas descobertas. O próprio autor da descoberta está “em choque” com a sua fórmula, que põe em causa tudo o que sabíamos sobre o espaço e tempo na computação.
“É uma espécie de abanão na minha visão do mundo”, começa por explicar Ryan Williams, investigador do Massachusetts Institute of Technology.”Ainda estou chocado com o facto de isto sequer existir”.
O tempo e o espaço de memória são as duas principais restrições à computação, explica a New Scientist.
Alguns problemas exigem muita memória, e outros muito tempo (ou ambas as coisas). O tempo em computação é o número de passos que um computador dá para realizar uma certa tarefa, e o espaço é o número de posições de memória que a mesma tarefa requer.
Se uma tarefa requer X passos, na pior das hipóteses, em que o computador precisa de aceder à sua memória para cada passo, precisará de X posições de memória — qualquer computação que leve X passos pode ser feita com X/log X de memória. Ou não?
Um novo artigo mostra que este rácio pode ser reduzido drasticamente — para a raiz quadrada de X / log X. Em vez de 100 ou 50 slots de memória, um problema de 100 passos podia ser reduzido a 15 slots.
O próprio investigador que descobriu esta fórmula, Ryan Williams, está “em choque” com a descoberta, que põe em causa tudo o que sabíamos sobre o espaço e tempo na computação.
Demorei meses a convencer-me de que não era falso”, diz. “Ainda é muito difícil para mim compreender o que está a acontecer. Posso percorrer todos os passos, a prova, e verificar que cada passo está correto e que é verdade. Mas, no final, continuo a interrogar-me”.
O especialista criou então um modelo que pode representar qualquer problema computacional e depois aplicou o novo algoritmo de avaliação de árvores, mostrando que podia reduzir drasticamente a quantidade de memória necessária. O algoritmo envolve truques matemáticos e “cancelamentos mágicos” que, em última análise, fornecem respostas válidas.
“É muito emocionante”, comenta Ian Mertz, da Universidade Charles, na República Checa, um dos investigadores que desenvolveu o novo algoritmo. “É sem dúvida um resultado contra-intuitivo, embora eu diga que os nossos algoritmos de avaliação de árvores já eram bastante contra-intuitivos.”
“Agora que sabemos que os algoritmos eficientes em termos de tempo podem ser eficientes em termos de espaço, podemos procurar soluções que sejam bastante boas tanto para o tempo como para o espaço ao mesmo tempo, e isso é útil num sentido real”, conclui.
