שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2022 - התמרת פורייה מהירה

**(א)** נתון כי הטבעי $m$ מחלק את הטבעי $n$. מהו הפלט של $\text{DFT}_m$ מסדר $m$, כאשר הקלט הוא וקטור המקדמים של הפולינום $p(x)=x^n$? **(ב)** הציגו את כל החישובים מעל שדה המרוכבים (לרבות הקריאות הרקורסיביות) במסגרת הרצת FFT מסדר 4 ($\text{FFT}(\cdot,\omega_4)$) על מקדמי הפולינום $p(x)=x^3+4x^2-2x+3$.

רמז: בסעיף (א) אין צורך בחישוב — הציבו שורש יחידה מסדר $m$ בפולינום $x^n$ ושאלו מה נותנת ההנחה $m\mid n$. בסעיף (ב) רשמו את המקדמים לפי סדר **עולה** של החזקות והמשיכו לפי מבנה ההפרד-ומשול הרגיל.

פתרון: **(א)** נעריך את $p(x)=x^n$ בשורשי היחידה מסדר $m$, $\;\omega=e^{2\pi i/m}$: לכל $k$ מתקיים $p(\omega^k)=(\omega^k)^n=\omega^{kn}$. מכיוון ש-$m\mid n$ נכתוב $n=mq$, ואז $\omega^{kn}=(\omega^m)^{kq}=1^{kq}=1$. לכן **הפלט הוא $(1,1,\dots,1)$** ($m$ אחדים). **(ב)** וקטור המקדמים $(3,-2,4,1)$, $\;\omega=i$: - $\text{FFT}((3,-2,4,1),\,\omega=i)$: - **זוגיים** $\text{FFT}((3,4),\,\omega^2=-1)$: $\;\text{FFT}(3)=3,\ \text{FFT}(4)=4$, מחזיר $(3+\omega^0\!\cdot 4,\ 3+\omega^2\!\cdot 4)=(7,-1)$. - **אי-זוגיים** $\text{FFT}((-2,1),\,\omega^2=-1)$: $\;\text{FFT}(-2)=-2,\ \text{FFT}(1)=1$, מחזיר $(-2+\omega^0\!\cdot 1,\ -2+\omega^2\!\cdot 1)=(-1,-3)$. - **שילוב** ($E=(7,-1),\ O=(-1,-3)$): $\;y_0=7+i^0(-1)=6,\quad y_1=-1+i^1(-3)=-1-3i,\quad y_2=7-i^0(-1)=8,\quad y_3=-1-i(-3)=-1+3i$. **הפלט:** $(6,\ -1-3i,\ 8,\ -1+3i)$. (בדיקה: $p(1)=6,\ p(i)=-1-3i,\ p(-1)=8,\ p(-i)=-1+3i$.) $\blacksquare$