בדיקת קבוצה
בסטטיסטיקה ובקומבינטוריקה, בדיקת קבוצה היא הליך בדיקה לזיהוי עצמים במבחן על קבוצות פריטים, להבדיל מבדיקה פרטנית. ממצאים בתחום מחקר זה פורסמו לראשונה על ידי רוברט דורפמן ב-1943,[1] ולתחום זה שימושים מעשיים מגוונים.
דוגמה לבדיקת קבוצה היא בדיקה של קבוצת נורות המחוברות בשרשרת כשידוע שנורה אחת בדיוק פגומה. המטרה היא למצוא את הנורה הפגומה באמצעות מספר הבדיקות המינימלי (כאשר בדיקה היא חיבור לחשמל של קבוצה של נורות לחשמל). פתרון פשטני עשוי להיות בדיקה של כל נורה בנפרד, אולם כאשר מספר הנורות רב, בדיקתן בקבוצות הופכת ליעילה בהרבה. לדוגמה - באמצעות חיבור של חצי מהנורות יחד, ניתן לקבוע לאיזה חצי מהקבוצה שייכת הנורה המקולקלת.
תוכנית לבדיקת קבוצה עשויה להיות פשוטה או מורכבת, והבדיקות הנעשות בכל שלב עשויות להיות שונות זו מזו. שיטת בדיקה שבה בדיקה בשלב הבא מתבססת על בדיקה מהשלב הקודם, נקראת שיטה אדפטיבית, ואילו שיטת בדיקה שבה כל הבדיקות שיבוצעו ידועות מראש נקראת לא אדפטיבית. המבנה של שיטת הבדיקה בשיטה האדפטיבית ידוע כ-"pooling design" או איגום.
לבדיקת קבוצה שימושים מתחומים רבים בהם סטטיסטיקה, ביולוגיה, מדעי המחשב, רפואה, הנדסה, אבטחת מידע וזיהוי פלילי. דוגמה ליישום שעורר עניין מחודש בבדיקות קבוצה הוא פרויקט גנום האדם.
היסטוריה
עריכהבמהלך מלחמת העולם השנייה יזמו שירותי בריאות הציבור האמריקאיים ומערכת השירות הסלקטיבי פרויקט גדול כדי לאתר חולי עגבת בקרב מגויסים. בדיקה פרטנית לעגבת הצריכה נטילות דם רבות, ובדיקה שלהן כדי להוכיח או לשלול קיום עגבת. באותה עת בדיקות כאלו היו יקרות, ובדיקה של כל חייל בצורה פרטנית עשויה הייתה להיות יקרה ולא יעילה. רוברט דורפמן הציע פתרון יעיל לבעיה באמצעות בדיקת קבוצה.[1]
קישורים חיצוניים
עריכה
- Eppstein, David, Michael T. Goodrich, and Daniel S. Hirschberg. Improved combinatorial group testing for real-world problem sizes.