פסאודו-אקראיות
סדרה פסאודו-אקראית של מספרים היא כזו שנראית אקראית סטטיסטית, למרות שנוצר בתהליך דטרמיניסטי לחלוטין שניתן לחזור עליו. הצורך בסדרות כאלה נובע מכך שרבים ממקורות האקראיות הזמינים לבני אדם (כגון הטלת קוביות) מסתמכים על תהליכים פיזיקליים שאינם זמינים לתוכנות מחשב.
רקע
עריכהליצירת מספרים אקראיים יש שימושים רבים, כגון לדגימה אקראית, שיטת מונטה קרלו, משחקי לוח והימורים. בפיזיקה, לעומת זאת, רוב התהליכים הם דטרמיניסטיים, כלומר הם תמיד מייצרים את אותה תוצאה מאותה נקודת התחלה. כמה יוצאי דופן בולטים הם דעיכה רדיואקטיבית ומדידה קוונטית, שניהם תהליכים אקראיים לפי הפיזיקה שביסודם. כיוון שתהליכים אלו אינם מקורות מעשיים למספרים אקראיים, נעשה שימוש במספרים פסאודו-אקראיים, אשר באופן אידיאלי הם בלתי צפויים בדומה לרצף אקראי באמת, למרות שהם נוצרים על ידי תהליך דטרמיניסטי.
ביישומים רבים, התהליך הדטרמיניסטי הוא אלגוריתם מחשב הקרוי מחולל מספרים פסאודו-אקראיים, אשר תחילה יש לספק לו מספר הנקרא גרעין אקראי. כיוון שאותו גרעין יניב את אותו רצף בכל פעם, חשוב שהגרעין ייבחר היטב ויישמר מוסתר, במיוחד ביישומי אבטחת מידע, שבהם אי-חיזוי הדפוס הוא מאפיין קריטי.[1]
במקרים מסוימים, שבהם חשוב שהרצף יהיה בלתי ניתן לחיזוי בעליל, נעשה שימוש במקורות פיזיים של מספרים אקראיים, כגון דעיכה רדיואקטיבית או רעש אלקטרומגנטי אטמוספירי שנאסף ממקלט רדיו המכוון בין תחנות.[2] השקעת הזמן הדרושה להשגת המספרים הללו מובילה לפשרה: שימוש בכמה מקריאות הפיזיקה הללו כגרעין למחולל מספרים פסאודו-אקראיים.
היסטוריה
עריכהלפני המחשוב המודרני, חוקרים שנזקקו למספרים אקראיים יצרו אותם באמצעים שונים (קוביות, קלפים, גלגלי רולטה וכו'[3]) או השתמשו בטבלאות מספרים אקראיים קיימות.
הניסיון הראשון לספק לחוקרים אספקה זמינה של מספרים אקראיים היה בשנת 1927, כאשר הוצאת אוניברסיטת קיימברידג' פרסמה טבלה של 41,600 מספרים שפותחה על ידי הסטטיסטיקאי L. H. C. Tippett. בשנת 1947, מכון ראנד יצר מספרים על ידי הדמיה אלקטרונית של גלגל רולטה; התוצאות פורסמו בשנת 1955 כספר בשם A Million Random Digits with 100,000 Normal Deviates (אנ').[3]
בתורת הסיבוכיות
עריכהבמדעי המחשב, התפלגות היא פסאודו-אקראית מול קבוצה של בודקים אם אף בודק אינו יכול להבחין במידה משמעותית בינה לבין התפלגות אחידה.[4] מושג זה של פסאודו-אקראיות נחקר בתורת הסיבוכיות ויש לו יישומים לקריפטוגרפיה.
בניסוח פורמלי, יהיו S ו-T קבוצות סופיות ותהי F = {f: S → T} קבוצה של פונקציות. התפלגות D מעל S היא ε-פסאודו-אקראית מול F אם לכל f ב-F המרחק הסטטיסטי בין ההתפלגויות ו- , כאשר X נדגם מ-D ו-Y נדגם מהתפלגות אחידה על S, הוא לכל היותר ε.
ביישומים טיפוסיים, הקבוצה F מתארת מודל של חישוב עם משאבים מוגבלים ואדם מעוניין לתכנן התפלגויות D עם תכונות מסוימות שהן פסאודו-אקראיות כנגד F. התפלגות D מצוינת לעיתים קרובות כפלט של מחולל מספרים פסאודו-אקראיים.
לקריאה נוספת
עריכה- Donald E. Knuth (1997) The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition). Addison-Wesley Professional, מסת"ב 0-201-89684-2
קישורים חיצוניים
עריכה
- Salil P. Vadhan, Pseudorandomness, 2012
הערות שוליים
עריכה- ^ Mark Ward (9 באוגוסט 2015). "Web's random numbers are too weak, researchers warn". BBC.
{{cite news}}: (עזרה) - ^ George Johnson, Connoisseurs of Chaos Offer A Valuable Product: Randomness, The New York Times, June 12, 2001
- ^ 1 2 "A Million Random Digits". RAND Corporation. בינואר 2001. נבדק ב-2017-03-30.
{{cite web}}: (עזרה) - ^ Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008