הצגת המקור של הדף "פסאודו-אקראיות"

[[קובץ:Random digits.png|250px|ממוזער|שמאל|קטע מהספר A Million Random Digits with 100,000 Normal Deviates]]
[[סדרה (מתמטיקה)|סדרה]] '''פסאודו-אקראית''' של מספרים היא כזו שנראית [[אקראיות סטטיסטית|אקראית סטטיסטית]], למרות שנוצר בתהליך דטרמיניסטי לחלוטין שניתן לחזור עליו. הצורך בסדרות כאלה נובע מכך שרבים ממקורות האקראיות הזמינים לבני אדם (כגון הטלת קוביות) מסתמכים על תהליכים פיזיקליים שאינם זמינים ל[[תוכנה|תוכנות מחשב]].

==רקע==
ליצירת מספרים אקראיים יש שימושים רבים, כגון ל[[דגימה (סטטיסטיקה) |דגימה]] אקראית, [[שיטת מונטה קרלו]], [[משחק לוח|משחקי לוח]] ו[[הימורים]]. ב[[פיזיקה]], לעומת זאת, רוב התהליכים הם דטרמיניסטיים, כלומר הם תמיד מייצרים את אותה תוצאה מאותה נקודת התחלה. כמה יוצאי דופן בולטים הם [[דעיכה רדיואקטיבית]] ומדידה קוונטית, שניהם תהליכים אקראיים לפי הפיזיקה שביסודם. כיוון שתהליכים אלו אינם מקורות מעשיים למספרים אקראיים, נעשה שימוש במספרים פסאודו-אקראיים, אשר באופן אידיאלי הם בלתי צפויים בדומה לרצף אקראי באמת, למרות שהם נוצרים על ידי תהליך דטרמיניסטי.

ביישומים רבים, התהליך הדטרמיניסטי הוא [[אלגוריתם]] מחשב הקרוי [[מחולל מספרים פסאודו-אקראיים]], אשר תחילה יש לספק לו מספר הנקרא גרעין אקראי. כיוון שאותו גרעין יניב את אותו רצף בכל פעם, חשוב שהגרעין ייבחר היטב ויישמר מוסתר, במיוחד ביישומי [[אבטחת מידע]], שבהם אי-חיזוי הדפוס הוא מאפיין קריטי.{{הערה|{{cite news |newspaper=[[BBC]] |title=Web's random numbers are too weak, researchers warn |url=https://www.bbc.com/news/technology-33839925|author=Mark Ward |date=August 9, 2015}}}}

במקרים מסוימים, שבהם חשוב שהרצף יהיה בלתי ניתן לחיזוי בעליל, נעשה שימוש במקורות פיזיים של מספרים אקראיים, כגון דעיכה רדיואקטיבית או רעש אלקטרומגנטי אטמוספירי שנאסף מ[[מקלט רדיו]] המכוון בין תחנות.{{הערה|{{קישור כללי|הכותב=George Johnson|כותרת=Connoisseurs of Chaos Offer A Valuable Product: Randomness|אתר=The New York Times|תאריך=June 12, 2001|כתובת=https://www.nytimes.com/2001/06/12/science/connoisseurs-of-chaos-offer-a-valuable-product-randomness.html}}}} השקעת הזמן הדרושה להשגת המספרים הללו מובילה לפשרה: שימוש בכמה מקריאות הפיזיקה הללו כגרעין למחולל מספרים פסאודו-אקראיים.

==היסטוריה==
לפני המחשוב המודרני, חוקרים שנזקקו למספרים אקראיים יצרו אותם באמצעים שונים ([[קוביית משחק|קוביות]], [[קלף משחק|קלפים]], גלגלי [[רולטה]] וכו'{{הערה|שם=ראנד|{{Cite web|url=http://www.rand.org/pubs/monograph_reports/MR1418/index2.html|title=A Million Random Digits|date=January 2001 |publisher=RAND Corporation|access-date=2017-03-30}}}}) או השתמשו בטבלאות מספרים אקראיים קיימות.

הניסיון הראשון לספק לחוקרים אספקה זמינה של מספרים אקראיים היה בשנת 1927, כאשר [[הוצאת אוניברסיטת קיימברידג']] פרסמה טבלה של 41,600 מספרים שפותחה על ידי ה[[סטטיסטיקאי]] L. H. C. Tippett. בשנת 1947, [[מכון ראנד]] יצר מספרים על ידי הדמיה אלקטרונית של גלגל רולטה; התוצאות פורסמו בשנת 1955 כספר בשם A Million Random Digits with 100,000 Normal Deviates {{אנ|A Million Random Digits with 100,000 Normal Deviates}}.{{הערה|שם=ראנד}}

==בתורת הסיבוכיות==
ב[[מדעי המחשב]], [[התפלגות]] היא פסאודו-אקראית מול קבוצה של בודקים אם אף בודק אינו יכול להבחין במידה משמעותית בינה לבין [[התפלגות אחידה בדידה|התפלגות אחידה]].{{הערה| [[עודד גולדרייך|Oded Goldreich]], '''Computational Complexity: A Conceptual Perspective''', [[Cambridge University Press]], 2008}} מושג זה של פסאודו-אקראיות נחקר ב[[תורת הסיבוכיות]] ויש לו יישומים ל[[קריפטוגרפיה]].

בניסוח פורמלי, יהיו ''S'' ו-''T'' [[קבוצה סופית|קבוצות סופיות]] ותהי '''F''' = {''f'': ''S'' → ''T''} קבוצה של פונקציות. התפלגות '''D''' מעל ''S'' היא ε-פסאודו-אקראית מול '''F''' אם לכל ''f'' ב-'''F''' המרחק הסטטיסטי בין ההתפלגויות <math>f(X)</math> ו-<math>f(Y)</math>, כאשר X נדגם מ-'''D''' ו-Y נדגם מהתפלגות אחידה על ''S'', הוא לכל היותר ε.

ביישומים טיפוסיים, הקבוצה '''F''' מתארת מודל של חישוב עם משאבים מוגבלים ואדם מעוניין לתכנן התפלגויות '''D''' עם תכונות מסוימות שהן פסאודו-אקראיות כנגד '''F'''. התפלגות '''D''' מצוינת לעיתים קרובות כפלט של [[מחולל מספרים פסאודו-אקראיים]].

==לקריאה נוספת==
<div class="mw-content-ltr">
* [[דונלד קנות'|Donald E. Knuth]] (1997) ''[[The Art of Computer Programming]], Volume 2: Seminumerical Algorithms (3rd edition)''. Addison-Wesley Professional, {{isbn|0-201-89684-2}}
</div>

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
<div class="mw-content-ltr">
* [[סליל ודהן|Salil P. Vadhan]], [https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-published-Dec12.pdf Pseudorandomness], 2012
</div>

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:פסאודו-אקראיות]]
[[קטגוריה:מדעי המחשב]]
[[קטגוריה:אקראיות]]