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