מטלת מחה (ממ”ן) 13
הקורס: 20417 ,אלגוריתמים
חומר הלימוד למטלה: פרק 5 בספר
מספר השאלות: 4 משקל המטלה: %4
סמסטר: 2020ב מועד הגשה: 2020.05.10
קיימות שתי חלופות להגשת מטלות:
• שליחת מטלות באמצעות מערכת המטלות המקוות באתר הבית של הקורס
• שליחת מטלות באמצעות הדואר או הגשה ישירה למחה במפגשי ההחיה
הסבר מפורט ב”והל הגשת מטלת מחה”
שאלה מס’ 1%) 30 (
וםבפולי ביט .FFT הרצת 3 2 כל את הציגו. 4-מ הקט שדרגתו p() 2 3 1 xx x x
החישובים מעל שדה המרוכבים (לרבות הקריאות הרקורסיביות) עבור:
(, ) FFT ( על מקדמי הפוליום. 4) א) הרצת FFT מסדר 4) הרצת
1) ב) הרצת FFT-INVERSE) הרצת
( על הערכים שהתקבלו בסעיף הקודם. (,( ) ) FFT 4
שאלה מס’ 2%) 30 (
כפל מספרים שלמים בגישת FFT :כפל מספרים שלמים היה בעיה אלגוריתמית בעלת חשיבות
מעשית עליוה. לשם פשטות להלן יח ששי המספרים המוכפלים שווי אורך (לשיהם ייצוג
ביארי של n ביטים), וששיהם חיוביים. בתרגיל זה יוצגו עיקר הרכיבים באחד האלגוריתמים
n n ) log( בלבד. כזכור, 2 היעילים ביותר המוכרים כיום לכפל שלמים: זמן הריצה שלו הוא
אלגוריתם הכפל של Karatsuba מבוסס על פיצול הספרות של כל קלט לשי בלוקים שווי גודל,
n( ) .הציגו אלגוריתם משופר, שמחלק כל קלט ל- k n (/) בלוקים בגודל k . 3 log 2 ורץ בזמן
היעזרו באלגוריתם ה-FFT לפתרון תתי-הבעיות המתקבלות. היחו לשם פשטות (וללא הצדקה),
כי ההכפלות שמתבצעות במהלך הקריאות הרקורסיביות אין מגדילות את אורכם של המספרים,
k( ) פעולות על ביטים. בחרו לבסוף 2 ולכן יתן לממש הכפלות אלו בצורה תמימה תוך ביצוע
את גודלם של הבלוקים להיות log n k .
16
שאלה מס’ 3%) 30 (
x f את הגזרת מסדר k של k ( ) ( ) חישוב כל הגזרות של פוליום בקודה. מקובל לסמן ב-
,למשל . f ( ) x קציההפו) 1) , f () () x fx (2) , f () () x fx (3) וכן f () () x fx
(0) וםהפולי מקדמי יםתו . f () () x fx 2
01 2 ( ) … n
n קודה התוו f x a ax ax ax
( ) (0 (מסוימת x0 . הציגו אלגוריתם לחישוב ערכי כל הגזרות
0 0 ( ),…, ( ) n קודה באותה f x fx 0 , x
תוך ביצוע n n ) log( פעולות אריתמטיות בסיסיות בלבד. (פעולה בסיסית = חיבור, חיסור, כפל,
חילוק או השוואה של מספרים). למשל לפוליום מדרגה 4 n יש לחשב את הערכים הבאים:
(0) 2 3 4
0 0 10 2 0 3 0 4 0
(1) 2 3
0 1 20 3 0 4 0
(2) 2
0 2 30 4 0
(3)
0 3 40
(4)
0 4
() () () ()
() 2 3 () 4 ()
( ) 2 2 3 3 4 ( )
( ) 2 3 2 3 4 ( )
( ) 2 3 4
f x a ax a x a x a x
f x a ax a x a x
f x a ax a x
f x a ax
fx a
דרשת תשובה של 5-4 שורות בלבד המבוססת על FFT .לא יתן יקוד על האלגוריתם
n( ) המחוברים. העזרו בתשובתכם בצמצום 2 הטריוויאלי שמחשב בפרד כל אחד מבין
הסטדרטי של עצרות:
! 1 2 … ( 1) ( 1) ( 2) … ( 1) ! 1 2 … ( 1)
m mm
m m
.
שאלה מס’ 4%) 10 (
כפל מטריצות ריבועיות (Strassen .(כזכור, כפל של שתי מטריצות ריבועיות B, A מסדר n n
(מעל שדה שרירותי) מיב מטריצה AB C אף היא מסדר n n , המוגדרת ע”י הכלל
, ,,
1
i j ik k j
k n
C AB
.
n( ) פעולות אריתמטיות בסיסיות מעל השדה 3 לכן מימוש ישיר של כפל מטריצות כרוך ב-
n( ) פעולות כפל. בתרגיל זה וכיח כי יתן להכפיל 3 הדון (כפל/חיבור/חיסור), ובפרט ב-
2 באמצעות ריבועיות מטריצות log 7 2.81 פרטי. בלבד בסיסיות אריתמטיות פעולות ( )() n On
n n ההוכחה מובאים להלן. יח בה”כ כי n זוגי. פרק כל מטריצה ל-4 תתי-מטריצות מסדר 2 2
, , ab eg rs AB C
cd f h tu
.
וודאו (לא להגשה) כי מהגדרת כפל מטריצות מתקיים:
17
r aeb f
s ag bh
t ced f
u cgdh
כעת גדיר:
1
2
3
4
5
6
7
( )
( )
( )
( )
( )( )
( )( )
( )( )
P a gh
P ab h
P cd e
P d fe
P ad eh
P bd f h
P ac eg
,…, P P , כרוך ב-7 פעולות כפל בלבד (וכן מספר 7 1) ב) וודאו (לא להגשה) כי חישוב המטריצות
. n n מצומצם של פעולות חיבור/חיסור) של מטריצות מסדר 2 2
(ג) וודאו (לא להגשה) כי מתקיים:
1 2
3 4
4562
1537
sPP
tPP
rPPPP
uPPPP
n( )
| מילות מפתח | 13, אלגוריתמים, ממן |
| מקצוע/ות | ממ"נים |
| מספר מילים | |
| מספר מקורות | 1 |
| שנת הגשה | 2020 |