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

נביט בפולינום $p(x) = 5x^3 - 2x^2 + 3x - 4$. הציגו את כל החישובים מעל שדה המרוכבים (לרבות הקריאות הרקורסיביות) במסגרת הרצת FFT מסדר 4 (הרצת FFT על מקדמי הפולינום) (22 נק'). בדקו את תשובתכם ע"י הצבה ישירה של הערכים המתאימים בפולינום (3 נק').

רמז: התחילו על ידי חלוקת וקטור המקדמים של הפולינום לשני תת-וקטורים, אחד עבור המקדמים במקומות הזוגיים ואחד עבור המקדמים במקומות האי-זוגיים, והפעילו רקורסיבית את אלגוריתם ה-FFT על כל אחד מהם.

פתרון: מטרתנו היא לחשב את **התמרת פורייה הבדידה (DFT)** של וקטור מקדמי הפולינום $p(x) = 5x^3 - 2x^2 + 3x - 4$. וקטור המקדמים הוא $a = (a_0, a_1, a_2, a_3) = (-4, 3, -2, 5)$. חישוב ה-DFT שקול להערכת הפולינום $p(x)$ ב**שורשי היחידה** מסדר 4: $\omega_4^0, \omega_4^1, \omega_4^2, \omega_4^3$. אלגוריתם **FFT (Fast Fourier Transform)** מבצע זאת ביעילות באמצעות גישת **הפרד ומשול**. **שלב 1: הפרד (Divide)** נחלק את וקטור המקדמים $a$ לשני תת-וקטורים: * וקטור המקדמים במקומות הזוגיים: $a_{even} = (a_0, a_2) = (-4, -2)$ * וקטור המקדמים במקומות האי-זוגיים: $a_{odd} = (a_1, a_3) = (3, 5)$ **שלב 2: כבוש (Conquer) - קריאות רקורסיביות** נחשב את ה-FFT רקורסיבית עבור כל תת-וקטור. מדובר ב-DFT מסדר 2. שורשי היחידה מסדר 2 הם $\omega_2^0=1, \omega_2^1=-1$. חישוב $y_{even} = \text{FFT}(a_{even}) = \text{FFT}(-4, -2)$: $y_{even,0} = a_{even,0} \cdot \omega_2^0 + a_{even,1} \cdot \omega_2^0 = -4 \cdot 1 + (-2) \cdot 1 = -6$ $y_{even,1} = a_{even,0} \cdot \omega_2^0 + a_{even,1} \cdot \omega_2^1 = -4 \cdot 1 + (-2) \cdot (-1) = -4 + 2 = -2$ לכן, $y_{even} = (-6, -2)$. חישוב $y_{odd} = \text{FFT}(a_{odd}) = \text{FFT}(3, 5)$: $y_{odd,0} = a_{odd,0} \cdot \omega_2^0 + a_{odd,1} \cdot \omega_2^0 = 3 \cdot 1 + 5 \cdot 1 = 8$ $y_{odd,1} = a_{odd,0} \cdot \omega_2^0 + a_{odd,1} \cdot \omega_2^1 = 3 \cdot 1 + 5 \cdot (-1) = 3 - 5 = -2$ לכן, $y_{odd} = (8, -2)$. **שלב 3: אמזג (Combine)** נשלב את התוצאות מהשלב הרקורסיבי. שורשי היחידה מסדר 4 הם $\omega_4^0 = 1, \omega_4^1 = i, \omega_4^2 = -1, \omega_4^3 = -i$. נוסחאות השילוב עבור $k=0, 1$ הן: $y_k = y_{even,k} + \omega_4^k \cdot y_{odd,k}$ $y_{k+2} = y_{even,k} - \omega_4^k \cdot y_{odd,k}$ עבור $k=0$: $y_0 = y_{even,0} + \omega_4^0 \cdot y_{odd,0} = -6 + 1 \cdot 8 = 2$ $y_2 = y_{even,0} - \omega_4^0 \cdot y_{odd,0} = -6 - 1 \cdot 8 = -14$ עבור $k=1$: $y_1 = y_{even,1} + \omega_4^1 \cdot y_{odd,1} = -2 + i \cdot (-2) = -2 - 2i$ $y_3 = y_{even,1} - \omega_4^1 \cdot y_{odd,1} = -2 - i \cdot (-2) = -2 + 2i$ התוצאה הסופית של ה-FFT היא הווקטור: $y = (2, -2 - 2i, -14, -2 + 2i)$ **בדיקת התשובה** נבדוק את התוצאה על ידי הצבה ישירה של שורשי היחידה מסדר 4 בפולינום $p(x) = 5x^3 - 2x^2 + 3x - 4$. * $x = \omega_4^0 = 1$: $p(1) = 5(1)^3 - 2(1)^2 + 3(1) - 4 = 5 - 2 + 3 - 4 = 2$. תואם ל-$y_0$. * $x = \omega_4^1 = i$: $p(i) = 5(i)^3 - 2(i)^2 + 3(i) - 4 = 5(-i) - 2(-1) + 3i - 4 = -5i + 2 + 3i - 4 = -2 - 2i$. תואם ל-$y_1$. * $x = \omega_4^2 = -1$: $p(-1) = 5(-1)^3 - 2(-1)^2 + 3(-1) - 4 = -5 - 2 - 3 - 4 = -14$. תואם ל-$y_2$. * $x = \omega_4^3 = -i$: $p(-i) = 5(-i)^3 - 2(-i)^2 + 3(-i) - 4 = 5(i) - 2(-1) - 3i - 4 = 5i + 2 - 3i - 4 = -2 + 2i$. תואם ל-$y_3$. הבדיקה מאשרת את נכונות התוצאה. $\blacksquare$