שאלה (יש לי מחר מבחן)
אין שום מענה מצוות הקורס ולא קיימים סטודנטים, אז אם אפשר את דעתכם על הפתרון שלי. הבעיה: על סרט מגנטי רשומות מיליון מילים בינריות באורך 20 ביט כל אחת. עומד לרשותכם זכרון של 2000 ביטים, הציעו שיטה הסתברותית למצוא מילה בינארית בעלת 20 ביטים השונה מכל המילים שרשומות על הסרט, שתמתמש במספר קטן ככל האפשר של מעברים על הסרט. מה ההסתברות למצוא מילה כזו, בשיטה שהצעתם במעבר אחד על הסרט. הפתרון שלי: עבור על הסרט וספור כמה פעמים מופיע כל ביט מסויים בכל המילים. בסיום המעבר בנה מילה שבה כל ביט דלוק רק אם ההסתברות שהוא מופיע במילה קטנה מ 50%. נאתחל counter ל-1. מכאן והלאה כל פעם עוברים על הסרט ואם המילה קיימת אז נשנה את הביט במיקום ה counter, נקדם את הcounter ונחזור על צעד זה. כמובן שלולאה זו יכולה לרוץ מקסימום log 1000000 פעמים כאשר בזמן זה ה counter אינו חורג מגודל המילה ולכן נמצא מילה שונה בטוח והאלגוריתם יעצור. בנוגע להסתברות, כאן אני בטוח לא סגור על עצמי כי זה לא ממש הסתברות אלא יותר סטטיסטיקה. ישנם 20 ביטים והסיכוי שביט יהיה שווה לביט שבחרנו במילה שלנו הוא מקסימום חצי ולכן הסיכוי שבמילה כל הביטים יהיו שווים הוא 0.5 בחזקת 20, כלומר סה"כ הסיכוי שקיימת מילה כזו בסרט היא: 1000000 * 0.5^20 - במילים: מיליון כפול חצי בחזקת 20.
אין שום מענה מצוות הקורס ולא קיימים סטודנטים, אז אם אפשר את דעתכם על הפתרון שלי. הבעיה: על סרט מגנטי רשומות מיליון מילים בינריות באורך 20 ביט כל אחת. עומד לרשותכם זכרון של 2000 ביטים, הציעו שיטה הסתברותית למצוא מילה בינארית בעלת 20 ביטים השונה מכל המילים שרשומות על הסרט, שתמתמש במספר קטן ככל האפשר של מעברים על הסרט. מה ההסתברות למצוא מילה כזו, בשיטה שהצעתם במעבר אחד על הסרט. הפתרון שלי: עבור על הסרט וספור כמה פעמים מופיע כל ביט מסויים בכל המילים. בסיום המעבר בנה מילה שבה כל ביט דלוק רק אם ההסתברות שהוא מופיע במילה קטנה מ 50%. נאתחל counter ל-1. מכאן והלאה כל פעם עוברים על הסרט ואם המילה קיימת אז נשנה את הביט במיקום ה counter, נקדם את הcounter ונחזור על צעד זה. כמובן שלולאה זו יכולה לרוץ מקסימום log 1000000 פעמים כאשר בזמן זה ה counter אינו חורג מגודל המילה ולכן נמצא מילה שונה בטוח והאלגוריתם יעצור. בנוגע להסתברות, כאן אני בטוח לא סגור על עצמי כי זה לא ממש הסתברות אלא יותר סטטיסטיקה. ישנם 20 ביטים והסיכוי שביט יהיה שווה לביט שבחרנו במילה שלנו הוא מקסימום חצי ולכן הסיכוי שבמילה כל הביטים יהיו שווים הוא 0.5 בחזקת 20, כלומר סה"כ הסיכוי שקיימת מילה כזו בסרט היא: 1000000 * 0.5^20 - במילים: מיליון כפול חצי בחזקת 20.
