דילוג לתוכן המרכזי
GuyAI

בגרות במדעי המחשב מבני נתונים ומסלול 899271 - קיץ 2025

4–5 יח"ל · שאלון 899271 · 12 שאלות · 3 שעות · פתרון מלא לכל סעיף

בחינת הבגרות במדעי המחשב, מבני נתונים ומסלול, קיץ 2025, כל 12 השאלות כמו בשאלון. לכל סעיף יש תשובה ופתרון מלא: הרעיון, הקוד או המעקב, ובדיקה קצרה. כל קוד מופיע ב-Java וב-C#. נסו לפתור לבד, ואז פתחו את הפתרון.

הוראות הבחינה (כמו בשאלון)

א. משך הבחינה: שלוש שעות.
ב. מבנה השאלון ומפתח ההערכה: בשאלון זה שני פרקים.
פרק ראשון – 25×2 – 50 נקודות
פרק שני – 25×2 – 50 נקודות
סך הכול – 100 נקודות
ג. חומר עזר מותר בשימוש: כל חומר עזר, חוץ ממחשבון שיש בו אפשרות תכנות.
ד. הוראות מיוחדות:
(1) רשמו על הכריכה החיצונית של המחברת את שם המסלול שלמדתם.
המסלול הוא אחד משלושת המסלולים האלה: אלגוריתמים, מודלים חישוביים, תכנות מונחה עצמים.
(2) את כל התוכניות שיש לכתוב בשפת מחשב בפרקים הראשון והשני כתבו בשפה אחת בלבד – Java או C#.
הערה: לא יורדו נקודות אם תכתבו בתוכניות אות גדולה במקום אות קטנה או להפך.

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

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

בהצלחה!

השאלות
בשאלון זה שני פרקים. יש לענות על שאלות משני הפרקים, לפי ההוראות בכל פרק.
הערה: בכל שאלה שנדרשת בה קליטה, אין צורך לבדוק את תקינות הקלט.
לפותרים בשפת Java: בכל שאלה שנדרשת בה קליטה, הניחו שבתוכנית כתובה ההוראה:
Scanner input = new Scanner (System.in);

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

פרק ראשון

ענו על שתיים מן השאלות 1–3 (לכל שאלה – 25 נקודות).

שאלה 1 · חנות משחקים – מחיקה משרשרת חוליות (25 נקודות)

נתונה המחלקה Game – משחק מחשב, ולה שתי תכונות:

•name – שם המשחק, מטיפוס מחרוזת.
•price – מחיר המשחק – מספר הגדול מ־ 0 , מטיפוס שלם.

הניחו שיש פעולות get/Get ו־ set/Set לתכונות המחלקה.

נתונה המחלקה Store – חנות משחקי מחשב, ולה תכונה אחת:

•lst – הפניה לשרשרת חוליות שאינה ריקה, מטיפוס Game . כל חוליה בשרשרת מכילה משחק הנמכר בחנות.

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

א.

ממשו את הפעולה של ממשק המחלקה Store שלפניכם:

Java – public int remove (int n, int pr)
C# – public int Remove (int n, int pr)

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

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

דוגמה: בעבור pr = 30 , n = 3 והשרשרת lst שלפניכם:

הפעולה תחזיר 3 והשרשרת תיראה כך בתום הפעולה:

הסבר: יש בשרשרת ארבעה משחקים שמחירם 30 . מכיוון ש־ n = 3 , נמחקו שלושת המשחקים הראשונים בשרשרת שמחירם 30 , והפעולה החזירה 3 .

דוגמה נוספת: בעבור אותה השרשרת מן הדוגמה המקורית שלעיל ו־ pr = 30 , n = 5 , הפעולה תחזיר 4 והשרשרת תיראה כך בתום הפעולה:

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

ב.

ממשו את הפעולה של ממשק המחלקה Store שלפניכם:

Java – public int removeCheap (int num)
C# – public int RemoveCheap (int num)

הפעולה תמחק מן השרשרת את num המשחקים הזולים ביותר. הפעולה תחזיר את סכום המחירים הכולל של כל המשחקים שנמחקו.
הניחו ש־ num גדול מ־ 0 וקטן מכמות המשחקים בשרשרת.

הערות:

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

דוגמה: בעבור אותה השרשרת מן הדוגמה המקורית בסעיף א ו־ num = 5 , הפעולה תחזיר 142 , והשרשרת תיראה כך:

הסבר: חמשת המשחקים הזולים יותר (30+30+30+27+25) נמחקו מן השרשרת וסכום מחירם הכולל הוא 142 .
בשרשרת נשאר משחק אחד שמחירו 99 ואחד שמחירו 30 (אפשר להשאיר בשרשרת משחק אחר שעולה 30 , אין חשיבות איזה מהם יישאר).

◂ פתרון מלא לשאלה 1

סעיף א

תשובה

מוחקים מתחילת השרשרת כל עוד lst מכיל משחק במחיר pr (ו-count < n), ואז עם pos בודקים את pos.getNext(): אם מחירו pr – pos.setNext(pos.getNext().getNext()) ו-count++, אחרת מתקדמים. מחזירים count. יעילות O(L).

מה נדרש: לממש פעולה במחלקה Store שמוחקת מהשרשרת lst לכל היותר n משחקים שמחירם pr (הראשונים שבהם), ומחזירה כמה משחקים נמחקו.

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

1.מחיקה מתחילת השרשרת – אם החוליה הראשונה מכילה משחק במחיר pr, מקדמים את lst לחוליה הבאה. חוזרים על כך כל עוד צריך (ייתכן שכמה משחקים בתחילת השרשרת עולים pr – כמו בדוגמה "a" ו־"g").
2.מחיקה מאמצע/סוף השרשרת – מחזיקים הפניה pos ובודקים תמיד את החוליה שאחרי pos. אם המשחק בה עולה pr – מדלגים עליה (pos.setNext(pos.getNext().getNext())) ו־pos לא מתקדם (כי החוליה הבאה החדשה עוד לא נבדקה). אחרת – pos מתקדם.

בשני השלבים סופרים את המחיקות ב־count ועוצרים כש־count מגיע ל־n. כך נמחקים בדיוק n המשחקים הראשונים שמחירם pr, ושאר החוליות נשארות באותו סדר.

פתרון:

public int remove(int n, int pr)
{
    int count = 0;
    // מחיקה מתחילת השרשרת – כל עוד החוליה הראשונה מכילה משחק במחיר pr
    while (lst != null && count < n && lst.getValue().getPrice() == pr)
    {
        lst = lst.getNext();
        count++;
    }
    if (lst == null)
        return count;
    // מחיקה מאמצע/סוף השרשרת – בודקים תמיד את החוליה שאחרי pos
    Node<Game> pos = lst;
    while (pos.hasNext() && count < n)
    {
        if (pos.getNext().getValue().getPrice() == pr)
        {
            pos.setNext(pos.getNext().getNext());
            count++;
        }
        else
        {
            pos = pos.getNext();
        }
    }
    return count;
}

בדיקה: על השרשרת מהדוגמה (a:30, g:30, b:27, v:99, k:30, c:25, p:30):

•remove(3, 30) החזירה 3 והשרשרת: b:27, v:99, c:25, p:30 (נמחקו a, g מהתחלה ו־k מהאמצע; p נשאר).
•remove(5, 30) החזירה 4 והשרשרת: b:27, v:99, c:25 (נמחק גם p מהסוף).
•remove(2, 50) החזירה 0 והשרשרת לא השתנתה.

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

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

הקוד המלא
public int remove(int n, int pr)
{
    int count = 0;
    // מחיקה מתחילת השרשרת – כל עוד החוליה הראשונה מכילה משחק במחיר pr
    while (lst != null && count < n && lst.getValue().getPrice() == pr)
    {
        lst = lst.getNext();
        count++;
    }
    if (lst == null)
        return count;
    // מחיקה מאמצע/סוף השרשרת – בודקים תמיד את החוליה שאחרי pos
    Node<Game> pos = lst;
    while (pos.hasNext() && count < n)
    {
        if (pos.getNext().getValue().getPrice() == pr)
        {
            pos.setNext(pos.getNext().getNext());
            count++;
        }
        else
        {
            pos = pos.getNext();
        }
    }
    return count;
}

סעיף ב

תשובה

כל עוד num > 0: מוצאים את המחיר המינימלי min, k = remove(num, min), sum += k*min, num -= k. מחזירים sum (בדוגמה: 142). יעילות O(num·L) ≤ O(L²).

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

רעיון: חוזרים על התהליך הבא כל עוד נשאר מה למחוק (num > 0):

1.מוצאים את המחיר הנמוך ביותר min בשרשרת (מעבר אחד על השרשרת).
2.מוחקים בעזרת הפעולה מסעיף א עד num משחקים שמחירם min: k = remove(num, min). הפעולה מחזירה כמה נמחקו בפועל.
3.מוסיפים לסכום k·min ומקטינים את num ב־k.

אם יש יותר משחקים במחיר min ממה שנשאר למחוק – remove מוחקת רק num מהם (וזה מותר, כי לפי ההערה אין חשיבות איזה מהם יימחק). בכל סיבוב נמחק לפחות משחק אחד, ולכן הלולאה מסתיימת. כיוון ש־num קטן ממספר המשחקים, השרשרת לעולם לא מתרוקנת, כך ש־lst אינו null בתחילת כל סיבוב. הפעולה remove שומרת על סדר שאר המשחקים.

פתרון (Java) – הפעולה remove מסעיף א נמצאת באותה מחלקה:

// משתמשת בפעולה remove מסעיף א
public int removeCheap(int num)
{
    int sum = 0;
    while (num > 0)
    {
        // מציאת המחיר הנמוך ביותר בשרשרת
        int min = lst.getValue().getPrice();
        Node<Game> pos = lst.getNext();
        while (pos != null)
        {
            if (pos.getValue().getPrice() < min)
                min = pos.getValue().getPrice();
            pos = pos.getNext();
        }
        // מחיקת עד num משחקים במחיר המינימלי
        int k = remove(num, min);
        sum = sum + k * min;
        num = num - k;
    }
    return sum;
}

בדיקה: על השרשרת מהדוגמה עם num = 5:

סיבובminנמחקו (k)sumnum שנשארהשרשרת אחרי הסיבוב
1251 (c)254a:30, g:30, b:27, v:99, k:30, p:30
2271 (b)523a:30, g:30, v:99, k:30, p:30
3303 (a, g, k)1420v:99, p:30

הפעולה מחזירה 142 והשרשרת v:99, p:30 – כמו בדוגמה. בדקנו גם num = 1 (מוחזר 25), num = 3 (מוחזר 82), num = 6 (מוחזר 172, נשאר v:99).

יעילות: בכל סיבוב מעבר על השרשרת למציאת המינימום ומעבר נוסף ב־remove ⇒ O(L) לסיבוב. יש לכל היותר num סיבובים ⇒ O(num·L), ובמקרה הגרוע (num קרוב ל־L) O(L²).

הקוד המלא
// משתמשת בפעולה remove מסעיף א
public int removeCheap(int num)
{
    int sum = 0;
    while (num > 0)
    {
        // מציאת המחיר הנמוך ביותר בשרשרת
        int min = lst.getValue().getPrice();
        Node<Game> pos = lst.getNext();
        while (pos != null)
        {
            if (pos.getValue().getPrice() < min)
                min = pos.getValue().getPrice();
            pos = pos.getNext();
        }
        // מחיקת עד num משחקים במחיר המינימלי
        int k = remove(num, min);
        sum = sum + k * min;
        num = num - k;
    }
    return sum;
}

שאלה 2 · תור – רצף של איברים שווים (25 נקודות)

נוסח השאלה:

שימו לב: לשאלה זו שני נוסחים: בשפת Java בעמודים 4–5 ובשפת C# בעמודים 6–7.

לפותרים בשפת Java

א.(1)

לפניכם הפעולה mmm , המקבלת תור – q ובו מספרים הגדולים מ־ 0 , ומספר שלם – z הגדול מ־ 0 .

Java
public static boolean mmm (Queue<Integer> q, int z)
{
    q.insert (0);
    int num = q.head();
    int y = 0;
    while (q.head() > 0)
    {
        if (y < z)
        {
            if (q.head() == num)
            {
                y++;
            }
            else
            {
                num = q.head();
                y = 1;
            }
        }
        q.insert (q.remove());
    }
    q.remove();
    return y == z;
}

נתון תור q מטיפוס שלם:

(1) עקבו בעזרת טבלת המעקב שלפניכם אחר הפעולה mmm(q , 4) , וכתבו מה הפעולה מחזירה.

התור qnumyy < zq.head() == num
(2)

הסבירו מה הפעולה mmm עושה.

(3)

מהי סיבוכיות זמן הריצה של הפעולה mmm ? נמקו את תשובתכם.

ב.(1)

לפניכם הפעולה what , המקבלת תור – q ובו מספרים הגדולים מ־ 0 , ואת גודל התור – n .

Java
public static int what (Queue<Integer> q, int n)
{
    if (mmm (q, n))
        return n;
    return what (q, n - 1);
}

נתון תור – q מטיפוס שלם:

(1) עקבו אחר הפעולה what (q, 6) , וכתבו מה הפעולה מחזירה (אין צורך לעקוב אחר הפעולה mmm).
המעקב יכלול בכל קריאה את הערכים של q , n ואת הערך המוחזר.
לפניכם הצעה לטבלת מעקב (אין חובה להשתמש בטבלה זו).

התור q שמתקבל בפעולההערך n שמתקבל בפעולהmmm (q, n) == trueערך מוחזר
(2)

הסבירו מה הפעולה what עושה.

(3)

מהי סיבוכיות זמן הריצה של הפעולה what ? נמקו את תשובתכם.

◂ פתרון מלא לשאלה 2

סעיף א(1)

תשובה

mmm(q, 4) מחזירה false (הרצף הארוך ביותר של איברים שווים צמודים הוא 1, 1, 1 – באורך 3); התור חוזר למצבו המקורי.

מה נדרש: לעקוב אחר mmm(q, 4) (ב־C#: Mmm) על התור שבאיור ולכתוב מה מוחזר. באיור, מראש התור (משמאל) לסוף התור (מימין): 1, 3, 1, 1, 1, 2.

רעיון: הפעולה מכניסה 0 לסוף התור כ"סימן עצירה" (כל המספרים בתור גדולים מ־0). אחר כך היא מסובבת את התור: כל איבר יוצא מהראש ונכנס לסוף, עד שה־0 מגיע לראש. במהלך הסיבוב num הוא הערך של הרצף הנוכחי ו־y סופר כמה איברים שווים ברצף יש עד עכשיו. ברגע ש־y מגיע ל־z, התנאי y < z נכשל ו־y "מוקפא".

פתרון – טבלת מעקב (z = 4). כל שורה היא סיבוב אחד של הלולאה: התור – כפי שהוא בתחילת הסיבוב (הראש משמאל), y < z – לפי y שלפני הסיבוב, num ו־y – הערכים אחרי הסיבוב.

התור q (מראש התור לסופו)numyy < zq.head() == num
1, 3, 1, 1, 1, 2, 0 (לפני הלולאה)10
1, 3, 1, 1, 1, 2, 011truetrue
3, 1, 1, 1, 2, 0, 131truefalse
1, 1, 1, 2, 0, 1, 311truefalse
1, 1, 2, 0, 1, 3, 112truetrue
1, 2, 0, 1, 3, 1, 113truetrue
2, 0, 1, 3, 1, 1, 121truefalse
0, 1, 3, 1, 1, 1, 221

בשורה האחרונה בראש התור 0, ולכן הלולאה מסתיימת. q.remove() מוציא את ה־0, והתור חוזר להיות 1, 3, 1, 1, 1, 2 – בדיוק כמו בהתחלה.
y = 1 ≠ 4 ⇒ הפעולה מחזירה false.

בדיקה: על הקוד של השאלה: mmm(q, 4) = false, והתור אחרי הקריאה: [1, 3, 1, 1, 1, 2].

סעיף א(2)

תשובה

מחזירה true אם בתור יש רצף של לפחות z איברים שווים צמודים, אחרת false; התור נשאר ללא שינוי.

מה נדרש: להסביר מה mmm עושה.

רעיון והסבר: הפעולה עוברת על איברי התור לפי הסדר וסופרת את אורך רצף האיברים השווים הצמודים הנוכחי: אם האיבר שווה לקודם – y גדל ב־1, ואם לא – מתחיל רצף חדש (num = האיבר, y = 1). ברגע ש־y מגיע ל־z הספירה נעצרת (y נשאר z עד הסוף).

תשובה: הפעולה מחזירה true אם בתור q יש רצף של לפחות z איברים שווים זה לזה הצמודים זה לזה (כלומר z פעמים ברצף אותו מספר), ואחרת false. בסיום הפעולה התור q חוזר למצבו המקורי (אותם איברים באותו סדר).

בדיקה: על התור 1, 3, 1, 1, 1, 2: z = 1, 2, 3 ⇒ true (יש רצף 1, 1, 1 באורך 3), z = 4, 5, 6 ⇒ false.

טעות נפוצה: לחשוב שהפעולה בודקת אם מספר מופיע z פעמים בסך הכול בתור. בתור שלנו 1 מופיע 4 פעמים, אבל mmm(q, 4) מחזירה false – כי הרצף הצמוד הארוך ביותר הוא באורך 3.

סעיף א(3)

תשובה

O(n) – מעבר אחד על n איברי התור, O(1) לכל איבר.

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

תשובה: O(n), כאשר n מספר האיברים בתור q.

נימוק: הלולאה while מסובבת את התור פעם אחת: בכל סיבוב איבר אחד עובר מהראש לסוף, והיא נעצרת כשה־0 (שהוכנס לסוף) מגיע לראש – כלומר בדיוק n סיבובים. בכל סיבוב מתבצע מספר קבוע של פעולות שכל אחת O(1) (head, insert, remove, השוואות). מחוץ ללולאה – מספר קבוע של פעולות. סך הכול n·O(1) + O(1) = O(n).

סעיף ב(1)

תשובה

what(q, 6) מחזירה 3 (n = 6, 5, 4 – false; n = 3 – true).

מה נדרש: לעקוב אחר what(q, 6) (ב־C#: What) ולכתוב מה מוחזר. התור שבאיור, מראש התור לסופו: 1, 3, 1, 1, 1, 2.

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

פתרון – טבלת מעקב:

התור q שמתקבל בפעולההערך n שמתקבל בפעולהmmm (q, n) == trueערך מוחזר
1, 3, 1, 1, 1, 26false3 (מהקריאה what(q, 5))
1, 3, 1, 1, 1, 25false3 (מהקריאה what(q, 4))
1, 3, 1, 1, 1, 24false3 (מהקריאה what(q, 3))
1, 3, 1, 1, 1, 23true3

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

בדיקה: על הקוד של השאלה: what(q, 6) = 3, והתור בסוף: [1, 3, 1, 1, 1, 2].

(בקוד המודפס בשאלון הביטוי n − 1 נדפס בסימן מינוס טיפוגרפי; בקוד שלמעלה הוא נכתב בסימן המינוס הרגיל ‎-‎ – זה אותו הקוד.)

סעיף ב(2)

תשובה

מחזירה את אורך הרצף הארוך ביותר של איברים שווים צמודים בתור (התור לא משתנה).

מה נדרש: להסביר מה what עושה.

תשובה: הפעולה מחזירה את אורך הרצף הארוך ביותר של איברים שווים צמודים בתור q. התור q לא משתנה.

הסבר: what מנסה את האורכים n, n − 1, n − 2, … לפי הסדר, ועוצרת באורך הראשון k שעבורו mmm(q, k) מחזירה true. לפי סעיף א, mmm(q, k) מחזירה true בדיוק כשיש רצף שווים באורך k לפחות, ולכן האורך הראשון (הגדול ביותר) שמצליח הוא אורך הרצף הארוך ביותר. הרקורסיה תמיד נעצרת, כי mmm(q, 1) תמיד מחזירה true (כל איבר הוא רצף באורך 1).

בדיקה: 5, 5, 5, 5 ⇒ 4 ; 1, 2, 3, 4 ⇒ 1 ; 2, 2, 1, 2, 2, 2 ⇒ 3 ; 4, 4, 9, 9, 9, 4, 4 ⇒ 3.

סעיף ב(3)

תשובה

O(n²) במקרה הגרוע: עד n קריאות רקורסיביות, בכל אחת mmm ב־O(n).

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

תשובה: O(n²) במקרה הגרוע (n – גודל התור).

נימוק: כל קריאה ל־what מבצעת קריאה אחת ל־mmm, שעולה O(n) (סעיף א(3)), ועוד מספר קבוע של פעולות. הרקורסיה מתחילה ב־n ויורדת ב־1 בכל קריאה, עד לאורך הרצף הארוך ביותר L, כלומר יש n − L + 1 קריאות. במקרה הגרוע – כששום שני איברים צמודים אינם שווים (L = 1) – יש n קריאות, וכל אחת O(n) ⇒ n·O(n) = O(n²).
(במקרה הטוב – כל האיברים שווים – יש קריאה אחת בלבד ⇒ O(n).)

שאלה 3 · עץ K־שמאלי (25 נקודות)

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

דוגמה:

עץ זה אינו "עץ 1־שמאלי" כי בעץ יש מסלול שבו יותר מקשת אחת שמאלית (במסלול המקווקו יש שתי קשתות שמאליות).
לעומת זאת, עץ זה הוא "עץ 2־שמאלי" כי אין בו מסלול שבו יותר משתי קשתות שמאליות (ובאותה מידה הוא גם "עץ 3־שמאלי", וגם "עץ 4־שמאלי" וכן הלאה).

א.

סרטטו "עץ 1־שמאלי" (כלומר שבכל מסלול של העץ יש קשת אחת שמאלית לכל היותר), ובו 8 צמתים ומקסימום 4 רמות.

ב.

כתבו פעולה חיצונית ששמה isLeftK בשפת Java או IsLeftK בשפת C# , המקבלת עץ בינרי – root מטיפוס שלם שאינו ריק, וערך K שאינו שלילי, ומחזירה true אם העץ הוא "עץ K־שמאלי", ואם לא – היא מחזירה false .

◂ פתרון מלא לשאלה 3

סעיף א

תשובה

לדוגמה: שורש 1; בן שמאלי 2 (עלה), בן ימני 3; ל-3: שמאלי 4, ימני 5; ל-4: ימני 6; ל-5: שמאלי 7, ימני 8. (8 צמתים, 4 רמות, בכל מסלול ≤ קשת שמאלית אחת.)

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

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

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

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

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

מסלולקשתות שמאליות
1 → 21
1 → 3 → 4 → 61 (3→4)
1 → 3 → 5 → 71 (5→7)
1 → 3 → 5 → 80

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

טעות נפוצה: לתת לצומת 4 (שהגענו אליו בקשת שמאלית) בן שמאלי – אז במסלול יהיו 2 קשתות שמאליות.

סעיף ב

תשובה

רקורסיה עם תקציב K: בן שמאלי – אם K == 0 מחזירים false, אחרת בודקים אותו עם K − 1; בן ימני – בודקים עם אותו K; עלה – true. יעילות O(n).

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

רעיון: K הוא "תקציב" הקשתות השמאליות שעוד מותר להשתמש בהן בהמשך המסלול.

•ירידה לבן השמאלי צורכת קשת שמאלית אחת: אם לצומת יש בן שמאלי והתקציב הוא 0 – העץ אינו K־שמאלי. אחרת בודקים ברקורסיה את תת־העץ השמאלי עם K − 1.
•ירידה לבן הימני לא משנה את התקציב: בודקים את תת־העץ הימני עם אותו K.
•צומת שאין לו בנים (עלה) – המסלול הסתיים בלי לחרוג ⇒ true.

העץ הוא K־שמאלי אם ורק אם שתי הבדיקות מצליחות.

פתרון:

public static boolean isLeftK(BinNode<Integer> root, int k)
{
    if (root.hasLeft())
    {
        // ירידה שמאלה "צורכת" קשת שמאלית אחת
        if (k == 0 || !isLeftK(root.getLeft(), k - 1))
            return false;
    }
    if (root.hasRight())
    {
        // ירידה ימינה לא משנה את מספר הקשתות השמאליות
        if (!isLeftK(root.getRight(), k))
            return false;
    }
    return true;
}

בדיקה: על העץ מהדוגמה בשאלה: isLeftK(root, 1) = false (המסלול המקווקו מכיל 2 קשתות שמאליות), isLeftK(root, 2) = true, isLeftK(root, 0) = false. על העץ מסעיף א: K = 1 ⇒ true, K = 0 ⇒ false.

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

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

הקוד המלא
public static boolean isLeftK(BinNode<Integer> root, int k)
{
    if (root.hasLeft())
    {
        // ירידה שמאלה "צורכת" קשת שמאלית אחת
        if (k == 0 || !isLeftK(root.getLeft(), k - 1))
            return false;
    }
    if (root.hasRight())
    {
        // ירידה ימינה לא משנה את מספר הקשתות השמאליות
        if (!isLeftK(root.getRight(), k))
            return false;
    }
    return true;
}

פרק שני (50 נקודות) – אלגוריתמים

יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).

שאלה 4 · טענות על גרפים וסריקת DFS (25 נקודות)

בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.

א.(1)

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

(1) נתון גרף לא מכוון ובו n קודקודים. אם יש בגרף n−1 קשתות, בהכרח אין בו מעגלים.

(2)

נתון גרף ממושקל (אי־שלילי) ובו מעגל אחד לפחות. העץ הפורש המינימלי של הגרף בהכרח אינו מכיל את הקשת עם המשקל הגבוה ביותר בגרף.

(3)

נתון גרף לא מכוון ובו n קודקודים ורכיב קשירות אחד. ייתכן שלאחר מחיקת קודקוד אחד (והקשתות שמחוברות אליו), יהיו בגרף n−1 רכיבי קשירות.

(4)

נתון גרף לא מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים בגרף שיש ביניהם מסלול.

(5)

נתון גרף מכוון ללא מעגלים. סריקת DFS תמצא תמיד את המרחק המינימלי בין שני קודקודים שיש ביניהם מסלול.

(6)

נתון גרף לא מכוון. בעץ פורש DFS של הגרף שהורץ מקודקוד התחלה s , יש קודקוד v ולו x בנים. לכן בכל עץ פורש DFS של הגרף שהורץ מקודקוד התחלה v , בהכרח יש לקודקוד v לפחות x בנים.

ב.

נתון גרף לא מכוון G ובו 5 קודקודים: a , b , c , d , s .

לאחר הרצת DFS מקודקוד התחלה s התקבל העץ שבסרטוט הנתון:

בנוגע לכל אחד משלושת העצים שלפניכם, קבעו אם ייתכן שהוא התקבל מהרצת DFS על אותו הגרף G , מקודקוד התחלה a . נמקו את קביעותיכם.

◂ פתרון מלא לשאלה 4

סעיף א(1)

תשובה

לא נכונה. דוגמה נגדית: משולש a–b–c וקודקוד מבודד d (4 קודקודים, 3 קשתות, ויש מעגל).

מה נדרש: לקבוע אם כל גרף לא מכוון עם n קודקודים ו־n−1 קשתות הוא בהכרח חסר מעגלים.

רעיון: n−1 קשתות ללא מעגל מחייבות שהגרף יהיה קשיר (עץ). אבל אם הגרף אינו קשיר, אפשר "לבזבז" את הקשתות על מעגל בחלק אחד שלו ולהשאיר קודקוד מבודד.

פתרון: הטענה לא נכונה. דוגמה נגדית עם 4 קודקודים a, b, c, d וקשתות:
a–b , b–c , c–a

n = 4 ויש n−1 = 3 קשתות, אבל a→b→c→a הוא מעגל (הקודקוד d מבודד).

בדיקה: בגרף שנבנה יש מעגל, עם 3 קשתות בדיוק.

טעות נפוצה: לבלבל עם המשפט הנכון: "גרף קשיר עם n−1 קשתות הוא עץ (אין בו מעגלים)". בלי קשירות המשפט לא מתקיים.

סעיף א(2)

תשובה

לא נכונה. דוגמה נגדית: משולש a,b,c עם משקלים 1,1,1 וקשת c–d במשקל 10 – כל עץ פורש חייב להכיל את c–d.

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

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

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

קשתa–bb–cc–ac–d
משקל11110

בגרף יש מעגל (a–b–c). הקשת הכבדה ביותר היא c–d (10), והיא הקשת היחידה שמגיעה ל־d. לכן כל עץ פורש – ובפרט העפ"מ – מכיל אותה. עפ"מ לדוגמה: a–b , b–c , c–d במשקל 12.

בדיקה: כל העצים הפורשים במשקל המינימלי (12) מכילים את c–d.

סעיף א(3)

תשובה

נכונה. בגרף "כוכב" (מרכז המחובר לכל שאר n−1 הקודקודים) מחיקת המרכז משאירה n−1 קודקודים מבודדים = n−1 רכיבי קשירות.

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

רעיון: אחרי מחיקת קודקוד נשארים n−1 קודקודים. כדי שיהיו n−1 רכיבים, כל קודקוד שנשאר צריך להיות מבודד – כלומר כל הקשתות בגרף עברו דרך הקודקוד שנמחק.

פתרון: הטענה נכונה. ניקח גרף "כוכב": קודקוד מרכזי x המחובר בקשת לכל אחד מ־n−1 הקודקודים האחרים, ואין קשתות נוספות. הגרף קשיר (רכיב אחד). כל הקשתות נוגעות ב־x, ולכן אחרי מחיקת x (והקשתות שלו) לא נשארת אף קשת: n−1 קודקודים מבודדים, כלומר n−1 רכיבי קשירות.

דוגמה עם 4 קודקודים: x–1 , x–2 , x–3. מחיקת x משאירה את 1, 2, 3 – שלושה רכיבים = n−1.

בדיקה: בכוכב עם n קודקודים (למשל n = 2 עד 8) תמיד מתקבלים n−1 רכיבים.

סעיף א(4)

תשובה

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

מה נדרש: לקבוע אם המסלול שנמצא בעץ ה־DFS בין שני קודקודים הוא תמיד הקצר ביותר, כשהגרף לא מכוון וללא מעגלים.

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

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

בדיקה: ביער, מכל קודקוד התחלה ובכל סדר של סריקת השכנים, העומק של כל קודקוד בעץ ה־DFS שווה למרחק שמחשב BFS – כי יש מסלול יחיד בין כל שני קודקודים.

סעיף א(5)

תשובה

לא נכונה. דוגמה נגדית: s→a , a→b , b→c , s→c. DFS שהולך קודם ל־a מגיע ל־c במסלול באורך 3, אבל המרחק הוא 1.

מה נדרש: לקבוע אם ב־DAG (גרף מכוון ללא מעגלים) המסלול בעץ ה־DFS הוא תמיד הקצר ביותר.

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

פתרון: הטענה לא נכונה. דוגמה נגדית עם 4 קודקודים:
s→a , a→b , b→c , s→c

אין בגרף מעגל מכוון. נריץ DFS מ־s ונבחר קודם את השכן a:
s → a → b → c (c מתגלה דרך b), ואחר כך הקשת s→c כבר מובילה לקודקוד שהתגלה.
בעץ ה־DFS המסלול מ־s ל־c הוא s→a→b→c באורך 3, אבל המרחק המינימלי מ־s ל־c הוא 1 (הקשת s→c).

בדיקה: בכל עצי ה־DFS מ־s, עומק c הוא 1 או 3 (תלוי בסדר הסריקה), והמרחק לפי BFS הוא 1.

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

סעיף א(6)

תשובה

לא נכונה. דוגמה נגדית: קשתות s–v , v–a , v–b , a–s , b–s. ב־DFS מ־s (s→v→a, ואחר כך v→b) ל־v יש 2 בנים, אבל ב־DFS מ־v (v→a→s→b) ל־v יש בן אחד.

מה נדרש: לקבוע אם מספר הבנים של v בעץ DFS מ־s הוא חסם תחתון למספר הבנים של v כשהוא השורש.

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

פתרון: הטענה לא נכונה. דוגמה נגדית עם 4 קודקודים s, v, a, b וקשתות:
s–v , v–a , v–b , a–s , b–s

DFS מ־s (בוחרים קודם את v):
s → v → a (השכנים של a: v, s – כבר התגלו) → חוזרים ל־v → b (השכנים של b: v, s – כבר התגלו).
קשתות העץ: s–v , v–a , v–b. ל־v יש 2 בנים (x = 2).

DFS מ־v: v → a → s → b (מ־s ממשיכים ל־b), ואז כל הקודקודים התגלו.
קשתות העץ: v–a , a–s , s–b. ל־v יש בן אחד בלבד. (כל סדר סריקה מ־v נותן בן אחד ל־v, כי הגרף בלי v הוא קשיר: a–s–b.)

בדיקה: בכל עצי ה־DFS, מ־s ל־v יכולים להיות 1 או 2 בנים, ומ־v תמיד בן אחד בלבד.

סעיף ב

תשובה

(i) לא ייתכן – אין קשת a–b ב־G. (ii) לא ייתכן – אין קשת d–c ב־G. (iii) ייתכן – a→s→b, ומ־b אל d ואל c.

מה נדרש: לקבוע לכל אחד מהעצים (i), (ii), (iii) אם הוא יכול להיות עץ DFS מ־a של אותו גרף G.

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

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

עץקשתות העץקביעהנימוק
(i)a–b , b–d , b–c , c–sלא ייתכןהבן של a הוא b, כלומר נדרשת קשת a–b – והיא לא ב־G (השכן היחיד של a הוא s).
(ii)a–s , s–b , b–d , d–cלא ייתכןנדרשת קשת d–c, אבל d ו־c אחים בעץ הנתון ולכן אין ביניהם קשת.
(iii)a–s , s–b , b–d , b–cייתכןכל הקשתות קיימות ב־G, ויש סדר סריקה שנותן אותו (ראו למטה).

סריקה שנותנת את (iii): מתחילים ב־a ← עוברים לשכן היחיד s ← מ־s בוחרים את b ← מ־b עוברים ל־d (השכנים של d: b ואולי s – כבר התגלו) ← חוזרים ל־b ועוברים ל־c ← חוזרים. כל הקודקודים התגלו. זה נכון לכל אחד מהגרפים האפשריים (עם s–d , s–c או בלעדיהן), כי מ־s אפשר לבחור קודם את b.

בדיקה: בדיוק 4 גרפים על 5 הקודקודים נותנים את העץ הנתון מ־s (העץ ועוד תת־קבוצה של {s–d , s–c}). בכל אחד מהם נמצאו כל עצי ה־DFS מ־a: (iii) מתקבל, (i) ו־(ii) אף פעם לא.

שאלה 5 · דייקסטרה וגובה עצי DFS (25 נקודות)

בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.

א.(1)

לפניכם גרף ממושקל G₁ :

(1) איזה אלגוריתם מחזיר את המסלול הקצר (הקל) בין שני קודקודים בגרף ממושקל (אי־שלילי) כלשהו? מהי סיבוכיות זמן הריצה של האלגוריתם? נמקו את תשובתכם.

נוסף על כך, הריצו את האלגוריתם שכתבתם, בעבור הגרף הנתון G₁ , מצומת S לצומת T . בצעו מעקב שלב אחר שלב ורשמו את המסלול ואת אורכו (סכום משקליו).

(2)

עבור גרף G ממושקל כלשהו, הרצנו את האלגוריתם המוצא את המסלול הקצר (הקל) בין שני קודקודים, וקיבלנו מסלול העובר דרך הקשתות E(eᵢ , eⱼ , eₘ , ...) .

– האם המסלול הקצר בין שני הקודקודים יישאר בהכרח זהה אם משקל כל אחת מן הקשתות בגרף יוכפל ב־ x (1 < x) ? נמקו את תשובתכם.

– האם המסלול הקצר בין שני הקודקודים יישאר בהכרח זהה אם משקל כל אחת מן הקשתות בגרף יגדל ב־ x (1 < x)? נמקו את תשובתכם.

ב.(1)

לפניכם גרף מכוון G :

(1) הציגו שתי סריקות DFS מקודקוד התחלה a כך שיתקבלו שני עצים שהגבהים שלהם שונים זה מזה.

(2)

הוסיפו מספר מינימלי של קשתות כך שבשלוש סריקות DFS מקודקוד a , יתקבלו שלושה עצים שהגבהים שלהם שונים זה מזה. סרטטו את הגרף לאחר ההוספה, והציגו את שלוש הסריקות.

◂ פתרון מלא לשאלה 5

סעיף א(1)

תשובה

אלגוריתם דייקסטרה, O(V²) (במימוש עם ערימה: O((V+E)·log V)). המסלול: S→C→D→T, אורכו 34.

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

רעיון: אלגוריתם דייקסטרה מתאים לכל גרף (מכוון או לא, עם מעגלים או בלי) שמשקליו אי־שליליים. בכל שלב שולפים את הקודקוד שטרם טופל עם d[] הקטן ביותר – ערכו כבר סופי (כי אין משקלים שליליים שיכולים "להקטין" אותו אחר כך) – ומעדכנים (מקלים) את הקשתות היוצאות ממנו: אם d[u] + w(u,v) < d[v] אז d[v] ← d[u] + w(u,v) ו־π[v] ← u.
(בלמן־פורד גם נכון, אבל איטי יותר – O(V·E); מיון טופולוגי מתאים רק לגרף ללא מעגלים, והגרף "כלשהו".)

סיבוכיות: יש V שליפות. במימוש עם מערך, כל שליפה היא חיפוש מינימום בין V קודקודים – O(V), ובסך הכול O(V²). כל קשת מוקלת פעם אחת (כשהקודקוד שממנו היא יוצאת נשלף) – O(E) ≤ O(V²). סך הכול O(V²). (במימוש עם ערימת מינימום: כל שליפה ועדכון O(log V), ובסך הכול O((V+E)·log V).)

פתרון – מעקב על G₁: בכל תא: d (π). קודקוד שנשלף מסומן בהדגשה וערכו סופי.

שלבנשלףSABCDT
אתחול–0∞∞∞∞∞
1S (0)07 (S)14 (S)13 (S)∞∞
2A (7)712 (A)13 (S)∞39 (A)
3B (12)1213 (S)∞39 (A)
4C (13)1328 (C)39 (A)
5D (28)2834 (D)
6T (34)34

הסברים לשלבים:

•שלב 2: דרך A: B = 7+5 = 12 < 14 – עדכון; T = 7+32 = 39.
•שלב 3: דרך B: C = 12+2 = 14, לא קטן מ־13 – אין עדכון.
•שלב 4: דרך C: D = 13+15 = 28; T = 13+26 = 39, לא קטן ממש מ־39 – אין עדכון.
•שלב 5: דרך D: T = 28+6 = 34 < 39 – עדכון.

שחזור המסלול לפי π מהסוף: T ← D ← C ← S.
המסלול: S → C → D → T, אורכו 13 + 15 + 6 = 34.

בדיקה: מעקב מלא אחרי דייקסטרה נותן בדיוק את הטבלה הזאת. בנוסף נמנו כל המסלולים מ־S ל־T: הקצרים ביותר הם SCDT = 34, SABCDT = 35, SBCDT = 37, SAT = 39, SCT = 39 – ואכן 34 הוא המינימום.

סעיף א(2)

תשובה

הכפלה ב־x: כן, המסלול נשאר קצר ביותר (כל המסלולים מוכפלים ב־x). הגדלה ב־x: לא בהכרח (מסלול עם k קשתות גדל ב־k·x). למשל ב־G₁ עם x = 6: S→C→D→T = 52 אבל S→A→T = 51.

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

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

פתרון:
הכפלה ב־x – כן, בהכרח נשאר. אם למסלול P יש קשתות במשקלים w₁, …, w_k, אז אחרי ההכפלה משקלו x·w₁ + … + x·w_k = x·w(P). כל מסלול מוכפל באותו מספר חיובי x, ולכן הסדר בין המסלולים לא משתנה: אם w(E) ≤ w(P) לכל מסלול P, אז גם x·w(E) ≤ x·w(P). המסלול E נשאר מסלול קצר ביותר.

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

•S→C→D→T (3 קשתות): 34 + 3·6 = 52
•S→A→T (2 קשתות): 39 + 2·6 = 51

עכשיו המסלול הקצר הוא S→A→T, ולא המסלול שהתקבל קודם.

בדיקה: גם אחרי הכפלה ב־1.5, 2, 3, 10 דייקסטרה מוצא את S→C→D→T. אחרי הוספת 6 (וגם 10) התקבל S→A→T באורך 51 (עם x = 5 יש תיקו 49 = 49).

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

סעיף ב(1)

תשובה

סריקה 1: a→b, a→c, a→d (סדר b, c, d) – עץ בגובה 1. סריקה 2: a→d→c, ואז a→b – עץ בגובה 2.

מה נדרש: שתי סריקות DFS מ־a שנותנות עצים בגבהים שונים.

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

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

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

בדיקה: בכל עצי ה־DFS האפשריים מ־a מתקבלים בדיוק שני גבהים – 1 ו־2.

סעיף ב(2)

תשובה

מספיק להוסיף קשת אחת, c→b. גבהים: 1 (a→b, a→c, a→d), 2 (a→c→b, a→d), 3 (a→d→c→b).

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

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

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

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

סריקהסדר השכנים של aמהלךקשתות העץגובה
1b, c, da→b; a→c (c→b כבר התגלה); a→d (d→c כבר התגלה)a–b , a–c , a–d1
2c, b, da→c→b; חוזרים; a→d (d→c כבר התגלה)a–c , c–b , a–d2
3d, …a→d→c→b; חוזרים עד a, כל השכנים כבר התגלוa–d , d–c , c–b3

מספר הקשתות שהוספנו: 1 – וזה המינימום.
(גם הוספת b→d הייתה מתאימה: a→b→d→c נותן גובה 3.)

בדיקה: בגרף המקורי מתקבלים רק הגבהים 1, 2. מבין ההוספות של קשת אחת, c→b ו־b→d נותנות שלושה גבהים שונים, והגבהים שמתקבלים עם c→b הם בדיוק 1, 2, 3 כמו בטבלה.

שאלה 6 · גרף־כמעט־עץ (25 נקודות)

גרף לא מכוון נקרא "גרף־כמעט־עץ" אם קיימת בו קשת שכאשר מורידים אותה מקבלים עץ.

א.

סרטטו גרף שיש בו 6 קודקודים והוא "גרף־כמעט־עץ".

ב.(1)

נתון "גרף־כמעט־עץ" ובו n קודקודים.

(1) האם אפשר לדעת את מספר הקשתות בגרף זה? נמקו את תשובתכם. אם עניתם שאפשר, ציינו את מספר הקשתות.

(2)

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

ג.(1)

נתון גרף לא מכוון G ובו n קודקודים, המיוצג על ידי רשימת סמיכויות.

(1) כתבו אלגוריתם יעיל המחזיר "אמת" אם הגרף הוא "גרף־כמעט־עץ" ואחרת הוא מחזיר "שקר".

(2)

מהי סיבוכיות זמן הריצה של האלגוריתם שכתבתם? נמקו את תשובתכם.

◂ פתרון מלא לשאלה 6

סעיף א

תשובה

למשל: קודקודים 1–6, קשתות 1–2 , 2–3 , 3–1 , 3–4 , 4–5 , 4–6. הורדת הקשת 1–2 נותנת עץ.

מה נדרש: דוגמה לגרף לא מכוון עם 6 קודקודים שאם מורידים ממנו קשת מתאימה – מקבלים עץ.

רעיון: מתחילים מעץ על 6 קודקודים (5 קשתות) ומוסיפים לו קשת אחת. הקשת החדשה סוגרת מעגל אחד, והורדתה מחזירה את העץ.

פתרון:

קשתות: 1–2 , 2–3 , 3–1 , 3–4 , 4–5 , 4–6 (6 קשתות).
אם מורידים את הקשת 1–2 נשארות 5 קשתות: 2–3 , 3–1 , 3–4 , 4–5 , 4–6. הגרף קשיר ואין בו מעגל – זה עץ. לכן זהו "גרף־כמעט־עץ".

בדיקה: הגרף מקיים את ההגדרה, ואחרי הורדת 1–2 מתקבל עץ.

סעיף ב(1)

תשובה

כן. מספר הקשתות הוא n.

מה נדרש: לקבוע אם מספר הקשתות ב"גרף־כמעט־עץ" עם n קודקודים ידוע, ואם כן – מהו.

רעיון: בכל עץ עם n קודקודים יש בדיוק n−1 קשתות.

פתרון: כן. לפי ההגדרה יש קשת e שאחרי הורדתה מתקבל עץ על אותם n קודקודים (הורדת קשת לא מורידה קודקודים). לעץ הזה יש n−1 קשתות, ולכן לגרף המקורי יש n−1 + 1 = n קשתות.

בדיקה: בדוגמה מסעיף א: 6 קודקודים ו־6 קשתות. גם בבדיקה הממוחשבת – לכל אחד מ־3,898 הגרפים־כמעט־עצים עד 6 קודקודים היו בדיוק n קשתות.

סעיף ב(2)

תשובה

כן. יש רכיב קשירות אחד – הגרף קשיר.

מה נדרש: לקבוע את מספר רכיבי הקשירות של "גרף־כמעט־עץ".

רעיון: עץ הוא גרף קשיר, והוספת קשת לא יכולה לנתק גרף.

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

בדיקה: בדוגמה מסעיף א הגרף קשיר. גם בבדיקה הממוחשבת כל הגרפים־כמעט־עצים היו קשירים.

סעיף ג(1)

תשובה

G הוא גרף־כמעט־עץ ⇔ G קשיר ויש בו בדיוק n קשתות. האלגוריתם: סופרים קשתות (עוצרים אם יש יותר מ־n); אם ≠ n – שקר; אחרת BFS מקודקוד כלשהו: אם הגיע לכל n הקודקודים – אמת, אחרת שקר.

מה נדרש: אלגוריתם יעיל שבודק אם גרף (ברשימת סמיכויות) הוא "גרף־כמעט־עץ".

רעיון: נוכיח ש־G הוא גרף־כמעט־עץ אם ורק אם G קשיר ויש בו בדיוק n קשתות.

•⇐ (כיוון ראשון): הוכח בסעיף ב – יש n קשתות והגרף קשיר.
•⇒ (כיוון שני): נניח ש־G קשיר ויש בו n קשתות. גרף קשיר שאינו עץ מכיל מעגל, ו־G אינו עץ (לעץ יש n−1 קשתות). נוריד קשת כלשהי שנמצאת על מעגל: הגרף נשאר קשיר (בין קצות הקשת יש עדיין מסלול – שאר המעגל), ונשארות בו n−1 קשתות. גרף קשיר עם n−1 קשתות הוא עץ. לכן G הוא גרף־כמעט־עץ.

אז מספיק לספור קשתות ולבדוק קשירות.

פתרון – האלגוריתם (הגרף פשוט – בלי קשתות מקבילות ולולאות; כל קשת מופיעה פעמיים ברשימת הסמיכויות – פעם אצל כל אחד מקצותיה):

1.count ← 0
2.לכל קודקוד v בגרף: לכל שכן u ברשימת הסמיכויות של v:
•count ← count + 1
•אם count > 2n: החזר "שקר" (יותר מ־n קשתות – אפשר לעצור מיד)
3.אם count ≠ 2n: החזר "שקר" (מספר הקשתות count/2 שונה מ־n)
4.סמן את כל הקודקודים "לא התגלה". הרץ BFS (או DFS) מקודקוד כלשהו s, וספור את הקודקודים שהתגלו (כולל s) במשתנה visited.
5.אם visited = n: החזר "אמת", אחרת החזר "שקר".

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

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

סעיף ג(2)

תשובה

O(n) (ובאופן כללי O(V+E), אבל בזכות העצירה המוקדמת E ≤ n).

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

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

פתרון:

•שלב 2 (ספירת קשתות): עוברים על n רשימות. בגלל העצירה כש־count > 2n, סופרים לכל היותר 2n+1 איברים. לכן הזמן הוא O(n).
•שלב 3: השוואה אחת – O(1).
•שלבים 4–5 (BFS): BFS לוקח O(V+E). מגיעים לשלב הזה רק אם E = n, ולכן O(n + n) = O(n).

סך הכול: O(n). (בלי העצירה המוקדמת הסיבוכיות היא O(n + E), שהיא עדיין לינארית בגודל הקלט – רשימת הסמיכויות.)

בדיקה: הלולאה של ספירת הקשתות עוצרת ברגע ש־count עובר את 2n, ו־BFS רץ רק על גרפים עם n קשתות בדיוק.

פרק שני (50 נקודות) – מודלים חישוביים

יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).

שאלה 7 · שפות רגולריות והשלמת אוטומט סופי (25 נקודות)

בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.

א.(1)

לפניכם שלוש שפות מעל הא"ב {a , b} :

L₁ = { aⁿbᵐaᵏ | n, m, k > 0, n = k }

L₂ = { aⁿbᵐaᵏ | n, m, k > 0, n % 2 = k % 2 }

L₃ = { aⁿbᵐaᵏ | n, m, k > 0, n+m+k < 100 }

לפניכם ארבעה סעיפים (1)–(4). ענו על כולם (בנימוק מספיק הסבר מילולי, אין צורך באוטומט).

(1) בנוגע לכל אחת מן השפות L₁–L₃ , כתבו אם היא רגולרית או לא רגולרית. נמקו את תשובתכם.

(2)

האם השפה L₁ ∩ L₃ רגולרית? נמקו את תשובתכם.

(3)

האם השפה L₁ ∩ L̅₃ רגולרית? נמקו את תשובתכם.

(4)

האם השפה L₂ ∩ L̅₃ רגולרית? נמקו את תשובתכם.

ב.(1)

נתונה השפה L מעל הא"ב {a,b,c} :

L = {aᵐbᵏcˣ | m, k, x > 0 וגם (m%2 = k%2 או m%2 = x%2)}

הסבר: השפה L מכילה מילים שבהן כל אחת מן האותיות abc מופיעה פעם אחת לפחות, ולפי סדר זה (המופעים של a תחילה ואחר כך של b ואחר כך של c). כמו כן, אם מספר המופעים של האות a הוא זוגי/אי־זוגי, מספר המופעים של האות b או של האות c יהיה גם הוא זוגי/אי־זוגי בהתאמה.

דוגמה למילה בשפה L היא abbbbccc , כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא אי־זוגי, וכך גם מספר המופעים של האות c .

דוגמה נוספת למילה בשפה L היא aaaabbc , כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש. כמו כן מספר המופעים של האות a הוא זוגי, וכך גם מספר המופעים של האות b .

דוגמה למילה שאינה בשפה L היא aabc . אומנם כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש, אך מספר המופעים של האות a הוא זוגי, ואילו מספר המופעים של האות b ושל האות c הוא אי־זוגי.

(1) לפניכם חמש מילים: abbcc , abcc , bbc , abc , abbac.

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

(2)

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

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

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

◂ פתרון מלא לשאלה 7

סעיף א(1)

תשובה

L₁ – לא רגולרית; L₂ – רגולרית; L₃ – רגולרית (סופית). (וגם L₃ − L₁ רגולרית – סופית.)

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

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

פתרון:
L₁ – לא רגולרית. כדי לבדוק ש־k = n, האוטומט צריך "לזכור" את n (מספר ה־a בבלוק הראשון) עד שיגיע לבלוק האחרון, ו־n יכול להיות גדול כרצוננו. נימוק מדויק: אילו היה אוטומט סופי עם p מצבים, בין המילים a¹b, a²b, …, aᵖ⁺¹b היו שתיים, aⁱb ו־aʲb עם i ≠ j, שמסתיימות באותו מצב. אז האוטומט היה מקבל או דוחה יחד את aⁱbaⁱ (בשפה) ואת aʲbaⁱ (לא בשפה) – סתירה.

L₂ – רגולרית. צריך לזכור רק את הזוגיות של n (2 אפשרויות) ואת הזוגיות של k – מידע חסום. אוטומט סופי דטרמיניסטי (מעבר שלא מופיע – דחייה):

מצבמשמעותab
s (התחלה)–A1–
A1n אי־זוגי (בבלוק ה־a הראשון)A0B1
A0n זוגיA1B0
B1בבלוק ה־b, n אי־זוגיC11B1
B0בבלוק ה־b, n זוגיC01B0
C11 ✔n אי־זוגי, k אי־זוגיC10–
C10n אי־זוגי, k זוגיC11–
C01n זוגי, k אי־זוגיC00–
C00 ✔n זוגי, k זוגיC01–

מצבים מקבלים: C11, C00.

L₃ – רגולרית. התנאי n+m+k < 100 אומר שאורך כל מילה קטן מ־100, ולכן יש בשפה מספר סופי של מילים. כל שפה סופית היא רגולרית (אפשר לבנות אוטומט שבו מסלול לכל מילה).

(הערה: אם קוראים את הסימון כ"הפרש" L₃ − L₁ – גם היא רגולרית: L₃ − L₁ ⊆ L₃, כלומר שפה סופית.)

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

סעיף א(2)

תשובה

כן. L₁ ∩ L₃ ⊆ L₃ ולכן היא סופית – וכל שפה סופית רגולרית.

מה נדרש: לקבוע אם L₁ ∩ L₃ רגולרית.

רעיון: חיתוך עם שפה סופית נותן שפה סופית.

פתרון: רגולרית. כל מילה ב־L₁ ∩ L₃ שייכת ל־L₃, ול־L₃ יש מספר סופי של מילים (אורך < 100). לכן L₁ ∩ L₃ היא שפה סופית: { aⁿbᵐaⁿ | n, m > 0, 2n + m < 100 }, וכל שפה סופית היא רגולרית.

טעות נפוצה: לחשוב שאם L₁ לא רגולרית אז כל חיתוך שלה לא רגולרי. החיתוך "חותך" את הספירה לטווח חסום, ובטווח חסום אוטומט יכול לזכור את n.

סעיף א(3)

תשובה

לא. L₁ ∩ L̅₃ = { aⁿbᵐaⁿ | 2n+m ≥ 100 }. אילו הייתה רגולרית, אז L₁ = (L₁ ∩ L₃) ∪ (L₁ ∩ L̅₃) הייתה רגולרית (איחוד עם שפה סופית) – סתירה.

מה נדרש: לקבוע אם L₁ ∩ L̅₃ רגולרית (L̅₃ – המשלים של L₃ ביחס ל־{a,b}*).

רעיון: L₁ מתפרקת לשני חלקים: המילים הקצרות (בתוך L₃) והארוכות (מחוץ ל־L₃). החלק הקצר סופי, ולכן כל "הקושי" של L₁ נמצא בחלק הארוך.

פתרון: לא רגולרית. L₁ ∩ L̅₃ = { aⁿbᵐaⁿ | n, m > 0, 2n + m ≥ 100 } – אלה כל המילים של L₁ חוץ ממספר סופי של מילים קצרות.
מתקיים: L₁ = (L₁ ∩ L₃) ∪ (L₁ ∩ L̅₃).
נניח בשלילה ש־L₁ ∩ L̅₃ רגולרית. L₁ ∩ L₃ סופית ולכן רגולרית (סעיף 2), ואיחוד של שתי שפות רגולריות הוא רגולרי – כלומר L₁ הייתה רגולרית. אבל בסעיף 1 ראינו ש־L₁ לא רגולרית – סתירה.
במילים: גם במילים הארוכות האוטומט צריך לזכור את n כדי להשוות אותו ל־k, ו־n לא חסום.

סעיף א(4)

תשובה

כן. L₂ רגולרית, L̅₃ רגולרית (משלים של רגולרית), וחיתוך של רגולריות הוא רגולרי.

מה נדרש: לקבוע אם L₂ ∩ L̅₃ רגולרית.

רעיון: תכונות הסגירות של השפות הרגולריות – משלים וחיתוך.

פתרון: רגולרית. L₃ רגולרית (סופית), ולכן גם המשלים שלה L̅₃ רגולרי (באוטומט מלא ל־L₃ מחליפים מצבים מקבלים ולא מקבלים). L₂ רגולרית (סעיף 1). חיתוך של שתי שפות רגולריות הוא רגולרי (אוטומט מכפלה). לכן L₂ ∩ L̅₃ רגולרית.
במילים אחרות: L₂ ∩ L̅₃ = L₂ פחות מספר סופי של מילים – האוטומט של L₂ צריך רק לזכור זוגיות, ובנוסף לספור את האורך עד 100 (מספר סופי של מצבים).

סעיף ב(1)

תשובה

abbcc – לא שייכת; abcc – שייכת; bbc – לא שייכת; abc – שייכת; abbac – לא שייכת.

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

רעיון: בודקים קודם את הצורה (בלוק a, אחריו בלוק b, אחריו בלוק c, כל בלוק לא ריק), ואז את הזוגיות: m%2 = k%2 או m%2 = x%2.

פתרון:

מילהצורה aᵐbᵏcˣ?m, k, xזוגיותשייכת?
abbccכן1, 2, 2m אי־זוגי, k ו־x זוגיים – אין התאמהלא
abccכן1, 1, 2m ו־k אי־זוגיים – התאמהכן
bbcלא – אין a (m = 0)––לא
abcכן1, 1, 1כולם אי־זוגיים – התאמהכן
abbacלא – a מופיעה אחרי b––לא

בדיקה: חמש המילים מול הגדרת L – התוצאות זהות לטבלה.

סעיף ב(2)

תשובה

q2→q1: a ; q3→q4: b ; q4→q3: b ; q5→q6: b ; q6→q5: b ; q3→q10: c ; q6→q10: c ; q4→q8: c ; q7→q8: c ; q8→q9: c ; q9→q8: c ; q10→q10: c. מצבים מקבלים: q8, q10.

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

רעיון: נבין מה כל מצב "זוכר":

•q1 / q2 – בבלוק ה־a: מספר a אי־זוגי / זוגי (q0→q1 ב־a, q1→q2 ב־a, ולכן q2→q1 ב־a).
•q3 / q4 – אחרי מספר אי־זוגי של a, בבלוק ה־b: מספר b אי־זוגי / זוגי. ב־q3 כבר m%2 = k%2.
•q5 / q6 – אחרי מספר זוגי של a, בבלוק ה־b: מספר b אי־זוגי / זוגי. ב־q6 כבר m%2 = k%2.
•q10 – התנאי m%2 = k%2 כבר מתקיים, ולכן כל מספר חיובי של c מתקבל ⇒ q10 מקבל, עם לולאת c.
•q7, q8, q9 – התנאי על b לא מתקיים, ולכן צריך m%2 = x%2: q8 = "מספר ה־c עד עכשיו מתאים לזוגיות של m" (מקבל), q7 ו־q9 = "לא מתאים".
•מ־q4 (m אי־זוגי, k זוגי): c ראשון ⇒ x = 1 אי־זוגי = m ⇒ q8.
•מ־q5 (m זוגי, k אי־זוגי): c ראשון ⇒ x = 1 ≠ m ⇒ q7, ועוד c ⇒ x = 2 ⇒ q8.
•q8 ⇄ q9 בכל c נוסף (הזוגיות מתחלפת).

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

טבלת המעברים המלאה (מעבר שאינו בטבלה – האוטומט נתקע ודוחה):

מצבabcמקבל?
q0 (התחלה)q1––לא
q1q2q3–לא
q2q1q5–לא
q3–q4q10לא
q4–q3q8לא
q5–q6q7לא
q6–q5q10לא
q7––q8לא
q8––q9כן
q9––q8לא
q10––q10כן

(בהדגשה – התוויות שהוספנו. התוויות המודפסות a, a, b, b, c נשארו כמו שהן.)

מעקב לדוגמה:

•abbbbccc: q0 –a→ q1 –b→ q3 –b→ q4 –b→ q3 –b→ q4 –c→ q8 –c→ q9 –c→ q8 ✔ (מקבל).
•aaaabbc: q0→q1→q2→q1→q2 –b→ q5 –b→ q6 –c→ q10 ✔.
•aabc: q0→q1→q2 –b→ q5 –c→ q7 ✘ (q7 לא מקבל).

בדיקה: האוטומט המושלם (בדיוק 17 המעברים המצוירים) מקבל בדיוק את המילים של L.

שאלה 8 · פעולות על שפות ואוטומט מחסנית (25 נקודות)

בשאלה זו שני סעיפים, א–ב, שאין קשר ביניהם. ענו על שני הסעיפים.

א.(1)

נתונות שלוש שפות L₁ , L₂ , L₃ מעל הא"ב {a, b, c} .

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

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

(1) R(R(L₁) · R(L₂)) = L₁ · L₂

(2)

L₁ · (L₂ ∪ L₃) = (L₁ · L₂) ∪ (L₁ · L₃)

(3)

L₁ ∩ (L₂ · L₃) = (L₁ ∩ L₂) · (L₁ ∩ L₃)

ב.

נתונה השפה L מעל הא"ב {a, b, c} :

L = {aⁱbʲcⁱ⁻ʲ | i ≥ 4, (i − j) ≥ 3}

בנו אוטומט מחסנית דטרמיניסטי המקבל את השפה L .

◂ פתרון מלא לשאלה 8

סעיף א(1)

תשובה

לא נכונה. R(R(L₁)·R(L₂)) = L₂·L₁. דוגמה: L₁ = {a}, L₂ = {b}: אגף שמאל {ba}, אגף ימין {ab}.

מה נדרש: לקבוע אם היפוך של שרשור ההיפוכים מחזיר את L₁·L₂.

רעיון: היפוך של שרשור הופך גם את הסדר: R(xy) = R(y)·R(x), ולכן R(A·B) = R(B)·R(A).

פתרון: לא נכונה.
R(R(L₁)·R(L₂)) = R(R(L₂)) · R(R(L₁)) = L₂ · L₁ , ובדרך כלל L₂·L₁ ≠ L₁·L₂.
דוגמה נגדית: L₁ = {a} , L₂ = {b}.

•R(L₁) = {a}, R(L₂) = {b}, R(L₁)·R(L₂) = {ab}, R({ab}) = {ba}.
•L₁ · L₂ = {ab}.

{ba} ≠ {ab} – הטענה לא מתקיימת.

בדיקה: חישוב שני האגפים לדוגמה הזאת; ובאופן כללי R(R(L₁)·R(L₂)) = L₂·L₁ תמיד.

סעיף א(2)

תשובה

נכונה – שרשור מתפלג מעל איחוד.

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

רעיון: מראים הכלה בשני הכיוונים, לפי ההגדרה של שרשור: w ∈ A·B אם w = xy עם x ∈ A ו־y ∈ B.

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

•⊆: תהי w ∈ L₁·(L₂ ∪ L₃). אז w = xy עם x ∈ L₁ ו־y ∈ L₂ ∪ L₃. אם y ∈ L₂ אז w ∈ L₁·L₂, ואם y ∈ L₃ אז w ∈ L₁·L₃. בכל מקרה w ∈ (L₁·L₂) ∪ (L₁·L₃).
•⊇: תהי w ∈ (L₁·L₂) ∪ (L₁·L₃). אם w ∈ L₁·L₂ אז w = xy עם x ∈ L₁, y ∈ L₂ ⊆ L₂ ∪ L₃, ולכן w ∈ L₁·(L₂ ∪ L₃). אותו דבר אם w ∈ L₁·L₃.

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

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

סעיף א(3)

תשובה

לא נכונה. דוגמה: L₁ = {ab}, L₂ = {a}, L₃ = {b}: אגף שמאל {ab}, אגף ימין ∅·∅ = ∅.

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

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

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

•אגף שמאל: L₂·L₃ = {ab}, ולכן L₁ ∩ (L₂·L₃) = {ab}.
•אגף ימין: L₁ ∩ L₂ = ∅ ו־L₁ ∩ L₃ = ∅, ושרשור עם הקבוצה הריקה הוא ריק: ∅·∅ = ∅.

{ab} ≠ ∅ – הטענה לא מתקיימת.

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

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

סעיף ב

תשובה

דוחפים X עבור ה־a הראשון ו־A עבור כל a נוסף; כל b שולף A; כל c שולף; ה־c ששולף את X עובר למצב המקבל f – בתנאי שנקראו לפחות 3 c (אם היו b) או לפחות 4 c (אם לא היו b). טבלת המעברים המלאה בפתרון.

מה נדרש: אוטומט מחסנית דטרמיניסטי (אמ"ד) שמקבל בדיוק את המילים aⁱbʲcⁱ⁻ʲ עם i ≥ 4 ו־i − j ≥ 3.

רעיון:

•מספר ה־c הוא i − j, כלומר מספר ה־b ועוד מספר ה־c שווה למספר ה־a. לכן: דוחפים סימן לכל a, ושולפים סימן לכל b ולכל c. המילה תקינה אם המחסנית מתרוקנת בדיוק עם ה־c האחרון.
•כדי לדעת מתי הוצא הסימן האחרון (בלי מעברי ε), ה־a הראשון דוחף סימן מיוחד X ושאר ה־a דוחפים A. ה־c ששולף את X הוא בהכרח האחרון – עוברים איתו למצב המקבל f, שאין ממנו מעברים (תו נוסף ⇒ דחייה).
•b אסור לו לשלוף את X (זה אומר j ≥ i, ואז אין מקום ל־c).
•בהגדרת השפה אין דרישה ש־j > 0, ולכן גם j = 0 מותר (מילים בלי b, כמו aaaacccc).
•התנאים על i ו־j: אם יש b (j ≥ 1) – הדרישה i − j ≥ 3 כבר נותנת i ≥ 4, ולכן צריך לפחות 3 c. אם אין b (j = 0) – צריך i ≥ 4, כלומר לפחות 4 c. את מספר ה־c (עד 3 או 4) סופרים במצבים.

פתרון:

•א"ב הקלט: {a, b, c}. א"ב המחסנית: {⊥, X, A}, בתחילה במחסנית רק ⊥ (סימן תחתית).
•מצב התחלה: q0. מצב מקבל: f. המילה מתקבלת אם בסוף הקלט האוטומט במצב f.
•אין מעברי ε, ולכל שלשה (מצב, תו, ראש המחסנית) יש לכל היותר מעבר אחד ⇒ האוטומט דטרמיניסטי. צירוף שאינו בטבלה ⇒ האוטומט נתקע והמילה נדחית.
מצבתו קלטראש המחסניתפעולה במחסניתמצב חדשהסבר
q0a⊥push Xqaה־a הראשון
qaaXpush Aqaעוד a
qaaApush Aqaעוד a
qabApopqbb ראשון
qbbApopqbעוד b
qacApopp1c ראשון, אין b
p1cApopp2c שני
p2cApopp3c שלישי
p3cApopp4c רביעי ומעלה
p4cApopp4
p3cXpopfc רביעי והאחרון
p4cXpopfc אחרון (5 ומעלה)
qbcApopr1c ראשון, אחרי b
r1cApopr2c שני
r2cApopr3c שלישי ומעלה
r3cApopr3
r2cXpopfc שלישי והאחרון
r3cXpopfc אחרון (4 ומעלה)

(אין מעבר מ־f – אחרי שהמחסנית חזרה ל־⊥ אסור שיבוא עוד תו. אין מעבר ל־b או c עם X בראש – זה היה אומר שה־b/c "גומרים" את ה־a מוקדם מדי.)

מעקב על aaaabccc (i = 4, j = 1, i − j = 3 ⇒ בשפה):

נקראמצב אחרימחסנית (הראש מימין)
–q0⊥
aqa⊥X
aqa⊥XA
aqa⊥XAA
aqa⊥XAAA
bqb⊥XAA
cr1⊥XA
cr2⊥X
cf⊥

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

דוגמאות דחייה: aaaaccc (j = 0, רק 3 c: ב־p2 נקרא c עם X בראש – אין מעבר); aaaabbcc (i − j = 2: ב־r1 נקרא c עם X בראש – אין מעבר); aaaacccccc (c נוסף אחרי f – אין מעבר).

בדיקה: האוטומט מקבל בדיוק את המילים של L – כך עולה גם מבדיקה של כל המילים הקצרות מעל {a,b,c}. בין השאר: aaaacccc, aaaabccc, aaaaabbccc מתקבלות; aaaaccc, aaabcc, aaaabbcc, aaaacccccc נדחות.

שאלה 9 · מכונת טיורינג – חצי המספר או המספר פחות 1 (25 נקודות)

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

•אם המספר שהתקבל זוגי – המכונה מחזירה את המספר המקורי חלקי 2 .
•אם המספר שהתקבל אי־זוגי – המכונה מחזירה את המספר המקורי פחות 1 .

הנחיות:

– אין צורך לשמור על הקלט (אפשר לשנות את הקלט לסימנים שונים).

– המספר המוחזר יופיע במקום כלשהו בסרט בין שני סימני $ .

– אין צורך לבדוק את תקינות הקלט.

דוגמה למספר זוגי

הסרט לפני ההרצה:

הסרט לאחר ההרצה:

דוגמה למספר אי־זוגי

הסרט לפני ההרצה:

הסרט לאחר ההרצה:

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

(25 נקודות)
◂ פתרון מלא לשאלה 9

פתרון

תשובה

בודקים זוגיות במעבר אחד ימינה. אי־זוגי: ה־1 הראשון ← $, ו־$ בתא הריק הראשון ⇒ $1ⁿ⁻¹$. זוגי: בכל סבב ה־1 השמאלי ← x וה־1 הימני ← Y; כשאין יותר 1 – ה־x האחרון ← $, כל Y ← 1, ו־$ בתא הריק הראשון ⇒ $1ⁿᐟ²$.

מה נדרש: מכונת טיורינג שמקבלת 1ⁿ (n > 1) אחרי סימן תחילת הסרט ⊢, ומשאירה על הסרט $1ʳ$, כאשר r = n/2 אם n זוגי ו־r = n − 1 אם n אי־זוגי.

רעיון:

1.זוגיות: עוברים ימינה על ה־1 ומחליפים בין שני מצבים (זוגי/אי־זוגי) עד התא הריק △.
2.n אי־זוגי: צריך n − 1 אחדות. חוזרים לתחילת הסרט, הופכים את ה־1 הראשון ל־$, הולכים ימינה עד △ וכותבים $. נשארו בין שני ה־$ בדיוק n − 1 אחדות.
3.n זוגי: צריך n/2 אחדות. עובדים בסבבים: בכל סבב הופכים את ה־1 השמאלי ביותר ל־x ("נזרק") ואת ה־1 הימני ביותר ל־Y ("נשמר"). כך כל סבב "מטפל" בזוג אחדות. כשמחפשים 1 שמאלי ומוצאים Y – כל האחדות טופלו: יש ⊢ xⁿᐟ² Yⁿᐟ². אז ה־x האחרון (הצמוד ל־Y) הופך ל־$, כל Y הופך ל־1, ובתא הריק הראשון כותבים $. התוצאה: ⊢ x…x $ 1ⁿᐟ² $.

פתרון:

•א"ב הסרט: {⊢, 1, △, x, Y, $}. △ – תא ריק.
•הראש מתחיל על ⊢ במצב q0. (אם לפי הסימון שלכם הראש מתחיל על התו הראשון אחרי ⊢ – מתחילים ישר במצב qE.)
•מצב עצירה: h. תזוזות: R ימינה, L שמאלה.
מצבקוראכותבתזוזהמצב חדשהסבר
q0⊢⊢RqEהתחלה
qE11RqOעד כאן מספר אי־זוגי של 1
qO11RqEעד כאן מספר זוגי של 1
qE△△Le0n זוגי
qO△△Lo0n אי־זוגי
o011Lo0חזרה לתחילה
o0⊢⊢Ro1
o11$Ro2ה־1 הראשון ← $
o211Ro2
o2△$Rh$ בסוף – עצירה
e011Le0חזרה לתחילה
e0⊢⊢Re1
e1xxRe1דילוג על x
e11xRe2ה־1 השמאלי ← x
e1YYLf1אין יותר 1 – סיום
e211Re2ימינה עד סוף האחדות
e2YYLe3
e2△△Le3
e31YLe4ה־1 הימני ← Y
e411Le4חזרה שמאלה
e4xxRe1סבב חדש
f1x$Rf2ה־x האחרון ← $
f2Y1Rf2כל Y ← 1
f2△$Rh$ בסוף – עצירה

למה ב־e3 תמיד יש 1? בתחילת כל סבב מספר האחדות שנשארו זוגי וחיובי. אחרי שה־1 השמאלי הפך ל־x נשאר לפחות 1 אחד, וזה ה־1 שמשמאל ל־Y הראשון (או ל־△).

מעקב – n = 6 (זוגי) (מצב הסרט בסוף כל שלב):

שלבהסרט
התחלה⊢111111
בדיקת זוגיות (qE בסוף) ⇒ זוגי⊢111111
סבב 1⊢x1111Y
סבב 2⊢xx11YY
סבב 3⊢xxxYYY
e1 פוגש Y ⇒ f1: ה־x האחרון ← $⊢xx$YYY
f2: Y ← 1, ו־$ בסוף⊢xx$111$

בין שני ה־$: 111 = 3 = 6/2 ✔ (כמו בדוגמה).

מעקב – n = 5 (אי־זוגי): ⊢11111 ← (qO בסוף, אי־זוגי) ← o1: ⊢$1111 ← o2 כותב $ בסוף: ⊢$1111$. בין ה־$: 1111 = 4 = 5 − 1 ✔.

בדיקה: לכל n (למשל 1 עד 40) נשארים על הסרט בדיוק שני סימני $ וביניהם n/2 אחדות (n זוגי) או n − 1 אחדות (n אי־זוגי). למשל n = 4 ⇒ ⊢x$11$ (30 צעדים), n = 7 ⇒ ⊢$111111$, n = 20 ⇒ עשר אחדות בין ה־$.

תכנות מונחה עצמים

יש לענות על שתי שאלות במסלול שלמדתם (לכל שאלה – 25 נקודות).

שאלה 10 · גן החיות – היררכיית בעלי חיים (25 נקודות)

נוסח השאלה:

> שימו לב: השאלות 10–12 הן גם בעבור הפותרים בשפת Java וגם בעבור הפותרים בשפת C# .
> לכל שאלה נוסח בשפת Java ונוסח בשפת C# .

לשאלה זו שני נוסחים: בשפת Java בעמודים 14–15 ובשפת C# בעמודים 16–17.

לפותרים בשפת Java

בגן החיות "חיים בשלום" פותחה מערכת ממוחשבת ובה שומרים נתונים על בעלי החיים שבגן. המערכת כוללת את המחלקות האלה: בעל חיים – Animal , ציפור – Bird , תוכי – Parrot , דג – Fish , נחש – Snake .

נתון חלק ממבנה המחלקות במערכת הממוחשבת:

Java
public class Animal {
    private String color;
    private int weight;
    public Animal (String color, int weight)
    {
        this.color = color;
        this.weight = weight;
    }
    public String toString() {
        return "My color is " + this.color + "! And I weigh " + weight + " kilos!";
    }
}
public class Bird {
    private String color;
    private int weight;
    private boolean isFlying;
    public void zoo () {
        System.out.println ("Hello");
    }
}
public class Parrot {
    private String color;
    private int weight;
    private boolean isFlying;
    private boolean isTalking;
    public void zoo () {
        System.out.println ("Hello");
    }
}
public class Fish {
    private String color;
    private int weight;
    private String waterType;      // דג ים/דג מים מתוקים
}
public class Snake {
    private String color;
    private int weight;
    private int length;
    private boolean isVenomous;    // האם הנחש ארסי?
}

הניחו שיש פעולות get ו־ set לתכונות המחלקות.

א.

כתבו מחדש את הכותרות, התכונות והפעולות של המחלקות: Bird , Parrot , Fish ו־ Snake , לפי עקרונות תכנות מונחה עצמים (אין לשנות את המחלקה Animal). בסעיף זה אין צורך לכתוב פעולות בונות. הניחו שהפעולות get ו־ set קיימות.

נוסף על כך, סרטטו תרשים הייררכייה בין כל המחלקות. יש לסמן ירושה באמצעות החץ ◁——— .

ב.

נתונה המחלקה Tester :

Java
public class Tester {
    public static void main (String[] args) {
        Animal[] animals = new Animal [5];
        animals [0] = new Bird ("white", 4, false);
        animals [1] = new Fish ("blue", 3, "sweet water");
        animals [2] = new Parrot ("brown", 12, true, true);
        animals [3] = new Snake ("gray", 2, 6, true);
        animals [4] = new Snake ("black", 3, 4, false);
        //***
    }
}

הוסיפו פעולות בונות למחלקות Bird , Parrot , Fish ו־ Snake , המאתחלות את תכונות המחלקות (כך שהפעולה main תרוץ ללא שגיאות).

הערה: אין לשנות את הפעולה הבונה הנתונה של Animal .

ג.(1)

בפעולה main נוסף קטע הקוד שלפניכם (במקום המסומן ב־ *):

Java
for (int i = 0; i < animals.length; i++) {
    System.out.println (animals[i]); }

קטע הקוד תקין ומדפיס את הפלט שלפניכם:

I'm a bird! My color is white! And I weigh 4 kilos!
My color is blue! And I weigh 3 kilos!
I'm a parrot! My color is brown!
I'm a snake! I'm venomous, be careful! My color is gray! And I weigh 2 kilos!
I'm a snake! I'm not venomous! My color is black! And I weigh 3 kilos!

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

הערה: אין לשנות את הפעולה toString במחלקה Animal . תשובה שבה יהיה שינוי לא תזוכה בנקודות.

(2)

במחלקה Tester נוספה הפעולה שלפניכם:

Java
public static void hello (Animal [] arr) {
    for (int i = 0; i < arr.length; i++) {
        arr[i].zoo(); }
}

אם הפעולה תקינה, כתבו את הפלט שלה עבור המערך animals (הנתון לעיל), ואם הפעולה לא תקינה – תקנו אותה (כך שהקריאה ל־ zoo בתוך הלולאה תהיה תקינה) וכתבו את הפלט עבור המערך animals .

הערות:

•אין לשנות את המחלקות עצמן. תשובה שבה יהיה שינוי במחלקות לא תזוכה בנקודות.
•הפעולה צריכה לרוץ ללא שגיאות עבור כל מערך מטיפוס Animal .
◂ פתרון מלא לשאלה 10

סעיף א

תשובה

Bird יורשת מ־Animal (isFlying, zoo); Parrot יורשת מ־Bird (isTalking); Fish יורשת מ־Animal (waterType); Snake יורשת מ־Animal (length, isVenomous). התכונות color ו־weight נשארות רק ב־Animal.

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

רעיון

•התכונות color ו־weight משותפות לכל בעלי החיים והן כבר נמצאות ב־Animal. לכן כל המחלקות יורשות (ישירות או בעקיפין) מ־Animal, ומוחקים מהן את color ו־weight.
•Bird ו־Parrot חולקות גם את isFlying ואת הפעולה zoo(), ותוכי הוא ציפור. לכן Parrot יורשת מ־Bird ומוסיפה רק את isTalking (את isFlying ואת zoo() היא יורשת).
•Fish ו־Snake יורשות ישירות מ־Animal ומוסיפות רק את התכונות הייחודיות להן.
•הפעולות get/set של כל תכונה נמצאות במחלקה שבה התכונה מוגדרת, ועוברות בירושה.

פתרון – :

public class Bird extends Animal {
    private boolean isFlying;
    public void zoo() {
        System.out.println("Hello");
    }
}
public class Parrot extends Bird {
    private boolean isTalking;
}
public class Fish extends Animal {
    private String waterType;      // דג ים/דג מים מתוקים
}
public class Snake extends Animal {
    private int length;
    private boolean isVenomous;    // האם הנחש ארסי?
}

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

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

טעות נפוצה: להגדיר את Parrot כיורשת ישירות מ־Animal ולהשאיר בה את isFlying ואת zoo() – זו כפילות קוד, ותוכי הוא ציפור.

סעיף ב

תשובה

בכל פעולה בונה קוראים לפעולה הבונה של מחלקת הבסיס: Bird(color, weight, isFlying) → super(color, weight); Parrot(color, weight, isFlying, isTalking) → super(color, weight, isFlying); Fish(color, weight, waterType) → super(color, weight); Snake(color, weight, length, isVenomous) → super(color, weight).

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

רעיון

•התכונות color ו־weight הן פרטיות (private) ב־Animal, ולכן המחלקה היורשת אינה יכולה להציב בהן ישירות. מעבירים אותן לפעולה הבונה של מחלקת הבסיס: super(color, weight) ב־Java, : base(color, weight) ב־C#.
•ל־Animal אין פעולה בונה ללא פרמטרים, ולכן חובה לקרוא במפורש לפעולה הבונה של מחלקת הבסיס בכל פעולה בונה של מחלקה יורשת.
•Parrot יורשת מ־Bird, ולכן היא קוראת לפעולה הבונה של Bird עם (color, weight, isFlying) ומאתחלת בעצמה רק את isTalking.
•סדר הפרמטרים נקבע לפי הקריאות ב־main: new Snake ("gray", 2, 6, true) – צבע, משקל, אורך, ארסי (הפלט בסעיף ג "And I weigh 2 kilos" מאשר ש־2 הוא המשקל).

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

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

טעות נפוצה: לכתוב this.color = color; בפעולה הבונה של Bird – התכונה פרטית ב־Animal ולכן זו שגיאת הידור. גם פעולה בונה בלי קריאה ל־super/base לא תעבור הידור, כי ל־Animal אין פעולה בונה ריקה.

הקוד המלא
public class Bird extends Animal {
    private boolean isFlying;

    public Bird(String color, int weight, boolean isFlying) {
        super(color, weight);
        this.isFlying = isFlying;
    }

    public void zoo() {
        System.out.println("Hello");
    }
}

public class Parrot extends Bird {
    private boolean isTalking;

    public Parrot(String color, int weight, boolean isFlying, boolean isTalking) {
        super(color, weight, isFlying);
        this.isTalking = isTalking;
    }
}

public class Fish extends Animal {
    private String waterType;      // דג ים/דג מים מתוקים

    public Fish(String color, int weight, String waterType) {
        super(color, weight);
        this.waterType = waterType;
    }
}

public class Snake extends Animal {
    private int length;
    private boolean isVenomous;    // האם הנחש ארסי?

    public Snake(String color, int weight, int length, boolean isVenomous) {
        super(color, weight);
        this.length = length;
        this.isVenomous = isVenomous;
    }
}

סעיף ג(1)

תשובה

דורסים toString רק ב־Bird ("I'm a bird! " + super.toString()), ב־Parrot ("I'm a parrot! My color is " + getColor() + "!") וב־Snake (קידומת לפי isVenomous + super.toString()); ב־Fish לא צריך.

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

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

עצםשורת הפלטמה צריך
BirdI'm a bird! + הפלט של Animalלדרוס ב־Bird: קידומת + super.toString()
Fishבדיוק הפלט של Animalלא צריך toString ב־Fish (יורשת מ־Animal)
ParrotI'm a parrot! My color is brown! – בלי I'm a bird! ובלי משקללדרוס ב־Parrot: מחרוזת חדשה; הצבע פרטי ב־Animal, ולכן ניגשים אליו בעזרת getColor()
SnakeI'm a snake! + קטע שתלוי ב־isVenomous + הפלט של Animalלדרוס ב־Snake: קידומת לפי isVenomous + super.toString()

ב־C# כל ToString מוגדרת עם override (גם ב־Parrot, שדורסת את הגרסה של Bird).

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

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

I'm a bird! My color is white! And I weigh 4 kilos!
My color is blue! And I weigh 3 kilos!
I'm a parrot! My color is brown!
I'm a snake! I'm venomous, be careful! My color is gray! And I weigh 2 kilos!
I'm a snake! I'm not venomous! My color is black! And I weigh 3 kilos!

טעות נפוצה: להוסיף toString גם ל־Fish (מיותר – זה בדיוק מה שנורש), או לכתוב ב־Parrot "I'm a parrot! " + super.toString() – זה היה מדפיס גם I'm a bird! ואת המשקל.

הקוד המלא
public class Bird extends Animal {
    private boolean isFlying;

    public Bird(String color, int weight, boolean isFlying) {
        super(color, weight);
        this.isFlying = isFlying;
    }

    public void zoo() {
        System.out.println("Hello");
    }

    public String toString() {
        return "I'm a bird! " + super.toString();
    }
}

public class Parrot extends Bird {
    private boolean isTalking;

    public Parrot(String color, int weight, boolean isFlying, boolean isTalking) {
        super(color, weight, isFlying);
        this.isTalking = isTalking;
    }

    public String toString() {
        return "I'm a parrot! My color is " + getColor() + "!";
    }
}

public class Fish extends Animal {
    private String waterType;      // דג ים/דג מים מתוקים

    public Fish(String color, int weight, String waterType) {
        super(color, weight);
        this.waterType = waterType;
    }
}

public class Snake extends Animal {
    private int length;
    private boolean isVenomous;    // האם הנחש ארסי?

    public Snake(String color, int weight, int length, boolean isVenomous) {
        super(color, weight);
        this.length = length;
        this.isVenomous = isVenomous;
    }

    public String toString() {
        String s = "I'm a snake! ";
        if (isVenomous)
            s = s + "I'm venomous, be careful! ";
        else
            s = s + "I'm not venomous! ";
        return s + super.toString();
    }
}

סעיף ג(2)

תשובה

לא תקינה (שגיאת הידור: ב־Animal אין zoo). תיקון: if (arr[i] instanceof Bird) ((Bird)arr[i]).zoo(); (ב־C#: is Bird / Zoo). הפלט עבור animals: Hello, Hello (שתי שורות).

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

רעיון – הפעולה לא תקינה (שגיאת הידור). הטיפוס המוצהר של arr[i] הוא Animal, והמהדר בודק קריאה לפי הטיפוס המוצהר; ב־Animal אין פעולה zoo() (ב־C#: Zoo()), ולכן הקריאה לא עוברת הידור, גם אם בזמן ריצה העצם הוא Bird.
התיקון: לבדוק אם העצם הוא ציפור (instanceof Bird ב־Java, is Bird ב־C#) ורק אז להמיר (casting) ל־Bird ולקרוא ל־zoo(). Parrot יורשת מ־Bird, ולכן גם תוכי עובר את הבדיקה.

•בלי הבדיקה, המרה של Fish או Snake ל־Bird הייתה זורקת חריגה בזמן ריצה (ClassCastException / InvalidCastException), והפעולה לא הייתה רצה ללא שגיאות לכל מערך.
•אם במערך יש תא ריק (null), הבדיקה instanceof / is מחזירה false, ולכן גם אז אין שגיאה.

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

בדיקה – עבור animals: Bird (תא 0) ו־Parrot (תא 2) מדפיסים, Fish ו־Snake לא. הפלט (Java ו־C#):

Hello
Hello

הפעולה המקורית אכן לא עוברת הידור (Java: cannot find symbol ... method zoo() ... location: class Animal; C#: 'Animal' does not contain a definition for 'Zoo'). במערך עם Fish, תא null ו־Parrot מודפס Hello אחד, בלי שגיאה.

הקוד המלא
public static void hello (Animal [] arr) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] instanceof Bird) {
            ((Bird) arr[i]).zoo();
        }
    }
}

שאלה 11 · One, Two, Three – תכונה סטטית ושרשור פעולות בונות (25 נקודות)

נוסח השאלה:

לשאלה זו שני נוסחים: בשפת Java בעמודים 18–19 ובשפת C# בעמודים 20–21.

לפותרים בשפת Java

נתונות המחלקות One , Two , Three :

Java
public class One {
    public static int count = 0;
    private int number;
    public One() {
        count++;
        number = count;
    }
    public One (int num) {
        number = num;
    }
    public String toString() {
        return count + ", "+ number;
    }
}
---------------------------------------------
public class Two extends One {
    private String strTwo;
    public Two() {
        strTwo = "Fast";
    }
    public Two (String s) {
        super (15);
        strTwo = s;
    }
    public String toString() {
        return super.toString() + " "+strTwo;
    }
}
-------------------------------------------------
public class Three extends Two {
    private String strThree;
    public Three (String s) {
        strThree = s;
    }
    public String toString() {
        return super.toString() + " "+ strThree;
    }
}
א.

נתונה המחלקה Test :

Java
public class Test
{
    public static void main (String[] args)
    {
        One[] arr=new One[6];
        arr[0]= … // (1)
        arr[1]= … // (2)
        arr[2]= … // (3)
        arr[3]= … // (4)
        arr[4]= … // (5)
        arr[5]= … // (6)
        for (int i = 0; i < arr.length; i++) {
            System.out.println (arr[i]);
        }
    }
}

השלימו את השורות (1)–(6) כך שהפלט יהיה:

4, 1 Fast
4, 2 Fast Car
4, 3 Fast Horse
4, 15 Small
4, 15 Tall
4, 4
ב.

הכותרת של המחלקה Three השתנתה לכותרת:

Java
public class Three extends One

האם שינוי זה יגרום לשגיאה? אם כן – הסבירו את השגיאה, אם לא – רשמו מה יהיה הפלט של הפעולה main אחרי השינוי (השורות החסרות הן כפי שכתבתם בסעיף א).

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

◂ פתרון מלא לשאלה 11

סעיף א

תשובה

(1) new Two() (2) new Three("Car") (3) new Three("Horse") (4) new Two("Small") (5) new Two("Tall") (6) new One()

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

רעיון

•count היא תכונה סטטית – משותפת לכל העצמים. היא גדלה רק בפעולה הבונה One(). ההדפסה מתבצעת אחרי שכל ששת העצמים נוצרו, ולכן בכל השורות מודפס הערך הסופי של count – 4. כלומר One() צריכה לרוץ בדיוק 4 פעמים.
•number נקבעת ביצירת העצם: ב־One() היא מקבלת את count באותו רגע (1, 2, 3, 4 לפי סדר היצירה), וב־One(int num) היא מקבלת את num.
•שרשור פעולות בונות:
•Two() קוראת במובלע ל־One() (count++), ו־strTwo = "Fast".
•Two(String s) קוראת במפורש ל־One(15) – בלי count++, ו־number = 15, strTwo = s.
•Three(String s) קוראת במובלע ל־Two() ← One() (count++), ולכן strTwo = "Fast" ו־strThree = s.
•toString משרשרת: One מחזירה count, number; Two מוסיפה רווח ו־strTwo; Three מוסיפה רווח ו־strThree.
שורהעצםcount אחרי היצירהnumberמה יודפס
(1)new Two()114, 1 Fast
(2)new Three("Car")224, 2 Fast Car
(3)new Three("Horse")334, 3 Fast Horse
(4)new Two("Small")3154, 15 Small
(5)new Two("Tall")3154, 15 Tall
(6)new One()444, 4

השורה 4, 4 (בלי מילה) חייבת להיות עצם מסוג One שנוצר ב־One(), והוא היצירה הרביעית שמגדילה את count – ולכן הוא אחרון.

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

arr[0] = new Two();          // (1)
arr[1] = new Three("Car");   // (2)
arr[2] = new Three("Horse"); // (3)
arr[3] = new Two("Small");   // (4)
arr[4] = new Two("Tall");    // (5)
arr[5] = new One();          // (6)

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

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

4, 1 Fast
4, 2 Fast Car
4, 3 Fast Horse
4, 15 Small
4, 15 Tall
4, 4

טעות נפוצה: לחשוב שבשורה הראשונה יודפס 1, 1 Fast – count סטטית, וההדפסה מתבצעת רק אחרי שכל העצמים נוצרו, ולכן בכל השורות count = 4.

הקוד המלא
public class Test
{
    public static void main (String[] args)
    {
        One[] arr=new One[6];
        arr[0] = new Two();          // (1)
        arr[1] = new Three("Car");   // (2)
        arr[2] = new Three("Horse"); // (3)
        arr[3] = new Two("Small");   // (4)
        arr[4] = new Two("Tall");    // (5)
        arr[5] = new One();          // (6)
        for (int i = 0; i < arr.length; i++) {
            System.out.println (arr[i]);
        }
    }
}

סעיף ב

תשובה

אין שגיאה. הפלט: 4, 1 Fast / 4, 2 Car / 4, 3 Horse / 4, 15 Small / 4, 15 Tall / 4, 4

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

רעיון

•אין שגיאה. הפעולה הבונה Three(String s) קוראת עכשיו במובלע ל־One() – פעולה בונה ללא פרמטרים שקיימת ב־One. גם super.toString() (ב־C#: base.ToString()) קיימת ב־One, וב־C# ה־override של Three עדיין תקין, כי ToString של One היא override (וירטואלית).
•One[] arr עדיין יכול להכיל עצמי Three, כי Three יורשת מ־One.
•מה משתנה: לעצם Three אין עכשיו strTwo, ולכן המילה Fast לא מודפסת בו. One() עדיין נקראת פעמיים בשביל עצמי Three, ולכן count נשאר 4 וגם ערכי number לא משתנים.
שורהעצםnumberפלט
(1)new Two()14, 1 Fast
(2)new Three("Car")24, 2 Car
(3)new Three("Horse")34, 3 Horse
(4)new Two("Small")154, 15 Small
(5)new Two("Tall")154, 15 Tall
(6)new One()44, 4

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

4, 1 Fast
4, 2 Car
4, 3 Horse
4, 15 Small
4, 15 Tall
4, 4

שאלה 12 · A, B, C, D – העמסה, דריסה ופולימורפיזם (25 נקודות)

נוסח השאלה:

לשאלה זו שני נוסחים: בשפת Java בעמודים 22–23 ובשפת C# בעמודים 24–25.

לפותרים בשפת Java

נתונות המחלקות A , B , C , D :

Java
public class A {
    protected int i;
    public A (int i) { this.i = i; }
}
--------------------------------------------------------------------------------------------------------
public class B extends A {
    public B (int i) { super (i + 1); }
    public  boolean foo (Object myObject)  {
        System.out.println ("foo1");
        return ((myObject instanceof B) && (this.i == ((B)myObject).i));
    }
    public boolean foo (B myB, int num)  {
        System.out.println ("foo2");
        return (this.i +  myB.i)  <  num;
    }
}
--------------------------------------------------------------------------------------------------------
public class C extends B {
    public C (int i)  { super (i); }
    public boolean foo (int num)  {
        System.out.println ("foo3");
        return (this.i != num);
    }
}
--------------------------------------------------------------------------------------------------------
public class D extends B {
    public D (int i)  { super (i * 2); }
    public boolean foo (B myB, int num)    {
        System.out.println ("foo4");
        return super.foo (myB, 20);
    }
}
א.

סרטטו את תרשים ההייררכייה של המחלקות A , B , C , D . יש לסמן ירושה באמצעות החץ ◁——— .

ב.(1)

נתונה המחלקה Tester :

Java
public class Tester {
    public static void main (String[] args) {
        A a = new A (1);
        B b = new B (2);
        C c = new C (3);
        D d = new D (4);
        B bd = new D (5);
        A ac = new C (6);
        //***
    }
}

סרטטו את העצמים שנוצרו בפעולה main .

(2)

במקום המסומן ב־ * נוסף קטע הקוד התקין שלפניכם:

Java
System.out.println (c.foo(5));          //(1)
System.out.println (d.foo(a));          //(2)
System.out.println (bd.foo(b));         //(3)
System.out.println (bd.foo(b, 1));      //(4)
System.out.println (((C)ac).foo(c));    //(5)

כתבו את הפלט של הפעולה (כתבו את מספר השורה המשויך לכל פלט).

◂ פתרון מלא לשאלה 12

סעיף א

תשובה

B יורשת מ־A; C ו־D יורשות מ־B.

מה נדרש – תרשים ירושה של A, B, C, D.

רעיון – לפי הכותרות: B extends A (ב־C#: B : A), C extends B, D extends B. כלומר B יורשת מ־A, ו־C ו־D הן "אחיות" שיורשות שתיהן מ־B (ובעקיפין גם מ־A).

פתרון

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

סעיף ב(1)

תשובה

a→A(i=1), b→B(i=3), c→C(i=4), d→D(i=9), bd (מוצהר B)→D(i=11), ac (מוצהר A)→C(i=7)

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

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

•A(i) – מציבה i.
•B(i) – קוראת ל־A(i + 1).
•C(i) – קוראת ל־B(i), כלומר i + 1.
•D(i) – קוראת ל־B(i * 2), כלומר 2i + 1.
משתנהטיפוס מוצהרטיפוס העצם בפועלחישובi
aAA11
bBB2 + 13
cCC3 + 14
dDD4·2 + 19
bdBD5·2 + 111
acAC6 + 17

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

בדיקה – הדפסה של i לכל עצם נותנת את הערכים 1, 3, 4, 9, 11, 7, ב־Java וב־C#.

טעות נפוצה: לסרטט את העצם של bd מטיפוס B (הטיפוס המוצהר) – העצם עצמו נוצר ב־new D(5) ולכן הוא מטיפוס D, ו־i = 11 ולא 6.

סעיף ב(2)

תשובה

(1) foo3 true (2) foo1 false (3) foo1 false (4) foo4 foo2 true (5) foo1 false (ב־C#: Foo1…Foo4 ו־True/False)

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

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

1.בזמן הידור (העמסה): המהדר בוחר את החתימה לפי הטיפוס המוצהר של המשתנה ולפי הטיפוסים המוצהרים של הארגומנטים.
2.בזמן ריצה (דריסה): אם לחתימה שנבחרה יש גרסה דורסת בטיפוס בפועל של העצם – היא זו שמתבצעת.

הפעולות הקיימות: ב־B – foo(Object) ו־foo(B, int); ב־C נוספת foo(int); ב־D – דריסה של foo(B, int). ערכי i (מסעיף ב1): a=1, b=3, c=4, d=9, bd=11, ac=7.

שורהבחירת הפעולהביצועפלט
(1) c.foo(5)c מטיפוס C, ארגומנט int ← foo(int) של C4 != 5foo3 ואז true
(2) d.foo(a)ארגומנט אחד מטיפוס A – מתאימה רק foo(Object) (A אינו B)a אינו מופע של B ← false (בגלל && ההמרה (B)myObject לא מתבצעת)foo1 ואז false
(3) bd.foo(b)ארגומנט אחד ← foo(Object); D לא דורסת אותהb הוא B, אבל 11 == 3 לא מתקייםfoo1 ואז false
(4) bd.foo(b, 1)בהידור: foo(B, int) של B; בזמן ריצה העצם הוא D ← הגרסה הדורסת של DD מדפיסה foo4 וקוראת ל־super.foo(b, 20) (ה־1 לא בשימוש): 11 + 3 = 14 < 20foo4, foo2 ואז true
(5) ((C)ac).foo(c)ההמרה תקינה (העצם הוא C). הארגומנט c אינו int ולכן foo(int) לא מתאימה ← foo(Object)c הוא B, אבל 7 == 4 לא מתקייםfoo1 ואז false

פתרון – הפלט (Java):

(1) foo3
    true
(2) foo1
    false
(3) foo1
    false
(4) foo4
    foo2
    true
(5) foo1
    false

ב־C# הפלט זהה, פרט לכך שהשמות מודפסים באות גדולה (Foo1…Foo4, כפי שנכתב בקוד C#) והערכים הבוליאניים מודפסים True / False.
ב־C# הדריסה בשורה (4) מתרחשת כי Foo(B, int) מוגדרת ב־B כ־virtual וב־D כ־override; ב־Java כל פעולה ניתנת לדריסה בלי מילת מפתח.

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

טעות נפוצה: בשורה (3) לחשוב שהעצם מטיפוס D ולכן "תופעל הפעולה של D" – ל־D יש רק foo(B, int) עם שני פרמטרים, והקריאה עם ארגומנט אחד מתאימה רק ל־foo(Object). בשורה (4) – לשכוח שגם foo2 מודפס (בגלל super.foo).

טבלת התשובות
שאלהסעיףתשובה
1א

מוחקים מתחילת השרשרת כל עוד lst מכיל משחק במחיר pr (ו-count < n), ואז עם pos בודקים את pos.getNext(): אם מחירו pr – pos.setNext(pos.getNext().getNext()) ו-count++, אחרת מתקדמים. מחזירים count. יעילות O(L).

ב

כל עוד num > 0: מוצאים את המחיר המינימלי min, k = remove(num, min), sum += k*min, num -= k. מחזירים sum (בדוגמה: 142). יעילות O(num·L) ≤ O(L²).

2א(1)

mmm(q, 4) מחזירה false (הרצף הארוך ביותר של איברים שווים צמודים הוא 1, 1, 1 – באורך 3); התור חוזר למצבו המקורי.

א(2)

מחזירה true אם בתור יש רצף של לפחות z איברים שווים צמודים, אחרת false; התור נשאר ללא שינוי.

א(3)

O(n) – מעבר אחד על n איברי התור, O(1) לכל איבר.

ב(1)

what(q, 6) מחזירה 3 (n = 6, 5, 4 – false; n = 3 – true).

ב(2)

מחזירה את אורך הרצף הארוך ביותר של איברים שווים צמודים בתור (התור לא משתנה).

ב(3)

O(n²) במקרה הגרוע: עד n קריאות רקורסיביות, בכל אחת mmm ב־O(n).

3א

לדוגמה: שורש 1; בן שמאלי 2 (עלה), בן ימני 3; ל-3: שמאלי 4, ימני 5; ל-4: ימני 6; ל-5: שמאלי 7, ימני 8. (8 צמתים, 4 רמות, בכל מסלול ≤ קשת שמאלית אחת.)

ב

רקורסיה עם תקציב K: בן שמאלי – אם K == 0 מחזירים false, אחרת בודקים אותו עם K − 1; בן ימני – בודקים עם אותו K; עלה – true. יעילות O(n).

4א(1)

לא נכונה. דוגמה נגדית: משולש a–b–c וקודקוד מבודד d (4 קודקודים, 3 קשתות, ויש מעגל).

א(2)

לא נכונה. דוגמה נגדית: משולש a,b,c עם משקלים 1,1,1 וקשת c–d במשקל 10 – כל עץ פורש חייב להכיל את c–d.

א(3)

נכונה. בגרף "כוכב" (מרכז המחובר לכל שאר n−1 הקודקודים) מחיקת המרכז משאירה n−1 קודקודים מבודדים = n−1 רכיבי קשירות.

א(4)

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

א(5)

לא נכונה. דוגמה נגדית: s→a , a→b , b→c , s→c. DFS שהולך קודם ל־a מגיע ל־c במסלול באורך 3, אבל המרחק הוא 1.

א(6)

לא נכונה. דוגמה נגדית: קשתות s–v , v–a , v–b , a–s , b–s. ב־DFS מ־s (s→v→a, ואחר כך v→b) ל־v יש 2 בנים, אבל ב־DFS מ־v (v→a→s→b) ל־v יש בן אחד.

ב

(i) לא ייתכן – אין קשת a–b ב־G. (ii) לא ייתכן – אין קשת d–c ב־G. (iii) ייתכן – a→s→b, ומ־b אל d ואל c.

5א(1)

אלגוריתם דייקסטרה, O(V²) (במימוש עם ערימה: O((V+E)·log V)). המסלול: S→C→D→T, אורכו 34.

א(2)

הכפלה ב־x: כן, המסלול נשאר קצר ביותר (כל המסלולים מוכפלים ב־x). הגדלה ב־x: לא בהכרח (מסלול עם k קשתות גדל ב־k·x). למשל ב־G₁ עם x = 6: S→C→D→T = 52 אבל S→A→T = 51.

ב(1)

סריקה 1: a→b, a→c, a→d (סדר b, c, d) – עץ בגובה 1. סריקה 2: a→d→c, ואז a→b – עץ בגובה 2.

ב(2)

מספיק להוסיף קשת אחת, c→b. גבהים: 1 (a→b, a→c, a→d), 2 (a→c→b, a→d), 3 (a→d→c→b).

6א

למשל: קודקודים 1–6, קשתות 1–2 , 2–3 , 3–1 , 3–4 , 4–5 , 4–6. הורדת הקשת 1–2 נותנת עץ.

ב(1)

כן. מספר הקשתות הוא n.

ב(2)

כן. יש רכיב קשירות אחד – הגרף קשיר.

ג(1)

G הוא גרף־כמעט־עץ ⇔ G קשיר ויש בו בדיוק n קשתות. האלגוריתם: סופרים קשתות (עוצרים אם יש יותר מ־n); אם ≠ n – שקר; אחרת BFS מקודקוד כלשהו: אם הגיע לכל n הקודקודים – אמת, אחרת שקר.

ג(2)

O(n) (ובאופן כללי O(V+E), אבל בזכות העצירה המוקדמת E ≤ n).

7א(1)

L₁ – לא רגולרית; L₂ – רגולרית; L₃ – רגולרית (סופית). (וגם L₃ − L₁ רגולרית – סופית.)

א(2)

כן. L₁ ∩ L₃ ⊆ L₃ ולכן היא סופית – וכל שפה סופית רגולרית.

א(3)

לא. L₁ ∩ L̅₃ = { aⁿbᵐaⁿ | 2n+m ≥ 100 }. אילו הייתה רגולרית, אז L₁ = (L₁ ∩ L₃) ∪ (L₁ ∩ L̅₃) הייתה רגולרית (איחוד עם שפה סופית) – סתירה.

א(4)

כן. L₂ רגולרית, L̅₃ רגולרית (משלים של רגולרית), וחיתוך של רגולריות הוא רגולרי.

ב(1)

abbcc – לא שייכת; abcc – שייכת; bbc – לא שייכת; abc – שייכת; abbac – לא שייכת.

ב(2)

q2→q1: a ; q3→q4: b ; q4→q3: b ; q5→q6: b ; q6→q5: b ; q3→q10: c ; q6→q10: c ; q4→q8: c ; q7→q8: c ; q8→q9: c ; q9→q8: c ; q10→q10: c. מצבים מקבלים: q8, q10.

8א(1)

לא נכונה. R(R(L₁)·R(L₂)) = L₂·L₁. דוגמה: L₁ = {a}, L₂ = {b}: אגף שמאל {ba}, אגף ימין {ab}.

א(2)

נכונה – שרשור מתפלג מעל איחוד.

א(3)

לא נכונה. דוגמה: L₁ = {ab}, L₂ = {a}, L₃ = {b}: אגף שמאל {ab}, אגף ימין ∅·∅ = ∅.

ב

דוחפים X עבור ה־a הראשון ו־A עבור כל a נוסף; כל b שולף A; כל c שולף; ה־c ששולף את X עובר למצב המקבל f – בתנאי שנקראו לפחות 3 c (אם היו b) או לפחות 4 c (אם לא היו b). טבלת המעברים המלאה בפתרון.

9-

בודקים זוגיות במעבר אחד ימינה. אי־זוגי: ה־1 הראשון ← $, ו־$ בתא הריק הראשון ⇒ $1ⁿ⁻¹$. זוגי: בכל סבב ה־1 השמאלי ← x וה־1 הימני ← Y; כשאין יותר 1 – ה־x האחרון ← $, כל Y ← 1, ו־$ בתא הריק הראשון ⇒ $1ⁿᐟ²$.

10א

Bird יורשת מ־Animal (isFlying, zoo); Parrot יורשת מ־Bird (isTalking); Fish יורשת מ־Animal (waterType); Snake יורשת מ־Animal (length, isVenomous). התכונות color ו־weight נשארות רק ב־Animal.

ב

בכל פעולה בונה קוראים לפעולה הבונה של מחלקת הבסיס: Bird(color, weight, isFlying) → super(color, weight); Parrot(color, weight, isFlying, isTalking) → super(color, weight, isFlying); Fish(color, weight, waterType) → super(color, weight); Snake(color, weight, length, isVenomous) → super(color, weight).

ג(1)

דורסים toString רק ב־Bird ("I'm a bird! " + super.toString()), ב־Parrot ("I'm a parrot! My color is " + getColor() + "!") וב־Snake (קידומת לפי isVenomous + super.toString()); ב־Fish לא צריך.

ג(2)

לא תקינה (שגיאת הידור: ב־Animal אין zoo). תיקון: if (arr[i] instanceof Bird) ((Bird)arr[i]).zoo(); (ב־C#: is Bird / Zoo). הפלט עבור animals: Hello, Hello (שתי שורות).

11א

(1) new Two() (2) new Three("Car") (3) new Three("Horse") (4) new Two("Small") (5) new Two("Tall") (6) new One()

ב

אין שגיאה. הפלט: 4, 1 Fast / 4, 2 Car / 4, 3 Horse / 4, 15 Small / 4, 15 Tall / 4, 4

12א

B יורשת מ־A; C ו־D יורשות מ־B.

ב(1)

a→A(i=1), b→B(i=3), c→C(i=4), d→D(i=9), bd (מוצהר B)→D(i=11), ac (מוצהר A)→C(i=7)

ב(2)

(1) foo3 true (2) foo1 false (3) foo1 false (4) foo4 foo2 true (5) foo1 false (ב־C#: Foo1…Foo4 ו־True/False)

כל האתר במבט אחד

קיצורי דרך לכל הכלים, הבגרויות והקורסים

GuyAI הוא המורה הפרטי המתקדם בישראל, המבוסס על מודלי הבינה המלאכותית החזקים בעולם בשילוב הידע הפדגוגי של GOOL. המערכת מספקת פתרונות לכל המקצועות ולכל הרמות - מיסודי ועד אקדמיה, וממתמטיקה ועד היסטוריה.