בדיקת תכונות מדגמית

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

התחום הוצג לראשונה בשנת 1998, במאמר מאת עודד גולדרייך, שפי גולדווסר ודנה רון.[1]

דוגמה

עריכה

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

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

מקורות

עריכה

הערות שוליים

עריכה
  1. ^ O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its connection to learning and approximation. Journal of the ACM, July 1998, pages 653-750.