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

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

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

דוגמה

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

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

מקורות

• Eldar Fischer. The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75, 2001, pages 97-126.
• 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.
• R. Rubinfeld and M. Sudan, Robust characterization of polynomials with applications to program testing. SIAM J. on Computing, Vol. 25 (2), 1996, pages 252-271.
• D. Ron. Algorithmic and Analysis Techniques in Property Testing, Foundations and Trends in Theoretical Computer Science: vol. 5, no. 2, 2009, pages 73–205.