מתכונת 1 במדעי המחשב - מבני נתונים ומסלול 899271

מה נדרש: לספור כמה זוגות של איברים בתור (במקומות שונים) נבדלים זה מזה ב־ d לכל היותר, כאשר כל זוג נספר פעם אחת.

רעיון: מוציאים מהתור את האיבר הראשון v ולא מחזירים אותו. כעת בתור נמצאים בדיוק האיברים שבאו אחריו. מעבירים את כל האיברים האלה, אחד אחד, לתור עזר temp: כל איבר x מוצא, נבדק אם |v − x| ≤ d (אם כן – מגדילים את המונה), ומוכנס ל־ temp. אחר כך מחזירים את כל האיברים מ־ temp אל q (באותו הסדר). חוזרים על כך עד שהתור q מתרוקן.
כך כל זוג נבדק בדיוק פעם אחת – כשהאיבר המוקדם מבין השניים הוא v – ולכן אין ספירה כפולה.

פתרון: הקוד המלא – בלשונית Java/C#. בפעולה משתמשים רק בפעולות התור (insert, remove, isEmpty), בתור עזר ובמשתנים פשוטים, בלי מערך ובלי רשימה.

יעילות: הלולאה החיצונית מתבצעת n פעמים (בכל פעם יוצא מהתור איבר אחד לתמיד). כשנשארים בתור k איברים, הלולאות הפנימיות מעבירות אותם ל־ temp וחזרה – 2k פעולות. k = n − 1, n − 2, ..., 1, 0, ולכן סך הפעולות הוא 2·((n − 1) + (n − 2) + ... + 1) = n·(n − 1) ⇒ O(n²), כאשר n הוא מספר האיברים בתור.

בדיקה (התור 8, 3, 12, 5, 9, 20, 4 ו־ d = 2):

הפעולה מחזירה 4. מקרים נוספים: d = 0 ← 0, d = 1 ← 3, התור 5, 5, 5, 5 עם d = 0 ← 6.

טעות נפוצה: להחזיר גם את v לתור אחרי הסבב. אז התור לעולם לא מתרוקן והלולאה אינה מסתיימת; וגם אם סופרים סבבים, כל זוג נבדק פעמיים והתשובה כפולה.

מה נדרש: לעקוב אחר הקריאה what(lst, 5) ולרשום את הערך המוחזר.

רעיון: הפעולה קוראת לעצמה לפני שהיא בודקת את החוליה הנוכחית. לכן הקריאות יורדות עד סוף השרשרת (lst == null מחזירה 0), והבדיקה של החוליות מתבצעת בדרך חזרה, מהחוליה האחרונה לראשונה. כל קריאה מקבלת ב־r את התוצאה של המשך השרשרת, ומוסיפה 1 אם ערך החוליה שלה קטן מ־x.

פתרון – מעקב (השרשרת 4, 7, 2, 9, 5, 1; x = 5; השורות לפי סדר החזרה מהרקורסיה):

הפעולה מחזירה 3.

בדיקה: הקוד מדפיס what(lst, 5) = 3.

טעות נפוצה: לספור גם את החוליה 5. התנאי הוא קטן ממש (<), ולכן ערך השווה ל־x אינו נספר.

מה נדרש: לתאר במילים מה הפעולה מחשבת.

רעיון: נסתכל על הפעולה כעל הגדרה רקורסיבית:

פתרון: הפעולה סופרת כמה חוליות בשרשרת lst ערכן קטן מ־x ומחזירה את המספר. הפעולה רק קוראת ערכים (getValue, getNext) ואינה משנה את השרשרת. אם אף ערך אינו קטן מ־x מוחזר 0, וגם עבור שרשרת ריקה מוחזר 0.

בדיקה: על השרשרת 4, 7, 2, 9, 5, 1:

מה נדרש: סיבוכיות זמן, כאשר n הוא מספר החוליות ב־lst.

רעיון: סופרים את הקריאות הרקורסיביות ואת העבודה בכל קריאה.

פתרון: כל קריאה מבצעת קריאה רקורסיבית אחת בלבד, על החוליה הבאה. לכן יש n + 1 קריאות: אחת לכל חוליה ואחת ל־null בסוף. בכל קריאה, מלבד הקריאה הרקורסיבית, יש מספר קבוע של פעולות: השוואה, getValue, חיבור ו־return, כלומר O(1).
סה"כ: (n + 1) · O(1) = O(n). הפעולה תמיד עוברת על כל השרשרת, ולכן אין הבדל בין מקרה טוב למקרה גרוע.

בדיקה: סופרים את הקריאות במעקב. על שרשרות באורך 100, 200, 400, 800, 1600 היו 101, 201, 401, 801, 1601 קריאות, כלומר n + 1, גידול לינארי.

מה נדרש: לעקוב אחר guess(lst) ולרשום את הערך המוחזר.

רעיון: לפי סעיף א, what(lst.getNext(), lst.getValue()) מחזירה כמה חוליות אחרי החוליה הנוכחית קטנות מהערך שלה. guess מחברת את המספר הזה לתוצאה של guess על המשך השרשרת. כלומר התוצאה היא סכום של "כמה ערכים קטנים ממני באים אחריי" על כל החוליות.

פתרון – מעקב:

guess(lst) = 2 + 3 + 1 + 2 + 1 + 0 + 0 = 9.

בדיקה: הקוד מדפיס guess(lst) = 9.

מה נדרש: לתאר במילים מה guess מחשבת.

רעיון: לכל חוליה, מהראשונה ועד האחרונה, guess סופרת (בעזרת what) כמה חוליות שבאות אחריה קטנות ממנה, ומחברת את כל המספרים.

פתרון: הפעולה סופרת את הזוגות "ההפוכים" בשרשרת: זוגות של שתי חוליות שבהם החוליה שמופיעה קודם בשרשרת גדולה מהחוליה שמופיעה אחריה. כל זוג כזה נספר בדיוק פעם אחת – כשמגיעים לחוליה המוקדמת בזוג. הפעולה אינה משנה את השרשרת.

משמעות: התוצאה היא 0 בדיוק כשהשרשרת מסודרת בסדר עולה, כאשר ערכים שווים זה ליד זה מותרים (אין ערך שבא אחרי ערך גדול ממנו; למשל בשרשרת 2, 2, 5 התוצאה 0), והיא הכי גדולה, n(n−1)/2, כשהערכים שונים זה מזה ומסודרים בסדר יורד.

בדיקה: השרשרת 3, 1, 2 ⇒ 2 (הזוגות 3>1, 3>2); השרשרת 1, 2, 3 ⇒ 0; השרשרת 3, 2, 1 ⇒ 3.

מה נדרש: סיבוכיות זמן של guess, כאשר n הוא מספר החוליות ב־lst.

רעיון: guess מופעלת פעם אחת על כל חוליה (ועוד פעם על null). בכל הפעלה יש קריאה ל־what על המשך השרשרת, ולפי סעיף א(3) היא עולה O(אורך ההמשך).

פתרון: לחוליה הראשונה what עוברת על n−1 חוליות, לשנייה על n−2, וכן הלאה, עד 0 לחוליה האחרונה:
(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2 ⇒ O(n²).
what תמיד עוברת על כל ההמשך (אין בה עצירה מוקדמת), ולכן זו הסיבוכיות בכל מקרה, לא רק במקרה הגרוע.

בדיקה: סופרים את הקריאות ל־what כש־guess פועלת על שרשרות באורך n = 100, 200, 400, 800, 1600. היו 5050, 20100, 80200, 320400, 1280800 קריאות, כלומר בדיוק n(n+1)/2 (כולל הקריאות על null). כשמכפילים את n, מספר הקריאות גדל פי 4, כמו שמתאים ל־O(n²).

מה נדרש: לחתוך את ערך העלה לשני חלקים לפי הספרות: d/2 הספרות הימניות לבן הימני, ושאר הספרות לבן השמאלי.

רעיון:

פתרון: הקוד המלא – בלשונית Java/C#.

בדיקה: 4825: d = 4, p = 100 ← 48 ו־ 25. 9603: d = 4, p = 100 ← 96 ו־ 3. 307: d = 3, p = 10 ← 30 ו־ 7. 6: d = 1 ← false. מתקבלות בדיוק התוצאות האלה, וגם 10 ← בנים 1 ו־ 0.

טעות נפוצה: לחשב את p לפי d ולא לפי d/2 (או להפוך בין החלקים), ואז הבן השמאלי מקבל 0 והימני את כל המספר.

מה נדרש: לסרטט את העץ שנבנה בקריאה what(tr) כאשר tr הוא עלה שערכו 73846, להציג מעקב ולכתוב מה מוחזר.

רעיון: what מפעילה את cutDigits. אם הצומת לא נחתך (חד־ספרתי) – מחזירה 1. אחרת ממשיכה ברקורסיה על הבן השמאלי ועל הבן הימני ומחזירה את סכום התוצאות.

פתרון (מעקב):

העץ בתום הפעולה:

הפעולה מחזירה 5.

בדיקה: מתקבל העץ 73846(738(73(7, 3), 8), 46(4, 6)) והערך המוחזר 5.

מה נדרש: להסביר מה מבצעת what ומה היא מחזירה.

רעיון: כל צומת שיש לו יותר מספרה אחת נחתך לשני חלקים שצירופם (זה אחר זה) נותן בחזרה את המספר. החיתוך ממשיך עד שכל העלים חד־ספרתיים.

פתרון (הסבר):

בדיקה: הערך המוחזר שווה ל־ numDigits, וצירוף העלים משמאל לימין שווה למספר.

מה נדרש: לבחור 5 מתוך 7 טענות, לקבוע אם כל אחת נכונה, ולנמק (טענה נכונה) או להביא דוגמה נגדית עם 4 קודקודים לפחות (טענה לא נכונה).

רעיון: כאן מוצגות כל שבע הטענות. טענה נכונה מוכיחים בנימוק כללי; טענה לא נכונה מפריכים בדוגמה אחת.

פתרון:

(1) נכונה. כל קשת תורמת 1 לדרגה של כל אחד משני קצותיה, ולכן סכום הדרגות של כל הקודקודים הוא 2·|E| – מספר זוגי. סכום הדרגות הזוגיות הוא זוגי, ולכן גם סכום הדרגות האי־זוגיות זוגי. סכום של מספרים אי־זוגיים הוא זוגי רק כשמספר המחוברים זוגי – לכן מספר הקודקודים שדרגתם אי־זוגית זוגי.

(2) נכונה. נניח בשלילה שיש מעגל. נסיר קשת אחת מן המעגל – הגרף נשאר קשיר (שני קצות הקשת עדיין מחוברים דרך שאר המעגל). נמשיך להסיר כך קשתות ממעגלים עד שלא יישאר מעגל: נקבל עץ פורש עם פחות מ־ n − 1 קשתות. אבל בכל עץ עם n קודקודים יש בדיוק n − 1 קשתות – סתירה.

(3) לא נכונה. דוגמה נגדית – גרף לא מכוון עם הקשתות A–B (1), B–C (2), A–C (3), C–D (9). הקשת C–D היא הכבדה ביותר, אבל היא הקשת היחידה שמגיעה ל־ D , ולכן היא חייבת להיות בכל עץ פורש. העפ"מ (היחיד) הוא {A–B, B–C, C–D} במשקל 12 , והוא מכיל את הקשת הכבדה ביותר.

(4) נכונה. נניח בשלילה שיש עפ"מ T שאינו מכיל את e = (u , v). נוסיף את e ל־ T – נוצר מעגל שעובר דרך e . במעגל יש קשת נוספת e′ (שונה מ־ e), ומשקלה גדול ממשקל e . נסיר את e′ : מתקבל שוב עץ פורש, ומשקלו w(T) − w(e′) + w(e) < w(T) – בסתירה לכך ש־ T מינימלי.

(5) לא נכונה. דוגמה נגדית – גרף מכוון s→a→b→c (שלוש קשתות). DFS מ־ s מגלה את s, a, b, c – את כל הקודקודים. אבל מ־ c אין מסלול לאף קודקוד אחר (בפרט לא ל־ s), ולכן הגרף אינו קשיר היטב.

(6) נכונה. כשהאלגוריתם מגיע לקודקוד v לפי המיון הטופולוגי, כל הקודקודים שיש מהם קשת אל v כבר טופלו (הם מופיעים לפני v במיון). באינדוקציה לפי סדר המיון: המסלול הקל ביותר ל־ v מסתיים בקשת u→v , כש־ u לפני v במיון; כש־ u טופל, d(u) כבר היה נכון, ושיפור הקשת u→v נתן ל־ v את הערך הנכון. הנימוק אינו משתמש בכך שהמשקלים חיוביים (בניגוד לדייקסטרה), ובגמ"ל אין מעגלים ולכן גם לא מעגלים שליליים.

(7) לא נכונה. דוגמה נגדית – גרף לא מכוון עם הקודקודים s, a, b, c והקשתות s–a (3), s–b (4), a–b (2), b–c (1) (כל המשקלים שונים). המרחקים מ־ s : a = 3 (s–a), b = 4 (s–b , ודרך a המשקל 5), c = 5 (s–b–c). עץ המסלולים הקצרים הוא {s–a, s–b, b–c} במשקל 8 . אבל העפ"מ (קרוסקל: b–c , a–b , s–a) הוא {b–c, a–b, s–a} במשקל 6 . העצים שונים, ועץ המסלולים הקצרים אינו מינימלי.

בדיקה: בדוגמאות הנגדיות: בטענה (3) העפ"מ היחיד מכיל את C–D ; בטענה (7) העפ"מ {s–a, a–b, b–c} והמרחקים 0, 3, 4, 5 .

טעות נפוצה: בטענה (3) – לחשוב שקרוסקל "אף פעם לא בוחר" בקשת הכבדה ביותר. הוא כן בוחר בה, כשאין דרך אחרת לחבר את אחד הקודקודים.

מה נדרש: לקבוע לארבעה גרפים אם יש להם בדיוק מיון טופולוגי אחד; אם לא – להציג שני מיונים שונים, או להראות שאין מיון כלל.

רעיון: בונים מיון טופולוגי כך: בכל שלב בוחרים קודקוד שדרגת הכניסה שלו (בגרף שנותר) היא 0 , ומוחקים אותו. אם בכל שלב יש בדיוק מועמד אחד – המיון יחיד. אם בשלב כלשהו יש שני מועמדים – אפשר לבחור כל אחד מהם ולקבל שני מיונים שונים. אם בשלב כלשהו אין מועמד – יש בגרף מעגל ואין מיון כלל. (שקול לכך: המיון יחיד אם ורק אם כל שני קודקודים סמוכים בו מחוברים בקשת – כלומר יש בגרף מסלול מכוון שעובר בכל הקודקודים.)

פתרון: (הקשתות כפי שבאיור)

בדיקה: מספר המיונים הטופולוגיים בכל גרף: D₁ – 1 , D₂ – 2 , D₃ – 1 , D₄ – 2 , D₅ – 0 , D₆ – 1 , D₇ – 4 .

טעות נפוצה: לחשוב ש־ D₅ "אינו מיון יחיד" בגלל שיש לו כמה מיונים – אין לו אף מיון, כי יש בו מעגל. וב־ D₇ , שנראה כמו "שרשרת", D יכול להופיע בכל מקום לפני E .

מה נדרש: לבחור אלגוריתם למסלול קל ביותר בגרף עם משקלים שליליים (בלי מעגל שלילי), לתת את הסיבוכיות, ולהריץ אותו על G₁ בסדר הקשתות הנתון.

רעיון: אלגוריתם בלמן־פורד: מאתחלים d[S] = 0 ושאר הערכים ∞, ומבצעים V−1 סבבים. בכל סבב עוברים על כל הקשתות ומקלים כל קשת u→v: אם d[u] + w(u,v) < d[v] אז d[v] ← d[u] + w(u,v) ו־π[v] ← u. מסלול קל ביותר (בלי מעגל שלילי) הוא פשוט ויש בו לכל היותר V−1 קשתות, ואחרי הסבב ה־i כל מסלול קל ביותר עם i קשתות לכל היותר כבר נמצא. (דייקסטרה אינו מתאים לגרף "כלשהו" עם משקלים שליליים: הוא מקבע ערך של קודקוד כשהוא נשלף, וקשת שלילית שנבדקת אחר כך עלולה להקטין אותו.)

סיבוכיות: V−1 סבבים, ובכל סבב מקלים את כל E הקשתות, כל הקלה O(1): O(V·E). (סבב נוסף לבדיקת מעגל שלילי מוסיף O(E).)

פתרון – מעקב על G₁ (V = 5, ולכן 4 סבבים). בכל תא: d (π) בסוף הסבב.

הסברים:

שחזור המסלול לפי π: T ← Q ← S.
המסלול: S → Q → T, אורכו 3 + 1 = 4.

בדיקה: בלמן־פורד באותו סדר קשתות נותן בדיוק את הטבלה, ובסבב נוסף אין שיפור (אין מעגל שלילי). כל המסלולים מ־S ל־T: SQT = 4, SQPRT = 5, SPRT = 8, SQRT = 8 – והמינימום 4 יחיד.

מה נדרש: לבדוק אם P נשאר קצר ביותר אחרי (א) הוספת x לקשתות היוצאות מ־s, (ב) הפחתת x מכל הקשתות.

רעיון: נבדוק איך משתנה משקל של מסלול שלם בכל אחד מהשינויים. כשאין מעגל שלילי, מספיק להשוות מסלולים פשוטים (בלי חזרה על קודקוד).

פתרון:
הגדלת הקשתות היוצאות מ־s – כן, P נשאר קצר ביותר. מסלול פשוט מ־s ל־t יוצא מ־s בקשת הראשונה שלו ולא חוזר ל־s לעולם. לכן הוא משתמש בדיוק בקשת אחת שיוצאת מ־s, ומשקלו גדל בדיוק ב־x. כל המסלולים הפשוטים גדלים באותו x, והסדר ביניהם לא משתנה. (המשקלים רק גדלים, ולכן גם לא נוצר מעגל שלילי.) P נשאר מסלול קצר ביותר, ואורכו גדל ב־x.

הקטנת כל הקשתות ב־x – לא בהכרח. מסלול עם k קשתות קטן ב־k·x, ולכן מסלול עם הרבה קשתות "מרוויח" יותר ממסלול עם מעט קשתות. (בגרף עם מעגלים, הקטנה כזאת יכולה אפילו ליצור מעגל שלילי, ואז אין מסלול קצר ביותר בכלל.)
דוגמה נגדית – הגרף G₁ מסעיף (1), x = 1:

לפני השינוי S→Q→T היה הקצר ביותר (4 < 5), ואחרי השינוי S→Q→P→R→T קל יותר.

בדיקה: הגדלת הקשתות היוצאות מ־S ב־G₁ ב־x נותנת תמיד את S→Q→T באורך 4+x. אחרי הפחתת 1 מכל הקשתות בלמן־פורד החזיר S→Q→P→R→T באורך 1.

טעות נפוצה: לחשוב שאפשר "לתקן" משקלים שליליים על ידי הוספת אותו מספר לכל הקשתות ואז להריץ דייקסטרה. זה משנה את המסלולים, מאותה סיבה בדיוק.

מה נדרש: שתי סריקות DFS מ־a שנותנות עצים עם מספר עלים שונה (עלה = קודקוד בלי בנים בעץ).

רעיון: הקשתות בגרף: a→b , a→c , a→e , c→b , b→d , e→d. אם b מתגלה דרך c, אז c אינו עלה; אם b מתגלה ישירות מ־a – c נשאר עלה.

פתרון:
סריקה 1 (סדר השכנים של a: b, c, e):
a → b → d (ל־d אין קשתות יוצאות, חוזרים עד a) → c (הקשת c→b מובילה לקודקוד שכבר התגלה) → e (הקשת e→d מובילה לקודקוד שכבר התגלה).
קשתות העץ: a–b , b–d , a–c , a–e. העלים: d, c, e – 3 עלים.

סריקה 2 (סדר השכנים של a: c, b, e):
a → c → b → d (חוזרים עד a) → הקשת a→b מובילה לקודקוד שכבר התגלה → e (e→d כבר התגלה).
קשתות העץ: a–c , c–b , b–d , a–e. העלים: d, e – 2 עלים.

בדיקה: יש 4 עצי DFS מ־a: מספרי העלים בהם הם בדיוק 2 ו־3, ושני העצים שלמעלה נמצאים ביניהם.

מה נדרש: להוסיף כמה שפחות קשתות כך שיהיו שלוש סריקות DFS מ־a עם שלושה מספרי עלים שונים.

רעיון: קודם נראה שבגרף המקורי מתקבלים רק 2 או 3 עלים, ולכן צריך להוסיף לפחות קשת אחת. אחר כך נראה שקשת אחת מספיקה.
בעץ DFS מ־a יש 4 קודקודים מלבד השורש. נבדוק מי מהם יכול להיות אב (לא עלה):

כלומר מספר הקודקודים שאינם עלים (מלבד a) הוא 1 או 2, ומספר העלים הוא 4−1 = 3 או 4−2 = 2. צריך להוסיף לפחות קשת אחת.

פתרון: מוסיפים את הקשת a→d (מקווקוות באדום):

שלוש סריקות מ־a:

מספר הקשתות שהוספנו: 1 – וזה המינימום. (מתאימות גם b→e , d→e או e→c – כל אחת מהן מאפשרת עץ שהוא שרשרת עם עלה אחד, למשל a→c→b→d→e אחרי הוספת d→e.)

בדיקה: בגרף המקורי יש רק 2 ו־3 עלים; מבין ההוספות של קשת אחת: a→d נותנת {2, 3, 4}, ו־b→e , d→e , e→c נותנות {1, 2, 3}. שלושת העצים שבטבלה נמצאו בין עצי ה־DFS של הגרף החדש.

מה נדרש: הקודקודים שאפשר להגיע אליהם מ־ vⱼ בלי לעבור באף קשת "כבדה" (משקל > k).

רעיון: אם מוחקים מהגרף את כל הקשתות שמשקלן גדול מ־ k , מבוקשים בדיוק הקודקודים הישיגים מ־ vⱼ בגרף שנשאר. אין צורך למחוק בפועל – מספיק ש־BFS ידלג על קשת כבדה.

פתרון:

LightReach(G, vⱼ, k):
    לכל קודקוד u:  visited[u] ← false
    visited[vⱼ] ← true ;  Q ← תור ריק ;  Q.insert(vⱼ)
    R ← רשימה ריקה
    כל עוד Q אינו ריק:
        u ← Q.remove()
        לכל שכן v של u , כשמשקל הקשת u – v הוא w:
            אם w ≤ k וגם visited[v] = false:
                visited[v] ← true ;  הוסף את v ל־R ;  Q.insert(v)
    החזר את R

זמן ריצה: כל קודקוד נכנס לתור פעם אחת לכל היותר, וכל רשימת סמיכויות נסרקת פעם אחת (הבדיקה w ≤ k היא O(1)) ⇒ O(|V| + |E|).

בדיקה – על הגרף שבדוגמה עם vⱼ = 0 , k = 4 (שכנים בסדר עולה):

התוצאה {3, 7} – כמו בדוגמה. עם k = 5 היו מתקבלים 3 , 5 , 7 , 9 (דרך 7 – 9 במשקל 5 ו־ 9 – 5 במשקל 1).

טעות נפוצה: לבדוק רק את הקשתות היוצאות מ־ vⱼ – הקודקוד 7 מחובר ל־0 בקשת במשקל 6 , אבל הוא ישיג דרך 3 בקשתות 4 ו־ 2 .

מה נדרש: למצוא את רכיב הקשירות עם הכי הרבה קודקודים, ולבנות לו עץ פורש מינימלי.

רעיון:

פתרון:

MstOfLargest(G):
    // שלב 1: מציאת רכיב הקשירות הגדול ביותר
    לכל קודקוד u:  visited[u] ← false
    best ← קבוצה ריקה
    לכל קודקוד s מ־v₀ עד vₙ₋₁:
        אם visited[s] = false:
            comp ← BFS(s)      // מסמן ב־visited ומחזיר את כל הקודקודים שהתגלו
            אם |comp| > |best|:  best ← comp
    // שלב 2: האלגוריתם של פרים בתוך best
    r ← קודקוד כלשהו ב־best
    לכל קודקוד v:  key[v] ← ∞ ;  parent[v] ← null ;  inTree[v] ← false
    key[r] ← 0 ;  T ← רשימה ריקה
    חזור |best| פעמים:
        u ← הקודקוד שאינו בעץ וה־key שלו הקטן ביותר
        inTree[u] ← true
        אם parent[u] ≠ null:  הוסף את הקשת (parent[u], u) ל־T
        לכל שכן v של u , כשמשקל הקשת u – v הוא w:
            אם inTree[v] = false וגם w < key[v]:
                key[v] ← w ;  parent[v] ← u
    החזר את T

(אפשר גם להריץ את קרוסקל רק על הקשתות שבתוך best: למיין אותן לפי משקל ולהוסיף כל קשת שאינה סוגרת מעגל.)

זמן ריצה: שלב 1 – כל הסריקות יחד O(|V| + |E|). שלב 2 – |best| ≤ |V| איטרציות, בכל אחת חיפוש המינימום O(|V|) ועדכון השכנים; סך עדכוני השכנים O(|E|) ⇒ O(|V|² + |E|) = O(|V|²) (או O(|E|·log|V|) עם ערימה).

בדיקה – על הגרף שבדוגמה. שלב 1: BFS מ־0 מוצא {0, 3, 5, 7, 9} (5 קודקודים), BFS מ־1 מוצא {1, 4, 8} (3), BFS מ־2 מוצא {2, 6} (2). הגדול: {0, 3, 5, 7, 9}. שלב 2: פרים מ־ r = 0 (בעמודה האחרונה – key החדש של שכן, ובסוגריים ה־parent שלו):

הקשתות שהוחזרו: (0, 3) , (3, 7) , (7, 9) , (9, 5) – משקל כולל 4 + 2 + 5 + 1 = 12 , כמו בדוגמה (אותן קשתות, בסדר אחר). זה העץ הפורש המינימלי היחיד של הרכיב.

טעות נפוצה: להריץ פרים על הגרף כולו ולצפות לעץ אחד – הגרף אינו קשיר, ופרים מקודקוד אחד לעולם לא יגיע לרכיבים האחרים (ואם בוחרים "קודקוד כלשהו" שאינו ברכיב הגדול – מקבלים עץ של רכיב אחר).

מה נדרש: לבדוק אם איחוד של שפה רגולרית עם שפה לא רגולרית הוא בהכרח לא רגולרי.

רעיון: אם השפה הרגולרית "בולעת" את השפה הלא רגולרית (L₂ ⊆ L₁), האיחוד שווה ל־ L₁ ולכן רגולרי.

פתרון: הטענה לא נכונה. דוגמה נגדית:

בדיקה: מילים של L₂ עד אורך 8 – ε, ab, aabb, aaabbb, aaaabbbb – כולן ב־ Σ*, והאיחוד הוא Σ*.

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

מה נדרש: להוכיח או להפריך ששרשור של L* עם עצמה שווה ל־ L*.

רעיון: מראים הכלה בשני הכיוונים. L* היא קבוצת כל השרשורים של 0 או יותר מילים מ־ L (כולל ε).

פתרון: הטענה נכונה.

משתי ההכלות: L* • L* = L*.

בדיקה: למשל עבור L = {a}: גם L* וגם L* • L* הן כל המילים מעל {a}. למשל L = {ab}: L* = {ε, ab, abab, …}, ו־ ab • abab = ababab ∈ L*.

מה נדרש: לבדוק לכל מילה שני תנאים: (1) אין בה את הרצפים ba ו־ cc; (2) #b(w) + #c(w) אי־זוגי.

פתרון:

בדיקה: הגדרת השפה והאוטומט מסעיף ב(2) נותנים בדיוק את התשובות האלה.

טעות נפוצה: לקבל את ε בגלל שאין בה רצפים אסורים – אבל 0 הוא מספר זוגי, ולכן ε ∉ L.

מה נדרש: אוטומט סופי דטרמיניסטי עבור L, שמותר שיחסרו בו מעברים (מעבר חסר = המילה נדחית).

רעיון: האוטומט צריך לזכור שני דברים:

לכן 3 × 2 = 6 מצבים. מעבר שיוצר רצף אסור אינו מוגדר (במקום מצב בור) – לכן האוטומט אינו מלא.

פתרון – Σ = {a, b, c}, מצב התחלתי q0, מצבים מקבלים {q1, q3, q5}:

("–" = אין מעבר, המילה נדחית.)

הסבר המעברים: a מעביר ל"אחרון a" בלי לשנות זוגיות (חסר אחרי b); b מעביר ל"אחרון b" ומחליף זוגיות; c מעביר ל"אחרון c" ומחליף זוגיות (חסר אחרי c).

בדיקה:

האוטומט מקבל בדיוק את המילים של השפה – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a, b, c}.

טעות נפוצה: לסמן את q0 כמקבל – בהתחלה הסכום הוא 0 (זוגי), ולכן q0 אינו מקבל.

מה נדרש: לבדוק חמש מילים מול הגדרת L.

רעיון: מחשבים n, m, k, בודקים את זוגיות n ומפעילים את התנאי המתאים.

פתרון:

בדיקה: לפי הגדרת השפה: aabbc ✗, abbbbc ✓, aaaabbcc ✗, aabbcccc ✓, aaabbbbccc ✓ – וכך גם האוטומט מסעיף ג.

מה נדרש: המילה הקצרה ביותר בכל אחד מהמקרים.

פתרון:

בדיקה: בין המילים עד אורך 8: הקצרה ביותר עם n זוגי – aabb בלבד; הקצרה ביותר עם n אי־זוגי שיש בה b – abbc בלבד.

מה נדרש: להשלים לכל מעבר ממוספר את ראש המחסנית והפעולה, ולציין את המצבים המקבלים.

רעיון: המעברים בין q₀ ל־q₁ נתונים: אחרי n אותיות a המחסנית היא S A…A (n סימנים, ראש המחסנית מימין), והאוטומט ב־q₀ אם n זוגי וב־q₁ אם n אי־זוגי. (כש־n = 1 ראש המחסנית הוא S.)

ענף n זוגי (q₀ → q₂ → q₃ ⇄ q₄): צריך m = n , ואחר כך מספר זוגי של c.

ענף n אי־זוגי (q₁ , q₅ , q₆ , q₇ , q₈): ה־b לא משנים את המחסנית, רק את הזוגיות: q₅ = מספר אי־זוגי של b , q₆ = מספר זוגי (לפחות 2). המעברים 6–8 צריכים לפעול גם כש־A בראש וגם כש־S בראש (n = 1), ולכן על כל אחד מהם שני סימונים.

פתרון: (ראש המחסנית / פעולה)

מצבים מקבלים: q₃ , q₈ .

האוטומט דטרמיניסטי: מכל מצב, לכל זוג (אות קלט, ראש מחסנית) יש לכל היותר מעבר אחד.

בדיקה:

השלמה חלופית: אפשר גם לרשום במעבר 3 "S / ללא שינוי" (ה־S נשאר בתחתית), ואז במעברים 4 ו־5 בראש המחסנית יופיע S (S / ללא שינוי). גם השלמה זו מקבלת בדיוק את L. באופן כללי, כל השלמה שמקבלת בדיוק את L נכונה.

טעות נפוצה: לערבב בין שתי ההשלמות – S / ללא שינוי במעבר 3 אבל "ריקה" במעברים 4–5: אז aabbcc נדחית. בענף האי־זוגי – לשכוח את הסימון S במעברים 6–8 (אז abbc נדחית).

מה נדרש: המילה הקצרה ביותר ב־L₁.

רעיון:
אורך המילה הוא n + k + k + 2n = 3n + 2k. הוא הקטן ביותר כש־n ו־k קטנים ככל האפשר, כלומר n = k = 1.

פתרון:
n = 1, k = 1: a¹ b¹ a¹ c² = abacc (אורך 5). כל בחירה אחרת של n, k ≥ 1 נותנת אורך 7 לפחות, ולכן זו המילה הקצרה ביותר והיחידה באורך זה.

בדיקה: המילים של L₁ עד אורך 9 הן abacc, abbaacc, aabacccc, abbbaaacc – הקצרה ביותר abacc.

טעות נפוצה: לבחור n = 0 או k = 0 (למשל המילה הריקה או aacc) – בשפה n, k ≥ 1.

מה נדרש: אוטומט מחסנית דטרמיניסטי ל־L₁ = {aⁿ bᵏ aᵏ c²ⁿ | n, k ≥ 1}.

רעיון:

פתרון:

בכל צירוף (מצב, אות, ראש מחסנית) יש לכל היותר מעבר אחד ואין מעברי ε – האוטומט דטרמיניסטי. צירוף שאינו בטבלה = דחייה (למשל b אחרי שהתחיל הגוש השני של a; a נוסף כשבראש המחסנית כבר A או X – יותר a מ־b; c כשבראש עדיין B – פחות a מ־b; כל אות אחרי q6).

מעקב על aabacccc (n = 2, k = 1):

הקלט נגמר במצב q6 ⇒ מתקבלת.

בדיקה: האוטומט מקבל בדיוק את המילים של L₁ – גם מילים של L₁ וגם מילים שמתקבלות מהן בשינוי, הוספה או מחיקה של אות אחת מטופלות נכון. למשל abacc, abbaacc, aabacccc מתקבלות; abaccc (מספר אי־זוגי של c), abbacc (פחות a מ־b), aabaccc נדחות.

טעות נפוצה: לדחוף סימן גם על ה־a שבגוש השני – אז אין דרך להשוות אותם ל־b. ה־a השניים צריכים לשלוף.

מה נדרש: לקבוע לכל מילה אם אפשר לחלק אותה לשני חלקים: הראשון ב־R(L₁) והשני ב־L₁.

רעיון:
ההיפוך של aⁿ bᵏ aᵏ c²ⁿ הוא c²ⁿ aᵏ bᵏ aⁿ, ולכן R(L₁) = {c²ⁿ aᵏ bᵏ aⁿ | n, k ≥ 1}. לכן מילה ב־L₂ נראית כך: c²ⁿ aᵏ bᵏ aⁿ ואחריה aᵐ bʲ aʲ c²ᵐ (n, k, m, j ≥ 1). מספר ה־c בהתחלה קובע את n, מספר ה־a שאחריהם קובע את k – ולכן החלק הראשון נקבע באופן יחיד, ונשאר לבדוק את השארית.

פתרון:
(1) ccabaabacc: בהתחלה 2 c ⇒ n = 1; אחריהן a אחד ⇒ k = 1; אז b אחד ו־a אחד (aⁿ, n = 1). החלק הראשון: ccaba = R(abacc) ∈ R(L₁). השארית: abacc = a¹ b¹ a¹ c² ∈ L₁ (m = j = 1). ⇒ שייכת ל־L₂.

(2) ccabaabaacc: שוב 2 c ⇒ n = 1, ואחריהן a אחד ⇒ k = 1, b אחד, a אחד: החלק הראשון חייב להיות ccaba (אין חלוקה אחרת). השארית: abaacc – a¹ b¹ ואז aa: ב־L₁ אחרי b¹ באים בדיוק a¹ ואז c, אבל כאן באים שני a. השארית אינה ב־L₁. ⇒ לא שייכת ל־L₂.

(3) ccccabaaabbaacc: 4 c ⇒ n = 2; a אחד ⇒ k = 1; b אחד; ואז aⁿ = aa. החלק הראשון: ccccabaa = R(aabacccc) ∈ R(L₁). השארית: abbaacc = a¹ b² a² c² ∈ L₁ (m = 1, j = 2). ⇒ שייכת ל־L₂.

בדיקה: בכל נקודות החלוקה האפשריות לכל מילה: (1) – חלוקה אחת ccaba | abacc; (2) – אין אף חלוקה; (3) – חלוקה אחת ccccabaa | abbaacc.

טעות נפוצה: להפוך את L₁ "בגושים" (c²ⁿ bᵏ aᵏ aⁿ) במקום להפוך את סדר כל האותיות: ההיפוך של aⁿ bᵏ aᵏ c²ⁿ הוא c²ⁿ aᵏ bᵏ aⁿ.

מה נדרש – לארגן את המחלקות בהיררכיית ירושה כך שכל תכונה וכל פעולה יופיעו פעם אחת בלבד, ולסרטט את תרשים ההייררכייה.

רעיון

כך מתקבלים שני "ענפים" מתחת ל־Exhibit: ציורים ופסלים.

פתרון – :

public class Painting extends Exhibit {
    private String artist;
    public void light() {
        System.out.println("Light on " + artist);
    }
}
public class Portrait extends Painting {
    private String person;        // מי מצויר בדיוקן
}
public class Statue extends Exhibit {
    private String material;      // חומר: אבן/ברונזה/שיש
}
public class Bust extends Statue {
    private int height;           // גובה בסנטימטרים
}

תרשים ההייררכייה (החץ עם המשולש הריק מצביע מהמחלקה היורשת אל מחלקת הבסיס):

בדיקה – המחלקות המלאות (אותן כותרות ותכונות, יחד עם הפעולות הבונות מסעיף ב) תקינות ב־Java וב־C#.

טעות נפוצה: להוריש את Bust ישירות מ־Exhibit ולהשאיר בה את material – כפילות קוד; פסל ראש הוא פסל.

מה נדרש – פעולות בונות שמתאימות לקריאות ב־main / Main ומאתחלות את כל התכונות.

רעיון

פתרון – הקוד המלא בלשונית Java/C#.

בדיקה – המחלקות עם הפעולות הבונות ו־Tester הנתונה תקינות ב־Java וב־C#, והפעולה הראשית מתבצעת ללא שגיאות.

טעות נפוצה: לכתוב ב־Portrait this.artist = artist; – artist פרטית ב־Painting, ולכן זו שגיאת הידור; מעבירים אותה ב־super.

מה נדרש – לדרוס את toString (ב־C#: ToString) רק במחלקות שבהן הפלט שונה מזה שהמחלקה כבר יורשת.

רעיון – println(hall[i]) מפעיל את toString של הטיפוס בפועל של העצם. נבדוק כל שורה בפלט:

לפי הנתון, פסל ראש שגובהו 50 ס"מ לפחות הוא Large, ולכן התנאי הוא height >= 50 (Poet בגובה 55 – Large; Sailor בגובה 30 – Small).
ב־C# כל ToString מוגדרת עם override (גם ב־Bust, שדורסת את הגרסה של Statue).

פתרון – הקוד המלא (המחלקות הסופיות) בלשונית Java/C#.

בדיקה – Tester עם הלולאה הנתונה (Java ו־C#) מדפיסה בדיוק:

Queen, 1720 by Ruth
Statue: Rider, 1904 [bronze]
Large bust of Poet
Garden, 1889 by Vincent
Small bust of Sailor

טעות נפוצה: להוסיף toString גם ל־Portrait (מיותר), או לכתוב ב־Bust super.toString() – זה היה מדפיס Statue: Poet, 1860 [marble].

מה נדרש – לקבוע אם הפעולה תקינה; אם לא – לתקן ולכתוב את הפלט עבור hall.

רעיון – הפעולה לא תקינה (שגיאת הידור): הטיפוס המוצהר של arr[i] הוא Exhibit, וב־Exhibit אין פעולה light() (ב־C#: Light()). המהדר בודק את הקריאה לפי הטיפוס המוצהר, ולא לפי העצם שיהיה שם בזמן ריצה.
התיקון: לבדוק אם העצם הוא ציור (instanceof Painting ב־Java, is Painting ב־C#), ורק אז להמיר ל־Painting ולקרוא ל־light(). Portrait יורשת מ־Painting, ולכן גם דיוקן עובר את הבדיקה; פסלים ופסלי ראש לא.

פתרון – הפעולה המתוקנת בלשונית Java/C#.

בדיקה – עבור hall: Portrait (תא 0, הציירת Ruth) ו־Painting (תא 3, הצייר Vincent) מדפיסים. הפלט (Java ו־C#):

Light on Ruth
Light on Vincent

הפעולה המקורית אכן לא עוברת הידור (Java: cannot find symbol; C#: שגיאה CS1061). במערך עם Bust, תא null, Exhibit ו־Painting מודפסת שורה אחת (Light on Maya), בלי שגיאה.

מה נדרש – לבחור לכל תא במערך עצם (ופעולה בונה) כך שתודפס בדיוק השורה הנתונה.

רעיון

בדיקת הסכום: 8 + 40 + 60 + 40 + 8 + 40 = 196 – בדיוק הערך שמודפס. השורה (4) חייבת להיות new Led() ולא new Led("white"): Led עם מחרוזת נותנת תמיד 8W. השורה (2) – Strip: רק ל־Strip יש מטרים, והצבע שלה תמיד white כי היא עוברת דרך Led().

פתרון – השורות החסרות (זהות ב־Java וב־C#):

arr[0] = new Led("red");     // (1)
arr[1] = new Strip(3);       // (2)
arr[2] = new Lamp(60);       // (3)
arr[3] = new Led();          // (4)
arr[4] = new Led("blue");    // (5)
arr[5] = new Strip(2);       // (6)

התוכנית המלאה בלשונית Java/C#.

בדיקה – הפלט ב־Java וב־C# הוא בדיוק הפלט הנדרש:

red[8W/196W]
3m white[40W/196W]
[60W/196W]
white[40W/196W]
blue[8W/196W]
2m white[40W/196W]

מעבר על כל הבחירות האפשריות של פעולות בונות (עם הארגומנטים שמופיעים בפלט) מראה שזה הפתרון היחיד.

טעות נפוצה: לחשוב שבשורה (1) יודפס red[8W/8W] – total סטטית, וההדפסה מתבצעת רק אחרי שכל העצמים נוצרו. טעות נוספת: לשכוח ש־Lamp() לא מציבה בעצמה דבר – היא עוברת ל־Lamp(40), ושם total גדלה.

מה נדרש – לקבוע אם Strip שיורשת ישירות מ־Lamp גורמת לשגיאה, ואם לא – מה הפלט.

רעיון

בדיקה – הגרסה ששונתה (Java ו־C#) מדפיסה:

red[8W/196W]
3m [40W/196W]
[60W/196W]
white[40W/196W]
blue[8W/196W]
2m [40W/196W]

טעות נפוצה: לחשוב שאחרי השינוי total ישתנה – ההספק של Strip נקבע ב־Lamp() גם לפני השינוי (דרך Led()) וגם אחריו.

מה נדרש – לצייר את העצמים שנוצרים ולכתוב את הפלט.

רעיון – לכל new רצה הפעולה הבונה המתאימה לפרמטרים. Dot() קוראת ל־this(5) (ב־C# : this(5)), כלומר ל־Dot(int v). הפעולות הבונות של Ring קוראות קודם לפעולה הבונה של Dot (super/base). התכונה count היא תכונת מחלקה (static) – יש ממנה עותק אחד משותף לכל העצמים, והיא גדלה ב־1 בכל פעם ש־Dot(int v) רצה, כלומר פעם אחת לכל עצם שנוצר (Dot או Ring). arr[3] = arr[1] לא יוצרת עצם. ההדפסה מזמנת את toString של העצם בפועל.

פתרון

ההמרה (Ring) arr[2] נחוצה כי arr[2] הוא מטיפוס Dot (ההפניה), והפעולה הבונה מצפה ל־Ring; העצם עצמו הוא אכן Ring, לכן ההמרה מצליחה.

העצמים (4 עצמים בלבד):

arr[0] ──► Dot   v = 5
arr[1] ──► Ring  v = 5, r = 1   ◄── arr[3]   (אותו עצם!)
arr[2] ──► Ring  v = 4, r = 3
arr[4] ──► Ring  v = 4, r = 13

הפלט:

v = 5
(v = 5, r = 1)
(v = 4, r = 3)
(v = 5, r = 1)
(v = 4, r = 13)
count = 4

בדיקה – הפלט זהה ב־Java וב־C# ותואם לטבלה.

טעות נפוצה: לחשוב ש־Dot() ו־Dot(5) מגדילות את count פעמיים – Dot() רק מעבירה את הבנייה ל־Dot(int v), ולכן כל עצם מוסיף 1 בדיוק. וגם: לספור את arr[3] כעצם חמישי.

מה נדרש – לעקוב אחר הזימונים ולכתוב את כל מה שמודפס.

רעיון – up ו־step(int) דרוסות ב־Ring; step() בלי פרמטרים קיימת רק ב־Dot, והיא קוראת פעמיים ל־up() – וזו נבחרת לפי סוג העצם בזמן ריצה. ב־Ring, step(int k) קוראת קודם ל־super.step(k) (הגרסה של Dot, שמכפילה את v) ואחר כך מקטינה את r. המרה (casting) משנה רק את טיפוס ההפניה, לא את העצם. ב־C# Up ו־Step(int) מוגדרות virtual ונדרסות ב־override, ו־Step() (שאינה virtual) קוראת ל־Up הווירטואלית – ההתנהגות זהה.

פתרון

מצב המערך בסוף: arr[0] → e (v=3, r=8); arr[1] ו־arr[3] → אותו Ring (v=15, r=10); arr[2] → Ring (v=8, r=2); arr[4] → Ring (v=4, r=17). count = 5 (חמישה עצמים נוצרו בסך הכול; העצם Dot המקורי של arr[0] כבר לא מודפס, אבל נספר).

הפלט:

e: (v = 3, r = 8)
(v = 3, r = 8)
(v = 15, r = 10)
(v = 8, r = 2)
(v = 15, r = 10)
(v = 4, r = 17)
count = 5

בדיקה – הפלט של ההמשך (אחרי סעיף א) זהה ב־Java וב־C# ותואם לטבלה. שימו לב ש־v של עצמי Ring משתנה רק ב־step(int), כי Dot.up לא רצה על עצמי Ring.

טעות נפוצה: לחשוב ש־arr[1].step() מפעילה את Dot.up (כי step כתובה ב־Dot) – הקריאה up() שבתוך step נבחרת לפי סוג העצם, ולכן רצה Ring.up. וגם: לשכוח ש־q הוא אותו עצם כמו arr[1] ו־arr[3].