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

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

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

נתונה המחלקה Reading – מדידה של תחנה מטאורולוגית, ולה שתי תכונות:

•station – מספר התחנה, מטיפוס שלם

•temp – הטמפרטורה שנמדדה (במעלות), מטיפוס שלם

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

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

הערות:

•כל תחנה מודדת כמה פעמים ביום, ולכן אותה תחנה יכולה להופיע בתור כמה פעמים.

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

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

למשל, בתור שלפניכם (משמאל – ראש התור) פער הטמפרטורות של תחנה 12 הוא 25 − 18 = 7, של תחנה 30 הוא 9 − (−2) = 11 ושל תחנה 7 הוא 0.

station	12	30	12	7	30	12	7
temp	18	9	25	14	−2	21	14

א.(1)

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

Java – public static Queue<Reading> tempGaps (Queue<Reading> qRead)

C# – public static Queue<Reading> TempGaps (Queue<Reading> qRead)

הפעולה מקבלת תור מדידות – qRead, ומחזירה תור חדש של עצמים מטיפוס Reading, ובו כל תחנה מופיעה פעם אחת בלבד: בתכונה station – מספר התחנה, ובתכונה temp – פער הטמפרטורות של התחנה.

בעבור התור שבדוגמה, הפעולה תחזיר תור ובו שלושה עצמים: (12, 7), (30, 11), (7, 0).

הערות:

•אין חשיבות לסדר העצמים בתור המוחזר.

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

•אפשר לשנות את התור שהתקבל.

(2)

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

ב.(1)

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

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

Java – public static Queue<Integer> unstable (Queue<Reading> qRead)

C# – public static Queue<int> Unstable (Queue<Reading> qRead)

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

בעבור התור שבדוגמה: הפערים הם 7, 11, 0, הממוצע הוא 6, ולכן הפעולה תחזיר תור ובו 12 ו־30.

אפשר להשתמש בפעולה שכתבתם בסעיף א.

הערות:

•אפשר לשנות את התור שהתקבל.

(2)

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

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

סעיף א(1)

תשובה

בכל סבב מוציאים מדידה ראשונה, עוברים על כל שאר המדידות: של אותה תחנה – מעדכנים max/min, של תחנה אחרת – לתור עזר שמחליף את qRead; מכניסים לתוצאה new Reading(station, max − min).

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

רעיון: כל עוד התור אינו ריק:

1.מוציאים את המדידה הראשונה first – זו תחנה שעוד לא טופלה. מאתחלים max ו־min בטמפרטורה שלה.

2.מוציאים את כל שאר המדידות אחת אחת: מדידה של אותה תחנה – מעדכנים את max ואת min (ולא שומרים אותה); מדידה של תחנה אחרת – מכניסים לתור עזר temp.

3.בסוף המעבר temp מכיל בדיוק את המדידות של התחנות שעוד לא טופלו, ולכן ממשיכים איתו: q = temp.

4.מכניסים לתור התוצאה עצם חדש עם מספר התחנה ו־max − min.

מותר לשנות את התור שהתקבל (בסוף הוא מתרוקן), ומשתמשים רק בתורים.

פתרון:

public static Queue<Reading> tempGaps(Queue<Reading> q) {
    Queue<Reading> result = new Queue<Reading>();
    while (!q.isEmpty()) {
        Reading first = q.remove();             // מדידה של תחנה שעוד לא טופלה
        int max = first.getTemp();
        int min = first.getTemp();
        Queue<Reading> temp = new Queue<Reading>();
        while (!q.isEmpty()) {                  // מעבר על שאר המדידות
            Reading r = q.remove();
            if (r.getStation() == first.getStation()) {
                if (r.getTemp() > max)
                    max = r.getTemp();
                if (r.getTemp() < min)
                    min = r.getTemp();
            }
            else
                temp.insert(r);                 // תחנה אחרת – לסבב הבא
        }
        q = temp;
        result.insert(new Reading(first.getStation(), max - min));
    }
    return result;
}

בדיקה: על התור מהדוגמה: (12,18), (30,9), (12,25), (7,14), (30,−2), (12,21), (7,14).

סבב	first	max / min	temp בסוף הסבב	נוסף לתוצאה
1	(12,18)	25 / 18	(30,9), (7,14), (30,−2), (7,14)	(12,7)
2	(30,9)	9 / −2	(7,14), (7,14)	(30,11)
3	(7,14)	14 / 14	ריק	(7,0)

הפלט בפועל: [(12,7), (30,11), (7,0)]. נבדקו גם תור ריק, מדידה אחת, כל המדידות מאותה תחנה וכל התחנות שונות.

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

הקוד המלא

public static Queue<Reading> tempGaps(Queue<Reading> q) {
    Queue<Reading> result = new Queue<Reading>();
    while (!q.isEmpty()) {
        Reading first = q.remove();             // מדידה של תחנה שעוד לא טופלה
        int max = first.getTemp();
        int min = first.getTemp();
        Queue<Reading> temp = new Queue<Reading>();
        while (!q.isEmpty()) {                  // מעבר על שאר המדידות
            Reading r = q.remove();
            if (r.getStation() == first.getStation()) {
                if (r.getTemp() > max)
                    max = r.getTemp();
                if (r.getTemp() < min)
                    min = r.getTemp();
            }
            else
                temp.insert(r);                 // תחנה אחרת – לסבב הבא
        }
        q = temp;
        result.insert(new Reading(first.getStation(), max - min));
    }
    return result;
}

סעיף א(2)

תשובה

O(n²) – לכל תחנה עוברים על כל המדידות שנותרו בתור: (n−1)+(n−2)+…+1 במקרה הגרוע.

מה נדרש: סיבוכיות זמן הריצה של tempGaps כתלות ב־n – מספר המדידות בתור.

רעיון: כל פעולה על תור (insert, remove, isEmpty) היא O(1), וכך גם ההשוואות והעדכונים של max ו־min. סופרים כמה פעמים מתבצעת הלולאה הפנימית.

פתרון:

•כל סבב של הלולאה החיצונית מוציא מדידה אחת ועובר על כל המדידות שנותרו בתור.

•המקרה הגרוע: כל המדידות מתחנות שונות. אז בכל סבב יוצאת מהתור מדידה אחת בלבד, והלולאה הפנימית עוברת על n−1, n−2, …, 1, 0 מדידות.

•סך הכול (n−1) + (n−2) + … + 1 = n(n−1)/2, כלומר O(n²).

(באופן כללי, אם יש k תחנות שונות יש k סבבים, וכל סבב עובר על לכל היותר n מדידות – O(k·n), ובמקרה הגרוע k = n.)

בדיקה: בדוגמה (n = 7, שלוש תחנות) היו 3 סבבים, והלולאה הפנימית עברה על 6, 4 ו־1 מדידות.

סעיף ב(1)

תשובה

מחשבים gaps = tempGaps(qRead); מעבר ראשון: סכום הפערים ומספר התחנות (תוך העברה לתור עזר); מעבר שני על תור העזר: מכניסים לתוצאה כל תחנה שהפער שלה > sum / count.

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

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

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

2.מחשבים ממוצע ממשי: (double) sum / count.

3.מעבר שני על temp: תחנה שהפער שלה גדול מהממוצע – נכנסת לתור התוצאה.

פתרון: (משתמשים בפעולה tempGaps / TempGaps מסעיף א)

public static Queue<Integer> unstable(Queue<Reading> q) {
    Queue<Reading> gaps = tempGaps(q);          // כל תחנה פעם אחת עם הפער שלה
    Queue<Reading> temp = new Queue<Reading>();
    int sum = 0;
    int count = 0;
    while (!gaps.isEmpty()) {                   // מעבר ראשון: סכום ומספר תחנות
        Reading r = gaps.remove();
        sum = sum + r.getTemp();
        count++;
        temp.insert(r);
    }
    double avg = (double) sum / count;
    Queue<Integer> result = new Queue<Integer>();
    while (!temp.isEmpty()) {                   // מעבר שני: השוואה לממוצע
        Reading r = temp.remove();
        if (r.getTemp() > avg)
            result.insert(r.getStation());
    }
    return result;
}

בדיקה: בדוגמה tempGaps מחזירה (12,7), (30,11), (7,0). sum = 18, count = 3, הממוצע 6.0. 7 > 6 ← 12 נכנס; 11 > 6 ← 30 נכנס; 0 > 6 לא. הפלט בפועל: [12, 30]. נבדקו גם: כל הפערים שווים ← תור ריק (אף פער אינו גדול מהממוצע); פערים 4, 2, 0 (ממוצע 2) ← רק התחנה עם 4; תור ריק ← תור ריק (מקרה שהשאלה אינה דורשת; החלוקה 0.0/0 נותנת NaN וההשוואה false).

טעות נפוצה: לחשב sum / count בחלוקת שלמים – למשל פערים 3 ו־4: הממוצע 3.5, אבל בחלוקת שלמים מתקבל 3, והתחנה עם פער 3 נכנסת בטעות. טעות נוספת: לעבור על התור פעם אחת בלבד – אחרי חישוב הסכום התור ריק אם לא שמרו את העצמים בתור עזר.

הקוד המלא

public static Queue<Integer> unstable(Queue<Reading> q) {
    Queue<Reading> gaps = tempGaps(q);          // כל תחנה פעם אחת עם הפער שלה
    Queue<Reading> temp = new Queue<Reading>();
    int sum = 0;
    int count = 0;
    while (!gaps.isEmpty()) {                   // מעבר ראשון: סכום ומספר תחנות
        Reading r = gaps.remove();
        sum = sum + r.getTemp();
        count++;
        temp.insert(r);
    }
    double avg = (double) sum / count;
    Queue<Integer> result = new Queue<Integer>();
    while (!temp.isEmpty()) {                   // מעבר שני: השוואה לממוצע
        Reading r = temp.remove();
        if (r.getTemp() > avg)
            result.insert(r.getStation());
    }
    return result;
}

סעיף ב(2)

תשובה

O(n²) – בגלל הקריאה ל־tempGaps; שני המעברים הנוספים O(n).

מה נדרש: סיבוכיות זמן הריצה של unstable כתלות ב־n – מספר המדידות בתור.

פתרון:

•הקריאה ל־tempGaps: O(n²) (סעיף א(2)).

•המעבר הראשון על תור הפערים (k ≤ n תחנות), כל איבר – remove ו־insert ב־O(1): O(n).

•המעבר השני על temp: O(n).

סך הכול O(n²) + O(n) + O(n) = O(n²) – החלק היקר הוא חישוב הפערים.

בדיקה: במקרה הגרוע (כל המדידות מתחנות שונות) tempGaps לבדה מבצעת n(n−1)/2 מעברים בלולאה הפנימית, ושני המעברים הנוספים מוסיפים רק כ־2n פעולות.

שאלה 2 · מסגרות בשרשרת חוליות (25 נקודות)

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

לדוגמה: בסדרת המספרים 4, 8, 2, 6, 8, 5, 4, 3 יש שתי מסגרות:

i. 4, 8, 2, 6, 8, 5, 4 – משקלה 8 + 2 + 6 + 8 + 5 = 29
ii. 8, 2, 6, 8 – משקלה 2 + 6 = 8

נתונה שרשרת חוליות lst מטיפוס שלם, המכילה מספרים חיוביים. כל מספר מופיע בשרשרת פעם אחת או פעמיים (לא יותר).

א.

כתבו פעולה ששמה frameWeight בשפת Java או FrameWeight בשפת C# המקבלת את השרשרת lst ומספר שלם num המופיע בשרשרת.
הפעולה תחזיר את משקל המסגרת שהמספר num מתחיל ומסיים.
אם num מופיע בשרשרת פעם אחת בלבד, הפעולה תחזיר −1 .

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

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

עבור num = 6 הפעולה תחזיר 28 (המסגרת: 6, 2, 9, 4, 2, 11, 6 , ומשקלה 2 + 9 + 4 + 2 + 11 = 28).
עבור num = 2 הפעולה תחזיר 13 (המסגרת: 2, 9, 4, 2).
עבור num = 11 הפעולה תחזיר −1 (משום ש־ 11 מופיע בשרשרת פעם אחת בלבד).

ב.

כתבו פעולה ששמה heaviest בשפת Java או Heaviest בשפת C# המקבלת את השרשרת lst . הפעולה תחזיר את המספר שמתחיל ומסיים את המסגרת הכבדה ביותר (המסגרת שמשקלה הגדול ביותר).
אם יש כמה מסגרות שמשקלן הגדול ביותר, הפעולה תחזיר מביניהן את המספר שההופעה הראשונה שלו קודמת בשרשרת. אם אין בשרשרת שום מסגרת, הפעולה תחזיר −1 .
אפשר להשתמש בפעולה שכתבתם בסעיף א.

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

לדוגמה: עבור השרשרת lst שבדוגמה לעיל הפעולה תחזיר 6 .
הסבר: בשרשרת שלוש מסגרות: של 6 (משקל 28), של 2 (משקל 13) ושל 9 (משקל 26). המסגרת של 6 היא הכבדה ביותר.

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

סעיף א

תשובה

מתקדמים בהפניה עזר p עד ההופעה הראשונה של num, ועוברים לחוליה שאחריה. מכאן מסכמים את הערכים עד שמגיעים שוב ל־num או לסוף השרשרת. אם הגענו לסוף (p == null) – מחזירים −1, אחרת מחזירים את הסכום.

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

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

1.מתקדמים בהפניה עזר p (lst עצמה לא זזה) עד החוליה הראשונה שערכה num, ועוברים לחוליה שאחריה.

2.מסכמים ערכים ומתקדמים כל עוד p != null והערך שונה מ־num.

3.אם הלולאה נעצרה כי p == null, לא נמצאה הופעה שנייה, ומחזירים −1. אחרת הלולאה נעצרה בהופעה השנייה של num, ומחזירים את הסכום.

שימו לב לסדר התנאים p != null && ...: אם p הוא null, החלק השני לא נבדק, ולכן אין גישה ל־null.

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

יעילות: מעבר אחד על השרשרת – O(n).

בדיקה (השרשרת 6, 2, 9, 4, 2, 11, 6, 3, 9, 8):

num	המספרים שבין שתי ההופעות	תוצאה
6	2, 9, 4, 2, 11	28
2	9, 4	13
9	4, 2, 11, 6, 3	26
11	אין הופעה שנייה	−1
8 (האחרון)	אין הופעה שנייה	−1

מתקבלים 28, 13, 26, −1, −1, והשרשרת לא משתנה. גם בסדרה שבפתיח התקבל משקל 8 למסגרת של 8.

הקוד המלא

public static int frameWeight(Node<Integer> lst, int num)
{
    Node<Integer> p = lst;
    while (p.getValue() != num)          // num מופיע בשרשרת – מגיעים להופעה הראשונה שלו
        p = p.getNext();
    p = p.getNext();
    int sum = 0;
    while (p != null && p.getValue() != num)
    {
        sum += p.getValue();             // מספר שנמצא בין שני הקצוות
        p = p.getNext();
    }
    if (p == null)                       // אין הופעה שנייה של num
        return -1;
    return sum;
}

סעיף ב

תשובה

max = −1, best = −1. לכל ערך v בשרשרת מחשבים w = frameWeight(lst, v). אם w > max (גדול ממש) מעדכנים max = w ו־best = v. בסוף מחזירים את best.

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

רעיון: כל מסגרת מתחילה באחד המספרים שבשרשרת. לכן עוברים על כל הערכים v בשרשרת, מחשבים frameWeight(lst, v) מסעיף א, ושומרים את המשקל הגדול ביותר (max) ואת המספר שלו (best).

•אם ל־v אין הופעה שנייה, frameWeight מחזירה −1, וזה לא משנה את המקסימום.

•מאתחלים max = −1 (ולא 0): מסגרת עם קצוות צמודים היא מסגרת חוקית שמשקלה 0, וצריך שתיבחר אם אין כבדה ממנה. אם אין אף מסגרת, best נשאר −1 – כמו שנדרש.

•מעדכנים רק כאשר w > max (גדול ממש). המעבר על השרשרת מגיע לכל מספר לראשונה בהופעה הראשונה שלו, ולכן בשוויון נשאר המספר שההופעה הראשונה שלו קודמת. (כל מסגרת נבדקת פעמיים, פעם מכל קצה, וזה לא משנה את התוצאה.)

פתרון: הקוד המלא – בלשונית Java/C#. frameWeight רק קוראת את השרשרת, ולכן אפשר לקרוא לה על אותה lst שוב ושוב בזמן המעבר.

יעילות: לכל אחת מ־n החוליות יש קריאה ל־frameWeight שעולה O(n), ולכן הפעולה היא O(n²).

בדיקה: בשרשרת שבדוגמה המשקלים הם 6 ⇒ 28, 2 ⇒ 13, 9 ⇒ 26, ולשאר המספרים −1. התקבל 6. מקרים נוספים: הסדרה שבפתיח 4, 8, 2, 6, 8, 5, 4, 3 ⇒ 4; השרשרת 1, 2, 3 (בלי מסגרות) ⇒ −1; השרשרת 1, 5, 5, 3 ⇒ 5 (מסגרת במשקל 0); השרשרת 7, 4, 7, 3, 1, 3 (שתי מסגרות במשקל 4) ⇒ 7.

טעות נפוצה: לאתחל את max ל־0 ולהשוות ב־>; אז מסגרת שמשקלה 0 לא נמצאת, והפעולה מחזירה −1 במקום המספר שלה.

הקוד המלא

public static int heaviest(Node<Integer> lst)
{
    int max = -1;
    int best = -1;
    Node<Integer> p = lst;
    while (p != null)
    {
        int w = frameWeight(lst, p.getValue());
        if (w > max)                     // רק גדול ממש – בשוויון נשאר המספר שהופיע קודם
        {
            max = w;
            best = p.getValue();
        }
        p = p.getNext();
    }
    return best;
}

שאלה 3 · פיצול צומת לחזקות של 2 (25 נקודות)

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

"חזקה של 2" היא מספר מהצורה 2 בחזקת k, כאשר k ≥ 0 שלם, כלומר אחד מהמספרים 1, 2, 4, 8, 16, 32, ... (גם המספר 1 הוא חזקה של 2).
לפניכם הפעולה החיצונית isPowerOfTwo/IsPowerOfTwo. אפשר להשתמש בפעולה בלי לממש אותה.

כותרת הפעולה	תיאור הפעולה
Java – `public static boolean isPowerOfTwo (int num)`	הפעולה מחזירה true אם הערך num שהתקבל (num > 0) הוא חזקה של 2,
C# – `public static bool IsPowerOfTwo (int num)`	אחרת היא מחזירה false.

א.

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

Java – public static boolean splitPower (BinNode<Integer> tr)

C# – public static bool SplitPower (BinNode<int> tr)

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

דוגמאות: בתום הפעולה ייראו הצמתים כך (עבור הערכים 100 , 6 , 8):

(עבור 100: החזקה הגדולה ביותר של 2 שקטנה מ־ 100 היא 64, ו־ 100 − 64 = 36. הערך 8 הוא חזקה של 2, ולכן לא נוספו לו בנים והפעולה החזירה false.)

ב.(1)

נתונה הפעולה build/Build שלפניכם, המקבלת צומת ללא בנים שערכו גדול מ־ 0.

בשפת :

public static void build(BinNode<Integer> tr) {
    if (splitPower(tr)) {
        build(tr.getLeft());
        build(tr.getRight());
    }
}

(1) סרטטו את העץ כפי שהוא ייראה בתום הפעולה build/Build עבור צומת ללא בנים – tr שערכו 92. יש להראות מעקב.

(2)

הסבירו מה מבצעת הפעולה build/Build.

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

סעיף א

תשובה

אם isPowerOfTwo(val) – מחזירים false. אחרת מחשבים p = 1 ומכפילים ב־ 2 כל עוד p·2 < val, מוסיפים בן שמאלי p ובן ימני val − p, ומחזירים true.

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

רעיון:

1.אם isPowerOfTwo(val) – מחזירים false ולא משנים דבר.

2.אחרת מחפשים את החזקה p: מתחילים מ־ p = 1 ומכפילים ב־ 2 כל עוד p·2 < val. בסוף הלולאה p היא החזקה הגדולה ביותר של 2 שקטנה מ־ val.

3.יוצרים בן שמאלי חדש עם הערך p ובן ימני חדש עם הערך val − p, ומחזירים true.

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

בדיקה: עבור 100: p עובר 1, 2, 4, 8, 16, 32, 64 (כי 128 כבר אינו קטן מ־ 100) ← בנים 64 ו־ 36, מוחזר true. עבור 6: p = 4 ← בנים 4 ו־ 2. עבור 8: חזקה של 2 ← false, בלי בנים. מתקבלים בדיוק העצים שבדוגמאות, וגם 3 ← בנים 2 ו־ 1, ו־ 1 ← false.

טעות נפוצה: לכתוב את תנאי הלולאה p < val (במקום p·2 < val). אז הלולאה מסתיימת כש־ p כבר גדולה מ־ val, והבן הימני יקבל ערך שלילי.

הקוד המלא

public static boolean splitPower(BinNode<Integer> tr) {
    int val = tr.getValue();
    if (isPowerOfTwo(val))
        return false;
    int p = 1;
    while (p * 2 < val)                 // החזקה הגדולה ביותר של 2 שקטנה מ־val
        p = p * 2;
    tr.setLeft(new BinNode<Integer>(p));
    tr.setRight(new BinNode<Integer>(val - p));
    return true;
}

סעיף ב(1)

תשובה

92 ← בנים 64 (עלה) ו־ 28; 28 ← בנים 16 (עלה) ו־ 12; 12 ← בנים 8 ו־ 4 (עלים). העלים: 64, 16, 8, 4.

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

רעיון: build מפעילה את splitPower על הצומת. אם נוספו בנים (true) – היא ממשיכה ברקורסיה על הבן השמאלי ואחר כך על הבן הימני. אם הוחזר false – הצומת נשאר עלה והקריאה מסתיימת.

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

קריאה	splitPower מחזירה	בנים שנוספו	המשך
build(92)	true	64 , 28	build(64), build(28)
build(64)	false (64 חזקה של 2)	–	עוצרים
build(28)	true	16 , 12	build(16), build(12)
build(16)	false	–	עוצרים
build(12)	true	8 , 4	build(8), build(4)
build(8)	false	–	עוצרים
build(4)	false	–	עוצרים

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

בדיקה: מתקבל העץ 92(64, 28(16, 12(8, 4))), והעלים הם 64, 16, 8, 4 – וסכומם 92.

סעיף ב(2)

תשובה

הפעולה מפרקת את ערך הצומת לחזקות של 2: היא בונה עץ שבו כל צומת פנימי הוא סכום שני בניו, והעלים הם החזקות של 2 (השונות) שסכומן הוא הערך – כלומר הייצוג הבינרי שלו; מספר העלים = מספר הספרות 1 בייצוג הבינרי.

מה נדרש: להסביר מה מבצעת build.

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

פתרון (הסבר): הפעולה בונה מתחת לצומת tr עץ שבו:

•ערך כל צומת פנימי שווה לסכום ערכי שני בניו, ולכן סכום ערכי כל העלים שווה לערך המקורי של tr.

•כל העלים הם חזקות של 2, שונות זו מזו, מהגדולה לקטנה (משמאל לימין). אלה בדיוק החזקות של 2 שמרכיבות את הערך – הייצוג הבינרי שלו. למשל 92 = 64 + 16 + 8 + 4, כלומר 1011100 בבסיס 2.

•כל בן שמאלי הוא עלה (הוא חזקה של 2), והפיצול ממשיך רק בבן הימני, ולכן העץ הוא "שרשרת" שיורדת ימינה.

•מספר העלים שווה למספר הספרות 1 בייצוג הבינרי של הערך. אם הערך הוא חזקה של 2 – העץ נשאר צומת יחיד.

בדיקה: סכום העלים שווה לערך, כל העלים חזקות של 2, ומספר העלים שווה למספר הספרות 1 בייצוג הבינרי.

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

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

שאלה 4 · תכונות של גרף ומיון טופולוגי של קורסים (25 נקודות)

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

א. להלן גרף G = (V, E) שאינו מכוון:

א.(1)

האם הגרף קשיר? נמקו.

(2)

האם הגרף דו־צדדי? נמקו.

(3)

האם הגרף מלא (שלם)? נמקו.

(4)

האם הגרף הוא עץ? נמקו.

ב.(1)

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

(1) סרטטו את רשימת הסמיכויות המייצגת את דרישות הקדם בין הקורסים.

(2)

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

•קורס E – ביטול הדרישה ש־ E יילמד לפני B

•קורס H – ביטול הדרישה ש־ H יילמד לפני F

•קורס A – ביטול הדרישה ש־ A יילמד לפני C

(2) סרטטו את רשימת הסמיכויות המתקבלת לאחר הביטולים המצוינים לעיל.

(3) I.

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

(3) II.

הפעילו את האלגוריתם שכתבתם עליו בסעיף (3)I על הגרף שהתקבל לאחר הביטולים (סעיף (2)), וכתבו סדר לימוד של הקורסים שמצאתם.
יש לבצע מעקב מפורט בכל שלב בהתאם לאלגוריתם שהפעלתם.

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

סעיף א(1)

תשובה

כן. יש מסלול בין כל שני קודקודים: כל הקודקודים מחוברים אל c (a – c , b – c , c – d – e – f), ולכן אפשר לעבור מכל קודקוד לכל קודקוד דרך c .

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

רעיון: מספיק להראות שמקודקוד אחד (למשל a) אפשר להגיע לכל שאר הקודקודים: אז בין כל שני קודקודים x , y יש מסלול x ⇝ a ⇝ y (הגרף אינו מכוון).

פתרון: מ־ a : אל b (קשת a – b), אל c (קשת a – c), אל d (a – c – d), אל e (a – c – d – e), אל f (a – c – d – e – f). כל 6 הקודקודים ישיגים מ־ a , ולכן הגרף קשיר.

בדיקה: סריקת BFS מ־ a מגלה את כל ששת הקודקודים.

סעיף א(2)

תשובה

לא. יש בגרף מעגל באורך אי־זוגי (המשולש a – b – c – a , באורך 3), ובגרף דו־צדדי אין מעגל באורך אי־זוגי.

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

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

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

בדיקה: אף אחת מ־2⁶ = 64 החלוקות של הקודקודים לשתי קבוצות אינה מתאימה.

סעיף א(3)

תשובה

לא. בגרף מלא יש קשת בין כל שני קודקודים, אבל כאן, למשל, אין קשת בין a ל־ d . (בגרף מלא עם 6 קודקודים יש 6·5/2 = 15 קשתות, וכאן יש רק 6.)

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

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

פתרון: אין קשת בין a ובין d (וגם לא בין a ל־ e , בין b ל־ f ועוד). לכן הגרף אינו מלא. דרך נוספת: בגרף מלא עם n = 6 קודקודים יש n(n − 1)/2 = 15 קשתות, ובגרף הנתון יש 6 קשתות בלבד.

בדיקה: ספירת הקשתות: 6 ≠ 15.

סעיף א(4)

תשובה

לא. עץ הוא גרף קשיר ללא מעגלים, ובגרף יש מעגל a – b – c – a . (גם: בעץ עם 6 קודקודים יש 5 קשתות, וכאן יש 6.)

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

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

פתרון: יש בגרף המעגל a – b – c – a , ולכן הגרף אינו עץ. בדיקה נוספת: בעץ עם n קודקודים יש בדיוק n − 1 קשתות; כאן n = 6 ויש 6 קשתות (ולא 5). אם נוריד קשת אחת מן המשולש (למשל b – c) נקבל עץ.

בדיקה: קשיר = כן, מספר קשתות = 6 ≠ 5 ⇒ לא עץ.

סעיף ב(1)

תשובה

A: B, C | B: D | C: D, F | D: E, G | E: B, H | F: G | G: H | H: F

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

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

פתרון (השכנים בכל רשימה לפי סדר אלפביתי):

קורס	הקורסים שהוא דרישת קדם להם (שכנים)
A	B → C
B	D
C	D → F
D	E → G
E	B → H
F	G
G	H
H	F

בדיקה: בגרף 12 חצים, ובטבלה 2 + 1 + 2 + 2 + 2 + 1 + 1 + 1 = 12 איברים.

טעות נפוצה: לרשום כל קשת בשתי הרשימות (כמו בגרף לא מכוון), למשל את B גם ברשימה של A וגם את A ברשימה של B.

סעיף ב(2)

תשובה

A: B | B: D | C: D, F | D: E, G | E: H | F: G | G: H | H: (ריקה)

מה נדרש: לעדכן את רשימת הסמיכויות מסעיף (1) אחרי מחיקת שלוש קשתות.

רעיון: קשת X → Y נמחקת מהרשימה של X בלבד. הביטולים: E → B , H → F , A → C .

פתרון:

קורס	הקורסים שהוא דרישת קדם להם (שכנים)
A	B
B	D
C	D → F
D	E → G
E	H
F	G
G	H
H	–

בדיקה: נשארו 12 − 3 = 9 קשתות, ובטבלה 1 + 1 + 2 + 2 + 1 + 1 + 1 + 0 = 9 איברים. הרשימה של H ריקה.

סעיף ב(3) I

תשובה

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

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

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

פתרון – מיון טופולוגי לפי דרגות כניסה:

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

2.מכניסים לתור את כל הקורסים שדרגת הכניסה שלהם 0.

3.כל עוד התור אינו ריק: מוציאים קורס u , מוסיפים אותו לסוף הסדר, ומקטינים ב־1 את דרגת הכניסה של כל קורס ברשימת הסמיכויות של u ; קורס שדרגתו הגיעה ל־0 נכנס לתור.

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

זמן הריצה O(|V| + |E|). (אפשר גם להריץ DFS ולסדר את הקודקודים לפי זמני הסיום מהגדול לקטן; קשת אחורה ב־DFS מעידה על מעגל.)

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

סעיף ב(3) II

תשובה

A , C , B , F , D , E , G , H (סדר לפי דרגות כניסה ותור, כשבכל שלב נכנסים לתור קורסים חדשים בסדר אלפביתי). כל סדר אחר שמקיים את כל דרישות הקדם נכון גם הוא.

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

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

פתרון – מעקב (בעמודה "דרגות כניסה שהוקטנו" רשומה דרגת הכניסה החדשה של כל שכן):

צעד	הוצא מהתור	דרגות כניסה שהוקטנו (ערך חדש)	נכנסו לתור	התור אחרי הצעד	הסדר עד כה
0	–	דרגות כניסה התחלתיות: A:0, B:1, C:0, D:2, E:1, F:1, G:2, H:2	A, C	[A, C]	–
1	A	B:0	B	[C, B]	A
2	C	D:1, F:0	F	[B, F]	A, C
3	B	D:0	D	[F, D]	A, C, B
4	F	G:1	–	[D]	A, C, B, F
5	D	E:0, G:0	E, G	[E, G]	A, C, B, F, D
6	E	H:1	–	[G]	A, C, B, F, D, E
7	G	H:0	H	[H]	A, C, B, F, D, E, G
8	H	–	–	[]	A, C, B, F, D, E, G, H

כל 8 הקורסים נכנסו לסדר, ולכן אין מעגל, וסדר הלימוד הוא:
A , C , B , F , D , E , G , H

בדיקה: עוברים על כל 9 הקשתות ומוודאים שהמקור לפני היעד: A→B ✓ , B→D ✓ , C→D ✓ , C→F ✓ , D→E ✓ , D→G ✓ , E→H ✓ , F→G ✓ , G→H ✓. הסדר אינו יחיד (יש 21 סדרים נכונים). למשל DFS לפי סדר אלפביתי, עם סידור לפי זמני סיום מהגדול לקטן, נותן C , F , A , B , D , G , E , H – גם הוא נכון.

טעות נפוצה: להוציא קורס לסדר לפני שדרגת הכניסה שלו ירדה ל־0 (למשל D מיד אחרי B, לפני שגם C נלמד).

שאלה 5 · טענות על גרפים – נכון / לא נכון (25 נקודות)

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

א.

בגרף G לא מכוון וקשיר הריצו BFS מקודקוד s . לכל קודקוד v , d[v] הוא מספר הקשתות במסלול הקצר ביותר מ־ s אל v שה־BFS מצא.
לכל קשת (u, v) בגרף מתקיים: ההפרש בין d[u] ובין d[v] הוא לכל היותר 1 .

ב.

בגרף G ממושקל, לא מכוון וקשיר, שבו כל משקלי הקשתות שונים זה מזה, הקשת שמשקלה הגדול ביותר אינה שייכת לאף עץ פורש מינימלי של הגרף.

ג.

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

ד.

נתון גרף G ממושקל ולא מכוון שבו כל המשקלים חיוביים, ונתון בו המסלול הקל ביותר מקודקוד a אל קודקוד b .
אם נוסיף אותו מספר קבוע c > 0 למשקל של כל אחת מהקשתות בגרף, אותו מסלול יישאר בהכרח המסלול הקל ביותר מ־ a אל b .

ה.

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

ו.

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

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

סעיף א

תשובה

נכונה. אם (u, v) קשת, אז אפשר להגיע ל־v דרך u: d[v] ≤ d[u] + 1, ובאותו אופן d[u] ≤ d[v] + 1. לכן |d[u] − d[v]| ≤ 1.

מה נדרש: להראות שבין שני קצות של קשת, מרחקי ה־BFS שונים לכל היותר ב־1.

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

פתרון: הטענה נכונה. תהי (u, v) קשת בגרף. ניקח מסלול קצר ביותר מ־ s אל u (באורך d[u]) ונוסיף לו את הקשת (u, v): קיבלנו מסלול מ־ s אל v באורך d[u] + 1 . המרחק הקצר ביותר אל v אינו גדול מאורך של מסלול כלשהו אליו, ולכן d[v] ≤ d[u] + 1 . הגרף לא מכוון, ולכן אפשר לעבור בקשת גם מ־ v אל u , ובאותו אופן d[u] ≤ d[v] + 1 . משני האי־שוויונים: d[v] − d[u] ≤ 1 וגם d[u] − d[v] ≤ 1 , כלומר |d[u] − d[v]| ≤ 1 .

בדיקה: בכל סריקת BFS בגרף קשיר, בכל קשת ההפרש בין המרחקים של קצותיה הוא 0 או 1.

טעות נפוצה: לחשוב שההפרש תמיד בדיוק 1 – בקשת בין שני קודקודים באותה "שכבה" (למשל בצלע של משולש שמול s ) ההפרש הוא 0.

סעיף ב

תשובה

לא נכונה. דוגמה נגדית: הקשתות a–b (1), b–c (2), a–c (3), c–d (9). הקשת c–d (הכבדה ביותר) היא הקשת היחידה שמגיעה ל־d, ולכן היא שייכת לכל עץ פורש – גם לעץ הפורש המינימלי {a–b, b–c, c–d} במשקל 12.

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

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

פתרון: הטענה לא נכונה. דוגמה נגדית: קודקודים a, b, c, d וקשתות a–b במשקל 1, b–c במשקל 2, a–c במשקל 3, c–d במשקל 9 (כל המשקלים שונים).
הקשת היחידה שנוגעת ב־ d היא c–d , ולכן כל עץ פורש מכיל אותה. העץ הפורש המינימלי הוא {a–b, b–c, c–d} במשקל 1 + 2 + 9 = 12 , והוא מכיל את הקשת הכבדה ביותר (9).
(הטענה נכונה רק לקשת כבדה ביותר שנמצאת על מעגל – אותה אפשר תמיד להחליף.)

בדיקה: מבין כל העצים הפורשים של הגרף, העץ המינימלי היחיד הוא {a–b, b–c, c–d} במשקל 12, ובו הקשת c–d.

סעיף ג

תשובה

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

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

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

פתרון: הטענה נכונה. נניח בשלילה שלכל קודקוד בגרף יש לפחות קשת אחת נכנסת. נתחיל בקודקוד כלשהו u₀ . יש קשת u₁ → u₀ ; ל־ u₁ יש קשת נכנסת u₂ → u₁ , וכן הלאה. כך נבנה סדרה u₀, u₁, u₂, …, uₙ של n + 1 קודקודים. בגרף יש רק n קודקודים, ולכן קודקוד כלשהו מופיע פעמיים: uᵢ = uⱼ עם i < j . אבל uⱼ → uⱼ₋₁ → … → uᵢ הוא מסלול מכוון שמתחיל ומסתיים באותו קודקוד – מעגל מכוון. זו סתירה לכך שהגרף חסר מעגלים.
(זו בדיוק הסיבה שהמיון הטופולוגי תמיד יכול להתחיל: תמיד יש קודקוד שאפשר לשים ראשון.)

סעיף ד

תשובה

לא נכונה. דוגמה נגדית: a–x (1), x–b (1), a–b (3). לפני השינוי המסלול הקל ביותר הוא a–x–b (2). אחרי הוספת 2 לכל קשת: a–x–b שוקל 6, ו־a–b שוקל 5 – המסלול הקל ביותר השתנה.

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

רעיון: מסלול עם k קשתות "מתייקר" ב־ k·c . מסלול עם הרבה קשתות מתייקר יותר ממסלול עם מעט קשתות, ולכן הסדר ביניהם יכול להתהפך.

פתרון: הטענה לא נכונה. דוגמה נגדית: קודקודים a, x, b וקשתות a–x במשקל 1, x–b במשקל 1, a–b במשקל 3.

•לפני השינוי: a–x–b שוקל 1 + 1 = 2 , ו־ a–b שוקל 3 ⇒ המסלול הקל ביותר הוא a–x–b .

•נוסיף c = 2 לכל קשת: a–x–b שוקל 3 + 3 = 6 , ו־ a–b שוקל 5 ⇒ המסלול הקל ביותר הוא עכשיו a–b .

בדיקה: המרחקים לפני ואחרי השינוי: 2 (דרך x) לפני, 5 (בקשת הישירה) אחרי.

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

סעיף ה

תשובה

נכונה. אם המסלול הוא v₁ → v₂ → … → vₙ, אז בכל מיון טופולוגי vᵢ חייב להופיע לפני vᵢ₊₁ (יש קשת ביניהם), ולכן הסדר נקבע: v₁, v₂, …, vₙ – ויש רק מיון אחד.

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

רעיון: במיון טופולוגי, לכל קשת u → v , u מופיע לפני v . קשתות המסלול "שרשרת" שקובעת את מקום כל הקודקודים.

פתרון: הטענה נכונה. נסמן את המסלול v₁ → v₂ → … → vₙ (הוא עובר בכל n הקודקודים, וכל קודקוד מופיע בו פעם אחת). בכל מיון טופולוגי, בגלל הקשת vᵢ → vᵢ₊₁ , הקודקוד vᵢ מופיע לפני vᵢ₊₁ , לכל i . לכן v₁ לפני v₂ לפני … לפני vₙ – זה כבר מסדר את כל הקודקודים, והמיון היחיד האפשרי הוא v₁, v₂, …, vₙ . הגרף חסר מעגלים, ולכן יש לו מיון טופולוגי לפחות אחד – ומכאן שיש בדיוק אחד.
(בלי המסלול זה לא נכון: לשני קודקודים בלי קשתות יש שני מיונים.)

סעיף ו

תשובה

לא נכונה. דוגמה נגדית: משולש s–a (2), s–b (2), a–b (1). עץ המסלולים הקצרים מ־s הוא {s–a, s–b} במשקל 4, ואילו העץ הפורש המינימלי שוקל 3 (למשל {a–b, s–a}).

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

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

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

•דייקסטרה מ־ s : d[a] = 2 (ישירות; דרך b זה 3), d[b] = 2 . עץ המסלולים הקצרים: {s–a, s–b} , משקלו 4 .

•עץ פורש מינימלי: {a–b, s–a} (או {a–b, s–b}) במשקל 1 + 2 = 3 < 4 .

בדיקה: העצים הפורשים של המשולש: המשקל המינימלי הוא 3, והעץ {s–a, s–b} (משקל 4) אינו מינימלי.

שאלה 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 , 5→6. יש מעגל 1→2→3→1, והורדת הקשת 3→1 נותנת גרף ללא מעגלים.

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

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

פתרון: (הקשת המקווקוות באדום היא הקשת שמורידים.)

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

בדיקה: הגרף מקיים את ההגדרה: הורדת 3→1 (וגם 1→2 או 2→3) מבטלת את המעגלים, והורדת כל קשת אחרת משאירה מעגל.

סעיף ב(1)

תשובה

לא. למשל עם 4 קודקודים a, b, c, d: הגרף a→b , b→a הוא גרף־כמעט־חסר־מעגלים עם 2 קשתות, וגם הגרף a→b , b→c , c→a , a→d , b→d , c→d – עם 6 קשתות.

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

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

פתרון: לא. שתי דוגמאות עם n = 4 (קודקודים a, b, c, d):

•G₁: a→b , b→a – 2 קשתות. יש מעגל a→b→a, והורדת a→b מבטלת אותו.

•G₃: a→b , b→c , c→a , a→d , b→d , c→d – 6 קשתות. המעגל היחיד הוא a→b→c→a (מ־d לא יוצאות קשתות), והורדת c→a מבטלת אותו.

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

בדיקה: בגרף מכוון כמעט־חסר־מעגלים מספר הקשתות נע בין 2 ל־n(n−1)/2 + 1 (עם 4 קודקודים: 2 עד 7).

סעיף ב(2)

תשובה

לא. G₁: a→b , b→a (עם c, d מבודדים) – 3 רכיבים. G₂: a→b , b→c , c→a , c→d – רכיב אחד.

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

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

פתרון: לא. שתי דוגמאות עם n = 4:

•G₁: a→b , b→a. הקודקודים c ו־d מבודדים – 3 רכיבי קשירות: {a, b}, {c}, {d}.

•G₂: a→b , b→c , c→a , c→d. בלי כיוונים הכול מחובר – רכיב אחד. המעגל היחיד הוא a→b→c→a, והורדת c→a מבטלת אותו.

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

בדיקה: G₁ ו־G₂ מקיימים את ההגדרה, עם 3 רכיבים ורכיב אחד. בבדיקת כל הגרפים עם 2 עד 4 קודקודים התקבלו כל המספרים מ־1 עד n−1.

סעיף ג(1)

תשובה

פתרון בסיסי (מלא ונכון): בודקים במיון טופולוגי (או ב־DFS – חיפוש קשת אחורה) אם יש בגרף מעגל; אם אין – שקר. אחרת, לכל קשת e בגרף: מורידים אותה זמנית ובודקים שוב אם יש מעגל; אם באחת הבדיקות אין מעגל – אמת; אם אחרי כל הקשתות עדיין לא – שקר. שיפור (רשות): מספיק לנסות רק את הקשתות של מעגל C אחד שנמצא ב־DFS (מקשת אחורה u→v ומצביעי π), כי קשת שהורדתה מבטלת את כל המעגלים חייבת להיות על כל מעגל, ובפרט על C.

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

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

פתרון – האלגוריתם הבסיסי:

פעולת עזר HasCycle(G, e): מחזירה "אמת" אם בגרף G בלי הקשת e יש מעגל (מיון טופולוגי):

1.חשב לכל קודקוד את דרגת הכניסה שלו (בלי הקשת e).

2.הכנס לתור את כל הקודקודים שדרגת הכניסה שלהם 0. count ← 0

3.כל עוד התור לא ריק: הוצא קודקוד u, count ← count + 1; לכל קשת u→v (חוץ מ־e): הקטן את דרגת הכניסה של v ב־1, ואם היא נעשתה 0 – הכנס את v לתור.

4.אם count < n – החזר "אמת" (יש קודקודים שלא נכנסו למיון – הם על מעגל או אחריו), אחרת החזר "שקר".

האלגוריתם הראשי:

1.אם HasCycle(G, אף קשת) = "שקר": החזר "שקר" (אין בגרף מעגל בכלל)

2.לכל קודקוד u, לכל קשת e = u→v ברשימה של u:

•אם HasCycle(G, e) = "שקר": החזר "אמת"

3.החזר "שקר" (הורדת כל קשת משאירה מעגל)

שיפור (רשות – לא נדרש לתשובה מלאה): אם הורדת קשת e מבטלת את כל המעגלים, אז e נמצאת על כל מעגל – ובפרט על מעגל C אחד שנמצא (אחרת C היה נשאר). לכן מספיק לנסות להוריד רק את הקשתות של C. את C מוצאים ב־DFS עם שלושה צבעים (לבן – לא התגלה, אפור – בטיפול, שחור – הסתיים): כשנמצאת קשת אחורה u→v (אל קודקוד אפור v), v הוא אב קדמון של u, והמסלול בעץ מ־v ל־u (לפי מצביעי π) יחד עם u→v הוא מעגל C. במעגל כזה יש לכל היותר n קשתות, ולכן במקום E בדיקות מבצעים לכל היותר n.

על הדוגמה מסעיף א מתקבל "אמת".

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

סעיף ג(2)

תשובה

האלגוריתם הבסיסי: O(E·(n+E)) – בדיקת מעגל אחת עולה O(n+E), ומבצעים אותה פעם אחת ועוד פעם לכל אחת מ־E הקשתות. עם השיפור (רק קשתות המעגל C, לכל היותר n): O(n·(n+E)).

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

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

פתרון:

•בדיקת מעגל אחת (HasCycle): חישוב דרגות הכניסה עובר על כל רשימות הסמיכויות – O(n + E); כל קודקוד נכנס לתור ויוצא ממנו פעם אחת לכל היותר, וכל קשת נבדקת פעם אחת – O(n + E).

•האלגוריתם הבסיסי: בדיקה אחת על הגרף כולו, ועוד בדיקה לכל קשת – (E + 1) בדיקות: O(E·(n+E)). (בגרף צפוף, E עד n², כלומר O(n⁴); בגרף דליל, E ≈ n, כלומר O(n²).)

•עם השיפור: DFS אחד למציאת C – O(n + E). במעגל C יש לכל היותר n קשתות (מעגל פשוט עובר בכל קודקוד פעם אחת לכל היותר), ולכל אחת – בדיקה אחת: O(n·(n+E)) (בגרף צפוף O(n³)).

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

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

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

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

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

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

א.(1)

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

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

L₂ = { aⁿbᵐ | n, m > 0, (n + m) % 3 = 0 }

L₃ = { aⁿbᵐ | n, m > 0, m < 20 }

לפניכם ארבעה סעיפים (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 = 1 או (k + x) % 2 = 0)}

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

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

דוגמה נוספת למילה בשפה L היא aabbcc , כי כל אחת מן האותיות abc מופיעה בה, ולפי הסדר הנדרש, ומספר המופעים של b ושל c יחד הוא 4 – זוגי.

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

(1) לפניכם חמש מילים: aaabc , abcbc , aabbbcc , abbbbbc , aacc.

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

(2)

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

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

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

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

סעיף א(1)

תשובה

L₁ – לא רגולרית; L₂ – רגולרית; L₃ – רגולרית (אינסופית, אבל מספיק לספור את ה־b עד 20).

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

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

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

L₂ – רגולרית. מספיק לזכור את (n + m) % 3 – שלוש אפשרויות – ואת השלב (בבלוק ה־a או בבלוק ה־b). אוטומט סופי דטרמיניסטי (מעבר שלא מופיע – דחייה):

מצב	a	b	מקבל?
S (התחלה)	A₁	–	לא
A₁	A₂	B₂	לא
A₂	A₀	B₀	לא
A₀	A₁	B₁	לא
B₂	–	B₀	לא
B₀	–	B₁	כן
B₁	–	B₂	לא

(A₀/A₁/A₂ – בבלוק ה־a, n % 3; B₀/B₁/B₂ – בבלוק ה־b, (n + m) % 3.)

L₃ – רגולרית. השפה אינסופית (אין הגבלה על n), אבל צריך לזכור רק את מספר ה־b עד 19 – מידע חסום. אוטומט: S –a→ A, לולאת a על A, A –b→ B₁, Bᵢ –b→ Bᵢ₊₁ (עד B₁₉), המצבים המקבלים B₁…B₁₉; b עשרים – אין מעבר (דחייה).

בדיקה: שני האוטומטים מקבלים בדיוק את המילים של L₂ ושל L₃.

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

סעיף א(2)

תשובה

כן. L₁ ∩ L₃ = { aⁿb²ⁿ | 1 ≤ n ≤ 9 } – שפה סופית (9 מילים), וכל שפה סופית רגולרית.

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

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

פתרון: רגולרית. מילה בחיתוך היא aⁿb²ⁿ (מ־L₁) שבה מספר ה־b קטן מ־20 (מ־L₃): 2n < 20, כלומר 1 ≤ n ≤ 9. לכן L₁ ∩ L₃ = { ab², a²b⁴, …, a⁹b¹⁸ } – 9 מילים בלבד. כל שפה סופית היא רגולרית (אפשר לבנות אוטומט עם מסלול נפרד לכל מילה).

בדיקה: מבין המילים aⁿbᵐ, בחיתוך יש בדיוק 9 המילים האלה.

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

סעיף א(3)

תשובה

לא. L₁ ∩ L̅₃ = { aⁿb²ⁿ | n ≥ 10 }. אילו הייתה רגולרית, L₁ = (L₁ ∩ L₃) ∪ (L₁ ∩ L̅₃) הייתה רגולרית (איחוד עם שפה סופית) – סתירה לסעיף (1).

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

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

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

בדיקה: aⁿb²ⁿ שייכת ל־L₁ ∩ L̅₃ לכל n, וכל זוג תחיליות aⁱ, aʲ (i ≠ j) מובחן על ידי הסיומת b²ⁱ.

סעיף א(4)

תשובה

כן. L₁ ⊆ L₂ (אם m = 2n אז n + m = 3n מתחלק ב־3), ולכן L₁ ∪ L₂ = L₂ – רגולרית.

מה נדרש: לקבוע אם האיחוד של L₁ (לא רגולרית) עם L₂ (רגולרית) הוא רגולרי.

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

פתרון: רגולרית. כל מילה ב־L₁ היא aⁿb²ⁿ עם n > 0, ובה n + m = n + 2n = 3n, שמתחלק ב־3. לכן כל מילה של L₁ שייכת גם ל־L₂, כלומר L₁ ⊆ L₂, ולכן L₁ ∪ L₂ = L₂. ראינו בסעיף (1) ש־L₂ רגולרית.

בדיקה: כל מילה של L₁ שייכת ל־L₂, ו־L₁ ∪ L₂ שווה ל־L₂.

טעות נפוצה: לענות "לא רגולרית, כי L₁ לא רגולרית". אין כלל כזה לאיחוד – כאן L₁ "נבלעת" בתוך L₂.

סעיף ב(1)

תשובה

aaabc – שייכת; abcbc – לא שייכת; aabbbcc – לא שייכת; abbbbbc – שייכת; aacc – לא שייכת.

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

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

פתרון:

מילה	צורה aᵐbᵏcˣ?	m, k, x	התנאי	שייכת?
aaabc	כן	3, 1, 1	m ≠ 1, אבל k + x = 2 זוגי	כן
abcbc	לא – b מופיעה אחרי c	–	–	לא
aabbbcc	כן	2, 3, 2	m ≠ 1 ו־k + x = 5 אי־זוגי	לא
abbbbbc	כן	1, 5, 1	m = 1	כן
aacc	לא – אין b (k = 0)	–	–	לא

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

סעיף ב(2)

תשובה

q₁→q₂: a ; q₂→q₂: a ; q₃→q₃: b ; q₃→q₄: c ; q₄→q₄: c ; q₅→q₆: b ; q₆→q₅: b ; q₆→q₈: c ; q₇→q₈: c ; q₈→q₇: c. מצבים מקבלים: q₄, q₇.

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

רעיון: נבין מה כל מצב "זוכר", לפי המעברים שהתוויות שלהם נתונות:

•q₀ –a→ q₁ ו־q₁ –b→ q₃: אחרי a אחת בדיוק עוברים ל־q₃. לכן q₁ = "נקראה a אחת", והמעבר q₁→q₂ הוא a נוספת: a. מ־q₂ (לפחות שתי a) כל a נוספת נשארת ב־q₂: לולאה a.

•ענף m = 1 (q₃, q₄): התנאי כבר מתקיים, ולכן כל מספר חיובי של b ואחריו כל מספר חיובי של c מתקבל: לולאת b על q₃, q₃→q₄ ב־c, לולאת c על q₄, ו־q₄ מקבל.

•ענף m ≥ 2: q₂ –b→ q₅ (b אחת). צריך לעקוב אחרי הזוגיות של k + x: q₅ = מספר ה־b אי־זוגי, q₆ = זוגי, ולכן q₅ ⇄ q₆ ב־b.

•q₅ –c→ q₇ נתון: מ־q₅ (k אי־זוגי) c ראשונה נותנת k + x זוגי ⇒ q₇ = "k + x זוגי" – מקבל. מ־q₆ (k זוגי) c ראשונה נותנת k + x אי־זוגי ⇒ q₆→q₈ ב־c, ו־q₈ לא מקבל. כל c נוספת מחליפה זוגיות: q₇ ⇄ q₈ ב־c.

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

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

מצב	a	b	c	מקבל?	משמעות
q₀ (התחלה)	q₁	–	–	לא	התחלה
q₁	q₂	q₃	–	לא	נקראה a אחת בדיוק (m = 1)
q₂	q₂	q₅	–	לא	נקראו לפחות שתי a (m ≥ 2)
q₃	–	q₃	q₄	לא	m = 1, בבלוק ה־b
q₄	–	–	q₄	כן	m = 1, בבלוק ה־c – כל המשך של c תקין
q₅	–	q₆	q₇	לא	m ≥ 2, בבלוק ה־b, מספר ה־b עד כה אי־זוגי
q₆	–	q₅	q₈	לא	m ≥ 2, בבלוק ה־b, מספר ה־b עד כה זוגי
q₇	–	–	q₈	כן	m ≥ 2, בבלוק ה־c, k + x זוגי
q₈	–	–	q₇	לא	m ≥ 2, בבלוק ה־c, k + x אי־זוגי

מעקב לדוגמה:

•abbbcc: q₀ –a→ q₁ –b→ q₃ –b→ q₃ –b→ q₃ –c→ q₄ –c→ q₄ ✔ (מצב מקבל)

•aabbcc: q₀ –a→ q₁ –a→ q₂ –b→ q₅ –b→ q₆ –c→ q₈ –c→ q₇ ✔ (מצב מקבל)

•aabcc: q₀ –a→ q₁ –a→ q₂ –b→ q₅ –c→ q₇ –c→ q₈ ✘ (מצב לא מקבל)

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

שאלה 8 · שפה בינרית המוגדרת בארבע דרישות – דוגמאות והוכחת רגולריות (25 נקודות)

L היא שפת כל המילים מעל הא"ב {0, 1} המקיימות את כל הדרישות שלפניכם:

— המילה מתחילה באות 1 .

— האות השלישית מסוף המילה היא 0 (למשל, במילה 1011 האות השלישית מהסוף היא 0).

— הרצף 11 מופיע במילה בדיוק פעם אחת. מופעים חופפים נספרים כל אחד בנפרד; למשל, במילה 0111 הרצף 11 מופיע פעמיים.

— מספר המופעים של האות 0 במילה מתחלק ב־3 בלי שארית.

א.(1)

הביאו דוגמה אחת למילה השייכת לשפה L , שאורכה 7 אותיות לפחות.

(2)

הביאו דוגמה אחת למילה שאינה שייכת לשפה L , אף שהיא מקיימת שלוש מן הדרישות. ציינו איזו דרישה אינה מתקיימת בה.

ב.

הוכיחו שהשפה L רגולרית.

הערה: אפשר להיעזר בתכונות סגירות.

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

סעיף א(1)

תשובה

לדוגמה: 1010011 (יש עוד אפשרויות, למשל 1011001, 1101010).

מה נדרש: מילה ב־L באורך 7 לפחות.

רעיון:
מתחילים ב־1, שמים בדיוק שני 1 צמודים פעם אחת, מקפידים שהאות השלישית מהסוף תהיה 0 ושמספר ה־0 יהיה 3 (או 6...).

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

דרישה	בדיקה	מתקיימת?
מתחילה ב־1	1…	✔
השלישית מהסוף 0	…011	✔
11 בדיוק פעם אחת	רק בשתי האותיות האחרונות	✔
מספר ה־0 מתחלק ב־3	שלושה 0	✔

בדיקה: 1010011 שייכת ל־L. המילה הקצרה ביותר ב־L היא 11000 (אורך 5).

סעיף א(2)

תשובה

לדוגמה: 111000 – הרצף 11 מופיע בה פעמיים (במקומות 1–2 ו־2–3), ושאר הדרישות מתקיימות.

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

רעיון:
מנצלים את הספירה של מופעים חופפים: 111 מכיל את 11 פעמיים.

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

דרישה	בדיקה	מתקיימת?
מתחילה ב־1	1…	✔
השלישית מהסוף 0	111000	✔
11 בדיוק פעם אחת	111000 וגם 111000 – פעמיים	✘
מספר ה־0 מתחלק ב־3	שלושה 0	✔

לכן 111000 אינה שייכת ל־L. (דוגמאות נוספות: 110100 – האות השלישית מהסוף היא 1; 11001 – יש רק שני 0; 00011 – מתחילה ב־0.)

בדיקה: ב־111000 יש 2 מופעים של 11, שאר שלוש הדרישות מתקיימות ⇒ לא ב־L.

סעיף ב

תשובה

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

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

רעיון:
כמו בכל שפה שמוגדרת ב"וגם" של כמה דרישות: L = L₁ ∩ L₂ ∩ L₃ ∩ L₄, כאשר Lᵢ היא שפת המילים מעל {0, 1} המקיימות את הדרישה ה־i. בונים אוטומט סופי לכל Lᵢ, ומשתמשים בסגירות של השפות הרגולריות לחיתוך.

פתרון:
(→ = מצב התחלה; "מקבל" = מצב מקבל.)

L₁ – מתחילה ב־1 (0 בהתחלה – אין מעבר):

מצב	0	1	משמעות
→ s	–	g	עוד לא נקראה אות
g (מקבל)	g	g	האות הראשונה הייתה 1

L₂ – האות השלישית מהסוף היא 0. הכי פשוט: אוטומט סופי לא דטרמיניסטי ש"מנחש" שה־0 שנקרא עכשיו הוא השלישי מהסוף, ומוודא שאחריו באות בדיוק עוד שתי אותיות:

מצב	0	1
→ t0	{t0, t1}	{t0}
t1	{t2}	{t2}
t2	{t3}	{t3}
t3 (מקבל)	–	–

לכל אוטומט סופי לא דטרמיניסטי יש אוטומט סופי דטרמיניסטי שקול (בניית תת־הקבוצות; כאן יוצא אוטומט דטרמיניסטי עם 8 מצבים, שזוכר את שלוש האותיות האחרונות), ולכן L₂ רגולרית.

L₃ – הרצף 11 מופיע בדיוק פעם אחת. זוכרים כמה מופעים של 11 היו (0 או 1) ואם האות האחרונה היא 1; מופע שני – אין מעבר:

מצב	0	1	משמעות
→ z0	z0	o0	אין עדיין 11, האחרונה אינה 1
o0	z0	o1	אין עדיין 11, האחרונה 1
z1 (מקבל)	z1	o1	היה 11 אחד, האחרונה 0
o1 (מקבל)	z1	–	היה 11 אחד, האחרונה 1

L₄ – מספר ה־0 מתחלק ב־3:

מצב	0	1	משמעות
→ m0 (מקבל)	m1	m0	מספר ה־0 %3 = 0
m1	m2	m1	%3 = 1
m2	m0	m2	%3 = 2

("–" פירושו שאין מעבר, כלומר המילה נדחית.)

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

בדיקה: כל אחד מן האוטומטים (כולל האוטומט הלא דטרמיניסטי ואוטומט תת־הקבוצות שלו) מקבל בדיוק את המילים שמקיימות את הדרישה שלו. אוטומט המכפלה של הארבעה (40 מצבים ישיגים) מקבל בדיוק את L (11000, 1010011 מתקבלות; 111000, 0110100, 1100 נדחות).

טעות נפוצה: בדרישה "בדיוק פעם אחת" לשכוח שאחרי 11 אסור שיבוא עוד 1 (111 = שני מופעים), ולכן מהמצב o1 אין מעבר ב־1.

שאלה 9 · מכונת טיורינג – חלוקה ב־3 או שארית (25 נקודות)

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

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

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

הנחיות:

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

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

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

דוגמה למספר המתחלק ב־3

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

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

דוגמה למספר שאינו מתחלק ב־3

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

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

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

(25 נקודות)

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

פתרון

תשובה

בודקים את השארית ב־3 במעבר אחד ימינה (מצבים r₀, r₁, r₂). שארית 1 או 2: כותבים אחרי הקלט $1$ או $11$. שארית 0: בכל סבב שני ה־1 השמאליים ← x וה־1 הימני ← Y; כשאין יותר 1 – ה־x האחרון ← $, כל Y ← 1, ו־$ בתא הריק הראשון ⇒ $1ⁿᐟ³$.

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

רעיון:

1.שארית: עוברים ימינה על ה־1 ומחליפים מחזורית בין שלושה מצבים r₀ → r₁ → r₂ → r₀. כשמגיעים לתא הריק △, המצב אומר מה השארית.

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

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

פתרון:

•א"ב הסרט: {⊢, 1, △, x, Y, $}. △ – תא ריק.

•הראש מתחיל על ⊢ במצב q₀. (אם לפי הסימון שלכם הראש מתחיל על התו הראשון אחרי ⊢ – מדלגים על השורה הראשונה בטבלה.)

•מצב עצירה: h. תזוזות: R ימינה, L שמאלה. בסימון "קורא/כותב, תזוזה": למשל 1/x, R.

מצב	קורא	כותב	תזוזה	מצב חדש	הסבר
q₀	⊢	⊢	R	r₀	התחלה
r₀	1	1	R	r₁	עד כאן שארית 1
r₁	1	1	R	r₂	עד כאן שארית 2
r₂	1	1	R	r₀	עד כאן שארית 0
r₁	△	$	R	s₁	שארית 1: $ אחרי הקלט
s₁	△	1	R	s₃	כותבים 1
s₃	△	$	R	h	$ סוגר – עצירה
r₂	△	$	R	s₂	שארית 2: $ אחרי הקלט
s₂	△	1	R	s₁	כותבים 1 (והמשך כמו בשארית 1)
r₀	△	△	L	d₀	n מתחלק ב־3
d₀	1	1	L	d₀	חזרה לתחילת הסרט
d₀	⊢	⊢	R	e₁
e₁	x	x	R	e₁	דילוג על x
e₁	1	x	R	e₂	ה־1 השמאלי ← x
e₁	Y	Y	L	f₁	אין יותר 1 – סיום
e₂	1	x	R	e₃	ה־1 השמאלי הבא ← x
e₃	1	1	R	e₃	ימינה עד סוף האחדות
e₃	Y	Y	L	e₄
e₃	△	△	L	e₄
e₄	1	Y	L	e₅	ה־1 הימני ← Y
e₅	1	1	L	e₅	חזרה שמאלה
e₅	x	x	R	e₁	סבב חדש
f₁	x	$	R	f₂	ה־x האחרון ← $
f₂	Y	1	R	f₂	כל Y ← 1
f₂	△	$	R	h	$ בסוף – עצירה

למה ב־e₂ וב־e₄ תמיד יש 1? בתחילת כל סבב מספר האחדות שנשארו מתחלק ב־3 וחיובי (לפחות 3). אחרי ששני השמאליים הפכו ל־x נשאר לפחות 1 אחד, וזה ה־1 שמשמאל ל־Y הראשון (או ל־△).

מעקב – n = 6 (מתחלק ב־3) (מצב הסרט בסוף כל שלב):

שלב	הסרט
התחלה	⊢111111
בדיקת שארית (r₀ בסוף) ⇒ מתחלק ב־3	⊢111111
סבב 1	⊢xx111Y
סבב 2	⊢xxxxYY
e₁ פוגש Y ⇒ f₁: ה־x האחרון ← $	⊢xxx$YY
f₂: Y ← 1, ו־$ בסוף	⊢xxx$11$

בין שני ה־$: 11 = 2 = 6/3 ✔.

מעקב – n = 8 (שארית 2): בסוף בדיקת השארית המכונה במצב r₂ על התא הריק שאחרי הקלט. r₂ כותב $ ועובר ל־s₂; s₂ כותב 1 ועובר ל־s₁; s₁ כותב 1 ועובר ל־s₃; s₃ כותב $ ועוצר. הסרט: ⊢11111111$11$. בין ה־$: 11 = 2 = 8 % 3 ✔ (כמו בדוגמה).

בדיקה: לכל n נשארים על הסרט בדיוק שני סימני $ וביניהם המספר הנכון. למשל n = 3 ⇒ ⊢x$1$ (19 צעדים), n = 9 ⇒ ⊢xxxxx$111$, n = 7 ⇒ ⊢1111111$1$, n = 60 ⇒ עשרים אחדות בין ה־$.

טעות נפוצה: לכתוב את התוצאה של שארית 1/2 "בתוך" הקלט בלי $ לפני האחדות שלה – אז האחדות של הקלט נספרות גם הן. ה־$ הראשון חייב להפריד בין שאריות הקלט לבין התוצאה.

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

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

שאלה 10 · ירושה והכלה – שער נמל (Gate) (25 נקודות)

נוסח השאלה:

בנמל "חוף הצפון" פותחה מערכת ממוחשבת לניהול המשאיות הממתינות בשער הנמל, ובה המחלקות האלה:

Container – מכולה, Reefer – מכולת קירור, Tank – מכולת נוזלים, Flat – מכולה פתוחה, Truck – משאית,
Gate – שער הנמל.

להלן פירוט תכונות המחלקות:

למחלקה Container (מכולה) שתי תכונות: code – קוד המכולה (מטיפוס מחרוזת), owner – שם החברה שבבעלותה המכולה (מטיפוס מחרוזת).

למחלקה Reefer (מכולת קירור) שלוש תכונות: code – קוד המכולה (מטיפוס מחרוזת), owner – שם החברה שבבעלותה המכולה (מטיפוס מחרוזת), temp – טמפרטורת הקירור במעלות (מטיפוס שלם).

למחלקה Tank (מכולת נוזלים) שלוש תכונות: code – קוד המכולה (מטיפוס מחרוזת), owner – שם החברה שבבעלותה המכולה (מטיפוס מחרוזת), liquid – סוג הנוזל שבמכולה (מטיפוס מחרוזת).

למחלקה Flat (מכולה פתוחה) שלוש תכונות: code – קוד המכולה (מטיפוס מחרוזת), owner – שם החברה שבבעלותה המכולה (מטיפוס מחרוזת), covered – האם המטען מכוסה ביריעה (מטיפוס בוליאני. אם המטען מכוסה – true , ואם לא – false).

למחלקה Truck (משאית) שתי תכונות: driver – שם הנהג (מטיפוס מחרוזת), cont – המכולה שהמשאית מובילה (מטיפוס Container). כל משאית מובילה מכולה אחת בלבד.

למחלקה Gate (שער הנמל) שתי תכונות: arrT – מערך של המשאיות הממתינות בשער (מטיפוס Truck), count – כמות המשאיות השמורות במערך (מטיפוס שלם).

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

א.(1)

סרטטו תרשים הייררכייה בין כל המחלקות.

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

(2)

כתבו את כותרות המחלקות ואת התכונות שלהן. הניחו שבכל מחלקה הוגדרו פעולות get ו־ set ופעולות בונות.

ב.

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

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

ג.

כתבו במחלקה Gate פעולה ששמה arrange , המסדרת מחדש את המשאיות במערך arrT כך שיופיעו קודם המשאיות המובילות מכולות קירור, אחר כך המשאיות המובילות מכולות נוזלים, ואחר כך המשאיות המובילות מכולות פתוחות.

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

בסוף הפעולה המשאיות יופיעו ברצף בתחילת המערך (ללא null ביניהן), וכמותן לא תשתנה.

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

הערה: אין חשיבות לסדר המשאיות בתוך כל סוג. מותר להשתמש במערך עזר.

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

סעיף א(1)

תשובה

Reefer, Tank, Flat יורשות מ־Container; Truck מכילה Container; Gate מכילה (מערך של) Truck.

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

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

•"הוא סוג של"? מכולת קירור, מכולת נוזלים ומכולה פתוחה הן סוגים של מכולה. לכולן יש code ו־owner כמו ל־Container, ולכל אחת תכונה נוספת משלה ⇐ Reefer, Tank ו־Flat יורשות מ־Container.

•"יש לו"? למשאית יש מכולה (התכונה cont מטיפוס Container) ⇐ Truck מכילה את Container. לשער יש משאיות (המערך arrT מטיפוס Truck) ⇐ Gate מכילה את Truck. המעוין המלא מצויר בצד של המחלקה המכילה.

פתרון

•ירושה: Reefer, Tank ו־Flat יורשות מ־Container – מכל אחת מהן יוצא חץ שראשו משולש חלול אל Container (המחלקה Container היא מחלקת הבסיס).

•הכלה: Truck מכילה את Container – קו בין שתי המחלקות, והמעוין המלא בצד של Truck (משאית מכילה מכולה אחת).

•הכלה: Gate מכילה את Truck – המעוין המלא בצד של Gate (שער מכיל מערך של משאיות).

בדיקה – כל שש המחלקות מופיעות בתרשים. התכונות המשותפות code ו־owner יוגדרו רק במחלקת הבסיס Container.

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

סעיף א(2)

תשובה

Container(code, owner); Reefer extends Container(temp); Tank extends Container(liquid); Flat extends Container(covered); Truck(driver, cont: Container); Gate(arrT: Truck[], count)

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

רעיון – בכותרת של מחלקה יורשת מציינים את מחלקת הבסיס (extends ב־Java, : ב־C#). התכונות code ו־owner מוגדרות רק ב־Container, והמחלקות היורשות מקבלות אותן בירושה. כל תכונה מוגדרת private.

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

מחלקה	כותרת (Java)	תכונות
Container	`public class Container`	`String code`, `String owner`
Reefer	`public class Reefer extends Container`	`int temp`
Tank	`public class Tank extends Container`	`String liquid`
Flat	`public class Flat extends Container`	`boolean covered`
Truck	`public class Truck`	`String driver`, `Container cont`
Gate	`public class Gate`	`Truck[] arrT`, `int count`

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

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

טעות נפוצה: להגדיר את cont מטיפוס Reefer (או אחת היורשות האחרות). כך משאית יכולה להוביל רק סוג אחד של מכולה; התכונה צריכה להיות מטיפוס מחלקת הבסיס Container.

הקוד המלא

public class Container {
    private String code;      // קוד המכולה
    private String owner;     // שם החברה שבבעלותה המכולה
}

public class Reefer extends Container {
    private int temp;         // טמפרטורת הקירור
}

public class Tank extends Container {
    private String liquid;    // סוג הנוזל
}

public class Flat extends Container {
    private boolean covered;  // האם המטען מכוסה
}

public class Truck {
    private String driver;    // שם הנהג
    private Container cont;   // המכולה שהמשאית מובילה
}

public class Gate {
    private Truck[] arrT;     // מערך המשאיות
    private int count;        // כמות המשאיות השמורות במערך
}

סעיף ב

תשובה

חיפוש מינימום של ((Reefer)c).getTemp() רק בין המכולות שהן instanceof Reefer; מחזירים את שם הנהג, או null אם לא נמצאה מכולת קירור.

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

רעיון – חיפוש מינימום רק בין מכולות הקירור. עוברים על המשאיות עד count. לכל משאית לוקחים את המכולה ובודקים אם היא instanceof Reefer (ב־C#: is Reefer). אם כן, ממירים ל־Reefer וקוראים את הטמפרטורה. שומרים את הטמפרטורה הנמוכה ביותר עד עכשיו ואת שם הנהג שלה.

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

פתרון

public String coldestDriver() {
    String driver = null;    // אם אין מכולת קירור יוחזר null
    int min = 0;
    for (int i = 0; i < this.count; i++) {
        Container c = this.arrT[i].getCont();
        if (c instanceof Reefer) {
            int t = ((Reefer) c).getTemp();
            if (driver == null || t < min) {
                min = t;
                driver = this.arrT[i].getDriver();
            }
        }
    }
    return driver;
}

בדיקה – שער עם 7 משאיות: Dana (פתוחה), Omer (קירור, ‎-18), Yael (נוזלים), Avi (קירור, 4), Noa (פתוחה), Eli (קירור, ‎-25), Rina (נוזלים). הפעולה החזירה Eli (ב־Java וב־C#). בשער בלי מכולות קירור ובשער ריק היא החזירה null.

טעות נפוצה: לאתחל min = 0 ולהשוות t < min בלי לבדוק אם כבר נמצאה מכולת קירור. אם כל מכולות הקירור בטמפרטורה חיובית (למשל 4), אף אחת לא קטנה מ־0 והפעולה תחזיר null בטעות.

הקוד המלא

public String coldestDriver() {
    String driver = null;    // אם אין מכולת קירור יוחזר null
    int min = 0;
    for (int i = 0; i < this.count; i++) {
        Container c = this.arrT[i].getCont();
        if (c instanceof Reefer) {
            int t = ((Reefer) c).getTemp();
            if (driver == null || t < min) {
                min = t;
                driver = this.arrT[i].getDriver();
            }
        }
    }
    return driver;
}

סעיף ג

תשובה

מערך עזר: שלוש סריקות (קירור, נוזלים, פתוחות) בעזרת kind, העתקה למקום הפנוי הבא, העתקה חזרה ל־arrT; מחזירים את מספר משאיות הקירור.

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

רעיון – משתמשים במערך עזר temp באותו גודל. כותבים פעולת עזר kind שמחזירה מספר לכל סוג מכולה (1 – קירור, 2 – נוזלים, 3 – פתוחה) בעזרת instanceof / is. עוברים על המשאיות שלוש פעמים: בפעם הראשונה מעתיקים ל־temp את משאיות הקירור (וסופרים אותן), בפעם השנייה את משאיות הנוזלים, ובפעם השלישית את המשאיות הפתוחות. בסוף מעתיקים את count המשאיות מ־temp חזרה ל־arrT. count לא משתנה, והמשאיות נשארות ברצף.

פתרון

// מחזירה 1 למכולת קירור, 2 למכולת נוזלים, 3 למכולה פתוחה
private static int kind(Container c) {
    if (c instanceof Reefer)
        return 1;
    if (c instanceof Tank)
        return 2;
    return 3;
}

public int arrange() {
    Truck[] temp = new Truck[this.arrT.length];
    int k = 0;                                   // המקום הפנוי הבא ב-temp
    int reefers = 0;
    for (int type = 1; type <= 3; type++)        // קירור, אחר כך נוזלים, אחר כך פתוחות
        for (int i = 0; i < this.count; i++)
            if (kind(this.arrT[i].getCont()) == type) {
                temp[k] = this.arrT[i];
                k++;
                if (type == 1)
                    reefers++;
            }
    for (int i = 0; i < this.count; i++)         // העתקה חזרה למערך arrT
        this.arrT[i] = temp[i];
    return reefers;
}

בדיקה – אותו שער עם 7 משאיות: Dana Omer Yael Avi Noa Eli Rina. הפעולה החזירה 3, והמערך נהיה Omer Avi Eli Yael Rina Dana Noa (ב־Java וב־C#). הפעלה נוספת החזירה שוב 3 ולא שינתה את הסדר. בשער Gil Tal Ron (נוזלים, פתוחה, נוזלים) הפעולה החזירה 0, והסדר נהיה Gil Ron Tal.

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

טעות נפוצה: להעתיק בכל לולאה למקום i במערך העזר (temp[i] = arrT[i]) במקום למקום הפנוי הבא k. כך נוצרים "חורים" של null ב־temp, והמשאיות לא מסודרות ברצף.

הקוד המלא

// מחזירה 1 למכולת קירור, 2 למכולת נוזלים, 3 למכולה פתוחה
private static int kind(Container c) {
    if (c instanceof Reefer)
        return 1;
    if (c instanceof Tank)
        return 2;
    return 3;
}

public int arrange() {
    Truck[] temp = new Truck[this.arrT.length];
    int k = 0;                                   // המקום הפנוי הבא ב-temp
    int reefers = 0;
    for (int type = 1; type <= 3; type++)        // קירור, אחר כך נוזלים, אחר כך פתוחות
        for (int i = 0; i < this.count; i++)
            if (kind(this.arrT[i].getCont()) == type) {
                temp[k] = this.arrT[i];
                k++;
                if (type == 1)
                    reefers++;
            }
    for (int i = 0; i < this.count; i++)         // העתקה חזרה למערך arrT
        this.arrT[i] = temp[i];
    return reefers;
}

שאלה 11 · פעולות בונות, תכונת מחלקה (static), תרשימי הייררכייה והשלמת מחלקת־על (Card, Course) (25 נקודות)

נוסח השאלה:

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

א.

לפניכם המחלקה Card (קלף) ללא מימוש הפעולות הבונות, והמחלקה Joker (ג'וקר) ללא מימוש הפעולות הבונות ופעולת toString .

Java

public class Card {
    private static int total = 100;
    protected int score;
    public Card () {…}
    public Card (int score) {…}
    public String toString() {return "total=" + total + ", score=" + score;}
}
------------------------------------------------------------------
public class Joker extends Card {
    private boolean wild;
    public Joker (boolean wild) {…}
    public Joker (int score, boolean wild) {…}
    public String toString() {…}
}

לפניכם קטע קוד והפלט שהתקבל בעקבות הרצת קטע הקוד:

הקוד

Java

Card c1 = new Card (7);
System.out.println (c1);          //1
Card c2 = new Card ();
System.out.println (c2);          //2
Card c3 = new Joker (true);
System.out.println (c3);          //3
Card c4 = new Joker (3, false);
System.out.println (c4);          //4

הפלט

total=107, score=7                //1
total=108, score=1                //2
total=108, score=0, wild=true     //3
total=111, score=3, wild=false    //4

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

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

ב.(1)

נתונות המחלקות E, F, G, H והפעולה main במחלקה Tester , שרצה באופן תקין.

Java

public class Tester {
    public static void main(String[] args) {
        E e1 = new H();
        G g1 = new F();
        E e2 = new F();
    }
}

לפניכם שישה תרשימי הייררכייה 1–6 (החץ מסמן יחס ירושה). בנוגע לכל אחד מהם, ציינו אם ייתכן או לא ייתכן שהוא מתאר את יחס ההייררכייה בין המחלקות E, F, G, H . אם ציינתם שלא ייתכן, נמקו מדוע.

(2)

בסוף הפעולה main נוספו שורות הקוד שלהלן, שרצות באופן תקין:

Java

E e3 = new F();
H h1 = (H)e3;

בעקבות זאת, האם תשתנה תשובתכם בתת־סעיף ב(1)? נמקו את תשובתכם.

ג.

נתונה המחלקה OnlineCourse (קורס מקוון), היורשת מהמחלקה Course (קורס):

Java

public class OnlineCourse extends Course {
    private String link;
    public OnlineCourse (String link) {
        this.link = link;
    }
    public OnlineCourse (String title, int hours, String link) {
        super (title, hours);
        this.link = link;
    }
    public int price () {return super.price() - Course.discount; }
    public boolean isLong () {return this.hours > 30; }
    public String describe (int n) {return this.describe() + this.link.substring(0, n); }
}

כתבו במחלקה Course את תכונות המחלקה (כולל הרשאות הגישה) ואת הכותרות של הפעולות הנדרשות כדי שהמחלקה OnlineCourse תהיה תקינה, בהתאם לעקרונות תכנות מונחה עצמים.

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

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

סעיף א

תשובה

Card(): this(1) · Card(int score): total += score; this.score=score · Joker(boolean wild): super(0); wild=wild · Joker(int score, boolean wild): super(score); wild=wild · toString: super.toString() + ", wild=" + wild

מה נדרש – לממש את הפעולות הבונות של Card ושל Joker ואת toString של Joker כך שיתקבל הפלט הנתון.

רעיון – total היא תכונת מחלקה (static) פרטית של Card שערכה ההתחלתי 100. רק פעולות בונות של Card יכולות לשנות אותה. מסיקים מהפלט, שורה אחר שורה:

•//1 new Card(7) הדפיס total=107, score=7 ⇐ הבונה עם פרמטר מוסיפה ל־total את הניקוד ומציבה אותו ב־score.

•//2 new Card() הדפיס total=108, score=1 ⇐ הבונה בלי פרמטרים מתנהגת כמו Card(1): מזמנים this(1) / : this(1) (אפשר גם total++ ו־score = 1).

•//3 new Joker(true) הדפיס total=108 (לא השתנה), score=0. כל פעולה בונה של Card משנה את total לפי הניקוד: Card() מוסיפה 1, ו־Card(int) מוסיפה את הפרמטר. לכן כדי ש־total לא ישתנה ו־score יהיה 0, הבונה של Joker מזמנת את Card(0): super(0) / : base(0).

•//4 new Joker(3, false) הדפיס total=111, score=3 ⇐ super(score) / : base(score) (108 + 3).

•toString של Joker: super.toString() + ", wild=" + wild (ב־C#: base.ToString()). ב־C# ערך בוליאני מודפס True/False, ולכן גם הפלט בנוסח C# מציג True ו־False.

פתרון

public class Card {
    private static int total = 100;
    protected int score;

    public Card() {
        this(1);                // total גדל ב-1 ו-score הוא 1
    }

    public Card(int score) {
        total += score;         // כל קלף מוסיף את הניקוד שלו ל-total
        this.score = score;
    }

    public String toString() {return "total=" + total + ", score=" + score;}
}

public class Joker extends Card {
    private boolean wild;

    public Joker(boolean wild) {
        super(0);               // total לא משתנה ו-score הוא 0
        this.wild = wild;
    }

    public Joker(int score, boolean wild) {
        super(score);
        this.wild = wild;
    }

    public String toString() {
        return super.toString() + ", wild=" + this.wild;
    }
}

בדיקה – קטע הקוד מהשאלה מדפיס ב־Java:

total=107, score=7
total=108, score=1
total=108, score=0, wild=true
total=111, score=3, wild=false

וב־C# אותו פלט, עם wild=True ו־wild=False.

טעות נפוצה: לממש את Joker(boolean wild) בלי קריאה מפורשת ל־super ולהציב score = 0. אז מופעלת אוטומטית Card(), שמוסיפה 1 ל־total, ובשורה //3 מודפס total=109 (ובשורה //4 total=112).

הקוד המלא

public class Card {
    private static int total = 100;
    protected int score;

    public Card() {
        this(1);                // total גדל ב-1 ו-score הוא 1
    }

    public Card(int score) {
        total += score;         // כל קלף מוסיף את הניקוד שלו ל-total
        this.score = score;
    }

    public String toString() {return "total=" + total + ", score=" + score;}
}

public class Joker extends Card {
    private boolean wild;

    public Joker(boolean wild) {
        super(0);               // total לא משתנה ו-score הוא 0
        this.wild = wild;
    }

    public Joker(int score, boolean wild) {
        super(score);
        this.wild = wild;
    }

    public String toString() {
        return super.toString() + ", wild=" + this.wild;
    }
}

סעיף ב(1)

תשובה

1 – ייתכן; 2 – לא ייתכן; 3 – ייתכן; 4 – לא ייתכן; 5 – ייתכן; 6 – לא ייתכן.

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

רעיון – השמה X ref = new Y(); עוברת הידור רק אם Y היא X או תת־מחלקה של X (ישירה או עקיפה). מכל שורה ב־main מקבלים דרישה:

•E e1 = new H(); ⇐ H יורשת (ישירות או בעקיפין) מ־E.

•G g1 = new F(); ⇐ F יורשת מ־G.

•E e2 = new F(); ⇐ F יורשת מ־E.

פתרון

תרשים	מבנה (בן → אב)	ייתכן?	נימוק
1	E→G, F→E, H→E	ייתכן	H ו־F יורשות מ־E, ו־F יורשת מ־G בעקיפין (דרך E).
2	F→E, G→E, H→G	לא ייתכן	F ו־G הן "אחיות" (שתיהן יורשות מ־E), ו־F אינה יורשת מ־G ⇐ `G g1 = new F();` שגיאת הידור.
3	E→G, H→E, F→H	ייתכן	H יורשת מ־E, ו־F יורשת מ־E ומ־G בעקיפין (דרך H).
4	F→E, G→F, H→G	לא ייתכן	G יורשת מ־F, ולא להפך ⇐ `G g1 = new F();` שגיאת הידור.
5	G→E, H→E, F→G	ייתכן	H יורשת מ־E, F יורשת מ־G, ו־F יורשת מ־E בעקיפין (דרך G).
6	E→H, G→E, F→G	לא ייתכן	H היא מחלקת־על של E, ולא תת־מחלקה שלה ⇐ `E e1 = new H();` שגיאת הידור.

בדיקה – בנינו את המחלקות E, F, G, H לפי כל אחד מהתרשימים והידרנו את Tester (ב־Java וב־C#). בתרשימים 2, 4, 6 הייתה שגיאת הידור, ובתרשימים 1, 3, 5 התוכנית רצה תקין.

סעיף ב(2)

תשובה

כן. ההמרה (H)e3 של עצם F מצליחה רק אם F יורשת מ־H, ולכן רק תרשים 3 נשאר אפשרי (ב־1 וב־5 תהיה שגיאת ריצה).

מה נדרש – לבדוק אילו מהתרשימים שנמצאו אפשריים ב־ב(1) (1, 3, 5) נשארים אפשריים אחרי השורות החדשות.

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

פתרון – כן, התשובה משתנה: רק תרשים 3 נשאר אפשרי.

•תרשים 1: F ו־H הן "אחיות" (שתיהן יורשות מ־E). עצם F אינו H ⇐ שגיאת ריצה ⇐ לא ייתכן.

•תרשים 3: F יורשת מ־H ⇐ ההמרה תקינה ⇐ ייתכן.

•תרשים 5: F יורשת מ־G, ו־H היא "אחות" של G. עצם F אינו H ⇐ שגיאת ריצה ⇐ לא ייתכן.

•תרשימים 2, 4, 6 נשארים לא אפשריים (מהנימוקים של ב(1)).

בדיקה – עם השורות הנוספות (Java ו־C#): בתרשימים 1 ו־5 מתקבלת שגיאת ריצה (ClassCastException / InvalidCastException), ובתרשים 3 התוכנית רצה תקין.

סעיף ג

תשובה

protected int hours; protected static int discount; public Course(); public Course(String title, int hours); public int price() (ב־C#: public virtual int Price()); public String describe() (ב־C#: public string Describe())

מה נדרש – לכתוב את התכונות ואת כותרות הפעולות של Course שבלעדיהן OnlineCourse לא תעבור הידור.

רעיון – עוברים על OnlineCourse שורה אחר שורה ושואלים מה היא צריכה מ־Course:

שורה ב־OnlineCourse	מה נדרש ב־Course
`OnlineCourse(String link)` – אין קריאה מפורשת ל־super/base	מופעלת אוטומטית הבונה בלי פרמטרים ⇐ `Course()`
`super(title, hours)` / `: base(title, hours)`	פעולה בונה `Course(String title, int hours)`
`super.price() - Course.discount` שמוחזר כ־int	`public int price()`; ב־C# OnlineCourse כותבת `override`, ולכן ב־Course: `public virtual int Price()`. וגם תכונת מחלקה (static) מטיפוס שלם שנגישה ליורשת: `protected static int discount` (אם היא double, הביטוי הוא double ואי אפשר להחזיר אותו כ־int – שגיאת הידור)
`this.hours > 30`	תכונה מספרית שנגישה ליורשת ⇐ `protected int hours` (עם private תהיה שגיאת הידור)
`this.describe() + ...` – ב־OnlineCourse יש רק `describe(int n)`	העמסה: `public String describe()` (ב־C#: `public string Describe()`)

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

public class Course {
    protected int hours;
    protected static int discount;

    public Course() { }
    public Course(String title, int hours) { }
    public int price() { return 0; }
    public String describe() { return ""; }
}

אפשר להוסיף תכונה פרטית title לשמירת שם הקורס, אבל היא אינה נדרשת כדי ש־OnlineCourse תהיה תקינה.

הערה: מכיוון ש־describe(int n) אינה דורסת את describe() (זו העמסה), הקוד יעבור הידור גם אם describe() תחזיר טיפוס אחר (למשל int), כי חיבור עם מחרוזת נותן מחרוזת. הכותרת הטבעית היא עם טיפוס החזרה String (ב־C#: string), וכך היא מוצגת כאן.

בדיקה – Course יחד עם OnlineCourse ללא שינוי תקינות ב־Java וב־C#. בדקנו גם שכל רכיב נחוץ: בלי Course() או בלי Course(String, int), עם private int hours או hours מטיפוס מחרוזת, עם discount שאינה static או שהיא double, בלי price() (וב־C# בלי virtual), בלי describe() – בכל אחד מהמקרים התקבלה שגיאת הידור.

טעות נפוצה: להגדיר את hours כ־private ולהניח שהיורשת "מקבלת" אותה. תכונה פרטית קיימת בעצם של היורשת, אבל אי אפשר לגשת אליה בשמה מתוך הקוד של OnlineCourse.

הקוד המלא

public class Course {
    protected int hours;
    protected static int discount;

    public Course() { }
    public Course(String title, int hours) { }
    public int price() { return 0; }
    public String describe() { return ""; }
}

שאלה 12 · מעקב – דריסה מול העמסה (Gem ו־Opal) (25 נקודות)

נוסח השאלה:

נתונות המחלקות Opal , Gem :

Java

public class Gem {
    private int w;

    public Gem() { this(1); }
    public Gem(int w) { this.w = w; }
    public int getW() { return this.w; }
    public void shine() { this.w = this.w + 1; }
    public void polish() {
        shine();
        this.w = this.w * 2;
    }
    public void join(Gem g) { this.w = this.w + g.getW(); }
    public String toString() { return "Gem " + this.w; }
}

public class Opal extends Gem {
    private int c;

    public Opal(int w, int c) {
        super(w);
        this.c = c;
    }
    public Opal(int c) {
        this(c * 2, c);
    }
    public void shine() { this.c = this.c + getW(); }
    public void join(Opal o) { this.c = this.c + o.c; }
    public String toString() { return "Opal " + getW() + "/" + this.c; }
}

א.

לפניכם קטע קוד:

Java

Gem[] g = new Gem[5];
g[0] = new Gem();
g[1] = new Opal(3);
g[2] = new Opal(4, 1);
g[3] = new Gem(6);
g[4] = g[2];
for (int i = 0; i < g.length; i++)
    System.out.println(g[i]);

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

ב.

לפניכם המשך קטע הקוד:

Java

g[0].polish();
g[1].polish();
g[2].join(g[1]);
Opal p = (Opal) g[1];
p.join((Opal) g[4]);
p.join(g[3]);
((Opal) g[4]).join(p);
g[3].polish();
System.out.println("p: " + p);
for (int i = 0; i < g.length; i++)
    System.out.println(g[i]);

כתבו מה הקוד מדפיס.

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

סעיף א

תשובה

Gem 1
Opal 6/3
Opal 4/1
Gem 6
Opal 4/1

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

רעיון – Gem() קוראת ל־this(1), כלומר w = 1. Opal(int c) קוראת ל־this(c * 2, c) – כלומר לפעולה הבונה Opal(int w, int c) של אותה מחלקה, וזו קוראת ל־super(w). g[4] = g[2] לא יוצרת עצם. ההדפסה מזמנת את toString של העצם בפועל: ב־Opal היא מחזירה "Opal " ואחריו w (דרך getW) ו־c מופרדים ב־/.

פתרון

שורה	פעולות בונות שרצות	w	c
`g[0] = new Gem()`	`Gem()` → `Gem(1)`	1	–
`g[1] = new Opal(3)`	`Opal(3)` → `Opal(6, 3)` → `Gem(6)`	6	3
`g[2] = new Opal(4, 1)`	`Opal(4, 1)` → `Gem(4)`	4	1
`g[3] = new Gem(6)`	`Gem(int w)`	6	–
`g[4] = g[2]`	אין עצם חדש – העתקת הפניה	(4)	(1)

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

g[0] ──► Gem   w = 1
g[1] ──► Opal  w = 6, c = 3
g[2] ──► Opal  w = 4, c = 1   ◄── g[4]   (אותו עצם!)
g[3] ──► Gem   w = 6

הפלט:

Gem 1
Opal 6/3
Opal 4/1
Gem 6
Opal 4/1

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

טעות נפוצה: לחשוב ש־new Opal(3) נותן w = 3 – הפעולה הבונה מעבירה c * 2 = 6 כ־w ו־3 כ־c.

סעיף ב

תשובה

p: Opal 18/10
Gem 4
Opal 18/10
Opal 16/11
Gem 14
Opal 16/11

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

רעיון – יש כאן שני מנגנונים שונים:

•דריסה – shine מוגדרת ב־Gem ונדרסת ב־Opal. polish() כתובה רק ב־Gem, והיא קוראת ל־shine() – שנבחרת לפי סוג העצם בזמן ריצה.

•העמסה – ב־Opal יש join(Opal o), שהיא פעולה אחרת מ־join(Gem g) של Gem (הפרמטר מטיפוס אחר), ולא דורסת אותה. איזו מהן תרוץ נקבע בזמן הידור, לפי טיפוס ההפניה שעליה מזמנים ולפי טיפוס הארגומנט: דרך הפניה מטיפוס Gem רואים רק את join(Gem); דרך הפניה מטיפוס Opal רואים את שתיהן, ונבחרת המתאימה ביותר לטיפוס הארגומנט.

ב־C# shine מוגדרת virtual/override, ו־Join(Opal) היא פעולה נוספת (העמסה) – ההתנהגות זהה.

פתרון

פקודה	טיפוס ההפניה / הארגומנט	מה רץ בפועל	שינוי
`g[0].polish()`	Gem (עצם Gem)	`Gem.polish` → `Gem.shine`	g[0]: w = 1 + 1 = 2, ואז 2·2 = 4
`g[1].polish()`	Gem (עצם Opal)	`Gem.polish` → `Opal.shine` (דריסה)	g[1]: c = 3 + 6 = 9, ואז w = 6·2 = 12
`g[2].join(g[1])`	הפניה Gem, ארגומנט Gem	רק `join(Gem)` נראית	g[2]: w = 4 + 12 = 16
`Opal p = (Opal) g[1]`		p מפנה לאותו עצם כמו g[1]
`p.join((Opal) g[4])`	הפניה Opal, ארגומנט Opal	`join(Opal)` – המתאימה ביותר	g[1]: c = 9 + 1 = 10
`p.join(g[3])`	הפניה Opal, ארגומנט Gem	`join(Gem)` (שעברה בירושה)	g[1]: w = 12 + 6 = 18
`((Opal) g[4]).join(p)`	הפניה Opal, ארגומנט Opal	`join(Opal)`	g[2]: c = 1 + 10 = 11
`g[3].polish()`	Gem (עצם Gem)	`Gem.polish` → `Gem.shine`	g[3]: w = 6 + 1 = 7, ואז 14
הדפסה		`Opal.toString`	p: Opal 18/10

מצב המערך בסוף: g[0] → Gem 4; g[1] (= p) → Opal w=18, c=10; g[2] ו־g[4] → אותו Opal w=16, c=11; g[3] → Gem 14.

הפלט:

p: Opal 18/10
Gem 4
Opal 18/10
Opal 16/11
Gem 14
Opal 16/11

בדיקה – הפלט של ההמשך (אחרי סעיף א) זהה ב־Java וב־C# ותואם לטבלה.

טעות נפוצה: לחשוב ש־g[2].join(g[1]) מפעילה את join(Opal) כי שני העצמים הם Opal – בחירה בין פעולות מועמסות נעשית לפי הטיפוסים המוצהרים (Gem), ולכן רצה join(Gem) ומשתנה w ולא c. וגם: לשכוח ש־g[4] הוא אותו עצם כמו g[2].

טבלת התשובות

שאלה	סעיף	תשובה
1	א(1)	בכל סבב מוציאים מדידה ראשונה, עוברים על כל שאר המדידות: של אותה תחנה – מעדכנים max/min, של תחנה אחרת – לתור עזר שמחליף את qRead; מכניסים לתוצאה new Reading(station, max − min).
	א(2)	O(n²) – לכל תחנה עוברים על כל המדידות שנותרו בתור: (n−1)+(n−2)+…+1 במקרה הגרוע.
	ב(1)	מחשבים gaps = tempGaps(qRead); מעבר ראשון: סכום הפערים ומספר התחנות (תוך העברה לתור עזר); מעבר שני על תור העזר: מכניסים לתוצאה כל תחנה שהפער שלה > sum / count.
	ב(2)	O(n²) – בגלל הקריאה ל־tempGaps; שני המעברים הנוספים O(n).
2	א	מתקדמים בהפניה עזר p עד ההופעה הראשונה של num, ועוברים לחוליה שאחריה. מכאן מסכמים את הערכים עד שמגיעים שוב ל־num או לסוף השרשרת. אם הגענו לסוף (p == null) – מחזירים −1, אחרת מחזירים את הסכום.
2	ב	max = −1, best = −1. לכל ערך v בשרשרת מחשבים w = frameWeight(lst, v). אם w > max (גדול ממש) מעדכנים max = w ו־best = v. בסוף מחזירים את best.
3	א	אם isPowerOfTwo(val) – מחזירים false. אחרת מחשבים p = 1 ומכפילים ב־ 2 כל עוד p·2 < val, מוסיפים בן שמאלי p ובן ימני val − p, ומחזירים true.
	ב(1)	92 ← בנים 64 (עלה) ו־ 28; 28 ← בנים 16 (עלה) ו־ 12; 12 ← בנים 8 ו־ 4 (עלים). העלים: 64, 16, 8, 4.
	ב(2)	הפעולה מפרקת את ערך הצומת לחזקות של 2: היא בונה עץ שבו כל צומת פנימי הוא סכום שני בניו, והעלים הם החזקות של 2 (השונות) שסכומן הוא הערך – כלומר הייצוג הבינרי שלו; מספר העלים = מספר הספרות 1 בייצוג הבינרי.
4	א(1)	כן. יש מסלול בין כל שני קודקודים: כל הקודקודים מחוברים אל c (a – c , b – c , c – d – e – f), ולכן אפשר לעבור מכל קודקוד לכל קודקוד דרך c .
	א(2)	לא. יש בגרף מעגל באורך אי־זוגי (המשולש a – b – c – a , באורך 3), ובגרף דו־צדדי אין מעגל באורך אי־זוגי.
	א(3)	לא. בגרף מלא יש קשת בין כל שני קודקודים, אבל כאן, למשל, אין קשת בין a ל־ d . (בגרף מלא עם 6 קודקודים יש 6·5/2 = 15 קשתות, וכאן יש רק 6.)
	א(4)	לא. עץ הוא גרף קשיר ללא מעגלים, ובגרף יש מעגל a – b – c – a . (גם: בעץ עם 6 קודקודים יש 5 קשתות, וכאן יש 6.)
	ב(1)	A: B, C \| B: D \| C: D, F \| D: E, G \| E: B, H \| F: G \| G: H \| H: F
	ב(2)	A: B \| B: D \| C: D, F \| D: E, G \| E: H \| F: G \| G: H \| H: (ריקה)
	ב(3) I	מיון טופולוגי (למשל לפי דרגות כניסה, או בעזרת DFS וסדר זמני הסיום ההפוך). סדר כזה קיים אם ורק אם אין בגרף מעגל מכוון; אם האלגוריתם אינו מצליח לסדר את כל הקודקודים – יש מעגל ואי אפשר ללמוד את כל הקורסים.
	ב(3) II	A , C , B , F , D , E , G , H (סדר לפי דרגות כניסה ותור, כשבכל שלב נכנסים לתור קורסים חדשים בסדר אלפביתי). כל סדר אחר שמקיים את כל דרישות הקדם נכון גם הוא.
5	א	נכונה. אם (u, v) קשת, אז אפשר להגיע ל־v דרך u: d[v] ≤ d[u] + 1, ובאותו אופן d[u] ≤ d[v] + 1. לכן \|d[u] − d[v]\| ≤ 1.
	ב	לא נכונה. דוגמה נגדית: הקשתות a–b (1), b–c (2), a–c (3), c–d (9). הקשת c–d (הכבדה ביותר) היא הקשת היחידה שמגיעה ל־d, ולכן היא שייכת לכל עץ פורש – גם לעץ הפורש המינימלי {a–b, b–c, c–d} במשקל 12.
	ג	נכונה. אילו לכל קודקוד הייתה קשת נכנסת, היינו הולכים מקודקוד כלשהו אחורה לאורך קשתות נכנסות; אחרי n צעדים קודקוד חוזר על עצמו – וזה מעגל מכוון, בסתירה לכך שהגרף חסר מעגלים.
	ד	לא נכונה. דוגמה נגדית: a–x (1), x–b (1), a–b (3). לפני השינוי המסלול הקל ביותר הוא a–x–b (2). אחרי הוספת 2 לכל קשת: a–x–b שוקל 6, ו־a–b שוקל 5 – המסלול הקל ביותר השתנה.
	ה	נכונה. אם המסלול הוא v₁ → v₂ → … → vₙ, אז בכל מיון טופולוגי vᵢ חייב להופיע לפני vᵢ₊₁ (יש קשת ביניהם), ולכן הסדר נקבע: v₁, v₂, …, vₙ – ויש רק מיון אחד.
	ו	לא נכונה. דוגמה נגדית: משולש s–a (2), s–b (2), a–b (1). עץ המסלולים הקצרים מ־s הוא {s–a, s–b} במשקל 4, ואילו העץ הפורש המינימלי שוקל 3 (למשל {a–b, s–a}).
6	א	למשל: קודקודים 1–6, קשתות 1→2 , 2→3 , 3→1 , 3→4 , 4→5 , 4→6 , 5→6. יש מעגל 1→2→3→1, והורדת הקשת 3→1 נותנת גרף ללא מעגלים.
	ב(1)	לא. למשל עם 4 קודקודים a, b, c, d: הגרף a→b , b→a הוא גרף־כמעט־חסר־מעגלים עם 2 קשתות, וגם הגרף a→b , b→c , c→a , a→d , b→d , c→d – עם 6 קשתות.
	ב(2)	לא. G₁: a→b , b→a (עם c, d מבודדים) – 3 רכיבים. G₂: a→b , b→c , c→a , c→d – רכיב אחד.
	ג(1)	פתרון בסיסי (מלא ונכון): בודקים במיון טופולוגי (או ב־DFS – חיפוש קשת אחורה) אם יש בגרף מעגל; אם אין – שקר. אחרת, לכל קשת e בגרף: מורידים אותה זמנית ובודקים שוב אם יש מעגל; אם באחת הבדיקות אין מעגל – אמת; אם אחרי כל הקשתות עדיין לא – שקר. שיפור (רשות): מספיק לנסות רק את הקשתות של מעגל C אחד שנמצא ב־DFS (מקשת אחורה u→v ומצביעי π), כי קשת שהורדתה מבטלת את כל המעגלים חייבת להיות על כל מעגל, ובפרט על C.
	ג(2)	האלגוריתם הבסיסי: O(E·(n+E)) – בדיקת מעגל אחת עולה O(n+E), ומבצעים אותה פעם אחת ועוד פעם לכל אחת מ־E הקשתות. עם השיפור (רק קשתות המעגל C, לכל היותר n): O(n·(n+E)).
7	א(1)	L₁ – לא רגולרית; L₂ – רגולרית; L₃ – רגולרית (אינסופית, אבל מספיק לספור את ה־b עד 20).
	א(2)	כן. L₁ ∩ L₃ = { aⁿb²ⁿ \| 1 ≤ n ≤ 9 } – שפה סופית (9 מילים), וכל שפה סופית רגולרית.
	א(3)	לא. L₁ ∩ L̅₃ = { aⁿb²ⁿ \| n ≥ 10 }. אילו הייתה רגולרית, L₁ = (L₁ ∩ L₃) ∪ (L₁ ∩ L̅₃) הייתה רגולרית (איחוד עם שפה סופית) – סתירה לסעיף (1).
	א(4)	כן. L₁ ⊆ L₂ (אם m = 2n אז n + m = 3n מתחלק ב־3), ולכן L₁ ∪ L₂ = L₂ – רגולרית.
	ב(1)	aaabc – שייכת; abcbc – לא שייכת; aabbbcc – לא שייכת; abbbbbc – שייכת; aacc – לא שייכת.
	ב(2)	q₁→q₂: a ; q₂→q₂: a ; q₃→q₃: b ; q₃→q₄: c ; q₄→q₄: c ; q₅→q₆: b ; q₆→q₅: b ; q₆→q₈: c ; q₇→q₈: c ; q₈→q₇: c. מצבים מקבלים: q₄, q₇.
8	א(1)	לדוגמה: 1010011 (יש עוד אפשרויות, למשל 1011001, 1101010).
	א(2)	לדוגמה: 111000 – הרצף 11 מופיע בה פעמיים (במקומות 1–2 ו־2–3), ושאר הדרישות מתקיימות.
	ב	L = L₁ ∩ L₂ ∩ L₃ ∩ L₄ (שפה לכל דרישה). ל־L₁, L₃, L₄ יש אוטומט סופי דטרמיניסטי, ול־L₂ אוטומט סופי לא דטרמיניסטי (ששקול לדטרמיניסטי) – כולן רגולריות. השפות הרגולריות סגורות לחיתוך ⇒ L רגולרית.
9	-	בודקים את השארית ב־3 במעבר אחד ימינה (מצבים r₀, r₁, r₂). שארית 1 או 2: כותבים אחרי הקלט $1$ או $11$. שארית 0: בכל סבב שני ה־1 השמאליים ← x וה־1 הימני ← Y; כשאין יותר 1 – ה־x האחרון ← $, כל Y ← 1, ו־$ בתא הריק הראשון ⇒ $1ⁿᐟ³$.
10	א(1)	Reefer, Tank, Flat יורשות מ־Container; Truck מכילה Container; Gate מכילה (מערך של) Truck.
	א(2)	Container(code, owner); Reefer extends Container(temp); Tank extends Container(liquid); Flat extends Container(covered); Truck(driver, cont: Container); Gate(arrT: Truck[], count)
	ב	חיפוש מינימום של ((Reefer)c).getTemp() רק בין המכולות שהן instanceof Reefer; מחזירים את שם הנהג, או null אם לא נמצאה מכולת קירור.
	ג	מערך עזר: שלוש סריקות (קירור, נוזלים, פתוחות) בעזרת kind, העתקה למקום הפנוי הבא, העתקה חזרה ל־arrT; מחזירים את מספר משאיות הקירור.
11	א	Card(): this(1) · Card(int score): total += score; this.score=score · Joker(boolean wild): super(0); wild=wild · Joker(int score, boolean wild): super(score); wild=wild · toString: super.toString() + ", wild=" + wild
	ב(1)	1 – ייתכן; 2 – לא ייתכן; 3 – ייתכן; 4 – לא ייתכן; 5 – ייתכן; 6 – לא ייתכן.
	ב(2)	כן. ההמרה (H)e3 של עצם F מצליחה רק אם F יורשת מ־H, ולכן רק תרשים 3 נשאר אפשרי (ב־1 וב־5 תהיה שגיאת ריצה).
	ג	protected int hours; protected static int discount; public Course(); public Course(String title, int hours); public int price() (ב־C#: public virtual int Price()); public String describe() (ב־C#: public string Describe())
12	א	`Gem 1 Opal 6/3 Opal 4/1 Gem 6 Opal 4/1`
12	ב	`p: Opal 18/10 Gem 4 Opal 18/10 Opal 16/11 Gem 14 Opal 16/11`

פרק ראשון

שאלה 1 · פערי טמפרטורות בתחנות מדידה – תור (25 נקודות)

סעיף א(1)

סעיף א(2)

סעיף ב(1)

סעיף ב(2)

שאלה 2 · מסגרות בשרשרת חוליות (25 נקודות)

סעיף א

סעיף ב

שאלה 3 · פיצול צומת לחזקות של 2 (25 נקודות)

סעיף א

סעיף ב(1)

סעיף ב(2)

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

שאלה 4 · תכונות של גרף ומיון טופולוגי של קורסים (25 נקודות)

סעיף א(1)

סעיף א(2)

סעיף א(3)

סעיף א(4)

סעיף ב(1)

סעיף ב(2)

סעיף ב(3) I

סעיף ב(3) II

שאלה 5 · טענות על גרפים – נכון / לא נכון (25 נקודות)

סעיף א

סעיף ב

סעיף ג

סעיף ד

סעיף ה

סעיף ו

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

סעיף א

סעיף ב(1)

סעיף ב(2)

סעיף ג(1)

סעיף ג(2)

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

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

סעיף א(1)

סעיף א(2)

סעיף א(3)

סעיף א(4)

סעיף ב(1)

סעיף ב(2)

שאלה 8 · שפה בינרית המוגדרת בארבע דרישות – דוגמאות והוכחת רגולריות (25 נקודות)

סעיף א(1)

סעיף א(2)

סעיף ב

שאלה 9 · מכונת טיורינג – חלוקה ב־3 או שארית (25 נקודות)

פתרון

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

שאלה 10 · ירושה והכלה – שער נמל (Gate) (25 נקודות)

סעיף א(1)

סעיף א(2)

סעיף ב

סעיף ג

שאלה 11 · פעולות בונות, תכונת מחלקה (static), תרשימי הייררכייה והשלמת מחלקת־על (Card, Course) (25 נקודות)

סעיף א

סעיף ב(1)

סעיף ב(2)

סעיף ג

שאלה 12 · מעקב – דריסה מול העמסה (Gem ו־Opal) (25 נקודות)

סעיף א

סעיף ב

רוצים להשלים את חוויית הלמידה?

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