מטלת מחה (ממ"ן) 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( )