מטלת מחה (ממ"ן) 14
הקורס: 20417 ,אלגוריתמים
חומר הלימוד למטלה: פרק 6 בספר
מספר השאלות: 4 משקל המטלה: %4
סמסטר: 2020ב מועד הגשה: 2020.05.31

קיימות שתי חלופות להגשת מטלות:
• שליחת מטלות באמצעות מערכת המטלות המקוות באתר הבית של הקורס
• שליחת מטלות באמצעות הדואר או הגשה ישירה למחה במפגשי ההחיה
הסבר מפורט ב"והל הגשת מטלת מחה"

שאלה מס' 1%) 40 (
מסלולים מזעריים בשריג עם מחירים על הקודקודים. תון שריג ריבועי מסדר  n n עם מחירים
אי-שליליים על קדקודים: אברי השריג הם קודות מהצורה j i (, ) כאשר n ij   , 1 ,ולכל איבר
מותאם מחיר  0 (, ) j ci . הקואורדיטה הראשוה i מייצגת מיקום אופקי (ימיה / שמאלה)
בשריג. לכן השכבה השמאלית ביותר מורכבת מהקודות בהן 1 i ,והשכבה הימית ביותר
מהקודות בהן  n i .הקואורדיטה השייה j מייצגת מיקום אכי (מעלה / מטה). בשריג
או ) ( , ) 1, ) ij i j   או ) ( , ), 1, 1) ij i j   :מהצורה בצעדים רק ועהת מותרת
  j i ij) 1, 1 ,( , ) ( כלומר, "ימיה ולמטה" או "ימיה" או "ימיה ולמעלה". הציגו אלגוריתם
למציאת מסלול במחיר מזערי מהשכבה השמאלית ביותר לימית ביותר, כשמחיר מסלול מוגדר
n( )  פעולות אלמטריות בלבד, 2 כסכום מחירי הקודות במסלול. על האלגוריתם לבצע
כשפעולות אריתמטיות על המחירים, כמו חיבור, חיסור והשוואה, חשבות לפעולות אלמטריות.

שאלה מס' 2%) 20 (
ביית מגדל יציב מתיבות. תוה רשימה של n תיבות מלביות: לכל n i 1 תון האורך i( ) ,
הרוחב ( )i w והגובה ( )i h של התיבה מספר i .כל הרוחבים שוים, כל האורכים שוים וכל
הגבהים שוים. ברצוו לבות מגדל בגובה מרבי באמצעות החה של תיבות זו מעל זו. המגדל
.   ( ) () j  i וגם w j wi ( ) ()  שמקיימת i תיבה מעל רק חתמו j תיבה כאשר יציב חשב
(כלומר כשמימדי הבסיס של התיבה התחתוה גדולים מאלו של העליוה). הציגו אלגוריתם תכון
n( ) ) .פעולות חיבור, 2 דיאמי לביית מגדל יציב בגובה מרבי. האלגוריתם דרש לרוץ בזמן
חיסור והשוואה של מימדים i( )( ) , i w( ) ,i h חשבות פעולות אלמטרית שמתבצעת בזמן
.((1)
20

שאלה מס' 3%) 20 (
איטרפולציה באמצעות תכון דיאמי: פוליום ממשי מדרגה קטה מ- n היו ביטוי מהצורה
2 1
01 2 1 ( ) … n
n p x a ax ax a x       שכזה וםפולי כי קובע האלגברה של היסודי המשפט.
קבע ביחידות לפי ערכו ב- n קודות. למשל, כל קו ישר (כלומר כל פוליום מדרגה קטה מ-2 (
xy y x n n ( , ),…,( , ) 1 1 קבע ביחידות ע"י 2 קודות דרכן הוא עובר. באופן כללי, בהיתן n קודות
עבורן i j המקיים n -מ הקט מדרגה p( ) x ויחיד אחד וםפולי קיים, i j  לכל x  x
1 1 ( ) ,…, ( ) n n .(ותתוה קודותה של (טרפולציההאי וםפולי קרא זה וםפולי . p x y px y  
קודותה ותתו טרפולציההאי בבעיית 1 1 ( , ),…,( , ) n n המקיימות x y xy i j את לחשב ויש , x  x
.טרפולציההאי וםפולי של a a 0 1 ,…, n המקדמים

-ב סמן i j  לכל) א (i j , .( , ),…,( , ) xii j j y xy קודותה של טרפולציההאי וםפולי את p
מצאו 3 פוליומים פשוטים ( ) ,( ) ,( ) sx rx qx מדרגה 0 או 1 ,עבורם מתקיים
, 1, 1
, 1
() () () ()
( )
ij i j
i j
qxp x rxp x
p
s x
 

 

(ב) הציגו אלגוריתם תכון דיאמי לבעיית האיטרפולציה, המבוסס על וסחת הסיגה
מסעיף (א). לשם פשטות, החשיבו פעולות אריתמטיות על מספרים כפעולות אלמטריות.
יהי) ג (234 ,   2, 1,0,1,2 הערכים חמשת את p( ) x -ב הציבו . p() 2 3 4 xxx x x   
והריצו את אלגוריתם האיטרפולציה מהסעיף הקודם על חמש הקודות שמתקבלות.
וודאו שהאלגוריתם אכן מיב כפלט את מקדמיו של x( ) p .

שאלה מס' 4%) 20 (
יישומים של תכון דיאמי. תון גרף מכוון ( ,)  VE G עם משקלים אי-שליליים  0() e c לכל
אחת מהצלעות  E e , ותון קדקוד מסוים V r .הביטו באלגוריתם הבא:
, [ ] ,0) i (מאתחלים מערך חד-מימדי A באמצעות הכלל:
v r
A v
v r
   
  .
(ii (לולאה חיצוית: חוזרים שוב ושוב על הפעולה הבאה.
(1ii (לולאה פימית: סורקים את הצלעות בסדר לקסיקוגרפי. לכל (,)   E uv e מבצעים:
. A[] [] () v Au ce   יםמעדכ אז A[] [] () v Au ce   אם
(2ii (אם בהרצה הוכחית של כל הלולאה הפימית לא בוצע אף עדכון, אז האלגוריתם מסיים.
שאלות:
(א) מה מחשב האלגוריתם? הציגו הוכחה מפורטת לטעתכם בשיטת האידוקציה.
21

(ב) יהי n( ) B המספר המרבי של איטרציות שמתבצעות בלולאה החיצוית על גרפים בעלי n
קדקודים. חשבו את n( ) B , והציגו סדרת גרפים Gn עליהם מתבצעות בדיוק n( ) B איטרציות.
 , עבורם כסים ללולאה החיצוית פעמיים בלבד, וזאת למרות Gn) ג) הציגו סדרת גרפים אחרת
. n לכל |( ) | |( ) | EG EG n n
שמספר הצלעות שלהם זהה לגרפים מהסעיף הקודם, כלומר