אלגוריתמים

מוסד לימוד
סוג העבודה
מספר ממ"ן 12
מקצוע
קורס
מילות מפתח , ,
שנת הגשה 2020
מספר מקורות 1

תקציר העבודה

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

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

שאלה מס' 1%) 25 (
מסלולים כמעט מזעריים. תון גרף מכוון ( ,)  VE G עם משקלים חיוביים  0() e w לכל אחת
מהצלעות  E e ועם קדקוד מקור s .תון גם שלכל קדקוד v קיים מסלול v,Ps מ- s ל- v
P e בגרף. כרגיל, משקלו של מסלול מוגדר כסכום משקלי הצלעות () ( )
wP we  Ps,v ומסלול ,  
 . הגדרות חדשות: מסלול v,Ps   עבור כל מסלול אחר sv v s wP wP , , ()() קרא מזערי אם מתקיים
כמעט מזערי, אם משקלו קטן ביותר מבין כל המסלולים הלא מזעריים מ- s ל- v . v,Ps ייקרא
כל המשקלים האפשריים של מסלולים מ- s ל- v , k   w ww היה רשימת … 2 1 כלומר, אם
צלע. wP w ( ) s v,  2 מתקיים מזערי כמעט ולמסלול wP w ( ) s v,  1 מתקיים מזערי למסלול אז
. v,Ps (,)   E uv e תיקרא שימושית אם היא צלע אחרוה באיזשהו מסלול מזערי
א. הוכיחו שאם כל הצלעות ב- v,Ps שימושיות, אז v,Ps מסלול מזערי.
איו מסלול מזערי. v,Ps) אחת או יותר), אז v,Ps ב. הוכיחו שאם יש צלע לא שימושית ב-
מסלול כמעט מזערי אז מופיעה בו צלע לא שימושית אחת ויחידה. v,Ps ג. הוכיחו שאם
. הוכיחו שהרישא v,Ps (, )  uu e הצלע הלא שימושית היחידה במסלול כמעט מזערי 2 1 ד. תהי
של v,Ps מ- s ל- u1 מהווה מסלול מזערי, וגם שהסיפא של v,Ps מ- u2 ל- v מהווה מסלול
מזערי.
14

ה. הציגו בעזרת הסעיפים הקודמים אלגוריתם למציאת מסלול כמעט מזערי מקדקוד מקור
תון s לקדקוד יעד תון t" ,בזמן" V E | |) log (| |  ) .בחישוב זמן הריצה מיחים שחיבור,
חיסור והשוואה של משקלי צלעות – כולן פעולות אלמטריות שמתבצעות בזמן (1( .(

שאלה מס' 2%) 25 (
תיקון עץ פורש שהושמטה ממו צלע. תון עץ פורש מזערי T של גרף לא מכוון קשיר
צלע e T * תהי . e E  מהצלעות אחת לכל c e() 0  שליליים-אי משקלים עם G VE  (, )
.( E  E e \{ *} ,כלומר (e* של השמטתה לאחר G -מ המתקבל, הגרף G VE      , ויהי, בעץ
תון כי G קשיר. הציגו אלגוריתם שרץ "בזמן" (| |) E O ומתקן את T ,כך שיתקבל ממו עץ
פורש מזערי T עבור G) .הערות: (א) בדומה לאלגוריתמים חמדיים רבים עיקר הקושי (ולכן
גם מרבית היקוד) הוא בהוכחת הכוות ולא ביסוח האלגוריתם. (ב) במסגרת יתוח זמן הריצה,
היחו כי כל פעולה אלמטרית על המשקלים, כמו חיבור או השוואה, מתבצעת בזמן (1( .(

שאלה מס' 3%) 30 (
בעיית הספיקות (SAT-3 – (כשלון החמדות. הפורמט של וסחת CNF-3 הוגדר כזכור במסגרת
ממ"ן 1 .ביט באלגוריתם החמדן הבא למציאת השמה מספקת לוסחת CNF-3 שרירותית  .
האלגוריתם סורק את כל המשתים xn,…, x1 בזה אחר זה, ולכל משתה xi בוחר השמה,
שממקסמת את מספר הפסוקיות המסופקות החדשות. (למשל, כשהאלגוריתם מטפל במשתה
x . אם ב-5 1 x , בוחים רק את הפסוקיות שטרם סופקו ע"י ההשמה שקבעה כבר למשתה 2
מהפסוקיות הללו מופיע הליטרל x2 , וב-6 מהפסוקיות הללו מופיע הליטרל x2 ,אז מציבים
F  x , משום שכך יסופקו 6 פסוקיות חדשות במקום 5 .(הציגו וסחת CNF-3 עליה 2
האלגוריתם החמדן כשל: הוסחא ספיקה, אבל האלגוריתם מפיק כפלט השמה לא מספקת.

שאלה מס' 4%) 20 (
קידוד הופמן. עץ מושרש T קרא ביארי לחלוטין אם לכל קדקוד שלו שאיו עלה יש שי בים.
הוכיחו כי לכל עץ מושרש בירי לחלוטין T בעל n עלים, קיימת סדרת שכיחויות n , ,…, 2 1 f ff כך
שאחד מעצי הופמן של הסדרה הוא T) .הבהרה: כזכור, השורש אף פעם איו חשב לעלה בעצים
מושרשים. לכן הטעה חלה עבור 3  n בלבד).