FFT: Η Ιδιοφυΐα του Γκάους, η Επανάσταση των Cooley & Tukey

🎧 Ο Αλγόριθμος που Μας Έδωσε Ήχο, Εικόνα και Δεδομένα – 60 Χρόνια FFT

Πριν από 60 χρόνια, το 1965, δύο ερευνητές – οι James Cooley και John Tukey – παρουσίασαν έναν αλγόριθμο που θα γινόταν θεμέλιο για την επεξεργασία ψηφιακών σημάτων: τον γρήγορο Μετασχηματισμό Fourier (FFT). 

Ο αλγόριθμός τους μείωσε τον υπολογιστικό φόρτο ενός Διακριτού Μετασχηματισμού Fourier από $O(n^2)$ σε $O(nlog⁡n)$, επιτρέποντας επεξεργασία ήχου και εικόνας σε πραγματικό χρόνο.

Όμως λίγοι γνωρίζουν ότι... 160 χρόνια νωρίτερα, ένας νεαρός Carl Friedrich Gauss, μελετώντας τις τροχιές των αστεροειδών Pallas και Juno, είχε επινοήσει μια μέθοδο εκπληκτικά παρόμοια. Δεν τη δημοσίευσε ποτέ, ούτε ανέλυσε την αποδοτικότητά της. Η ιδέα όμως ήταν εκεί — θαμμένη στα χειρόγραφά του, πολύ πριν ακόμη ο Fourier διατυπώσει τη θεωρία του για τη θερμότητα.

Η εργασία των Cooley & Tukey ήρθε σε μια εποχή που οι υπολογιστές ξεκινούσαν να μεταμορφώνουν τον κόσμο. Ο FFT βρήκε εφαρμογή παντού: στις εικόνες JPEG, στη μουσική MP3, στη φασματοσκοπία, στα ραδιοτηλεσκόπια, ακόμα και στην κβαντική φυσική.

Ο FFT είναι ένας από τους σημαντικότερους αλγορίθμους του 20ού αιώνα – κομψός, θεμελιώδης και παγκοσμίως χρήσιμος. Και πίσω του κρύβεται μια σπάνια διαδρομή μαθηματικής σκέψης – από τον Γκάους στους σύγχρονους ψηφιακούς κόσμους.