אלגוריתמים, מסלולים והוכחת נכונות
הוצג| English | משמעות |
|---|---|
| algorithm/ˈælɡərɪθəm/ | אלגוריתם |
| boundary test/ˈbaʊndəri test/ | מבחן גבולות |
מה יכול להסביר תצפית זו?
- אלגוריתם יכול לעבוד לדוגמה אחת ולהכשל בגבול. הבדיקה חייבת להיות מעוצבת מהמפרט, ולא רק מסלול האושר.
- התחל בחזית. ציין את הכמותות או התכונות שת срав, ואז החלט איזה עדות יכולה להבדיל בין שתי הסברות.
בניית המודל
- אלגוריתם הוא הליך סופי ולא-מסומן למשימה. מעקב (trace) מקליט שינויים במצב. אינוונט של לולאה מתאר תכונה השומרת על עצמה בכל איטרציה ועוזר להצדיק נכונות.
- אלגוריתם: הליך סופי הפותר משימה מוגדרת; בדיקת גבול: בדיקה בגבול של טווח הקלט המותר.
מה צריך להתקיים לפני יישום חיפוש בינארי רגיל ברשימה?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
חיפוש בינארי פולל מחצית מהרשימה על ידי השוואה לאלמנט האמצעי, דבר הנכון רק אם הרשימה מסודרת לפי חוק ההשוואה. ערכים כפולים אינם בעייה, והאלגוריתם עובד בכל אורך רשימה.
התאמו כל מונח טכני למשמעותו המדויקת.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
השתמשו בהגדרות כדי להבדיל בין כמותיות ותהליכים הקשורים זה לזה.
בחר עדים שיכולים לבדוק אותו
- ציין תנאי כניסה ופלטים מצופים. השתמש במקרי גבול, קבוצות ריקות כאשר מותר, ערכים כפולים וערכים לא תקינים. הבדל בין אלגוריתם שגוי לבין מימוש שגוי או דרישה חסרה.
- בצע מעקב חיפוש ברשימה מדומיינת סמוכה קטנה. ציין את הסדר הנוהג במדדים. עבור חיפוש בינארי, עדכן את הגבולות כך שהמרווח הנותר יצטמצם ודחה כניסה לא סמוכה אלא אם כן מיון הוא חלק מהמשימה.
אילו שני הרגלים הופכים את החקירה או הדגם במקרה זה לקבלנים יותר?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ניסוח התנאים וההנחות מאפשר לאחרים לחזור על העבודה בדיוק, ורישום הראיות התומכות מאפשר להם לבדוק את המסקנה. הסתרת תוצאות המולכות מסירה את הראיות שיכולות לערער מסקנה שגויה, ומדידה אחת לעולם לא יכולה להוכיח טענה רחבה יותר.
עבודה על בסיס גודלים ידועים
- ציין את הערכים הידועים ואת יחידות המידה שלהם. בחר בקשר מכיוון שההנחות שלו מתאימות למקרה זה, ולאחר מכן סדר מחדש לפני ההצבה.
- ידוע: חיפוש ליניארי ברשימת שמונה פריטים עשוי לדרוש שמונה השוואות כאשר הפריט המבוקש הוא האחרון או שאינו קיים. הכפלת אורך הרשימה מכפילה את מספר ההשוואות במקרה הגרוע ביותר בתוך מודל זה. חיפוש בינארי מקטין את המרווח בכחצי בקירוב בכל שלב אך דורש מבנה מסודר מתאים.
חיפוש ליניארי סורק את כל 14 הפריטים ללא התאמה. כמה השוואות פריטים מתרחשות? השתמש באותו רצף: כמות ידועה → מודל → קשר → הצבה → יחידה ופרשנות.
חיפוש ליניארי סורק את כל 14 הפריטים ללא התאמה. כמה השוואות פריט מתרחשות?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
התוצאה היא 14 השוואות. ידוע: חיפוש ליניארי על 14 פריטים ללא מציאת התוצאה. כל פריט חייב להיות מושווה לפני שמעדרו בטוח, ולכן מספר ההשוואות הוא 14. חיפוש ללא הצלחה תמיד דורש את האורך המלא של הרשימה.
בדוק את המסקנה ואת הגבולות שלה
- בדיקת דוגמה מוצלחת אינה מוכיחה נכונות לכל הכניסה הקבועה. אל תביא סינטקס פסאודו-קוד ספציפי לקמבריד' לתוך קורס IB ללא מקור קורס.
- חזור לתצפית המקורית. הסבר מה התוצאה תומכת, אילו תנאים היא מניחה, ודרך אחת לבדוק הסבר מתחרה.
דוגמאת בדיקה אחת מוצלחת מוכיחה שמערכת נכונה לכל קלט תקף. טענה זו שגויה: בדיקה עוברת אחת מראה שהמערכת עובדת רק על הקלט הזה. נכונות דורשת נימוק עבור כל הקלטות התקפים או הוכחה - מקרים קיצוניים כמו רשימות ריקות וערכי סף הם בדיוק המקום בו קוד שלא נבדק נוטה לכשל.
אלגוריתמים, מעקב והוכחות נכונות: ציין תנאי כניסה ופלטים מצופים. השתמש במקרי גבול, קבוצות ריקות כאשר מותר, ערכים כפולים וערכים לא תקינים. הבדל בין אלגוריתם שגוי לבין מימוש שגוי או דרישה חסרה.
דוגמית בדיקה אחת מוצלחת מוכיחה שהאלגוריתם נכון לכל קלט תקף.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
מבחן אחד מצליח מראה שהאלגוריתם עובד רק על קלט זה. נכונות דורשת הוכחה לכל הקלטות החוקיות או הוכחה מתמטית - מקרים גבוליים כמו רשימות ריקות וערכי גבול הם בדיוק המקומות בהם קוד שאינו נבדק נוטה לכשל.
תהליך סופי פותר משימה מצוינת: כתוב את המונח הטכני.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
אלגוריתם הוא הליך סופי הפותר משימה המוגדרת.