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

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

רמז: רשמו תחילה את וקטור המקדמים לפי סדר **עולה** של החזקות — שימו לב שזה אינו הסדר שבו הפולינום כתוב — וזכרו ש-$\omega_4=e^{2\pi i/4}$. משם המשיכו לפי מבנה ההפרד-ומשול הרגיל של FFT.

פתרון: **וקטור הקלט.** לפי סדר עולה של החזקות, $a = (a_0, a_1, a_2, a_3) = (2, -3, 4, -5)$. שורש היחידה הוא $\omega_4 = e^{2\pi i/4} = i$, ומתקיים $\omega_4^0 = 1$, $\omega_4^1 = i$, $\omega_4^2 = -1$, $\omega_4^3 = -i$. **פיצול (הפרד ומשול).** מפרידים למקדמים במקומות הזוגיים ובמקומות האי-זוגיים: $$a^{[0]} = (a_0, a_2) = (2, 4), \qquad a^{[1]} = (a_1, a_3) = (-3, -5)$$ כלומר $p^{[0]}(x) = 2 + 4x$ ו-$p^{[1]}(x) = -3 - 5x$, ומתקיים $p(x) = p^{[0]}(x^2) + x \cdot p^{[1]}(x^2)$. **קריאה רקורסיבית 1: $\mathrm{FFT}((2,4), \omega_2)$**, כאשר $\omega_2 = -1$. הפיצול הוא לשני וקטורים באורך $1$: $(2)$ ו-$(4)$, ובבסיס הרקורסיה $\mathrm{FFT}((c), \omega_1) = (c)$. האיחוד עם $\omega_2^0 = 1$: $$y^{[0]}_0 = 2 + 1 \cdot 4 = 6, \qquad y^{[0]}_1 = 2 - 1 \cdot 4 = -2$$ כלומר $y^{[0]} = (6, -2)$ — אלו הערכים $p^{[0]}(1)$ ו-$p^{[0]}(-1)$. **קריאה רקורסיבית 2: $\mathrm{FFT}((-3,-5), \omega_2)$.** באותו אופן, מ-$(-3)$ ו-$(-5)$: $$y^{[1]}_0 = -3 + (-5) = -8, \qquad y^{[1]}_1 = -3 - (-5) = 2$$ כלומר $y^{[1]} = (-8, 2)$ — אלו הערכים $p^{[1]}(1)$ ו-$p^{[1]}(-1)$. **איחוד (שלב הפרפר) מסדר $4$.** לפי $y_k = y^{[0]}_k + \omega_4^k y^{[1]}_k$ ו-$y_{k+2} = y^{[0]}_k - \omega_4^k y^{[1]}_k$ עבור $k = 0, 1$: עבור $k = 0$ (עם $\omega_4^0 = 1$): $$y_0 = 6 + 1 \cdot (-8) = -2, \qquad y_2 = 6 - 1 \cdot (-8) = 14$$ עבור $k = 1$ (עם $\omega_4^1 = i$): $$y_1 = -2 + i \cdot 2 = -2 + 2i, \qquad y_3 = -2 - i \cdot 2 = -2 - 2i$$ **הפלט.** $$\mathrm{FFT}(a, \omega_4) = \big(y_0, y_1, y_2, y_3\big) = \big(-2,\; -2 + 2i,\; 14,\; -2 - 2i\big)$$ המתאימים לערכי הפולינום בנקודות $1,\, i,\, -1,\, -i$ בהתאמה. **בדיקה בהצבה ישירה.** $$p(1) = -5 + 4 - 3 + 2 = -2 \;\checkmark$$ $$p(i) = -5i^3 + 4i^2 - 3i + 2 = 5i - 4 - 3i + 2 = -2 + 2i \;\checkmark$$ $$p(-1) = 5 + 4 + 3 + 2 = 14 \;\checkmark$$ $$p(-i) = -5(-i)^3 + 4(-i)^2 + 3i + 2 = -5i - 4 + 3i + 2 = -2 - 2i \;\checkmark$$ כל ארבעת הערכים תואמים לפלט ה-FFT. $\blacksquare$