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

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

רעיון: כל עוד התור אינו ריק, מוציאים את האיבר הראשון v, ומעבירים את כל שאר האיברים דרך תור עזר temp: איבר x השווה ל־ v נספר (same++) ואינו מוחזר, ואיבר אחר מוכנס ל־ temp. אם לא נמצא אף איבר אחר השווה ל־ v (same == 0) – זה מוצר בודד, ומגדילים את המונה. בסוף הסבב מחזירים את האיברים מ־ temp אל q. כך בכל סבב יוצאים מהתור כל המופעים של מוצר אחד, וכל קוד מוצר נבדק פעם אחת בדיוק. התור מתרוקן בסוף, וזה מותר כי אין צורך לשמור עליו.

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

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

בדיקה (התור 7, 2, 7, 5, 9, 2, 7, 4):

הפעולה מחזירה 3. מקרים נוספים: 3, 3 ← 0; 1, 2 ← 2; 4, 6, 4, 6, 4 ← 0; 10, 20, 30, 20 ← 2.

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

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

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

פתרון – מעקב (השרשרת 3, 8, 5, 3, 6, 8, 6, 5; x = 6):
הקריאות יורדות: 3 ≠ 6 → 8 ≠ 6 → 5 ≠ 6 → 3 ≠ 6 → 6 == 6, והקריאה על החוליה החמישית מחזירה 1. החוליות 8, 6, 5 שאחריה לא נבדקות כלל.
החזרה (מהקריאה העמוקה החוצה):

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

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

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

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

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

בדיקה: על השרשרת 3, 8, 5, 3, 6, 8, 6, 5:

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

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

פתרון: כל קריאה מבצעת לכל היותר קריאה רקורסיבית אחת, על החוליה הבאה, ועוד מספר קבוע של פעולות (השוואות, getValue, חיבור), כלומר O(1).

הסיבוכיות (המקרה הגרוע) היא O(n).

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

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

רעיון: לפי סעיף א, d = what(lst.getNext(), lst.getValue()) הוא המקום של ההופעה הבאה של ערך החוליה בהמשך השרשרת – כלומר המרחק (במספר צעדים) מהחוליה הנוכחית לחוליה הבאה עם אותו ערך, או 0 אם אין כזו. r = guess(lst.getNext()) היא התוצאה על המשך השרשרת. הפעולה מחזירה את d אם d ≠ 0 ו־d קטן מ־r (או ש־r = 0), אחרת את r.
הקריאה הרקורסיבית על ההמשך מסתיימת לפני ההשוואה, ולכן התוצאות נקבעות מהחוליה האחרונה לראשונה.

פתרון – מעקב (השרשרת 3, 8, 5, 3, 6, 8, 6, 5; השורות לפי סדר החזרה מהרקורסיה):

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

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

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

רעיון: לכל חוליה, d הוא המרחק ממנה להופעה הבאה של אותו ערך (0 אם אין). guess מחזירה את הערך הקטן ביותר מבין כל ה־d השונים מ־0, כשהערך 0 משמש כסימן ל"עוד לא נמצא מרחק": התנאי d != 0 מדלג על חוליות שאין להן חוזרת, והתנאי r == 0 מאפשר ל־d הראשון שנמצא להיכנס.

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

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

בדיקה: 1, 2, 3, 4 ⇒ 0; ‏7, 7 ⇒ 1; ‏2, 9, 4, 2, 9 ⇒ 3.

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

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

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

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

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

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

הבחנה: "עץ 0־זיגזג" בן 4 רמות לכל היותר יכול להכיל רק 7 צמתים (השורש ועוד שתי "שרשראות" ישרות – שמאלה וימינה – של 3 צמתים כל אחת). לכן ב־9 צמתים חייבות להיות פניות, ויש לפזר אותן כך שבכל מסלול תהיה לכל היותר אחת.

פתרון – עץ לדוגמה (המספרים בצמתים רק למעקב):

בכתיב מילולי: לשורש 1 – בן שמאלי 2 ובן ימני 3. ל־2 – בן שמאלי 4 ובן ימני 5. ל־3 – בן שמאלי 6 ובן ימני 7. ל־4 – רק בן שמאלי 8. ל־6 – רק בן שמאלי 9. הצמתים 5, 7, 8, 9 הם עלים.

בדיקה – כל המסלולים מהשורש לעלים:

9 צמתים, 4 רמות, ובכל מסלול לכל היותר פנייה אחת ⇒ "עץ 1־זיגזג". (ובדוגמה: isZigzagK(עץ, 1) = true, isZigzagK(עץ, 0) = false. בסריקה של כל צורות העצים בנות 4 רמות לכל היותר נמצאו 44 עצים כאלה.)
יש עוד תשובות נכונות רבות.

טעות נפוצה: לתת לצומת 6 בן ימני – במסלול 1 → 3 → 6 כבר יש פנייה (ימין ואז שמאל), והבן הימני היה יוצר פנייה שנייה.

מה נדרש: פעולה שבודקת שבכל מסלול מהשורש לעלה יש לכל היותר K פניות.

רעיון: כדי לדעת אם ירידה לבן היא פנייה, צריך לדעת מאיזה כיוון הגענו לצומת הנוכחי. לכן כותבים פעולת עזר רקורסיבית zigzag(node, k, fromLeft):

השורש עצמו לא הגיע מאף כיוון, ולכן הקשתות היוצאות ממנו אינן פניות: isZigzagK מזמנת את פעולת העזר על הבן השמאלי (fromLeft = true) ועל הבן הימני (fromLeft = false) עם אותו K.

פתרון:

public static boolean isZigzagK(BinNode<Integer> root, int k)
{
    // הקשת הראשונה במסלול אינה יכולה ליצור פנייה
    if (root.hasLeft() && !zigzag(root.getLeft(), k, true))
        return false;
    if (root.hasRight() && !zigzag(root.getRight(), k, false))
        return false;
    return true;
}

// node – צומת שהגענו אליו מאביו; fromLeft – האם הגענו אליו בקשת שמאלית;
// k – כמה פניות עוד מותר לבצע בהמשך המסלול
public static boolean zigzag(BinNode<Integer> node, int k, boolean fromLeft)
{
    if (node.hasLeft())
    {
        int kLeft = k;
        if (!fromLeft)
            kLeft = k - 1;   // ימינה ואז שמאלה – פנייה
        if (kLeft < 0 || !zigzag(node.getLeft(), kLeft, true))
            return false;
    }
    if (node.hasRight())
    {
        int kRight = k;
        if (fromLeft)
            kRight = k - 1;  // שמאלה ואז ימינה – פנייה
        if (kRight < 0 || !zigzag(node.getRight(), kRight, false))
            return false;
    }
    return true;
}

בדיקה: על העץ מהדוגמה בשאלה: isZigzagK(root, 0) = false, isZigzagK(root, 1) = false (המסלול המודגש: ימין, שמאל, ימין – 2 פניות), isZigzagK(root, 2) = true, isZigzagK(root, 3) = true. על העץ מסעיף א: K = 1 ⇒ true, K = 0 ⇒ false. עץ שהוא עלה יחיד עם K = 0 ⇒ true.

יעילות: כל צומת מבוקר פעם אחת לכל היותר, ובכל ביקור מספר קבוע של פעולות ⇒ O(n), כאשר n מספר הצמתים בעץ.

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

מה נדרש: למצוא את כל הקודקודים שהמרחק שלהם מ־ vⱼ (מספר הקשתות במסלול הקצר ביותר) הוא בין 1 ל־ k .

רעיון: סריקה לרוחב (BFS) מגלה את הקודקודים לפי סדר המרחק מ־ vⱼ : קודם כל הקודקודים במרחק 1, אחר כך במרחק 2, וכן הלאה, וכשקודקוד v מתגלה מהקודקוד u מתקיים dist[v] = dist[u] + 1 – זה המרחק הקצר ביותר. לכן מספיק לשמור לכל קודקוד את dist שלו, ולא להרחיב (לא לעבור על השכנים של) קודקוד שמרחקו כבר k – השכנים החדשים שלו היו במרחק k + 1 . כל קודקוד נכנס לתור פעם אחת בלבד, ואין מעבר על מסלולים.

פתרון (הגרף מיוצג ברשימות שכנויות):

WithinK(G, vⱼ, k):
    לכל קודקוד u ב־V:   dist[u] ← −1          // −1 = עוד לא התגלה
    dist[vⱼ] ← 0
    Q ← תור ריק ;  Q.insert(vⱼ)
    R ← רשימה ריקה                          // הקודקודים שיוחזרו
    כל עוד Q אינו ריק:
        u ← Q.remove()
        אם dist[u] < k:                       // רק אז השכנים במרחק ≤ k
            לכל שכן v של u:
                אם dist[v] = −1:
                    dist[v] ← dist[u] + 1
                    הוסף את v ל־R
                    Q.insert(v)
    החזר את R

זמן ריצה: האתחול O(|V|). כל קודקוד נכנס לתור לכל היותר פעם אחת, ורשימת השכנים של כל קודקוד נסרקת לכל היותר פעם אחת – סך הכול O(|V| + |E|).

בדיקה – על הגרף שבדוגמה מקודקוד 4 עם k = 2 (שכנים בסדר עולה; בסוגריים – המרחק):

התוצאה: 0, 2, 9 – כמו בדוגמה.

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

מה נדרש: כמה קשתות לכל הפחות צריך להוסיף כדי שהגרף יהיה קשיר, ואילו קשתות.

רעיון: נסמן ב־ c את מספר רכיבי הקשירות.

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

פתרון:

ConnectEdges(G):
    לכל קודקוד u ב־V:   visited[u] ← false
    reps ← רשימה ריקה                      // נציג אחד מכל רכיב
    לכל קודקוד s מ־ v₀ עד vₙ₋₁:
        אם visited[s] = false:               // s פותח רכיב קשירות חדש
            הוסף את s ל־reps
            visited[s] ← true ;  Q ← תור ריק ;  Q.insert(s)
            כל עוד Q אינו ריק:
                u ← Q.remove()
                לכל שכן v של u:
                    אם visited[v] = false:
                        visited[v] ← true ;  Q.insert(v)
    c ← מספר האיברים ב־reps
    edges ← רשימה ריקה
    לכל i מ־2 עד c:
        הוסף ל־edges את הקשת (reps[1], reps[i])
    החזר את c − 1 ואת edges

זמן ריצה: בכל הסריקות יחד כל קודקוד נכנס לתור פעם אחת וכל רשימת שכנים נסרקת פעם אחת ⇒ O(|V| + |E|); בניית רשימת הקשתות O(c) ⊆ O(|V|). סך הכול O(|V| + |E|).

בדיקה – על הגרף שבדוגמה:

reps = [0, 1, 8], c = 3 ⇒ מוחזר 2 עם הקשתות (0, 1), (0, 8) – כמו בדוגמה. אחרי הוספתן הגרף קשיר, ואף קשת אחת שתתווסף לא הופכת את הגרף לקשיר.

טעות נפוצה: להחזיר את מספר הרכיבים c במקום c − 1, או לחבר את הנציגים "בזוגות" (רכיב 1 עם 2, רכיב 3 עם 4...) – אז הגרף לא בהכרח נעשה קשיר.

מה נדרש: לכל צומת – רשימת הצמתים שיש אליהם קשת ממנו, לפי סדר האלף־בית.

רעיון: עוברים על רשימת הקשתות E . כל קשת (X → Y) מוסיפה את Y לשכנים היוצאים של X בלבד (הגרף מכוון).

פתרון:

בדיקה: בטבלה 1 + 2 + 1 + 2 + 2 + 0 + 2 = 10 שכנים יוצאים – כמספר הקשתות.

מה נדרש: להריץ את Order צעד אחר צעד ולרשום אחרי כל איטרציה את התור, את U , את שני המערכים ואת R .

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

פתרון:

בדיקה: מעקב אחרי Order בדיוק כמתואר נותן את אותה טבלה. כל קשת בגרף הולכת "קדימה" ברשימה R , והערך הסופי של level[v] שווה למספר הקשתות במסלול הארוך ביותר שמסתיים ב־ v (למשל F : E→G→A→C→F , 4 קשתות).

טעות נפוצה: להכניס צומת לתור כבר כשמקטינים את הערך שלו במערך indeg , לפני שהגיע ל־ 0 – למשל להכניס את A לתור כבר באיטרציה 1 . A נכנס לתור רק באיטרציה 4 , אחרי שגם G (שיש ממנו קשת אל A) הוצא מן התור.

מה נדרש: הרשימה R שמוחזרת בסוף הריצה.

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

פתרון: B , E , D , G , A , C , F .
זהו מיון טופולוגי של הגרף – סדר אפשרי לביצוע המשימות: כל קשת X → Y מקיימת ש־ X מופיע ברשימה לפני Y (למשל G → A : G במקום הרביעי ו־ A במקום החמישי).

בדיקה: התוצאה: ['B', 'E', 'D', 'G', 'A', 'C', 'F'], וכל 10 הקשתות הולכות קדימה ברשימה.

מה נדרש: דייקסטרה ממקור vⱼ , ואחר כך הדפסת המסלול אל vₜ בסדר הנכון (מההתחלה לסוף).

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

פתרון:

Dijkstra(G, w, vⱼ):
    לכל קודקוד v ב־V:   d[v] ← ∞ ;  π[v] ← NIL
    d[vⱼ] ← 0
    P ← ∅ ;  T ← V
    כל עוד T ≠ ∅:
        u ← הקודקוד ב־T שעבורו d[u] מינימלי
        T ← T − {u} ;  P ← P ∪ {u}
        לכל שכן v של u כך ש־ v ∈ T:
            אם d[u] + w(u, v) < d[v]:
                d[v] ← d[u] + w(u, v)
                π[v] ← u

PrintPath(v):                      // מדפיס את המסלול מ־ vⱼ אל v
    אם v = vⱼ:
        הדפס v
    אחרת:
        PrintPath(π[v])
        הדפס v

ShortestRoute(G, w, vⱼ, vₜ):
    Dijkstra(G, w, vⱼ)
    אם d[vₜ] = ∞:
        הדפס "אין מסלול"
    אחרת:
        PrintPath(vₜ)

בדיקה: המעקב על G מ־K מופיע בסעיף ב(1). עבור vₜ = W: PrintPath(W) קורא ל־PrintPath(T), שקורא ל־PrintPath(Q), וכן הלאה דרך P ו־M עד PrintPath(K), שמדפיס את K. בחזרה מהרקורסיה מודפס: K M P Q T W.

טעות נפוצה: להדפיס את v לפני הקריאה הרקורסיבית – אז המסלול מודפס הפוך (W T Q P M K).

מה נדרש: זמן הריצה של האלגוריתם מסעיף א(1) כפונקציה של n (ומספר הקשתות |E|).

פתרון (מימוש פשוט – d ו־π במערכים, הגרף ברשימות שכנויות):

לכן זמן הריצה הוא O(n²) + O(n) = O(n²).

(הערה: עם ערימת מינימום – O((n + |E|)·log n).)

מה נדרש: להריץ את דייקסטרה מ־K על G, להראות בכל איטרציה את P, T ואת d/π של כל קודקוד, ולמצוא מה יודפס עבור W.

רעיון: בכל איטרציה בוחרים מ־T את הקודקוד בעל d מינימלי (בגרף הזה לא היה שוויון בשום שלב), מעבירים אותו ל־P ומרפים את הקשתות לשכניו שב־T.

פתרון – טבלת המעקב (בכל תא: d/π; מודגש – הקודקוד שנקבע באיטרציה):

פירוט ההרפיות:

המסלולים הקלים ביותר מ־K:

עבור vₜ = W האלגוריתם ידפיס: K M P Q T W (זמן נסיעה 22 דקות).

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

טעות נפוצה: לקבוע את P עם 12 (הקשת הישירה K–P) – המסלול K → M → P קל יותר (9).

מה נדרש: לשרטט את העץ שנוצר מקשתות ההורה π.

רעיון: לכל קודקוד v ≠ K מוסיפים את הקשת (π[v], v). מתקבלות n − 1 = 9 קשתות היוצרות עץ ששורשו K.

פתרון: לפי השורה האחרונה בטבלה מסעיף ב(1): π[L] = K, π[M] = K, π[P] = M, π[N] = P, π[Q] = P, π[T] = Q, π[R] = N, π[W] = T, π[Z] = T.

ובצורת עץ:

K
├── M   (3)
│   └── P   (9)
│       ├── Q   (13)
│       │   └── T   (15)
│       │       ├── W   (22)
│       │       └── Z   (24)
│       └── N   (14)
│           └── R   (20)
└── L   (7)

בדיקה: סכום המשקלים על המסלול מהשורש לכל קודקוד בעץ שווה ל־ d שלו (למשל K–M–P–Q–T–Z: 3 + 6 + 4 + 2 + 9 = 24). המסלול ש־PrintPath מדפיס עבור W הוא בדיוק המסלול מהשורש אל W בעץ.

מה נדרש: מילה אחת ב־L שיש בה a, b ו־c.

רעיון:
בונים מילה שמתחילה ומסתיימת באותה אות, עם 3 אותיות c (או 0 או 6...), באורך אי־זוגי, ומקפידים שאחרי b לא תבוא a מיד.

פתרון:
המילה aabccca:

בדיקה: לפי הגדרת השפה, המילה שייכת ל־L. המילים הקצרות ביותר ב־L שמכילות את שלוש האותיות הן באורך 5, למשל cabcc, cacbc, ccabc.

טעות נפוצה: לשכוח ש־b ו־a צמודות יוצרות ba גם באמצע המילה (למשל abccaba – לא בשפה).

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

רעיון:
לוקחים מילה "כמעט טובה" ומקלקלים בה דרישה אחת.

פתרון:
המילה aba:

לכן aba אינה שייכת ל־L. (דוגמאות נוספות: cbc – מספר ה־c הוא 2; aa – אורך זוגי.)

בדיקה: aba – שלוש דרישות מתקיימות, "אין ba" לא מתקיימת ⇒ לא ב־L.

טעות נפוצה: לחשוב ש־0 אותיות c לא מקיים "מתחלק ב־3". 0 מתחלק ב־3 בלי שארית.

מה נדרש: להראות ש־L רגולרית.

רעיון:
מפרקים את L לארבע שפות פשוטות – אחת לכל דרישה:

מילה שייכת ל־L בדיוק כשהיא מקיימת את כל הדרישות, ולכן L = L₁ ∩ L₂ ∩ L₃ ∩ L₄. מספיק להראות שכל Lᵢ רגולרית (בונים לה אוטומט סופי), ואז להשתמש בכך שהשפות הרגולריות סגורות לחיתוך.

פתרון:
אוטומט סופי דטרמיניסטי לכל אחת מן השפות (→ = מצב התחלה; "מקבל" = מצב מקבל):

L₁ – האות הראשונה זהה לאחרונה (והמילה לא ריקה). זוכרים את האות הראשונה, ובכל צעד בודקים אם האות האחרונה שנקראה זהה לה:

L₂ – מספר ה־c מתחלק ב־3. סופרים את ה־c מודולו 3 (a ו־b לא משנים את המצב):

L₃ – אין רצף ba. זוכרים אם האות האחרונה הייתה b; a אחרי b – אין מעבר (דחייה):

L₄ – אורך אי־זוגי. מצב לזוגי ומצב לאי־זוגי:

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

המסקנה: לכל אחת מן השפות L₁–L₄ יש אוטומט סופי דטרמיניסטי, ולכן כולן רגולריות. חיתוך של שתי שפות רגולריות הוא שפה רגולרית (אוטומט המכפלה: מריצים את שני האוטומטים "במקביל" ומקבלים כששניהם מקבלים). לכן L₁ ∩ L₂ רגולרית, ומכאן (L₁ ∩ L₂) ∩ L₃ רגולרית, ולבסוף L = (L₁ ∩ L₂ ∩ L₃) ∩ L₄ רגולרית. ∎

בדיקה: כל אחד מארבעת האוטומטים מקבל בדיוק את המילים שמקיימות את הדרישה שלו. אוטומט המכפלה של הארבעה (49 מצבים ישיגים) מקבל בדיוק את L (למשל a, aabccca, cabcc מתקבלות; aba, cbc, aa נדחות).

טעות נפוצה: לנסות לבנות מיד אוטומט אחד לכל L – זה אפשרי אבל ארוך ומועד לטעויות. ההוכחה בעזרת תכונת הסגירות לחיתוך קצרה ובטוחה יותר.

מה נדרש: לקבוע אם הסגור של השרשור שווה לשרשור הסגורים.

רעיון: ב־(L₁·L₂)* החלקים מ־L₁ ומ־L₂ מתחלפים (L₁ L₂ L₁ L₂ …), וב־L₁*·L₂* קודם כל החלקים מ־L₁ ורק אחריהם כל החלקים מ־L₂.

פתרון: לא נכונה. דוגמה נגדית: L₁ = {a} , L₂ = {b}.

השפות שונות – הטענה לא מתקיימת. (גם בכיוון השני: aab ∈ L₁*·L₂* אבל aab ∉ (L₁·L₂)*.)

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

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

רעיון: R(L) = { R(w) | w ∈ L } – הופכים כל מילה בנפרד. נראה הכלה בשני הכיוונים.

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

שתי ההכלות מתקיימות, ולכן השפות שוות.

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

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

רעיון: באגף ימין מספיק שהמילה כולה תתקבל משני שרשורים, ובכל אחד מהם ייתכן חיתוך אחר של המילה לשני חלקים. באגף שמאל דורשים חלק ראשון אחד ששייך גם ל־L₁ וגם ל־L₂.

פתרון: לא נכונה. דוגמה נגדית: L₁ = {a} , L₂ = {ab} , L₃ = {b, ε}.

∅ ≠ {ab} – הטענה לא מתקיימת. (הכיוון ⊆ דווקא תמיד נכון: מילה מאגף שמאל שייכת לשני השרשורים.)

בדיקה: שני האגפים לדוגמה הזאת: ∅ מול {ab}. באופן כללי אגף שמאל תמיד מוכל באגף ימין, אבל לא תמיד שווה לו.

טעות נפוצה: לבלבל בין ∅ (שפה ריקה) לבין {ε} (שפה שמכילה את המילה הריקה). ∅·A = ∅, אבל {ε}·A = A.

מה נדרש: אוטומט מחסנית דטרמיניסטי (אמ"ד) שמקבל בדיוק את המילים aⁿbᵐcᵏ עם n ≥ 2, m ≥ 0 ו־k = n + 2m.

רעיון:

פתרון:

מעקב על aaabccccc (n = 3, m = 1, k = 5 = 3 + 2·1 ⇒ בשפה):

סוף הקלט במצב f ⇒ מתקבלת.

דוגמאות דחייה: acc (n = 1: ב־q₁ נקרא c – אין מעבר); aabccc (רק 3 c במקום 4: הקלט נגמר במצב q₄, לא מקבל); aabcccccc (5 c: ה־c הרביעי מביא ל־f, ה־c החמישי – אין מעבר מ־f); aacca (a אחרי c – אין מעבר).

בדיקה: האוטומט מקבל בדיוק את המילים של L – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a,b,c}. בין השאר: aacc, aaaccc, aabcccc, aabbcccccc מתקבלות; ε, acc, abccc, aaccc, aabccc, aacca נדחות.

טעות נפוצה: לדחוף את אותו סימן גם עבור ה־a הראשון. אז אי אפשר לדעת, בלי מעבר ε, מתי המחסנית "התרוקנה", והאוטומט לא יודע מתי לעבור למצב המקבל.

מה נדרש: מעקב מלא על המילה b.

רעיון: מריצים את המעברים אחד אחד. מעברי המכונה: q₀: a/a,R → q₀ ; b/a,R → q₁ ; Δ/Δ,L → q₃ . q₁: a/b,R → q₂ ; b/b,R → q₁ ; Δ/b,L → q₃ . q₂: a/a,R → q₂ ; b/a,R → q₁ ; Δ/a,L → q₃ . q₃: a/a,L → q₃ ; b/b,L → q₃ ; ⊣/⊣,R → q₄ . q₄ – מצב מקבל.
בטבלה: תא 0 הוא הסמן ⊣ , הראש הקורא מסומן ב־[ ].

פתרון:

שלב 0→1: ב־q₀ קוראים b ⇐ כותבים a , זזים ימינה, q₁ (המכונה "זוכרת" שעליה לכתוב b). שלב 1→2: ב־q₁ קוראים Δ ⇐ כותבים את ה־b , זזים שמאלה, q₃. שלבים 2→4: q₃ חוזר שמאלה עד הסמן ⊣ , ואז זז ימינה ל־q₄. המילה מתקבלת, ועל הסרט ab.

בדיקה: המעקב עובר בדיוק בשלבים האלה.

מה נדרש: מעקב מלא על abb.

פתרון:

הסבר: ב־q₀ המכונה עוברת על ה־a (שלב 0→1). ב־b הראשון היא כותבת a ועוברת ל־q₁ – "מחזיקה" את ה־b שנמחק (1→2). ב־q₁ , כשקוראים b , כותבים את ה־b המוחזק ו"מחזיקים" את ה־b שנקרא – הוא שוב b , ולכן הסרט לא משתנה בתא הזה (2→3). ב־Δ נכתב ה־b המוחזק (3→4) – כל האותיות מה־b הראשון והלאה זזו תא אחד ימינה. q₃ חוזר שמאלה עד ⊣ (4→7), ו־q₄ (7→8). המילה מתקבלת, ועל הסרט aabb.

בדיקה: המעקב עובר באותם 9 שלבים, ובסוף: מתקבלת, תוכן הסרט aabb.

מה נדרש: תוכן הסרט בסוף הריצה על bbab.

רעיון: כפי שראינו בסעיפים (1) ו־(2), המכונה מדלגת על ה־a שבהתחלה, במקום ה־b הראשון כותבת a , ומזיזה את כל האותיות מה־b הראשון והלאה תא אחד ימינה (q₁ "מחזיק" b , q₂ "מחזיק" a).

פתרון: ב־bbab ה־b הראשון בתא 1. נכתב שם a , ו־"bbab" כולה זזה תא אחד ימינה. הסרט בסוף:

כלומר על הסרט abbab, והמכונה עוצרת ב־q₄ (מקבלת).

בדיקה: עבור bbab: מתקבלת, תוכן הסרט abbab.

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

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

פתרון: לא קיימות.

לכן מילה בלי b ומילה עם b לא יכולות לתת אותה תוצאה. ושתי מילים עם b שנותנות אותה תוצאה aʲ b u חייבות להיות שתיהן aʲ⁻¹ b u – כלומר אותה מילה. (באופן דומה, aⁱ שונות נותנות תוצאות שונות.) מהתוצאה תמיד אפשר לשחזר את המקור: אם יש בה b – מוחקים a אחד לפני ה־b הראשון.

בדיקה: כל המילים מעל {a, b} נותנות תוצאות שונות זו מזו.

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

פתרון: המכונה מכניסה a לפני ה־b הראשון במילה: היא מדלגת על ה־a שבהתחלה, כותבת a במקום ה־b הראשון, ומזיזה את כל האותיות מה־b הזה והלאה תא אחד ימינה (q₁ "מחזיק" b ו־q₂ "מחזיק" a שצריך לכתוב בתא הבא). בסוף היא חוזרת שמאלה עד הסמן ⊣ (q₃) ועוצרת ב־q₄ מעל התא הראשון. אם אין במילה b – המילה נשארת כמו שהיא. המכונה מקבלת כל מילה מעל {a, b} (גם את המילה הריקה).

בדיקה: b → ab , abb → aabb , bbab → abbab , a → a. פלט המכונה הוא בדיוק "הכנסת a לפני ה־b הראשון" לכל מילה.

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

רעיון – שואלים על כל זוג מחלקות שתי שאלות:

פתרון

בדיקה – כל שש המחלקות מופיעות בתרשים. התכונות המשותפות title ו־year יוגדרו רק במחלקת הבסיס Exhibit, וכל מחלקה יורשת מוסיפה רק את התכונה המיוחדת לה.

טעות נפוצה: לסמן ירושה בין Loan ל־Exhibit. השאלה אינה "סוג של" מוצג; יש לה מוצג, ולכן זו הכלה.

מה נדרש – כותרות שש המחלקות והתכונות שלהן (בלי פעולות; פעולות get/set ופעולות בונות מניחים שקיימות).

רעיון – בכותרת של מחלקה יורשת מציינים את מחלקת הבסיס (extends ב־Java, : ב־C#). התכונות title ו־year מוגדרות רק ב־Exhibit, והמחלקות היורשות מקבלות אותן בירושה. כל תכונה מוגדרת private (כימוס), ולגישה אליהן משתמשים בפעולות get/set.

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

ב־C#: public class Painting : Exhibit וכן הלאה, והטיפוסים string ו־bool.

בדיקה – הכותרות והתכונות (Java ו־C#) תקינות.

טעות נפוצה: להגדיר שוב את title ו־year במחלקות Painting, Sculpture, Photo. הן כבר מתקבלות בירושה מ־Exhibit.

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

רעיון – עוברים על ההשאלות שבמערך, רק עד count (אחרי count יש null). לכל השאלה לוקחים את המוצג שלה ובודקים:

אם אין פסלים, הסכום נשאר 0.

פתרון

public int totalWeight() {
    int sum = 0;
    for (int i = 0; i < this.count; i++) {
        Exhibit e = this.arrL[i].getExhibit();
        if (e instanceof Sculpture)
            sum += ((Sculpture) e).getWeight();
    }
    return sum;
}

בדיקה – תערוכה עם 5 השאלות: Sunrise ו־Harbor (ציורים), Dancer (פסל, 120 ק"ג), Lion (פסל, 340 ק"ג), Market (צילום). הפעולה החזירה 460 (ב־Java וב־C#). בתערוכה בלי פסלים היא החזירה 0.

טעות נפוצה: לקרוא ל־getWeight() על הפניה מטיפוס Exhibit בלי המרה ל־Sculpture. זו שגיאת הידור, כי ב־Exhibit אין פעולה כזו. המרה בלי בדיקת instanceof מראש גורמת לשגיאת ריצה כשהמוצג הוא ציור או צילום.

מה נדרש – להוציא מהמערך "המסודר" (ציורים ← פסלים ← צילומים) את ההשאלה של המוצג ששמו title, כך שהמערך יישאר "מסודר" ורציף, אלא אם המוצג אינו קיים או שהוא היחיד מסוגו.

רעיון

הוצאה של איבר והזזת כל מה שאחריו שמאלה שומרת על הסדר היחסי של כל שאר ההשאלות, ולכן המערך נשאר "מסודר".

פתרון

// מחזירה 1 לציור, 2 לפסל, 3 לצילום
private static int kind(Exhibit e) {
    if (e instanceof Painting)
        return 1;
    if (e instanceof Sculpture)
        return 2;
    return 3;
}

public boolean remove(String title) {
    int pos = -1;                              // מיקום המוצג במערך
    for (int i = 0; i < this.count && pos == -1; i++)
        if (this.arrL[i].getExhibit().getTitle().equals(title))
            pos = i;
    if (pos == -1)                             // אין מוצג בשם הזה
        return false;
    int k = kind(this.arrL[pos].getExhibit());
    int same = 0;                              // כמה מוצגים מאותו סוג
    for (int i = 0; i < this.count; i++)
        if (kind(this.arrL[i].getExhibit()) == k)
            same++;
    if (same == 1)                             // המוצג היחיד מסוגו
        return false;
    for (int i = pos; i < this.count - 1; i++) // הזזה שמאלה במקום אחד
        this.arrL[i] = this.arrL[i + 1];
    this.count--;
    this.arrL[this.count] = null;
    return true;
}

בדיקה – מערך בגודל 10: Sunrise Harbor (ציורים) Dancer Lion (פסלים) Market (צילום), count=5. הפלט ב־Java וב־C#:

גם במערך מלא (3 מתוך 3) הוצאת צילום כשיש שני צילומים החזירה true, והתא האחרון התאפס ל־null.

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

טעות נפוצה: להזיז את ההשאלות מהסוף להתחלה (for i = count-1 ...). כך כל התאים נדרסים באותו ערך. טעות נוספת היא לשכוח את count--, ואז ההשאלה האחרונה מופיעה פעמיים.

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

רעיון

פתרון

תרשים העצמים:

הפלט:

Card Dan
Card Noa 30
Card Tal
Gold 5
Card Ori
Gold 8
Card Lia
Gold 3

בדיקה – הפלט ב־Java וב־C# הוא בדיוק הפלט שלמעלה.

טעות נפוצה: לחשוב שבעצם GoldCard מודפסת רק השורה Gold – הפעולה הבונה של Card רצה קודם ומדפיסה גם היא.

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

רעיון – שלושה כללים:

פתרון

בדיקה – כל פקודה לבדה בפעולה הראשית תקינה ב־Java וב־C#. הפקודות הלא תקינות נכשלו בהידור בשתי השפות, פרט לפקודה שנכשלה בזמן ריצה (ב־Java: ClassCastException, ב־C#: InvalidCastException). הפלט של הפקודות התקינות זהה בשתי השפות.

מה נדרש – תרשים ירושה של K, L, M, N.

רעיון – לפי הכותרות: L extends K (ב־C#: L : K), M extends L, N extends M. זו שרשרת אחת: כל מחלקה יורשת מהקודמת, ולכן N היא בעקיפין גם M, גם L וגם K.

פתרון

בדיקה – התרשים מתאים לכותרות המחלקות; הקוד תקין ב־Java וב־C# עם ההייררכייה הזאת.

מה נדרש – לסרטט את ששת העצמים: לכל משתנה – הטיפוס המוצהר שלו, חץ אל העצם, הטיפוס בפועל של העצם וערך התכונה v.

רעיון – לכל העצמים יש תכונה אחת, v, שמוגדרת ב־K. נחשב אותה לפי שרשור הפעולות הבונות (מלמטה למעלה):

פתרון – התרשים (משמאל המשתנה עם הטיפוס המוצהר, מימין העצם עם הטיפוס שלו בפועל):

בדיקה – הדפסה של getV() לכל עצם נותנת את הערכים 3, 3, 6, 4, 7, 8, ב־Java וב־C#.

טעות נפוצה: ב־M לחשב (2 + 2)·2 = 8 – M מכפילה לפני שהיא מעבירה ל־L, ו־L היא שמוסיפה 2.

מה נדרש – הפלט של חמש השורות, עם מספר השורה.

רעיון – שני שלבים בכל קריאה:

הפעולות: ב־K – act(K); ב־L – act(L) חדשה ו־act(K) שדורסת את של K; ב־M – act(int) חדשה; ב־N – act(L) שדורסת את של L. ערכי v (מסעיף ב1): k=3, l=3, m=6, n=4, kl=7, ln=8.

פתרון – הפלט:

(1) L2
    K1
    L10
(2) L1
    24
(3) N1
    M1
    2
(4) L2
    K1
    L9
(5) M1
    3

ב־C# הפלט זהה (הפעולות מחזירות מחרוזות, ולכן אין הבדל True/true). ב־C# הדריסה מתרחשת כי Act(K) מוגדרת ב־K כ־virtual וב־L כ־override, ו־Act(L) מוגדרת ב־L כ־virtual וב־N כ־override.

בדיקה – הקוד כפי שהוא (Java ו־C#) מדפיס בדיוק את הפלט שלמעלה.

טעות נפוצה: בשורה (1) לבחור act(L) כי הארגומנט l הוא L – הטיפוס המוצהר של kl הוא K, ו־K מכירה רק את act(K). בשורה (3) – לשכוח שהקריאה act(other.getV()) בתוך N מקבלת int ולכן מגיעה ל־act(int) של M. בשורה (1) ו־(4) – לשכוח את ה־"L" שנוסף לפני המספר.