אני לא בטוחה שאני מבינה את ההגדרה של משפחה אוניברסלית והייתי שמחה אם מישהו יוכל לעזור לוודא את הענין..
ההגדרה שהגדרנו היא:
A family H of hash functions from U to [m] is said to be universal if and only if
for every k1!=k2 in U we have
Pr (h in H) [h(k1)==h(k2)] <= 1/m
והשאלה שלי היא:
האם עבור כל שני ערכים אנחנו מגרילים אקראית פונקציה מהמשפחה ובודקים האם הסיכוי קטן כפי המבוקש
או עבור כל פונקציה נגריל שני ערכים ונבקש שהסיכוי קטן כפי המבוקש
(כלומר מה מגרילים, פונקציה עבור כל שני ערכים, או 2 ערכים עבור כל פונקציה)
מהמצגת זה לא לגמרי ברור, לפי קורמן אני מבינה שהאפשרות הנכונה היא הראשונה.
כמו כן, מבחן 2009 סמסטר א מועד א שאלה 5:
(השאלה מצוטטת מטה למי שצריך)
עם סעיף א אין לי בעיה. הניסוח בסעיף ב מוזר ורציתי לוודא האם הכוונה להתייחס לטבלא הנתונה בדוגמא בתחילת השאלה.
לגבי סעיף ד, בהנחה שהבנתי את ההגדרה נכון ואכן מה שמגרילים הוא הפונקציה מהמשפחה, יוצא ששתי המשפחות לא אוניברסליות.
אם מישהו חושב אחרת אנא תנו צעקה :)
תודה מראש!
שאלה 5 (20 נקודות)
טבלת ה-hash הבאה נבנתה בשיטת linear probing עם הפונקציהh(x)=x mod 10 .
9 8 7 6 5 4 3 2 1 0
98 66 16 43 33 22
א. מצא שני איברים a ו-b שהכנסתם לטבלה, עם אותה פונקצית hash, תגרום למספר גדול ככל האפשר של פניות (probes) לטבלה. תאר/י את תהליך הכנסת שני האיברים לטבלה ואת מצב הטבלה בסיום שתי ההכנסות.
ב. נניח כי מבצעים חיפוש לאיבר אקראי a שאינו בטבלה כך ש Prob[h(a)=i]=1/10 עבור i=0,1,…,9. מה תוחלת מספר הפניות (probes) לטבלה שתבוצענה?
ג. תהא H={h1,h2,…,hk} משפחת פונקציות מ-{0,1,…,u-1} ל-{0,1,…,m-1}. מהו התנאי שצריך להתקיים על מנת ש-H תהיה משפחה אוניברסאלית?
ד. נתונות שתי משפחות של פונקציות H={h1,h2,h3} ו- G={g1,g2,g3}מ-{0,1,2,3,4} ל-{0,1,2}. (לדוגמא, h2(1)=1.) האם H היא משפחה אוניברסאלית? האם G היא משפחה אוניברסאלית? הוכח/י את תשובתך.
4 3 2 1 0
2 1 1 0 0 h1
2 2 1 1 0 h2
2 1 0 1 1 h3
4 3 2 1 0
2 2 0 1 0 g1
1 0 2 0 2 g2
1 2 0 0 1 g3