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

(שאלה רלוונטית לסטודנטים משנת 2025/2026) בשאלה זו נציג אלגוריתם להכפלת שתי מטריצות ריבועיות $A, B$ מסדר $n \times n$ מעל שדה פשוט. ניחו לשם פשטות כי $n$ הינו חזקה של $2$. תוצאת המכפלה הינה מטריצה $C = A \times B$ מסדר $n \times n$, שמקיימת $C_{i,j} = \sum_{1 \leq k \leq n} A_{i,k} \times B_{k,j}$. נפרק כל מטריצה ל-4 תתי-מטריצות מסדר $\frac{n}{2} \times \frac{n}{2}$, כדלקמן: $$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix},\quad B = \begin{pmatrix} e & g \\ f & h \end{pmatrix},\quad C = \begin{pmatrix} r & s \\ t & u \end{pmatrix}$$ מהגדרת כפל מטריצות: $$r = a \times e + b \times f,\quad s = a \times g + b \times h$$ $$t = c \times e + d \times f,\quad u = c \times g + d \times h$$ האלגוריתם מחשב את 7 המטריצות הבאות: $$P_3 = (c+d) \times e,\quad P_5 = (a+d) \times (e+h),\quad P_1 = a \times (g-h)$$ $$P_4 = d \times (f-e),\quad P_6 = (b-d) \times (f+h),\quad P_2 = (a+b) \times h$$ $$P_7 = (a-c) \times (e+g)$$ (א) הסבירו כיצד לחשב את $r, s, t, u$ באמצעות פעולות **חיבור וחיסור בלבד** על $P_1,...,P_7$ (ללא הכפלת מטריצות). לדוגמה: $u = -P_7 + P_5 + P_1 - P_3$ (אסורה הכפלת מטריצות). (ב) בדקו **כמה הכפלות של סקלרים** דרושות סה"כ לאלגוריתם הרקורסיבי שתואר בשאלה זו. (ניתן לפתור את סעיף ב' גם אם טועים בסעיף א'.)

רמז: בכל רמת רקורסיה מבצעים 7 כפלות רקורסיביות של מטריצות בגודל $n/2$. כתוב $T(n) = 7T(n/2)$ עם $T(1)=1$, ופתור לקבל $n^{\log_2 7}$.

פתרון: **סעיף (א) — חישוב $r, s, t, u$:** אימות: - $s = P_1 + P_2 = a(g-h) + (a+b)h = ag - ah + ah + bh = ag + bh$ ✓ - $t = P_3 + P_4 = (c+d)e + d(f-e) = ce + de + df - de = ce + df$ ✓ - $r = P_5 + P_6 - P_2 + P_4$: $(a+d)(e+h) + (b-d)(f+h) - (a+b)h + d(f-e)$ $= ae+ah+de+dh + bf+bh-df-dh - ah-bh + df-de = ae + bf$ ✓ - $u = -P_7 + P_5 + P_1 - P_3$ (נתון בשאלה): $-(a-c)(e+g) + (a+d)(e+h) + a(g-h) - (c+d)e$ $= -ae-ag+ce+cg + ae+ah+de+dh + ag-ah - ce-de = cg + dh$ ✓ **סיכום:** $$s = P_1 + P_2,\quad t = P_3 + P_4,\quad r = P_5 + P_6 - P_2 + P_4,\quad u = -P_7 + P_5 + P_1 - P_3$$ --- **סעיף (ב) — מספר הכפלות של סקלרים:** בכל שלב רקורסיבי מחשבים **7 כפלות** של מטריצות גודל $\frac{n}{2} \times \frac{n}{2}$; שאר הפעולות הן חיבורים/חיסורים (ללא כפלות סקלריות נוספות). נוסחת הנסיגה למספר הכפלות של סקלרים: $$T(n) = 7 \cdot T\!\left(\frac{n}{2}\right), \quad T(1) = 1$$ פתרון: $T(n) = 7^{\log_2 n} = n^{\log_2 7}$. **אימות עם משפט האב:** כולל גם עלות החיבורים, $T(n) = 7T(n/2) + O(n^2)$. כאן $a=7,\ b=2,\ f(n)=O(n^2)$. מכיוון ש-$\log_2 7 \approx 2.807 > 2$, לפי מקרה 1 של משפט האב: $T(n) = \Theta(n^{\log_2 7})$. **מסקנה:** מספר הכפלות הסקלריות = $\Theta(n^{\log_2 7})$.