עבודה 7 תכנון אלגוריתמים

מוסד לימוד
מקצוע
מילות מפתח , , ,
שנת הגשה 2004
מספר מילים 1105

תקציר העבודה

תכנון אלגוריתמים תרגיל מספר 7 ואחרון ! (NP,RP):
פורסם בתאריך: 3.6.04
מועד הגשה: 17.6.04
עודכן ב-5.6.04 (שבת) שימו לב: תיאור אלגוריתם כולל תמיד עיקרי הוכחת נכונות, וכן חישוב זמן ריצה!! ברדוקציות – הראו את שני הכיוונים ואת זמן הריצה.
לצורך הרדוקציות אתם רשאים להשתמש רק ברשימת הבעיות המופיעה באתר ציינו במפורש מהי הבעיה אותה בחרתם בכל פעם.
1. גודל וועד סטודנטים לשנה ב':
השאלה עוסקת באיתור ועד סטודנטים לשנה ב' (מבלי לשאול את הסטודנטים). על מנת להטריח כמה שפחות סטודנטים נדרש  ועד בעל גודל מינימאלי אפשרי, כך שיהיה בו נציג מכל אחד מ- n הקורסים (הלא ריקים) שלומדים תלמידי שנה ב'. (שימו לב כי סטודנט יכול להיות ביותר מקורס אחד) א.      ענה על סעיף זה באופן אינטואיטיבי לפני קריאת המשך השאלה (ללא ניקוד):
אילו משלושת הבעיות היא המסובכת ביותר ואילו הקלה ביותר:
·        האם קיים ועד בגודל k?
·        מה גודל הועד המינימאלי ?
·        מציאת הועד המינימאלי (רשימת הסטודנטים ממש). ב.       נסחו את הבעיה באופן פורמלי (כולל מהו הקלט והפלט).
ג.        נסחו את בעיית ההכרעה המתאימה לה (כולל מהו הקלט והפלט).
ד.       הראו שבעיית ההכרעה שניסחתם בסעיף ג' היא NP-שלמה.
ה.      נניח שקיים אלגוריתם B פולינומיאלי המכריע את בעיית ההכרעה שניסחתם בסעיף ג'. תארו אלגוריתם פולינומיאלי אשר מוצא ועד סטודנטים מינימאלי (כלומר מציג את קבוצת הסטודנטים בועד).
הערה:
משמעות סעיף ה' היא שמציאת הועד עצמו (כלומר הנציגים עצמם) אינה קשה יותר פולינומיאלית (מבחינת סיבוכיות חישוב) ממציאת הגודל של הוועד למרות שניתן היה לחשוב אחרת…

2 . מסלול פשוט מקסימאלי:
מופע: גרף לא מכוון שצלעותיו ממושקלות, ושני קדקודים s ו t.
מצא: מסלול פשוט בעל משקל מקסימלי מ-s ל-t (מסלול פשוט מכיל כל קדקוד לכל היותר פעם אחת).
א.      תארו אלגוריתם יעיל לפתרון כאשר מדובר בגרף חסר מעגלים. אתם יכולים להשתמש במשפטים ואלגוריתמים שהוכחו ללא צורך בהוכחה מחדש ובלבד שתנסחו אותם במדויק (אין צורך להוכיח באופן פורמאלי את הנכונות –ניתן להסביר בקצרה).
ב.       נסחו בעיית הכרעה המתאימה לבעיית האופטימיזציה הכללית והוכיחו כי היא NP שלמה.
ג.        הוכיחו כי בעיית האופטימיזציה היא NP קשה.
הערה:
שאלה זו מדגישה את הרעיון כי בעיה דומה במקרים מעט שונים יכולה להפוך מפתירה באופן יעיל ללא פתירה לכל ישום מעשי – זו היא אחת הסיבות שנושא זה הוא חיוני כל-כך במדעי המחשב.
3. משחקי משוואות:
אין קשר בין הסעיפים:
א)      קיבלת הודעה מוצפנת בשיטת RSA עם מפתח ציבורי (35,13), n=35, ההודעה שקיבלת היא "17". כיוון שקל לפרק את n במקרה זה, ניתן לפענח את ההודעה, מהי ההודעה המקורית ?
ב)      נסמן ב-NPC את מחלקת השפות ה-NP-שלמות.
בהנחה ש- הוכיחו או הפריכו:
a)      . b)      לא קיימת שפה L כך ש- וגם .
c)      לכל שתי שפות L1,L2 .
d)      איזו מהטענות ניתן להוכיח ללא ההנחה ?

4 . חיסכון בקריית שמונה:
נשכרתם ע"י עריית קריית שמונה למשימה הבאה:
בשכונת "החשמונאים" ישנם n בתים ורשת כבישים (דו-סטריים) בעלי אורך אחיד המחברים בין בתים שונים (לא קיים כביש בין כל שני בתים אבל ניתן להגיע מכל בית לכל שאר הבתים בשכונה).
ישנם בתים שמגיעים אליהם מספר כבישים מכיוונים שונים.
נגדיר בית ללא מוצא כבית שיש רק כביש אחד המגיע אליו.
על מנת לחסוך כסף בתחזוקת הכבישים רוצים בעירייה להשאיר בדיוק n-1 כבישים תוך שמירת התנאים הבאים:
עדיין יהיה ניתן להגיע מכל בית לכל שאר הבתים בשכונה.
יהיו בדיוק שמונה בתים ללא מוצא. (כיוון שהמספר שמונה הוא מיוחד לתושבי השכונה…).
השאלה היא האם ניתן לעמוד במשימה תחת האילוצים הנ"ל ?
א)      תארו את הבעיה באופן פורמאלי (כולל מה צ"ל).
ב)      הציעו אלגוריתם לפתרון (האלגוריתם אינו חייב להיות יעיל !).
תנו חסם עליון (כדי לא להסתבך בחישובים מאד מסובכים ניתן לתת חסם גס) לזמן הריצה של האלגוריתם שהצעתם ? עבור n = 88 (שכונה די קטנה) כמה זמן ייקח (בשנים !) לסיים את החישוב, אם כל פעולה בסיסית (שזמנה קבוע !) לוקחת 10-9 שניות (= ננו-שניה).
ג)       הוכיחו בשלושים ושמונה שורות (או פחות) כי בעיה זו היא NP שלמה.
5. אפס ?
נתון: פולינום P(x) ממעלה d. הגישה היחידה לפולינום היא על ידי בקשת ערך הפולינום P(x) (ערך הפולינום בנקודה x)  באחת הנקודות מתוך קבוצה בגודל m: {1,2,3,-,m} (m קבוע כלשהו שתקבעו בהמשך).
כלומר אין גישה ישירה למקדמי הפולינום. חישוב ערך הפולינום בנקודה לוקח זמן קבוע C>1.
שאלה: האם הפולינום הוא לא פולינום ה-0 (כל מקדמיו 0) ?
א)      הציגו אלגוריתם דטרמיניסטי הפותר את השאלה.
מה הוא זמן הריצה ?  מה ערך m המינימאלי לצורך כך ?
ב)      הציגו אלגוריתם שטועה באופן חד צדדי בהסתברות קטנה או שווה (1/3)k שזמן ריצתו k*C.
(תארו אותו והוכיחו נכונות על פי הדוגמא שראיתם בתרגול !). מהוא m שתקבעו לצורך כך ?
(לצורך ניתוח זמן ריצה בסעיף זה הניחו כי פעולות רנדומליות עולות 1).
ג)       (בונוס 10 נק') ניתן לראות כי ככל ש m גדול יותר נצטרך לחזור פחות פעמים על הרצת אלגוריתם בסיסי על מנת לקבל את אותה הסתברות.
מצד שני אם נניח כי הגרלת ביט אחד לוקחת זמן 1 אזי ברור שככל ש m גדול יותר הגרלת מספר תיקח לנו יותר זמן.
      הוכיחו כי מבחינת זמן הריצה הגרלת מספר יחיד בכל האלגוריתם (כלומר לאלגו' יש שלב יחיד)      היא היעילה ביותר. מהו m המתאים לכך ?