בדיקת תכונות מדגמית
בדיקת תכונות מדגמית (באנגלית: Property Testing) הוא ענף מחקר של מדעי המחשב העוסק באלגוריתמים אקראיים אשר תכליתם להבחין בין עצמים שיש להם תכונה מסוימת לבין עצמים הרחוקים מכל עצם שיש לו תכונה זאת. הבחנה בין המקרים האלו היא פתרון מקורב לבעיית ההכרעה הנסובה על זיהוי מדויק של עצמים שיש להם את התכונה האמורה (ודחיה של כל עצם שאין לו את התכונה). היתרון של אלגוריתמים מקורבים כאלו הוא שהם עשויים להיות הרבה יותר יעילים מאלגורתמי הכרעה מדויקים, ובפרט האלגוריתמים המקורבים מסוגלים להסתמך על מדגם קטן של העצם הנבחן.
דוגמה
ניתן להבחין בין רשימה ממוינת (של ערכים שונים) לרשימה אשר רחוקה בכל רשימה כזאת על ידי בחינה של מספר לוגריתמי של איברים בסדרה.
האלגוריתם פועל על ידי בחירה של איבר אקראי בסדרה, וחיפושו בסדרה על ידי ביצוע חיפוש בינארי. אם הסדרה אכן ממוינת וכל איברי שונים - האלגוריתם תמיד ימצא את הערך שנבחר במיקומו הראשוני, אולם אם הסדרה רחוקה מכל סדרה ממוינת - בהסתברות לא קטנה האלגוריתם לא יחזור למיקום ההתחלתי.
מקורות
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, pages 97--126, 2001.
O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM, pages 653--750, July 1998.
R. Rubinfeld and M. Sudan. Robust characterization of polynomials with applications to program testing. SIAM J. on Computing, Vol. 25 (2), pages 252--271, 1996.
D. Ron. Algorithmic and Analysis Techniques in Property Testing, Foundations and Trends in Theoretical Computer Science: vol. 5, no. 2, pages 73–205, 2009.
