¿Cómo explicarías por qué la Transformada Rápida de Fourier es más rápida que el algoritmo ingenuo para calcular la Transformada Discreta de Fourier, si tuvieras que hacer una presentación sobre ella para el público general (no matemático)?
Respuestas
¿Demasiados anuncios?
re5et
Puntos
406
Puedes decirlo: Cuando $N$ es una potencia de $2$ la FFT de Cooley-Tukey divide la $N$ -Problema DFT a dos $\frac{N}{2}$ Problemas de DFT. Usando la misma idea, uno puede dividir aún más los dos $\frac{N}{2}$ Los problemas de DFT a cuatro $\frac{N}{4}$ -Problemas de DFT, y así sucesivamente... Al final, tienes $\log_2 N$ pasos con $O(N)$ operaciones a realizar en cada paso.
Como ha sugerido Harald Hanche-Olsen, se puede decir "divide y vencerás". La parte de la división es la idea de Cooley-Tukey, divides y divides; al final lo has conquistado todo.
Digas lo que digas, el público no matemático probablemente ya se habrá adormecido. Puedes despertarlos diciendo "Gauss conocía la FFT, pero no la publicó" para añadir algo de dramatismo.
dandu
Puntos
113
La pregunta es vieja, la respuesta necro es necro, pero igual me divertí escribiéndolas así que aquí van.
(todo ello como si se dirigiera al público de t3h)
- Si intentas calcular la DFT de forma ingenua, te encontrarás calculando las mismas cosas una y otra vez*. La FFT brilla por evitar este trabajo redundante. La moraleja de la historia es que debes dejar la tapa del inodoro bajada si tu casa está formada principalmente por mujeres.
- Si alguien recuerda la propiedad distributiva, puede pasar de $a*x+a*y$ à $a*(x + y)$ , ahorrándote una multiplicación. La FFT básicamente hace esto a la DFT ingenua, pero muchas veces más, y el ahorro se suma hasta el punto de ahorrar más de un millón de multiplicaciones para un solo cálculo de DFT de tamaño de muestra modesto**. El uso de una FFT hará que tu ordenador te alabe como un maestro justo y es probable que no intente matarte en el levantamiento de la máquina.
- Si se retuerce*** lo suficiente los pulgares, un programador llegará con un código convolutivo*** que haga Indiana Jones: Rader's*** del Arca Perdida parecen razonables. También será más rápido que hacer la DFT directamente desde la definición. Qué bien.
* (descargo de responsabilidad preventivo: hasta dentro de un factor de fase/término)
** $2^{10}$
*** Por favor, no me mates.
EDITAR: Sí, ha habido respuestas mucho menos conscientes de sí mismas. Un ejemplo: al público en general no le importan las diferencias en los diagramas de flujo (DIF vs. DIT vs. diagramas de flujo más capaces de ser representados en hardware paralelo a pesar de la codificación de la salida, etc.). La perspectiva histórica es una tontería, porque se aleja totalmente de la cuestión: que la FFT es más eficiente que la ejecución directa de la definición de la DFT. Sólo termina con algo de que es eficiente. Francamente no importa qué, si el público es en realidad general y en realidad con una formación matemática media. Cuanto más memorable sea, mejor. Si se trata de un punto importante, estar sereno durante toda la presentación y romper la compostura ligeramente (o simplemente cambiar un poco de comportamiento) para una sola diapositiva (o equivalente), aunque no necesariamente se lleve a cabo un punto de vista, llevará el punto de vista a la cara colectiva de la audiencia y lo recordarán .
Si es verdaderamente un público general, el contenido importa mucho menos que la entrega.
