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

שאלה 4 – יישומים של FFT (סכום של קבוצות-מספרים) נתונות שתי קבוצות של מספרים טבעיים $S, T \subseteq \{1, \ldots, n\}$ בגודלן $|S| = |T| = \Theta(n)$. סכומן של הקבוצות מוגדר בצורה $S \oplus T = \{z | \exists x \in S \exists y \in T \text{ such that } x + y = z\}$. למשל, עבור $S = \{1, 4\}, T = \{7, 10, 40\}$ מקבלים $S \oplus T = \{8, 11, 14, 41, 44\}$. הציגו אלגוריתם לחישוב הקבוצה $S \oplus T$ תוך ביצוע $\Theta(n \log n)$ פעולות אריתמטיות בסיסיות בלבד (של חיבור, חיסור, כפל, חילוק או השוואה של מספרים). העזרו באלגוריתם ה-FFT.

רמז: נסו לייצג את הקבוצות $S$ ו-$T$ באמצעות פולינומים. כיצד מכפלת הפולינומים הללו קשורה לקבוצת הסכומים $S \oplus T$?

פתרון: הרעיון המרכזי בפתרון הוא לייצג את הקבוצות $S$ ו-$T$ באמצעות פולינומים, ואז להשתמש ב-**FFT (התמרת פורייה מהירה)** כדי לחשב את מכפלתם ביעילות. מכפלת הפולינומים מקודדת בתוכה את כל סכומי האיברים האפשריים. **1. ייצוג פולינומיאלי** נגדיר שני פולינומים, $P_S(x)$ ו-$P_T(x)$, המייצגים את הקבוצות $S$ ו-$T$ בהתאמה. הפולינומים יוגדרו כך שהמקדם של $x^k$ יהיה 1 אם $k$ שייך לקבוצה, ו-0 אחרת: $P_S(x) = \sum_{i \in S} x^i$ $P_T(x) = \sum_{j \in T} x^j$ מאחר ש-$S, T \subseteq \{1, \ldots, n\}$, הדרגה של כל אחד מהפולינומים היא לכל היותר $n$. כעת, נבחן את מכפלת הפולינומים, $P_C(x) = P_S(x) \cdot P_T(x)$: $P_C(x) = (\sum_{i \in S} x^i) \cdot (\sum_{j \in T} x^j) = \sum_{i \in S} \sum_{j \in T} x^{i+j}$ זוהי פעולת **קונבולוציה** של מקדמי הפולינומים. לפי הגדרת המכפלה, המקדם של $x^k$ בתוצאה, נסמנו $c_k$, הוא מספר הזוגות $(i, j)$ כך ש-$i \in S$, $j \in T$ ו-$i+j=k$. לכן, מספר טבעי $k$ שייך לקבוצת הסכומים $S \oplus T$ אם ורק אם קיים לפחות זוג אחד כזה, כלומר, אם ורק אם המקדם $c_k$ חיובי ($c_k > 0$). **2. האלגוריתם** האלגוריתם יתבסס על הרעיון של חישוב יעיל של מכפלת הפולינומים $P_S(x)$ ו-$P_T(x)$ באמצעות FFT. 1. **בניית וקטורי המקדמים:** ניצור שני וקטורים $A$ ו-$B$ באורך $n+1$. עבור כל $i$ מ-0 עד $n$, נגדיר: $A[i] = 1$ אם $i \in S$, ו-$A[i] = 0$ אחרת. $B[i] = 1$ אם $i \in T$, ו-$B[i] = 0$ אחרת. שלב זה דורש $O(n)$ פעולות. 2. **כפל פולינומים באמצעות FFT:** הדרגה המקסימלית של פולינום המכפלה $P_C(x)$ היא $n+n=2n$. כדי לחשב את הקונבולוציה בצורה נכונה (ללא "גלישה" ציקלית), נבחר $N$ שהוא חזקה של 2 ומקיים $N > 2n$. נרפד את הווקטורים $A$ ו-$B$ באפסים עד שיגיעו לאורך $N$. נשים לב ש-$N = \Theta(n)$. א. חשב את ההתמרות $\hat{A} = \text{FFT}(A)$ ו-$\hat{B} = \text{FFT}(B)$. ב. חשב את המכפלה הנקודתית (pointwise) של ההתמרות: $\hat{C}[k] = \hat{A}[k] \cdot \hat{B}[k]$ לכל $k=0, \ldots, N-1$. ג. חשב את ההתמרה ההופכית כדי לקבל את וקטור המקדמים של פולינום המכפלה: $C = \text{IFFT}(\hat{C})$. 3. **בניית קבוצת הפלט:** ניצור קבוצה ריקה, `SumSet`. נעבור על וקטור המקדמים $C$ מהאינדקס 0 ועד $2n$. עבור כל אינדקס $k$, אם $C[k]$ (לאחר עיגול, עקב אי-דיוקים נומריים אפשריים) גדול מ-0, נוסיף את $k$ לקבוצה `SumSet`. לבסוף, נחזיר את `SumSet`. **3. ניתוח סיבוכיות** - שלב 1 (בניית וקטורים): אורך הווקטורים הוא $n+1$, וגודל הקבוצות הוא $\Theta(n)$, לכן שלב זה לוקח $\Theta(n)$ זמן. - שלב 2 (כפל בעזרת FFT): גודל ההתמרה הוא $N=\Theta(n)$. חישוב FFT ו-IFFT לוקח $O(N \log N) = O(n \log n)$ פעולות אריתמטיות. המכפלה הנקודתית לוקחת $O(N) = O(n)$ פעולות. הסיבוכיות הכוללת של שלב זה היא $\Theta(n \log n)$. - שלב 3 (בניית קבוצת הפלט): אנו עוברים על $2n+1$ איברים בווקטור $C$. שלב זה לוקח $O(n)$ זמן. הסיבוכיות הכוללת של האלגוריתם נשלטת על ידי שלב ה-FFT, ולכן היא $\Theta(n \log n)$ פעולות אריתמטיות. $\blacksquare$