אלגוריתמים

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

תקציר העבודה

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

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

שאלה מס' 1%) 25 (
בעיית השידוך היציב. פתרו את שאלה 6.1 בספר הקורס.

שאלה מס' 2%) 25 (
הכוות צלעות. הציגו אלגוריתם שמכריע, בהתן גרף לא מכוון ( ,)  VE G ,האם יתן לכוון כל
אחת מהצלעות, כך שבגרף המכוון שמתקבל, דרגת הכיסה של כל קדקוד תהיה גדולה מאפס.
(לכל צלע  E uv {,} יתן לבחור כיוון יחיד: v u (,) או לחלופין u v .((, ) כשהתשובה חיובית, על
האלגוריתם להחזיר הכווה של הצלעות – המקיימת את הדרש. דרשת תשובה קצרה ומדויקת
של עד 8 משפטים.

שאלה מס' 3%) 25 (
מהצורה וסחה היא k-CNF וסחת :הגדרות). 2-SAT) הספיקות בעיית 1 2 …       m ,
הצורה פסוקית כשלכל, 1 ,2 , ( … ) i i i ik וכל,     zz z i j , מהליטרלים אחד והי z
1 1 ,…, , ,…, n n ההי            ( )( )( )( ) x1 2 1 3 13 2 3 x x x xx x x למשל . x xx x  
,לעומתה. פסוקיות m  4 -ו, יםמשת n  3 ,פסוקית בכל ליטרלים k  2 עם 2-CNF וסחת
1 23 24 5 בכל ליטרלים k  3 עם 3-CNF וסחת ההי        ( )( ) x xx xx x
x ערך i פסוקית,5  n משתים, ו- 2  m פסוקיות. השמה היה פוקציה שמתאימה לכל משתה
x מסופק אם ההשמה מקיימת i" אמת" T או "שקר" F . בהיתן השמה מסוימת, אזי הליטרל
i ,מסופקת i i i ik    ( … ) zz z ,1 ,2 , הפסוקית . xi  F אם מסופק xi והליטרל , x T
      1 2 … m כולה וסחאה. מסופק zz z i i ik ,1 ,2 , , ,…, שבה מהליטרלים אחד לפחות אם
12

מסופקת, אם כל הפסוקיות m ,..,1 מסופקות. הוסחא קראת ספיקה, אם לפחות אחת מבין
ההשמות האפשריות מספקת אותה. 2n

הציגו אלגוריתם יעיל, שבהיתן וסחה  בצורת CNF-2 מוצא לה השמה מספקת, ואם אין
השמה כזו – מדווח שהוסחה איה ספיקה. הדרכה: העזרו בגרף מכוון G שמותאם לוסחה  .

שאלה מס' 4%) 25 (
מסלולים מזעריים דרך קדקודים מועדפים. תון גרף מכוון (,)  VE G ,צמד קדקודים
.st U ,  וכן   U V המקיימת, U V  מועדפים קדקודים של קבוצה-ותת, stV  
לכל מסלול P בגרף סמן ב- P( )  את אורך המסלול (=מספר הצלעות במסלול), וב- U P #() את
מספרם של קדקודי U במסלול.
הציגו אלגוריתם למציאת מסלול מ- s ל- t ,שמבקר ב- U בדיוק פעמיים, ושאורכו מזערי מבין כל
המסלולים הללו. כלומר, האלגוריתם דרש להחזיר מסלול מ- s ל- t כך ש-  U P 2 , #() וכך
.   ( ) () P P   אז () # , 2 P U  המקיימים t -ל s -מ P וספים מסלולים םיש שאם

בשאלה זו מותרים מסלולים לא פשוטים, כלומר מותר למסלול לעבור דרך קדקוד מסוים, ואפילו
דרך צלע מסוימת יותר מפעם אחת. למשל, יח שהגרף היו משולש מכוון  stvs ללא
שום קדקוד או צלע וספת, ושהקבוצה המועדפת היה { }  v U .אזי המסלול היחיד, ולכן גם
.stvstvst    פשוט הלא המסלול והי ()# 2 P U  שמקיים, המזערי

הדרכה: העזרו ברדוקציה לגרף אחר G