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

שאלה 4 – כמויות DFT, אלגוריתמים אלקטרומטריים על שני השיעומים המשפיעים בחייגים (16 נקודות לשאלה א, 17 נקודות לשאלה ב): (א) מסיר הטלמטוריה הדיסקרטית DFT, מסדר $n$, כשחלט הוא $(1,...,1)$, כמטבח כשחלט הוא $p(x) = 1 + x + x^2 + ... + x^{n-1}$ של פולינומים של המחרטות־וקטור־וקטור. (ב) נתונים שני מספרים מרוכבים $x = a + bi, y = c + di$ (כשמטבח זמן, כשמטבח זמן כשהנותנים של הנותנים של הנותנים), הניחו לחשוב את הנוסחה של הנוצא חישוב $x \cdot y = (a \cdot c - b \cdot d) + (a \cdot d + b \cdot c)i$ לחישוב זימנו של הנוצא חישוב של הנוסחה של המחרטות של חישוב $x \cdot y$. וגם היא הנוסחה של הנוסחה של המחרטות של חישוב $x \cdot y$ לחישוב זימנו של הנוסחה של המחרטות של חישוב של הנוסחה של המחרטות של חישוב של הנוסחה של המחרטות של חישוב 3 גרסאות של המחרטות של חישוב של חישוב של חישוב של חישוב של חישוב של חישוב של בגבול של מספרים מרוכבים.

רמז: עבור סעיף א', יש לחשב סכום של סדרה הנדסית ולהפריד למקרים לפי מנת הסדרה. עבור סעיף ב', נסו לבטא את החלק הממשי והמדומה של המכפלה תוך שימוש ב-3 מכפלות ממשיות בלבד, במקום ב-4.

פתרון: סעיף א' פתרון התמרת פורייה הדיסקרטית (DFT) של וקטור $a = (a_0, a_1, \dots, a_{n-1})$ מוגדרת כווקטור $y = (y_0, y_1, \dots, y_{n-1})$ כאשר הרכיב ה-$k$ נתון על ידי הנוסחה: $y_k = \sum_{j=0}^{n-1} a_j \omega_n^{kj}$ כאשר $\omega_n = e^{2\pi i / n}$ הוא **שורש היחידה** הפרימיטיבי מסדר $n$. בשאלה זו, וקטור הקלט הוא $a = (1, 1, \dots, 1)$, כלומר $a_j = 1$ לכל $j=0, \dots, n-1$. חישוב ה-DFT של וקטור זה שקול להערכת הפולינום $P(x) = \sum_{j=0}^{n-1} x^j$ בנקודות $\omega_n^k$ עבור $k=0, \dots, n-1$. נציב את וקטור הקלט בנוסחת ה-DFT: $y_k = \sum_{j=0}^{n-1} 1 \cdot \omega_n^{kj} = \sum_{j=0}^{n-1} (\omega_n^k)^j$ זוהי **סדרה הנדסית** עם איבר ראשון 1, מנה $q = \omega_n^k$, ו-$n$ איברים. נפריד לשני מקרים: 1. **מקרה $k=0$**: במקרה זה, מנת הסדרה היא $q = \omega_n^0 = 1$. הסכום הוא סכום של $n$ פעמים 1: $y_0 = \sum_{j=0}^{n-1} 1^j = \sum_{j=0}^{n-1} 1 = n$. 2. **מקרה $k \in \{1, 2, \dots, n-1\}$**: במקרה זה, המנה $q = \omega_n^k \eq 1$. ניתן להשתמש בנוסחה לסכום סדרה הנדסית: $y_k = \frac{(\omega_n^k)^n - 1}{\omega_n^k - 1} = \frac{(\omega_n^n)^k - 1}{\omega_n^k - 1}$ מכיוון ש-$\omega_n$ הוא שורש יחידה מסדר $n$, מתקיים $\omega_n^n = 1$. לכן, $(\omega_n^n)^k = 1^k = 1$. נציב חזרה ונקבל: $y_k = \frac{1 - 1}{\omega_n^k - 1} = \frac{0}{\omega_n^k - 1} = 0$. לסיכום, וקטור הפלט של ה-DFT הוא $y = (n, 0, 0, \dots, 0)$. $\blacksquare$ **סעיף ב'** המטרה היא לחשב את המכפלה של שני מספרים מרוכבים $x = a+bi$ ו-$y = c+di$ תוך שימוש במספר מינימלי של פעולות כפל בין מספרים ממשיים. הדרך הסטנדרטית לחישוב המכפלה היא: $x \cdot y = (a+bi)(c+di) = (ac - bd) + (ad + bc)i$ החלק הממשי הוא $Re(xy) = ac - bd$ והחלק המדומה הוא $Im(xy) = ad + bc$. חישוב זה דורש **ארבע** פעולות כפל של מספרים ממשיים ($ac, bd, ad, bc$) ושתי פעולות חיבור/חיסור. ניתן לבצע את החישוב ביעילות רבה יותר באמצעות **שלוש** פעולות כפל ממשיות בלבד, בשיטה המיוחסת לגאוס. נגדיר שלוש מכפלות עזר ממשיות: 1. $P_1 = a \cdot c$ 2. $P_2 = b \cdot d$ 3. $P_3 = (a+b) \cdot (c+d) = ac + ad + bc + bd$ כעת נבטא את החלק הממשי והמדומה של $x \cdot y$ באמצעות $P_1, P_2, P_3$: החלק הממשי הוא $ac - bd$, וניתן לחשב אותו ישירות מ-$P_1$ ו-$P_2$: $Re(xy) = P_1 - P_2$ החלק המדומה הוא $ad + bc$. ניתן לבודד אותו מ-$P_3$ על ידי חיסור $P_1$ ו-$P_2$: $ad + bc = (ac + ad + bc + bd) - ac - bd = P_3 - P_1 - P_2$ $Im(xy) = P_3 - P_1 - P_2$ האלגוריתם המשופר הוא: 1. חשב את שלוש המכפלות $P_1, P_2, P_3$. 2. חשב את החלק הממשי: $Re = P_1 - P_2$. 3. חשב את החלק המדומה: $Im = P_3 - P_1 - P_2$. שיטה זו דורשת **3** פעולות כפל ממשיות בלבד, לעומת 4 בשיטה הנאיבית. היא דורשת יותר פעולות חיבור/חיסור (5 לעומת 2), אך היא עדיפה כאשר פעולות כפל יקרות משמעותית מפעולות חיבור. רעיון זה של הפחתת מספר הכפלים על חשבון הגדלת מספר פעולות החיבור/חיסור עומד בבסיס אלגוריתמי **הפרד ומשול** מהירים כמו אלגוריתם **קראצובה** להכפלת מספרים גדולים ואלגוריתם **שטרסן** להכפלת מטריצות. $\blacksquare$