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

מבררים את השפה ואת דרישות המסלול

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

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

כותבים חוזה קצר לפתרון

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

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

בודקים טעות שנראית קטנה

אתחול המקסימום ל־0 עלול להיכשל במערך שכל ערכיו שליליים. במערך ‎−8, ‎−3, ‎−10 התשובה היא ‎−3, ולא 0. זו דוגמה לכך שקוד יכול לעבוד על נתוני ההדגמה ולהיכשל בדרישה הכללית.

מסבירים מה נשמר לאורך הריצה

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

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

מתרגלים בלי להחליף עבודה עצמאית

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

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

מתרגמים את הדרישה לדוגמאות לפני הקוד

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

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

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

בונים טבלת מעקב שמראה את נקודת השינוי

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

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

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

בוחרים בדיקות שמכוונות לסוגי טעויות

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

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

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

מבחינים בין החזרה, הדפסה ושינוי נתונים

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

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

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

משווים דרכי פתרון לפי העבודה שהן מבצעות

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

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

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

מתרגלים עצמאות לאורך שבוע

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

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

מסבירים מדוע הלולאה מסתיימת

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

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

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

דוגמה לבדיקת קצה: מקסימום ברשימה שלילית

נניח שהמטלה היא למצוא את הערך הגדול ביותר ברשימה לא ריקה של מספרים שלמים. עבור הרשימה ‎−3, −7, −4 התשובה היא ‎−3. פתרון שמאתחל את המקסימום ל־0 ולא מעדכן אותו מחזיר ערך שאפילו אינו ברשימה. דרך מתאימה למקרה הזה היא להתחיל מן האיבר הראשון ולהשוות אליו את שאר האיברים. התנאי שהרשימה אינה ריקה הוא חלק מחוזה הפעולה, ולא פרט שאפשר לשכוח.

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

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

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

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

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