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

קורס: אלגוריתמים

אוניברסיטה: האוניברסיטה הפתוחה

שנה: 2021

סמסטר: ב

נושאים: התמרת פורייה מהירה, ניתוח אלגוריתמים, סיבוכיות

רמת קושי: בינוני-קשה

**הנחיות:** אסור להשתמש באלגוריתם של Strassen; הניחו שכל פעולה אריתמטית (חיבור/חיסור/כפל/חילוק/השוואה של מספרים) מתבצעת בזמן קבוע. **(א)** ברצוננו להפיק תחזית מזג-אוויר **למחרתיים**, עבור $n$ אתרים. לכל אתר $1\le k\le n$ נתונות שלוש מטריצות: $A_k$ מסדר $n\times\log n$ (מצב מזג-האוויר היום), $B_k$ מסדר $\log n\times n$ (השינוי מהיום למחר, כך ש-$C_k:=A_k\cdot B_k$ הוא מזג-האוויר מחר), ו-$D_k$ מסדר $n\times\sqrt n$ (השינוי ממחר למחרתיים, כך שמזג-האוויר במחרתיים הוא $C_k\cdot D_k$). הציגו אלגוריתם יעיל ככל האפשר לחישוב מזג-האוויר במחרתיים בכל האתרים. **(ב)** הציגו אלגוריתם לחישוב המכפלה $A\cdot E$ של שתי מטריצות $n\times n$, אם $A$ מקיימת שכל שורה בה היא הזזה מחזורית של השורה הראשונה (מטריצה **מחזורית/circulant**): אם השורה הראשונה היא $(a_0,a_1,\dots,a_{n-1})$, אזי שורה $t$ היא $(a_{n-t+1},\dots,a_n,a_0,a_1,\dots,a_{n-t})$. נדרש זמן $o(n^3)$ (רק אלגוריתם, ללא הוכחה).

רמז: בחלק (א) בחרו את סדר הכפל החכם: $B_k\cdot D_k$ תחילה (מטריצות "רזות") ואז $A_k\cdot(\cdot)$. בחלק (ב) שימו לב שמטריצה מחזורית כפול וקטור = קונבולוציה מעגלית, המחושבת ב-FFT.

פתרון: **(א)** נחשב לפי סדר הכפל $A_k\cdot(B_k\cdot D_k)$ (אסוציאטיביות): - $\widetilde{C}_k:=B_k\cdot D_k$: מכפלת $(\log n\times n)\cdot(n\times\sqrt n)$ בזמן $\Theta(\log n\cdot n\cdot\sqrt n)=\Theta(n^{3/2}\log n)$; התוצאה מסדר $\log n\times\sqrt n$. - $A_k\cdot\widetilde{C}_k$: מכפלת $(n\times\log n)\cdot(\log n\times\sqrt n)$ בזמן $\Theta(n\cdot\log n\cdot\sqrt n)=\Theta(n^{3/2}\log n)$. לכל אתר $\Theta(n^{3/2}\log n)$, ולכל $n$ האתרים סה"כ **$\Theta(n^{5/2}\log n)$**. (הסדר ההפוך $(A_k B_k)D_k$ היה עולה $\Theta(n^{5/2})$ לאתר, כלומר $\Theta(n^{7/2})$ סה"כ.) **(ב)** כל **עמודה** של $A\cdot E$ היא **קונבולוציה מעגלית** של השורה הראשונה $(a_0,a_{n-1},\dots,a_1)$ עם העמודה המתאימה של $E$ (שכן $A$ מחזורית). קונבולוציה מעגלית מחושבת ב-FFT: 0. חשב $\text{FFT}$ של (השורה הראשונה של) $A$. 1. לכל עמודה $i$ של $E$: חשב $\text{FFT}$ של העמודה, כפול איבר-איבר בתוצאת שלב 0, ובצע $\text{iFFT}$ — זו העמודה ה-$i$ של $A\cdot E$. 2. החזר את $A\cdot E$. **זמן ריצה:** $n$ ביצועים של FFT/iFFT, כל אחד $\Theta(n\log n)$, סה"כ $\Theta(n^2\log n)=o(n^3)$.

הנחיות: אסור להשתמש באלגוריתם של Strassen; הניחו שכל פעולה אריתמטית (חיבור/חיסור/כפל/חילוק/השוואה של מספרים) מתבצעת בזמן קבוע.

(א) ברצוננו להפיק תחזית מזג-אוויר למחרתיים, עבור

n

אתרים. לכל אתר

1 \leq k \leq n

נתונות שלוש מטריצות:

A_{k}

מסדר

n \times lo g n

(מצב מזג-האוויר היום),

B_{k}

מסדר

lo g n \times n

(השינוי מהיום למחר, כך ש-

C_{k} := A_{k} \cdot B_{k}

הוא מזג-האוויר מחר), ו-

D_{k}

מסדר

n \times n

(השינוי ממחר למחרתיים, כך שמזג-האוויר במחרתיים הוא

C_{k} \cdot D_{k}

). הציגו אלגוריתם יעיל ככל האפשר לחישוב מזג-האוויר במחרתיים בכל האתרים.

(ב) הציגו אלגוריתם לחישוב המכפלה

A \cdot E

של שתי מטריצות

n \times n

, אם

A

מקיימת שכל שורה בה היא הזזה מחזורית של השורה הראשונה (מטריצה מחזורית/circulant): אם השורה הראשונה היא

(a_{0}, a_{1}, \dots, a_{n - 1})

, אזי שורה

t

היא

(a_{n - t + 1}, \dots, a_{n}, a_{0}, a_{1}, \dots, a_{n - t})

. נדרש זמן

o (n^{3})

(רק אלגוריתם, ללא הוכחה).

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 56 · 2021 · סמסטר ב

★★★★★

התמרת פורייה מהירהניתוח אלגוריתמיםסיבוכיות

בחלק (א) בחרו את סדר הכפל החכם:

B_{k} \cdot D_{k}

תחילה (מטריצות "רזות") ואז

A_{k} \cdot (\cdot)

. בחלק (ב) שימו לב שמטריצה מחזורית כפול וקטור = קונבולוציה מעגלית, המחושבת ב-FFT.

(א) נחשב לפי סדר הכפל

A_{k} \cdot (B_{k} \cdot D_{k})

(אסוציאטיביות):

$C_{k} := B_{k} \cdot D_{k}$ : מכפלת $(lo g n \times n) \cdot (n \times n)$ בזמן $Θ (lo g n \cdot n \cdot n) = Θ (n^{3/2} lo g n)$ ; התוצאה מסדר $lo g n \times n$ .
$A_{k} \cdot C_{k}$ : מכפלת $(n \times lo g n) \cdot (lo g n \times n)$ בזמן $Θ (n \cdot lo g n \cdot n) = Θ (n^{3/2} lo g n)$ .

לכל אתר

Θ (n^{3/2} lo g n)

, ולכל

n

האתרים סה"כ

Θ (n^{5/2} lo g n)

. (הסדר ההפוך

(A_{k} B_{k}) D_{k}

היה עולה

Θ (n^{5/2})

לאתר, כלומר

Θ (n^{7/2})

סה"כ.)

(ב) כל עמודה של

A \cdot E

היא קונבולוציה מעגלית של השורה הראשונה

(a_{0}, a_{n - 1}, \dots, a_{1})

עם העמודה המתאימה של

E

(שכן

A

מחזורית). קונבולוציה מעגלית מחושבת ב-FFT:
0. חשב

FFT

של (השורה הראשונה של)

A

.
1. לכל עמודה

i

של

E

: חשב

FFT

של העמודה, כפול איבר-איבר בתוצאת שלב 0, ובצע

iFFT

— זו העמודה ה-

i

של

A \cdot E

.
2. החזר את

A \cdot E

.

זמן ריצה:

n

ביצועים של FFT/iFFT, כל אחד

Θ (n lo g n)

, סה"כ

Θ (n^{2} lo g n) = o (n^{3})

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