אלגוריתמים ופתרון בעיות
דומיין זה בודק חשיבה אלגוריתמית: ניסוח בעיה, בחירת פתרון, הוכחת נכונות וניתוח סיבוכיות. בבגרות 5 יחידות נדרשים גם מעבר ידני על אלגוריתמים וזיהוי מקרי קצה, לא רק קידוד.
מה נדרש
- קלט, פלט, סופיות ודטרמיניזם: לכל קלט חוקי האלגוריתם חייב לעצור ולתת פלט מוגדר.
- נכונות באמצעות אינווריאנטה: טענה שנכונה לפני הלולאה, נשמרת בכל צעד, ומבטיחה את התוצאה בסיום.
- סיבוכיות זמן ומקום בסימון O: מסתכלים על הסדר הגבוה ביותר כשהקלט גדל, לא על זמן ריצה בשניות.
- רקורסיה: חייבים מקרה בסיס ומקרה רקורסיבי שמצמצם את הבעיה; בלעדיהם אין עצירה.
- חיפוש ליניארי O(n) לעומת חיפוש בינארי O(log n) במערך ממוין; מיון פשוט O(n^2) לעומת merge sort O(n log n).
דוגמה מעובדת
חיפוש בינארי במערך ממוין באורך 16: בכל צעד טווח החיפוש מצטמצם בחצי, 16→8→4→2→1. לכן מספר ההשוואות המרבי הוא 5. הנימוק: אחרי k צעדים נשאר בערך n/2^k, וכשמגיעים לגודל 1 מתקבל k=log2 n. אם n=16, log2 16=4, אך מונים גם את בדיקת האי-שוויון האחרונה ולכן 5. אסור לסרוק את כל המערך - זה O(n), לא O(log n).
מלכודות שמאבדות נקודות
- טעות off-by-one בגבולות הטווח, במיוחד כשמעדכנים low/high.
- בלבול בין O ל-Θ: O הוא חסם מלמעלה, לא בהכרח הדוק.
- הוכחה בדוגמה אחת במקום אינווריאנטה או אינדוקציה.
- שכחת מקרה בסיס רקורסיבי או מקרה של מערך ריק.
- מסירת קוד בלי הסבר מדוע האלגוריתם עוצר ונותן תשובה נכונה.