בתשובה לשלוסמם, 14/07/09 13:48
 |
|
 |
||
|
||||
 |
מאוד קל למצוא מבחן שמבדיל בין רצף המגיע ממחולל פסאודו-אקראי לרצף אקראי באמת. פשוט עוברים על כל הגלעינים האפשריים למחולל ובודקים אם אחד מהם מייצר את הרצף שבידינו. במילים אחרות: רצף ממחולל פסאודו-אקראי הוא תמיד דחיס לאורך הגלעין. ההוכחה שהאלגוריתם באמת מבחין - תרגיל לקורא. המטרה במחולל מספרים אקראיים היא שלא יתקיים אלגוריתם יעיל שמצליח להבחין. אכן קל לראות שההצעה שלי רצה בזמן אקספוננציאלי באורך הגלעין ולכן לא מדובר באלגוריתם יעיל. |
 |
 |
 |
|
|
|
||
|
||||
|
הבעיה היא אם אין לך את המחולל אלא רק את הרצף. | |
|
|
|
|
|
||
|
||||
|
הרעיון (התיאורטי) במחולל הוא ש*אף אחד* לא מסוגל להבחין בצורה יעילה בין מה שהמחולל פולט למשהו אקראי אמיתי, ובכלל זה גם כאלו שיודעים בדיוק איך המחולל עובד. | |
|
|
|
|
|
||
|
||||
|
השאלה היא מה ההבדל בין משהו אקראי אמיתי למשהו שהמחולל פולט, גם אם יודעים איך המחולל עובד, הסבירות שתוכל להבחין בצורה יעילה הוא תיאורטי בלבד. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |