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

שאלה 1 – FFT וטרנספורמציה דיסקרטית של פורייה (עמוד 4) על שני הספקים הנסיונים של DFT בעזרת הפירוט הטריגונומטרי, נתונה הפולינום $p(x) = x^3 - 3x^2 + x + 4$ כשעל השורש בתיקיה של 4-שורשי היחידה. (ב) הציגו את כל החישובים של קרא הממרובכים בעזרת קרא $FFT$ מסדר 4 על מקדמי הפולינום $p(x) = x^3 - 3x^2 + x + 4$. קרא הממרובכים $FFT((u_4, 4, -3, 4), w = i)$ כאשר $w = e^{2\pi i/4}$.

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

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