אלגוריתמים
מוסד לימוד | האוניברסיטה הפתוחה |
סוג העבודה | ממ"ן |
מספר ממ"ן | 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