איך מגרילים מספרים במחשב 3094
כיצד "יוצר" המחשב מספרים אקראיים, ומה הקשר להצפנה?

שפת התכנות הראשונה שהכרתי הייתה BASIC, ואחד מהמשחקים הראשונים שכתבתי היה משחק שבו המחשב מגריל מספר והשחקן צריך לנחש אותו. למרבה הצער, שמתי לב לתופעה מאוד מוזרה במשחק שלי - המחשב תמיד הגריל את אותו המספר. לעומת זאת, אם הגדלתי את טווח המספרים שהוא יכל לבחור, הוא פתאום הגריל תמיד מספר אחר. רק אחרי זמן מה למדתי שכדי להבטיח שהמחשב יגריל מספר שונה בכל משחק, עלי לכתוב בתחילת התוכנית RANDOMIZE TIMER. מה זה בכלל אומר? מה הולך כאן?


תמונת מסך של Qbasic (צילום: Zekko)



שורש הבעיה נעוץ בכך שמחשבים הם יצורים דטרמיניסטיים באופיים - בהינתן המצב הנוכחי של תאי הזיכרון שלהם, הקידוד של החומרה שלהם וכו’, המצב הבא נקבע באופן יחיד. אין "הגרלות" שמבוצעות בתוך המחשב - לפחות, כך אנחנו מקווים; התנהגות בלתי צפויה של המחשב (של המחשב עצמו, לא של תוכנה שמריצים עליו) מעידה על תקלה חמורה בו. אם כן, איך אפשר ליצור אקראיות מהדטרמיניזם הזה? האם בכלל יש משמעות למילה הזו, "אקראיות"?

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

דרך אחת להכניס אקראיות למחשבים היא "לרמות". לחבר את המחשב להתקן פיזיקלי שמודד משהו שנחשב אקראי - פליטת קרינה מאטום כלשהו, למשל. גם לזה איני רוצה להיכנס, למרות שזה בהחלט פתרון לגיטימי שגם משתמשים בו בפועל. פרט לסרבול הטכני יש אפילו חסרון רעיוני כלשהו בהסתמכות על התקנים שהם "אקראיים באמת", שכן, כפי שאסביר בהמשך, לפעמים רוצים דווקא לחזור כמה פעמים על אותה סדרת ערכים אקראיים, ובאותם התקנים, ככל הידוע לי, הדרך היחידה לעשות זאת היא לרשום ולזכור את כל הערכים, וזה אינו רצוי.

הפתרון השני הוא להסתמך על גורמים שאינם בדיוק אקראיים מבחינה פיזיקלית, אבל לכל דבר ועניין נראים אקראיים - למשל, הקלדות על המקלדת. מן הסתם יש חוקיות גדולה למדי בהקלדות על המקלדת (למשל, כשכותבים באנגלית, צפוי שמייד אחרי כתיבת q ייכתב u), אבל אם נמדוד את קצב ההקלדה, ובפרט את מספר השניות שעוברות בין כל הקלדה לזו שאחריה, נראה משהו אקראי למדי (שכמובן, נע בתוך תחום מוגדר). באותו אופן גם תנועות העכבר הן "אקראיות" (חשבו על כך שכל תזוזה, ולו הקטנה ביותר של העכבר, נמדדת; כך שגם אם מזיזים את העכבר מנקודה א’ לנקודה ב’, יש אלפי דרכים שונות לעשות זאת, וזו שנבחרת היא "אקראית"). ישנם עוד גורמים "אקראיים" בריצת המחשב, אבל לא נתעמק ברובם; במקום זה נעסוק במקור הפופולרי והנפוץ ביותר לאקראיות, למרות שהחוקיות שבו גדולה מאוד - השעון הפנימי.

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

מחולל מספרים פסאודו אקראיים הוא אלגוריתם שמקבל כקלט מספר, ומוציא כפלט מספר אחר, "אקראי", שנראה בלתי תלוי במספר שהוא קיבל כקלט. למעשה האלגוריתם הוא דטרמיניסטי, בכך שעבור מספר קלט נתון הוא יוציא תמיד אותו מספר פלט - רק שנראה כאילו אין חוקיות. למשל, עבור שני מספרי קלט קרובים, שני מספרי הפלט יכולים להיות רחוקים (אבל לא בהכרח יהיו רחוקים, שהרי גם זו חוקיות!) - ולהפך. לדוגמה, המחולל הפסאודו־אקראי בגרסה אחת של שפת ג'אווה נותן עבור הקלט 0 את הפלט מינוס 1155484576 (תמיד). עבור הקלט 1 הוא נותן את הפלט מינוס 1155869325.

ברוב התוכניות אנו מעוניינים בסדרה של מספרים אקראיים (כי אנחנו מבצעים הרבה הגרלות). לשם כך זוכר המחולל את הפלט שהוא הוציא בפעם האחרונה שבה הוא נקרא, ובפעם הבאה שבה קוראים לו, פועל על המספר הזה בתור הקלט. כך, המחולל שנתן לנו מינוס 1155484576 זוכר את המספר הזה. אם מבקשים ממנו שוב מספר אקראי, הוא משתמש בו כקלט ונותן מינוס 723955400. בפעם הבאה הוא ישתמש במספר הזה וייתן 1033096058 (הפעם פלוס דווקא), וכן הלאה.

כמובן שהמחולל עדיין זקוק לקלט התחלתי כלשהו לפני שיוכל לייצר מספרים אקראיים שישמשו כקלטים בהמשך - לקלט ההתחלתי הזה קוראים ה”גרעין” (seed) של המחולל. בסדרה שהראינו זה עתה, הגרעין הוא 0. אם מזינים למחולל גרעינים שונים, סדרת הערכים שהמחולל יפלוט תהיה שונה בתכלית; ואם ניקח סדרת מספרים שנפלטה על ידי המחולל ונחפש בה חוקיות - נתקשה מאוד לגלות כזו. כל זה, כמובן, בתנאי שהמחולל שווה משהו. כדי שלא תהיה בסדרה חוקיות ברורה, הכרחי שטווח הערכים שהמחולל מסוגל להוציא יהיה גדול מאוד, ושהוא לא יחזור על עצמו - שהרי, ברגע שבו המחולל מוציא ערך שכבר היה בעבר באותה הסדרה, פירוש הדבר שהוא נכנס ללולאה (כי כאמור המחולל דטרמיניסטי, ולכן המשך הסדרה אחרי המופע השני של הערך יהיה זהה להמשך שלה אחרי המופע הראשון שלו).

כל זה טוב ויפה, אבל נניח שאני רוצה מספר אקראי בין 1 ל-‏6, כלומר הטלת קוביה. מה אני עושה? אני לוקח את הפלט מהפעלה אחת של המחולל, ובמקום להשתמש במספר כמות שהוא (כי כפי שראינו, זה לרוב מספר ענקי, ולפעמים שלילי) אני בודק מה השארית שהמספר הזה נותן בחלוקה ב-‏6. זה יהיה ערך בין 0 ל-‏5, שמתפלג באופן אחיד אם המחולל אכן מוצלח (כלומר, אם אחזור על ההגרלה הזו פעמים רבות, אראה שכל מספר התקבל בערך שישית מהפעמים). נותר לי רק להוסיף 1 לתוצאה. בצורה דומה אפשר לקבל מספר טבעי בכל טווח שהוא; אפשר גם להגריל מספרים "ממשיים" בתחום שבין 0 ו-‏1, פשוט על ידי נרמול - חלוקת המספר האקראי שהמחולל החזיר, במספר המקסימלי שהוא יכול להחזיר. לא כל המספרים בין 0 ל-‏1 יכולים להתקבל בשיטה זו (למשל, לא יתקבלו מספרים אי־רציונליים), אבל ממילא לא כל אותם המספרים יכולים בכלל להיות מיוצגים במחשב בשיטת היצוג הסטנדרטית.

כאן המקום לתאר כמה מחוללים קונקרטיים, אבל לא אעשה זאת, פשוט כי המתמטיקה של מחוללים טובים היא סבוכה וטכנית. אחד המחוללים הראשונים (אם לא הראשון) והפשוטים ביותר הומצא על ידי ג’ון פון נוימן - קח מספר בן n ספרות, העלה אותו בריבוע וקבל מספר עם 2n ספרות (הוסף 0 בתחילת המספר שהתקבל אם יש צורך), וכעת קח את n הספרות האמצעיות בתור הפלט. הבעיה בשיטה החביבה הזו היא שלולאות צצות יחסית מהר. פון נוימן, שמיוחס לו הציטוט "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin", כנראה לא נזקק למשהו מחוכם יותר, אבל לצורכי הצפנה, ואפילו עבור משחקים, זה לא מספיק טוב. באדיבות xkcd, הנה עוד דוגמה למחולל שכנראה לא כדאי להשתמש בו:


מחולל מספרים אקראיים (מקור: xkcd)



כעת אפשר להסביר מהו ה-Randomize timer של בייסיק. כשקוראים בשפת תכנות כלשהי לפונקציה שמחזירה מספר אקראי, לרוב הפונקציה הזו משתמשת במימוש של מחולל פסאודו אקראי זה או אחר. הגרעין של המחולל הזה מאותחל כאשר התוכנית מתחילה לרוץ - השאלה היא לאיזה ערך הוא יאותחל. אם השפה מאתחלת אותו תמיד ל-‏0, מן הסתם תמיד נקבל את אותה סדרה "אקראית". לכן כדי לקבל סדרות שונות בכל הרצה, יש להשתמש במקור שמובטח שתמיד ייתן ערך שונה - והשעון הפנימי של המחשב הוא המקור המושלם לכך. הפקודה Randomize timer מאתחלת את הגרעין של המחולל האקראי לערך שמושג מהשעון; בשפות אחרות יש פונקציה בשם srand שעושה את אותו הדבר. אלא שאין הכרח לאתחל דווקא באמצעות השעות; אפשר לאתחל גם באמצעות ערך מספרי שמועבר על ידי המשתמש עצמו, וכאן נכנס לתמונה אחת ההיבטים החביבים ביותר של מחולל פסאודו אקראי - אפשר לשחזר במדוייק את הסדרות האקראיות שהוא מייצר, מבלי לשמור אותן במלואן. פשוט מכניסים שוב את אותו גרעין, ומקבלים את אותה סדרה. בשביל מה זה טוב?

לפני שנים הייתי מכור למשחק מחשב אווילי בשם Worms, שבו השחקן שולט על צוות תולעים אכזריות שמפצפצות לצוותים אחרים של תולעים את הצורה עם בזוקות, רימונים ושאר מרעין בישין. הקרבות התנהלו בשדה קרב שנוצר באופן אקראי. חלק משדות הקרב היו מוצלחים במיוחד (נניח, הם היו עמוסים בצוקים שאם תולעת עומדת עליהם, אפשר לפצפץ אותה לאינסוף ביתר קלות). איך אפשר, אם כן, לשחזר את אותו שדה קרב? פשוט מאוד - לכל שדה קרב שהוגרל היה כתוב באופן מפורש הגרעין של המחולל הפסאודו אקראי שיצר אותו. כדי לקבל את אותו שדה קרב, כל שהיה נחוץ הוא לכתוב מחדש את הגרעין. כמובן, הגרעין נראה כמו ג’יבריש מאוד ארוך, ולא היה מאוד פרקטי לזכור אותו; אבל אפשר היה להכניס גרעינים משלך, פשוט בתור טקסט באנגלית - מאחורי הקלעים בוצעה המרה של הטקסט למספר - ולראות מה קיבלת. כך למשל, אם הייתי כותב "Alamo" הייתי מקבל דבר אחד (שנוצר בצורה אקראית לגמרי, ויכל להיות מוצלח או לא מוצלח, תלוי במזל), ואם הייתי כותב "Waterloo" היה מתקבל משהו שונה; אבל בכל פעם שבה הייתי כותב אותם, הייתי מקבל את אותו שדה קרב כמו בפעם הקודמת. התעלול נפוץ גם במשחקי מחשב אחרים, כמובן.

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

דוגמה שלישית, דומה ברוחה לדוגמה השניה - כשכותבים תוכנית מחשב, חלק בלתי נפרד מהתהליך הוא מה שנקרא unit testing - הרצת בדיקות "נקודתיות" שבודקות חלקים קטנים וספציפיים בתוכנית. לעתים הבדיקות הללו צריכות להיות אקראיות, שכן המתכנת לא מצליח לחשוב בעצמו על כל המקרים המעניינים. במקרה שבו בדיקה אקראית חושפת תקלה בתוכנית, לעתים קרובות ירצה המתכנת להריץ שוב ושוב את התוכנית עם אותו קלט בעייתי, עד שמתברר מה בדיוק הבעיה ואפשר לתקנה. לכן חשוב שהפלט של הבדיקה, פרט ל”זה וזה נכשל”, יכלול גם את הגרעין שיצר את האקראיות שהובילה לתקלה.

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

האם ניתן להבחין בזמן סביר בין ההגדרה הפורמלית של מחולל פסאודו אקראי לזו המעשית?

פורמט ה-MP3 חולל מהפכה אדירה בכל הנוגע לתרבות ההאזנה למוזיקה. סוד הקסם שלו היה כיווץ שהקטין מאוד את קבצי המוזיקה, עד לסדר גודל של מגהבייט לדקה. זה הפך את שיתוף קבצי המוזיקה לדבר מעשי ונפוץ. המחיר היה פגיעה כלשהי באיכות המוזיקה - MP3 הוא מה שנקרא "פורמט lossy". הכיווץ שהוא מציע מתבסס על זריקה לזבל של חלק מהמידע על הצליל - מידע שבתקווה אינו מורגש בפועל על ידי השומע. כמובן שטענה נפוצה היא שגם בקידודים איכותיים יחסית של MP3 (כלומר, כאלו שזורקים לזבל רק מעט דברים) עדיין ניתן להרגיש בהבדל. האמנם? האם ניתן להבחין בין קובץ מוזיקה "רגיל" ובין קובץ שכווץ באמצעות MP3? איך?

הפתרון הוא כמובן "מבחן האזנה", בדומה למבחני הטעימות שעושות חברות המזון. נותנים למישהו זוג קבצי מוזיקה של אותו שיר ושואלים אותו מה האמיתי ומה המכווץ. לצורך העניין נניח שהקבצים נראים אותו הדבר והם באותו הגודל - למשל, אם כיווצנו אחד עם MP3 ואז המרנו אותו בחזרה לפורמט ששומר את כל המידע, רק שכעת חסר מידע שהיה בקובץ המקורי והוא ממולא על ידי ביטים שלא משנים כלום בפלט הסופי.

כמובן ששומע בעל הבנה בפורמט של קבצי מוזיקה יכול לעבור על המידע שכתוב בקבצים ולבדוק באיזה קובץ יש יותר מידע רלוונטי. ייתכן שניתן לעשות זאת באמת ובתמים, אך לצורך הדיון נניח שזה דורש יותר מדי עבודה (בקרוב יהיה ברור לאן אני חותר עם כל ההנחות הללו). אם כן, מה שהשומע יעשה הוא פשוט להשמיע את שני הקבצים, ולומר מי מכווץ ומי לא. אם הוא לא מסוגל להבחין ביניהם, נצפה שהוא יטעה בערך ב-‏50% מהפעמים, כשחוזרים על הניסוי הזה פעמים רבות; אחרת, נצפה לראות הטייה סטטיסטית לטובת התשובה הנכונה.

אם בניסוי אכן נרשמו 50% טעויות, נוכל להגיד כי סטטיסטית, המאזין לא מסוגל להבחין בין קבצי MP3 ובין קבצי מוזיקה רגילים. אם נרצה ממש לקפוץ להסקת מסקנות, נוכל לטעון כי זה אומר שאין הבדל מעשי בין קבצי MP3 ובין קבצי מוזיקה רגילים, בכל הנוגע לאותו מאזין ספציפי. זו כמובן פרשנות של טענה מתמטית ואפשר לא לקבל אותה; אך לטעמי היא הגיונית בהחלט.

הבה נעבור כעת למספרים פסאודו אקראיים. השאלה המרכזית שעולה, כשמשתמשים במספרים פסאודו אקראיים ליישום כלשהו, היא "האם העובדה שאני משתמש במספרים פסאודו אקראיים ולא במספרים אקראיים באמת משנה משהו?".

ובכן, קשה לתת הגדרה פורמלית ל"משהו" הזה. אמרה ידועה היא שהיעד הנכסף של המתמטיקאי אינו משפט טוב כי אם הגדרה טובה. הגישה שאתאר במאמר הזה מנסה לפרמל את ה"משהו" הזה באמצעות משהו דמוי "מבחין ה-MP3" שתיארתי לעיל. נניח כי אני מהנדס תוכנה שקיבל לידיו "קופסה שחורה" של מחולל פסאודו אקראי שאני רוצה לבדוק את איכותו, וכמו כן יש לי גישה למחולל אקראי אמיתי (נניח, כזה שמבוסס על פיזיקה). מה שאעשה יהיה לכתוב תוכנית שלפעמים עונה 1 ולפעמים עונה 0, כתוצאה של חישוב אקראי כלשהו, ולבדוק אמפירית (על ידי זה שאריץ אותה פעמים רבות) מה ההסתברות שהיא תחזיר 1. אם אגלה שההסתברות הזו שונה כאשר האקראיות של התוכנית נובעת ממחולל "אמיתי", לעומת ההסתברות הזו כשהתוכנית משתמש במחולל הפסאודו אקראי, פירוש הדבר הוא שהמחולל הפסאודו אקראי איננו מוצלח - הנה, מצאנו תוכנית ("המבחין" שלי) שעבורה השימוש במחולל פסאודו אקראי באמת משנה משהו.

כדי להבין את הרעיון שלעיל הכרחי לתת דוגמה. אם כן, נניח שהמחולל שאני מנסה לבדוק הוא המחולל המופלא של xkcd שמחזיר תמיד 4, בעוד שמחולל אמיתי צריך להחזיר את הערכים בין 1 ל-‏6 בהסתברות אחידה. מה תהיה התוכנית שאכתוב? פשוט מאוד - תוכנית שמגרילה מספר בעזרת המחולל, פולטת 1 אם המחולל נתן 4, ו-‏0 אם הוא נתן משהו אחר. מה הולך כאן?

נניח שהתוכנית משתמשת במחולל האקראי האמיתי. מה ההסתברות שלה לפלוט 1? כמובן, 1/6. לכן אם אריץ אותה הרבה פעמים, אספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל מספר שקרוב ל-‏1/6. לעומת זאת, אם התוכנית משתמשת במחולל של xkcd, היא תמיד תחזיר 1, ולכן כשאספור כמה פעמים קיבלתי 1 ואחלק במספר ההרצות הכולל, אקבל 1. ההבדלים כאן ברורים בצורה שאינה משתמעת לשתי פנים.

השאלה המתבקשת כאן היא "איך ידעת לכתוב דווקא את התוכנה הזו ולא, נניח, תוכנה שפולטת 1 אם היא קיבלה מהמחולל 3 או 2?". מן הסתם התוכנית שכתבתי "תפורה" על המחולל הפסאודו אקראי של xkcd, במיוחד כדי להראות בעיה שיש בו (אם כי, שימו לב שהוא מחולל כה גרוע עד שגם התוכנית השניה הזו "תפיל" אותו). עבור מחוללים מסובכים יותר כלל לא ברור שאדע לכתוב תוכנית שיוצרת הבחנה בינו ובין התפלגות אקראית אמיתית; אבל זה שאני לא יודע לכתוב תוכנית כזו לא אומר שהיא לא קיימת. וזו בדיוק הדרישה ממחולל פסאודו אקראי "מתמטי" - שלא תהיה קיימת תוכנית שכזו.

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

אם כן, הסברתי כיצד קובעים שמחולל פסאודו אקראי הוא מוצלח - ובתורת ההצפנה, כדי שמשהו ייקרא "מחולל פסאודו אקראי" הוא צריך להיות מוצלח - אבל טרם הסברתי מה זה בעצם, מבחינה פורמלית, מחולל שכזה. ובכן, זה אלגוריתם דטרמיניסטי שמקבל קלט, ובונה ממנו פלט ארוך יותר, כך שאם הקלט התפלג באופן אחיד, גם הפלט אמור להיראות כאילו הוא מתפלג באופן אחיד, במובן שהוסבר לעיל. כאשר "משתמשים" במחולל הזה, מניחים שיש מקור של אקראיות "אמיתית" שמספק למחולל הפסאודו אקראי את הקלט הקצר - כאמור, בעולם האמיתי אפשר להשתמש בהתקנים פיזיקליים, בשעון המחשב ובדברים דומים לשם כך. מה שחשוב במחולל הפסאודו אקראי הוא ה"ניפוח" שהוא יוצר. איך זה מתקשר למחוללים אמיתיים, שכל הפלטים שהם מוציאים הם מאותו אורך כמו הגרעין הנוכחי? פשוט מאוד - אנחנו חושבים על הפלט הארוך של המחולל הפסאודו אקראי התיאורטי בתור כל הסדרה האקראית שנוצרת מהגרעין, עד שהיא מתחילה לחזור על עצמה. כלומר, גם על מחוללים "אמיתיים" ניתן לחשוב כעל יצורים שמבצעים "ניפוח" של קלט אקראי קצר.

בואו ניקח דוגמה ממש אווילית. נניח שאני מעביר למחולל קלט בן סיבית אחת - או 0, או 1. נניח שעל 0 הוא מחזיר 11 ועל 1 הוא מחזיר 01. זה אומר שיש לו בדיוק שני פלטים אפשריים מגודל 2, ובפרט שהפלט 00, למשל, לא יופיע אף פעם. זו הבעיה הבסיסית של מחולל פסאודו אקראי - מכיוון שהוא מבצע “ניפוח”, ולכל קלט אפשרי יש פלט אפשרי יחיד, הוא לא יכול לכסות את כל מרחב הפלטים האפשריים, ולכן אף פעם לא ייראה אקראי "לגמרי". תמיד אפשר יהיה להריץ אותו על כל הקלטים האפשריים ולראות איזה ערך של פלט אף פעם לא יכול להתקבל, ואז להשתמש בכך כדי להראות שההתפלגות של המחולל היא לא אחידה "באמת" כי היא פוסחת על ערכים. על כן, מעמידים את המחולל במבחן רק עבור ערכים גדולים מספיק של קלט שעבורם לא ניתן לבצע חיפוש ממצה על כל מרחב הקלטים (ההגדרות הפורמליות קצת יותר עדינות ומחוכמות, כמובן; אבל יהיה קשה להסביר אותן כאן בלי הכנה מוקדמת נוספת).

אחת התוצאות המדהימות הראשונות הנוגעות למחוללים פסאודו אקראיים היא שדי במחולל שכל מה שהוא עושה הוא לנפח את הקלט בביט אחד (כלומר, אם הוא מקבל n ביטים כקלט, הוא מוציא n+1 ביטים כפלט - ביטים שיכולים להיראות שונים לגמרי מהקלט שהתקבל) כדי שניתן יהיה לבנות מחולל עם ניפוח פולינומי כלשהו (נניח, מוציא פלט שגדול פי 5 מהקלט). התוצאה הזו מצמצמת מאוד את ה”אתגר” שבבניית מחולל פסאודו אקראי - כל מה שצריך הוא ניפוח שמגדיל בביט אחד. עם זאת, זה לא עזר - עד היום לא ידוע ולו על מחולל פסאודו אקראי אחד. כמובן, קיימים מחוללים רבים שבהם משתמשים בפועל, גם ביישומים קריפטוגרפיים רגישים; אבל אין הוכחה לכך שהם אכן עונים על ההגדרה הפורמלית, ולכן שאלת קיומו של מחולל פסאודו אקראי נותרה בגדר תעלומה.

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

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

כמובן, אלו מכם ששמעו קצת על קריפטוגרפיה בוודאי יודעים שיש שיטת הצפנה בטוחה "באופן מושלם" - הצפנה באמצעות פנקס חד־פעמי. הבעיה עם הפנקס החד־פעמי היא שהוא מאוד בזבזני - כל ביט של המפתח מתבזבז על ביט של ההודעה, וזהו. בהצפנות אולטרה־קריטיות זה מחיר סביר, אבל בחיי היום־יום שלנו אנחנו מעדיפים להחזיק מפתח קטן, קבוע, ולהשתמש בו כדי להצפין כמה הודעות שרק נרצה. זה בדיוק מה שמחולל פסאודו אקראי מאפשר לנו לעשות. הרעיון הוא פשוט להחריד - ניקח מפתח קטן אקראי; נשתמש במחולל כדי "לנפח" אותו לכל אורך פולינומי שנרצה (ההנחה היא שלא נוכל לשלוח יותר ממספר הודעות פולינומי בימי חיינו), ואז נשתמש בפלט בתור "פנקס חד פעמי" - כל הודעה שלנו תוצפן עם חלק מהפלט שטרם השתמשנו בו. זה הכל.

למה זה עובד? שוב, מבלי להוכיח פורמלית אלא רק לתת נימוק על קצה המזלג - אם היה אפשר לשבור את ההצפנה הזו בצורה יותר מוצלחת מאשר אפשר היה לשבור הצפנה שבה המפתח מוגרל לכל הודעה בנפרד (להבדיל מכך שהוא נוצר על ידי מחולל פסאודו אקראי), הרי שזה היה מספק לנו "מבחין" עבור המחולל הפסאודו אקראי. נניח שיש אלגוריתם ששובר את ההצפנה - איך היה פועל המבחין שנובע ממנו? בערך - ממש בערך - הוא היה מצפין משהו בעזרת ה-x האקראי שהוא קיבל, נותן לאלגוריתם ש"שובר" את ההצפנה לעבוד, ואם האלגוריתם הצליח ובאמת שבר את ההצפנה, פולט 1. אחרת, הוא פולט 0. אם באמת השימוש במחולל פסאודו אקראי "החליש" את ההצפנה, אנחנו מצפים שבאופן משמעותי, המבחין שלנו יפלוט 1 בהסתברות גבוהה יותר אם מזינים לו ערכים מהמחולל הפסאודו אקראי, מאשר אם מזינים לו ערכים אקראיים "אמיתיים".

האם קיים משהו דומה בפועל? כמובן. כל צפני השטף פועלים באופן דומה - בונים סדרה פסאודו אקראית של מספרים, ומשתמשים בהם להצפנה בסגנון פנקס חד־פעמי. אין הוכחה פורמלית שזה עובד טוב, אבל כשעושים את זה נכון זה עובד מצויין, כל עוד מי שמשתמש בצופן לא מבצע שגיאות מזעזעות בפרוטוקול שנבנה מעליו. זה כמובן נושא למאמר נפרד.
קישורים
P שונה מ-NP - "עניין של זמן", על מגבלות המחשב לפתור בעיות בזמן. מאמרו של גדי אלכסנדרוביץ'
מה לא יכול המחשב לעשות - מאמרו של גדי אלכסנדרוביץ'
BASIC - Wikipedia
דטרמיניזם - ויקיפדיה
מחולל מספרים פסאודו אקראיים - ויקיפדיה
ג’ון פון נוימן - ויקיפדיה
xkcd קומיקס על מתמטיקה ורומנטיקה
worms - ויקיפדיה
דחיסה מאבדת נתונים - ויקיפדיה
פנקס חד־פעמי - ויקיפדיה
שגיאות מזעזעות באלגוריתם ההצפנה WEP
לא מדויק - הבלוג של גדי אלכסנדרוביץ'
פרסום תגובה למאמר

פרסומים אחרונים במדור "מדע"


הצג את כל התגובות | הסתר את כל התגובות

רק כדי להיות קטנוני... 513104
כשאתה אומר "הכיוון ההפוך אינו נכון - ייתכן ש-P שונה מ-NP אך לא קיימים מחוללים כאלה" - האם אתה יכול להוכיח שזה ייתכן, או שאתה מתכוון רק שאנחנו לא יודעים להוכיח שזה לא ייתכן?
במילים אחרות, האם הכוונה היא ל "הכיוון ההפוך אינו נכון" או ל"הכיוון ההפוך אינו ידוע"?
רק כדי להיות קטנוני... 513109
שאלה טובה. נראה לי ש''הכיוון ההפוך אינו ידוע''.
רק כדי להיות קטנוני... 513113
אפשר להסביר את השאלה? מה זה להוכיח שייתכן?
רק כדי להיות קטנוני... 513114
להוכיח שאין סתירה בין הטענות "אין מחולל פסאודו אקראי" ובין "P שונה מ-NP". הרי ייתכן שהעובדה ש-P שונה מ-NP גוררת בהכרח קיום של מחולל פסאודו אקראי וטרם גילינו את זה.

בכל מקרה, זה גולש לדקויות שאני לא בטוח אם כדאי להיכנס אליהן כאן...
רק כדי להיות קטנוני... 513216
כבר עבר זמן מאז שלמדתי לפסיכומטרי.
יש לנו שתי טענות: A,B.
לדבריך A גוררת את B, אבל לא ידוע אם B גוררת את A.
מה ההבדל בין "ייתכן ש-B נכונה ו-A לא", לבין "אין סתירה בין B לשלילת A"?
אולי מישהו אחר מוכן להיכנס לדקויות?
רק כדי להיות קטנוני... 513222
הבעיה היא שאם A נכונה, אז יש סתירה בין B לשלילת A, פשוט כי שלילת A היא עצמה סתירה. הדקות שאני לא רוצה להיכנס אליה היא שהמשפט המקורי שלי מניח שייתכנו שני "יקומים" שונים - אחד שבו A נכונה, ואחד שבו היא לא נכונה - כשב"יקום" שלנו בדיוק אחד משני אלו קורה.

מן הסתם זה נובע מכך שהמשפט המקורי שלי לא ניסה לטעון טענה מתמטית מדוייקת...
רק כדי להיות קטנוני... 513322
הנה הוכחה שייתכן ש-P שונה מ-NP, אך לא קיימים מחוללים:

או שכן,
או שלא,
מה שבטוח - אולי!
=> ייתכן שזה נכון.
רק כדי להיות קטנוני... 513828
איפה ה-catch?
רק כדי להיות קטנוני... 524158
לפעמים אפשר להוכיח שמשהו ייתכן בלי קשר לאם הוא נכון או לא.
דילברט 513106
לא עדיף? 513134
רק כדי להיות יותר קטנוני... 513117
כדי להגריל מספר אקראי בטווח מסוים, לא כדאי להשתמש בשארית כי השארית בחלוקה במספר שאינו חזקה של 2 אינה מתפלגת באופן שווה (מיודענו ד"ר אור דונקלמן הקדיש לנושא רבע שעה באחת ההרצאות שלו). עדיף לחלק בערך המקסימלי של המחולל ולכפול בערך המקסימלי שרוצים לקבל, כמובן תוך שימת לב לבעיות של איבוד סיביות בחלוקה, מספר הסיביות המקסימלי וכו'.
רק כדי להיות יותר קטנוני... 513118
החכמתי (ומצד שני, לצרכים לא קריפטוגרפיים/קריטיים דומים נראה לי שגם שיטת החלוקה מספיק טובה).
רק כדי להיות יותר קטנוני... 513119
חישוב שאריות זאת עבודה לא נעימה. פעם הייתי צריך לפזר מספרים למספר תאים, ובניתי טבלה של סימני התחלקות בבסיס בינארי (משהו כמו שמתואר כאן תגובה 216062). אחרי שטרחתי להסביר למהנדס איך לממש את העסק, נפל לי האסימון שאני יכול פשוט להגדיר לו ספים, כמספר התאים (פחות 1) ושיבדוק אם המספר נופל בין הספים.

כמו כן, התברר לי בדרך הקשה, שאם תיקח מספרים עוקבים ותעשה עליהם CRC16, הביטים הנמוכים מאוד לא אקראיים.
רק כדי להיות יותר קטנוני... 513132
אפשר הסבר קצר ממה זה נובע?
רק כדי להיות יותר קטנוני... 513133
עכשיו אני רוצה להגריל מספר בין 1 ל-‏6, ולכן אני לוקח את תוצאת ההגרלה x, ובודק את התוצאה של ‎(x mod 6) + 1, שמתפלגת בין 1 ל-‏6 כמבוקש.

אבל נניח, לצורך הדיון, שיש לי מחולל מספרים אקראי חד-ספרתי, המגריל מספרים בין 0 ל-‏9 בלבד. מהמחולל הזה אני אקבל את המספרים 5 ו-‏6 בסבירות של 10%, ואת שאר המספרים בסבירות של 20%, כי יש להם שני מקורות בטווח המספרים של המחולל האקראי, בעוד ל-‏5 ו-‏6 יש מקור יחיד.
רק כדי להיות יותר קטנוני... 513135
ואיך נראים האחוזים אם המחולל עובד על טווח ריאליסטי יותר, וההגרלה היא עדיין של מספר בין 1 ל-‏6?
רק כדי להיות יותר קטנוני... 513137
יותר טוב, כמובן. אם הטווח של המחולל הוא 0 עד ℕ–1, יש תוצאות שמופיעות n פעמים בטווח, ויש תוצאות שמופיעות n+1 פעמים בטווח, כאשר n = ⌊ℕ/6⌋‎. הסיכוי לקבל את ההתוצאות הראשונות הוא n/ℕ, ואת התוצאות האחרות ‎(n+1)/ℕ. לכן היחס בין התפלגות התוצאות שמופיעות n+1 פעמים והתוצאות שמופיעות n פעמים הוא
‎(⌊ℕ/6⌋+1)/(⌊ℕ/6⌋) = 1 + 1/(⌊ℕ/6⌋)‎
אם ℕ=10, אזי ‎⌊ℕ/6⌋ = ⌊10/6⌋ = 1, והיחס יוצא 1:2..
רק כדי להיות יותר קטנוני... 513139
וזה נראה לי יחסית זניח ולכן הרשתי לעצמי להציע את זה במאמר. כמובן, אחרי שראיתי משהו כמו Bug attacks, לא אופתע לגלות שגם את זה אפשר לנצל איכשהו....
רק כדי להיות יותר קטנוני... 513140
>>perl -le 'print 0xffff_ffff % 6 '
3
>>perl -le 'print int 0xffff_ffff / 6 '
715827882

במילים אחרות, אם המחולל מייצר מספרים של 32 ביט, יש למספרים 1-3 סיכוי גדול יותר להיבחר. (גדול בערך ב- 1/715827882 ).

וקטנוניות אחרת:
האם המחוללים המקובלים חייב לעבור על כל המספרים האפשריים לפני שהוא חוזר למספר הגרעין?
(אני לא יודע את התשובה, אבל ליתר ביטחון אני מוסיף אינדקס (או סדרה אחרת) למספרים אקראים כדי להימנע מפיזור אחיד)
רק כדי להיות יותר קטנוני... 513143
נדמה לי שהתייחסתי לזה במאמר - מכיוון שהמחולל הוא דטרמיניסטי, אז אם הגענו פעמיים לאותו ערך x, אז כל מה שיקרה מעתה והלאה יהיה זהה למה שקרה אחרי הפעם הראשונה שבה היינו ב-x - כלומר, "המשחק נגמר" ולא נקבל עוד ערכים חדשים שטרם הוגרלו.
רק כדי להיות יותר קטנוני... 513147
אם ככה, אז הסיכוי לקבל אפס במחולל מקובל עם גרעין אפס תוך פחות מ-N פעולות הוא אפס.
נראה לי קצת בעייתי, אבל מה אני מבין.
רק כדי להיות יותר קטנוני... 513149
באופן כללי מחולל פסאודו־אקראי טוב הוא כזה שיהיה לנו סיכוי נמוך להבדיל בינו לבין מקור אקראי באמת.

בפועל מדברים על טווחי מספרים קצת יותר גדולים. אחרת באמת אפשר להשתמש בשיטות ספירה פשוטות. אבל כשטווחי המספרים גדולים מאוד, גם במחולל אקראי באמת הסיכוי שלך לקבל חזרה על ערך די זניח.
רק כדי להיות יותר קטנוני... 513151
דווקא להיפך. במחולל מספרים אקראי באמת, בהנחה שטווח המספרים הוא 2^32, הגרלת 2^16 ערכים ברצף צריכה לספק בהסתברות של 50% זוג אחד לפחות (אם אני זוכר נכון את פרדוקס יום ההולדת).
רק כדי להיות יותר קטנוני... 513154
אתה זוכר נכון, אבל זה עדיין ''זניח'' (אקספוננציאלי, אם כי עם בסיס קטן יותר).
רק כדי להיות יותר קטנוני... 513155
נניח ℕ=2 (מחולל בינארי)
רק כדי להיות יותר קטנוני... 513160
במחולל שכזה אני מניח שהקלטים והפלטים הם סדרה של אפסים ואחדים, ולא רק ''אפס'' או ''אחד'' בודד.
רק כדי להיות יותר קטנוני... 513194
מכיוון שאתה מזכיר מספרים, שווה לראות מהו חישוב מעשי.

אפשר לקנות היום במחיר סביר מחשב עם דיסק של 250GB, וזכרון של 4GB.

נתעלם לרגע מריבוי הליבות (לעניין המקבול נתייחס בהמשך). היצרץ מצהיר בהמעבד עובד בקצב של משהו כמו "2.5GHz", כלומר: 2.5 מליארד מחזורי שעון בשניה. נניח שהמעבד מבצע מליארד פעולות בשניה.

(באופן כללי: יש הרבה סיבות שיכולות לגרום למעבד לא לעבוד "במלוא הקצב". גם ההגדרה של "פעולה" היא הגדרה מאוד עמומה).

כידוע ‎2^10 זה בקירוב‏1 ‎10^3. כלומר מיליון זה ‎2^20 ומיליארד הם 2‎^30. כמוכן צריך לזכור שנוהגים לזכור נפח זכרון בבייטים ולצורך חישובינו מעניינים דווקא הביטים - כלומר: מספר הבייטים כפול 8 (או תוספת 3 למעריך - הכפלה של מספרים היא חיבור המעריכים).

לכן מבחינת נפח אחסון, הזכרון מספק לנו נפח של ‎2^35 והדיסק: נפח של ‎2^41.

ביממה יש 86,400 שניות, כלומר: בערך 2‎^16. בשנה יש בערך 30 מליון שניות, כלומר בערך ‎2^25 .

לכן אם ניקח ברצינות את ההנחה שלנו על מליארד (כלומר ‎2^30) פעולות בשניה, נקבל חישוב של ‎2^46 פעולות ביממה או ‎2^55 פעולות בשנה.

יש חישובים שאפשר לחלק לכמה חלקים לא תלויים. לדוגמה: "לנסות את כל האפשרויות" - פשוט מקצים לכל מחשב טווח אפשרויות לנסות. במקרה הזה אפשר להשתמש בכל הליבות של המעבד. אפשר גם לקנות עוד כמה מחשבים ולחלק את העבודה. כמובן שיש גבול לכמה שמשיגים מזה. חוות מחשבים עם 64 מחשבים מרובעי ליבות מקדמת אותנו פי 256, כלומר תוספת של ‎2^8 למאמץ המלחמתי.

עד עכשיו דיברנו על מחשבים צנועים במחיר מתאים לכל כיס (ושעוד עשר שנים יכנסו לכל כיס?). בתקציבים קצת יותר רציניים אפשר לבנות או לקנות מחשבים קצת יותר חזקים.

‏‏1 בתחום נפחי הדיסקים מדובר על שיוויון ממש: http://xkcd.com/394/
רק כדי להיות יותר קטנוני... 513152
אם מייצרים סדרה מספיק גדולה של מספרים אקראיים, ההסתברות שאחד מהם יחזור על עצמו לא זניחה.

-----
ובלי קשר, כדאי לקרות חלק מתגובות הקוראים לספר הבא:
בעיקר אהבתי את:

The book is a promising reference concept, but the execution is somewhat sloppy. Whatever algorithm they used was not fully tested. The bulk of each page seems random enough. However at the lower left and lower right of alternate pages, the number is found to increment directly
רק כדי להיות יותר קטנוני... 513150
למה לדעתך זה בעייתי?

(בלי קשר, זכור שאם באמת נוקטים בשיטה של צמצום התחום, נניח על ידי חלוקה ולקיחת השארית, אז אפס יתקבל הרבה מאוד פעמים).
רק כדי להיות יותר קטנוני... 513157
נניח בדיקה של פונקציה המקבלת שלם ומחזירה משהו הקשור אליו. נניח שהמתכנת החרוץ מצא לנכון לשמור במטמון את X התוצאות האחרונות. החלק המשתמש בזכרון המטמון לא יבדק.

וניטפוק עצמי: המחולל שבדקתי משתמש ברגיסטרים של נקודה צפה (המכילים בד"כ יותר סיביות מרגיסטרים של שלמים), ולכן הבעיה לעיל לא תתקים בו.

(אוף, מחשבים עברית קשה שפה)
רק כדי להיות יותר קטנוני... 513161
אני לא בטוח שהבנתי. למה לא ייבדק?
רק כדי להיות יותר קטנוני... 513164
כי אין ערך ב-CACHE עבור הקלט X.

(קצת נמאס לי מהקטנוניות, ומצידי אפשר להפסיק.‏1)
---
1. כאמור - במקרה הבודד שזה הפריע לי‏2, פשוט הוספתי אינדקס לתוצאה.
2. זאת היתה מערכת משובצת בלי FLOATING REGISTERS. המחולל הועתק מאיזשהו מאמר, ועבר על כל הערכים האפשריים ל-INTEGER לפני שחזר על עצמו.
רק כדי להיות יותר קטנוני... 513167
עדיין לא הבנתי מה זה בדיוק X (קלט או גודל של מקום שלוקחים ב-cache?) אבל זה לא משנה - כאמור, אם מפריע לך שיש מספרים שלא מופיעים, צמצם את הטווח ואז מובטח לך שכל המספרים יופיעו, וההתפלגות תהיה פחות-או-יותר אחידה.
רק כדי להיות אפלו עוד יותר קטנוני... 513145
אם כבר, המספרים 1, 2 ו-‏6

מחוללים אקראיים לא חייבים לעבור על כל המספרים האפשריים בטווח לפני סגירת מעגל, אבל הפונקציה חייבת להיות חח"ע ועל, כי אחרת יש ערכים (או שרשראות של ערכים) בעלי סיכוי גבוה יותר מאחרים.
רק כדי להיות אפילו עוד יותר קטנוני... [ת"ט] 513146
אההם, הקטנוניות הורגת אותי.
צ"ל: המספרים 1, 2, 3 ו-‏4, ועם הקוראים סליחה.
רק כדי להיות אפילו עוד יותר קטנוני... [ת"ט] 513148
אמנם 1-4, ועם הקוראים הסליחה.
שגיאות מזעזעות 513136
ככל שעובר הזמן, יש לי הרגשה שחלק מהשגיאות המזעזעות במימוש פרוטוקולי הצפנה (למשל ניפוח ההודעה ע"י ביטים לתיקון שגיאות לפני ההצפנה במקום אחריה, פרוטוקול GSM A5/x) הם שגיאות מכוונות המיועדות להחליש את ההצפנה. כך התוקף (נניח – סוכנות ביון לא קיימת, שלוש אותיות), המכיר את החולשה, יכול לפרוץ את ההצפנה בקלות רבה.

זה שאני פרנואיד לא אומר שלא רודפים אחריי :)
שגיאות מזעזעות 513138
מישהו שמכיר את פרטי עניין ה-GSM (נחש מי...) אמר לי, כששאלתי אותו איך עשו כזו שגיאה מזעזעת, שחומרת ההצפנה "הולבשה" על חומרה קיימת (שכללה את הקוד לתיקון שגיאות). שינוי של הסדר היה גורר הוצאות יותר גדולות, וכנראה שפשוט לא שמו על זה זין.

שגיאות מכוונות להחלשה כנראה יהיו הרבה פחות בולטות. גגל bug attacks להמחשה.
Bug or Feature?‎ 513142
כמו זה? http://www.grc.com/sn/SN-022.htm
שגיאות מזעזעות 513141
נראה לי שאתה קצת מגזים. GSM הוא תקן אירופאי ולא אמריקאי.

(זה שאתה פרנואידי לא אומר שדווקא ה־NSA‏‏1 רודף אחריך)

שגיאות מזעזעות 513162
אתה אופטימי מדי. אתה מקווה שהעולם מנוהל על ידי ממשלה רצינית ומתוחכמת (אם כי מרושעת).

האמת נוראה בהרבה. העולם מנוהל על ידי אידיוטים.
שגיאות מזעזעות 513321
אם האידיוטים נסתדר, החוכמולוגים יגמרו אותנו
נוהל בדיקה 513153
אם המחולל עצמו דטרמיניסטי, תמיד אוכל לקחת את המחולל עצמו ולהשתמש בו כתוכנית הבדיקה, ואז אכשל. למשל, אחולל בתכנית הבדיקה (כלומר, ע"י המחולל) סדרת מספרים , ואבדוק מה ההסתברות שכל איבר בה שווה לפלט המחולל. מובן כי כל האיברים בפלט תוכנית הבדיקה יהיו שווים לפלט המחולל, וזה יהיה סימן לחוסר אקראיות מול מחולל אמיתי.
גם אם כבודק לא ידוע לי המחולל, הרי שתכנית בדיקה כזו קיימת, לא?

מה פיספסתי?
נוהל בדיקה 513156
אין לך את המחולל, אלא רק את הפלט שלו. אם אתה יכול למצוא את החוקיות בפלט, המחולל לא מספיק רנדומלי.
נוהל בדיקה 513159
למעשה, אחת מהדרישות הקשוחות למחוללים (תיאורטיים) היא שהם יהיו עמידים גם בפני מישהו שמכיר אותם.
נוהל בדיקה 513158
במאמר קצת רימיתי - בהתחלה הצגתי את העניין כאילו המחולל זוכר את הפלט שלו ומשתמש בו בתור גרעין חדש בהפעלה הבאה. בהגדרה הפורמלית של מחוללים (ואני מניח שגם בחלק מהמימושים) זה לא כך - הגרעין הוא קלט, שהפלט עבורו הוא סדרה אחת ארוכה ואקראית לכאורה, שלא מקיימת תכונה כמו "אם מזינים את החצי הראשון של הסדרה למחולל מקבלים את החצי השני" וכו'.

לכן, אם אתה מחולל סדרת מספרים, זה עדיין לא עוזר לך מיידית - אתה צריך לגלות איכשהו מה הגרעין שיוצר אותה. אמנם, אם תמצא את הגרעין, תיווכח מייד בכך שהסדרה שקיבלת כנראה אינה אקראית "באמת" אלא נוצרה מהמחולל; הבעיה היא שמרחב החיפוש הוא גדול מאוד, כך שהבדיקה שאתה מציע אינה יעילה.
שאלה לאיילות 513175
רק לי יש הרגשה שמעל דיונים כאלה מתנוסס שלט: "הכניסה לגברים בלבד"?
שאלה לאיילות 513178
גם לי יש בעית הבנה רצינית עם רב החומר, איני תולה זאת במיני הביולוגי.
אגדת שלושה וארבעה, אולי חמישה 513181
לא ל*כל* הגברים, תגובה 222192 :-]
שאלה לאיילות 513182
למה? אני מקווה שאת לא רומזת שהנושא עצמו בלתי מובן לנשים... (הוא לא, ויעידו על כך הנשים שאני מכיר ועוסקות בו).
שאלה לאיילות 513427
אכן יש נשים שמבינות.
למעשה אחת מהתורמות הגלודות לתחום היא שפי גולדווסר [ויקיפדיה].
היא ממכון וויצמן כך שיתכן והיא אפילו תשתתף פה בדיון...
שאלה לאיילות 513489
נכון שיש נשים שעוסקות בנושא ויש גם את הפרופסורית ממכון ויצמן. יש גם נשים מתאגרפות ונשים שמרימות משקולות, אבל תסכים איתי שהן מיעוט שבמיעוט מכלל המין הנשי. אני לא באתי למתוח ביקורת על עצם פרסום המאמר כי כעיקרון אני בעד פרסום מאמרים בכל נושא אפשרי באייל, רק סיפרתי על התחושה הבודדת שהיתה לי כשנכנסתי לדיון הזה, ומאז לא נכנסתי כך שהכל בסדר מצידי, ובין כה יש פה משהו בשביל כל אחד. אז לבינתיים ניפרד כחברים.
שאלה לאיילות 513503
אני לחלוטין לא מסכים. כלומר, ברור לי שהעוסקים בנושא הם באופן כללי מיעוט שבמיעוט מכלל בני האדם, אבל אני לא חושב שהנשים הן מיעוט חריג. אין ספק שבעבר הנשים היו מיעוט שבמיעוט, אבל זאת מסיבות חברתיות מפגרות, לא בגלל שלנשים אין יכולת להבין ולהתעניין בדברים כאלו. נראה לי בשנים האחרונות המגמה היא של שיפור מתמיד, למרות שהדרך עוד ארוכה.

אגב, אפשר לנהל דיון ארוך ומעניין על השאלה מדוע לדעתך את ''נרתעת'' (אם זו המילה) מהנושאים הללו.
שאלה לאיילות 514290
לא יתכן שיכולתן של הנשים להבין ולהתעניין בדברים כאלו פחותה משל גברים באופן מולד, ולא רק מסיבות חברתיות?
שאלה לאיילות 514309
בתיאוריה? בוודאי שכן.
בפועל? ברור עובדתית שנשים מסוגלות להבין ולהתעניין בתחום לא פחות מגברים. השאלה היא רק סטטיסטית - איזה אחוז מהנשים מסוגל לכך (הרי גם לא כל הגברים מסוגלים לכך). כאמור, ההתרשמות האישית שלי מהאנשים שאני פוגש על בסיס יומיומי היא שלא מדובר במיעוט זניח בהשוואה לגברים.
שאלה לאיילות 514311
יוצא לך גם לצאת מהטכניון? :-)
שאלה לאיילות 514316
כן, ובחוץ אני לא פוגש לא גברים ולא נשים שמגלים עניין בנושאים הללו.
סליחה על החוצפה 514321
מה עם בלוג לימודי להדיוטות?
סליחה על החוצפה 514325
אני לא בטוח שהבנתי את השאלה.
סליחה על החוצפה 514326
אתה תורם הרבה בויקי, למה שלא תיזום בלוג היכרות בנושא המחשב, נראה שרב החומר כבר קיים באתרים שונים ובויקי, מי שיעשה משהו מסודר, יעזור רבות למאותגרים.
(ושוב סליחה על החוצפה - לבקש מאחר להתנדב).
סליחה על החוצפה 514331
אתה מתכוון למשהו כמו http://gadial.blogli.co.il/
תודה רבה! 514333
היפ היפ היפ! הוריי!
שאלה לאיילות 514398
לאחר עלעול בנתונים (+סיור בונוס שלא בטובתי בפקולטה המקומית למתמטיקה), אכן דווקא אחוז הנשים בלימודי מתמטיקה גבוה יחסית (34% בטכניון, 20% בתארים מתקדמים) לעומת אחוזן בתחומים 'גבריים' אחרים כמו פיזיקה (17%) או הנ' חשמל (13%).

שאלה לאיילות 514400
ושוב, חשוב להבין שיש מרכיב חברתי *לא זניח* שגורם לכך שהתחומים הללו דלים יחסית בנשים. בפרט, סביב הנדסת חשמל יש סטיגמות מכאן ועד להודעה חדשה (כמובן, שהרי הנדסת חשמל דורשת יכולות גבריות להפליא כמו היכולת לטפס על עמוד חשמל כשטסטר בין שינייך).
שאלה לאיילות 514403
לפחות לגבי חלק מהפיזיקאים והחשמלטורים הנסיונאים, התיאור עם העמוד והטסטר, בקירוב מסדר ראשון, לא חוטא בהרבה למציאות.
לגבי המרכיב החברתי, לא על זה נסוב השרשור (לאור סירובה של איילת מאחרת להרים את הכפפה שהשלכת לעברה). על מה כן נסוב השרשור? לא יודע, מה שמהווה עילה טובה לחתום את ההודעה.

זהו שמי וזו חתימתי וכל דבריי מניפולציה.
שאלה לאיילות 514407
הנקודה היא שאי אפשר להתעלם מהמרכיב החברתי כשמביאים אחוזים כלשהם.

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

בענין אחר: באופטיקה למשל ביצוע מחקר באקדמיה ‏1 מחייב דה פקטו עיסוק ידני בלתי פוסק ברכיבים אלקטרוניים ואופטיים ובנסיון לתקן את המערכת שמורכבת מהם. עבודה שמזכירה בסגנונה תיקון מכשיר וידאו מקולקל.
לדעתי, אין זה מקרה שאפילו בתוך הפיזיקה והנדסת החשמל הגבריים בדמוגרפייתם ממילא, אחוז הנשים באלקטרו-אופטיקה הדורשת לכלוך הידיים בולט בנמיכותו (ושבהנדסת מכונות היו מתים לאחוז הנשים שבשני אלה).

אנקדוטה השווה את משקלה בקליפות השום: לא מזמן חזיתי בשני מסטרנטים לפיזיקה מתקשים לתפעל ניסוי שכלל חימום מים בקומקום. שאלתי בהיתול "נכון שאתם תיאורטיקנים?", והנקבה שבהן השיבה שהיא דווקא נסיונאית. שאלתי איך היא עושה ניסויים [כשהסבטקסט הוא "עם כזה חוש טכני גרוע"] והיא השיבה, לתדהמתי, "בשביל זה יש לי את איקס" (כאשר איקס הוא שמו של חוקר אחר שעובד איתה).

1 לא יודע מה קורה מחוץ לה בינתיים.
שאלה לאיילות 514473
לא יודע באקדמיה, בתעשיה מהנדסי כמיה הם מהנדסים שמרבים ללכלך את ידיהם. למרות זאת אחוז הנשים בפקולטה להנדסה כמית הוא מהגבוהים בין הפקולטות ההנדסיות בטכניון.
שאלה לאיילות 514476
כשאתה כותב "ללכלך את הידיים", למה אתה מתכוון? אני השתמשתי במונח רחב מדי ובהשאלה, והתייחסתי ספציפית לסוג עבודת הכפיים שתיארתי לפני כן: עבודה ידנית עם רכיבים מכניים ואלקטרוניים.
ידוע לי מכלי ראשון שכימאים מלכלכים את הידיים, מילולית ומטאפורית. עדיין מדובר בז'אנר אחר של עבודת כפיים.
שאלה לאיילות 514478
לא, לא, אני לא מתכוון ללכלוך ידיים במעבדה. לא התכוונתי לכימאים, אלא למהנדסי כמיה. כאלו שמסתובבים במתקני ייצור, מטפסים על ראקטורים ועל עמודות זיקוק, עובדים עם משאבות ומחליפי חום.
שאלה לאיילות 514488
ובין האנשים שמסתובבים במתקני הייצור, מטפסים על הראקטורים, ועובדים עם המשאבות ומחליפי החום, האם אחוז הנשים גבוה בהתאמה לאחוזם בלימודים?
שאלה לאיילות 514512
לא. אכן תמצא בין מהנדסות הכמיה יותר מאשר בין מהנדסי הכמיה הגברים את הפונים לעבודה בחברות ההנדסה, במשרדי התכנון או לקורס קאוצ'ינג, ועדיין:
1. כמות המהנדסות המסתובבות במתקני היצור גדול מהצפוי בהתאם לסטריאוטיפ.
2. אחוז הסטודנטיות בפקולטה להנדסה כמית גדול מאלו בפקולטה להנדסת חשמל.
שאלה לאיילות 514543
מדוע אתה מעדיף לכתוב כמיה ולא כימיה, ואיך אתה מבטא את המילה הזו?
שאלה לאיילות 514544
חסכון בפונטים‏1, ואותו דבר.

__
1 אני מהדור שבו פונטים היו כסף.
שאלה לאיילות 514545
אז למה "כימאים" ולא "כמאים"?
שאלה לאיילות 514546
בגלל האיום הצפון בזה.
שאלה לאיילות 514548
דוגמה דומה שמסתובבת לי בראש ואין לי מושג מה הרלוונטיות שלה לדיון: עובדים ועובדות בתחנות דלק.
שאלה לאיילות 514507
בביקור היחיד שלי במתקן מהסוג הזה (חיפה כימיקלים) נדמה היה לי שראיתי הרבה יותר גברים מנשים, והייתי מנחש שמתוך המסלולים האפשריים למהנדס כימי, הנשים מבכרות את אלו שלא דורשים מעשים שכאלו. אבל זהו ניחוש לא מבוסס, כמובן. מה שכתבתי היה רק על סמך מה שאני מכיר.
תירוץ דחוק שאני יכול לתת הוא שאולי נשים שהולכות ללמוד הנדסה כימית לא יודעות את הגורל הפרולטרי שמצפה להן בסוף המסלול (כמו שמי שהולך ללמוד מדמ''ח חושב לרוב שהוא ילמד לתכנת, מי שהולך ללמוד חשמל שהוא הולך ללמוד להרכיב מעגלים, ומי שהולך ללמוד פיזיקה שהוא הולך ללמוד משהו שיעזור לו בחיים).
שאלה לאיילות 514475
"לדעתי, אין זה מקרה שאפילו בתוך הפיזיקה והנדסת החשמל הגבריים בדמוגרפייתם ממילא, אחוז הנשים באלקטרו-אופטיקה הדורשת לכלוך הידיים בולט בנמיכותו.."

למה אתה מתכוון? שנשים הרבה יותר שונאות ללכלך את הידיים מגברים?
שאלה לאיילות 514477
אני מתכוון שנשים נמשכות הרבה פחות מגברים לסוגים מסויימים של עבודה פיזית (למשל בניית/תיקון מכשירים מכל הסוגים). המשפט עובד בהחלט גם לכיוון ההפוך. ביולוגים צריכות לעשות לפעמים דברים לא נעימים (כמו לגלח ערוות חולדה, ובדרך לגרום לה בטעות לאורגזמה), וזה תחום שלנשים אין בעיה איתו.
שאלה לאיילות 514413
איך זה לעומת הדרישות מהביולוג הנסיונאי?
שאלה לאיילות 514464
כמו ההבדל בין הכנת מרק לתיקון מחשב.
(זו תגובה רצינית, למען הסר כל ספק)
אני מאשים 513504
כמי שחשב עצמו לדביל מוחלט בנושא, כל שנות ביה"ס, וגם כיום אינו יודע כמעט כלום על הנושא, אני מאשים את המורים הקשים שלרוע מזלי נפלו בחלקי. בשנים האחרונות (20?)החלו לצאת לאור בעברית הרבה ספרי מדע פופולארי המציגים את המתימטיקה בצורה קלה ולא מפחידה,(סיימון סינג, יאן וואטסון, ג'ון פאולוס (?) ועוד). אם הספרים האלה היו מצויים בימי לימודי התמונה היתה אחרת.
אני ממליץ לכל הסובל מ"חרדת המספרים" להתקרב לנושא בדרך זו,
לא תלמדי כך מתמטיקה , אבל תלמדי את מושגי היסוד ואת הדרך להסתכל על הנושא ללא פחד.
ממליץ גם להורים לתלמידים.
ספר מעולה: "ההיסטוריה של המתימטיקה"
הוצאת האוניברסיטה המשודרת, שני חלקים.
אני מאשים 513508
לדעתי האינטרנט גם מחולל מהפכה בנושא (בילדותי גיליתי את ''מתמטיקה'' של טיים לייף, אבל בהסתכלות לאחור זהו ספר לא ברור, ומתורגם מוזר. אני זוכר עד היום את המבוכה שגרמו לי המילים ''מלגו ומלבר'').
אני מאשים 513512
מצאתי פעם את הספר בערימת זבל, באותו הזמן כבר לא היה בו מה לחדש לי, אך בהיותי ביבלומניאק שמרתי אותו כדי לתתו בעתיד.
לאחד מחברי יש ילד שהתגלה כמחונן ונשלח לחוגים בויצמן, כשהבאתי לו את הספר, רטן והתלונן: אני טוב במתימטיקה, זה לא אומר שאני אוהב את זה. אביו ירד עליו: תעיין קודם בספר ואל תפסול מראש.
הנער שמע לו והחל לדפדף, אחרי רבע שעה שמענו צעקה מחדרו: מה?! לא יכול להיות!
הילד הפך לחוקר, היום הוא בצבא ב******
הספר עשה את שלו.
אני מאשים 513513
יפה.
למי שקורא אנגלית, ספר קאלט:
נראה לי שאתה טועה 514291
<קרש>
לדעתי האינטרנט מחולל רק פסוודו-מהפכה בנושא.
<קרש>
אני מאשים 513510
לא כל כך אהבתי את ''ההיסטוריה של המתמטיקה''. מה שכן, אני ממליץ לכל מי שמפחד ממדעי המחשב התיאורטיים על ''אלגוריתמיקה'' של דוד הראל (או על הגרסה המרוככת, ''המחשב אינו כל יכול'').
שאלה לאיילות 513490
גדי נמנה על אילו שמקווים שהנושא המדובר אינו בלתי־מובן גם לאילו שאינם נמנים על המין הנשי (הצלחתי לסבך מספיק?).
שאלה לאיילות 513892
נו, ומה רע אם תיכנסי לדיון הזה ותכירי גבר נחמד? :-P
שאלה לאיילות 513899
אני לא רואה שלט כזה. מצד שני, שלטים כאלו לא עצרו אותי אף פעם :-P

(מה שלי היה מוזר הוא שבבית הספר הייתי גרועה במתמטיקה, אבל מחוצה לו אני בכיף יכולה לעקוב אחרי דיונים כאלו או אחרים על מתמטיקה/אלגוריתמיקה. בוז לבית הספר!)
כיוון הסמיילי 513901
(בלי שום קשר לנושא המקורי. וכן, זה הפריע לי קצת, למרבה הפלא)

שוש, אני חושב שלך אפשר להעיר: p ו־P אינם תווים שמתהפכים. לכן צריך להשתמש בתו בכיוון ההפוך בעברית. כלומר :-q

ולקוות שזה ישאר בכיוון הנכון:

:-q
ואוו - זאת התגובה הכי off-topic שראיתי אי פעם באייל. 514199
קבל מברוק (דמיין כאן U+263A).
שאלה לאיילות 514342
במתמטיקה היכולת לעקוב אחרי דיון אינה מתרגמת היטב ליכולת להבין את החומר ולישם את ההבנה.
שיטה פרקטית להבחנה באקראיות 516018
לאחר נסיונות מפרכים עם מחוללים פסבדו אקראיים מובנים בשפה (בעיקר ב VB) התברר לי שהמחוללים הנ"ל אינם אקראיים לגמרי - כלומר לא עונים לגמרי על הציפיות מרצף אקראי. (מה שיצר אצלי סטיות במחקר, ובלגן שלא תרצו לשמוע עליו).
שיטה פרקטית יעילה להבחנה שמחולל הוא באמת פסבדו אקראי הוא יצירה באמצעותו רצף ארוך של קובץ בינארי, ואז לנסות לכווץ אותו באחד מתוכנות הכיווץ הנפוצות. אם הקובץ לא יתכווץ במימדיו יש יסוד להניח שהתפלגות איבריו היא אקראית, כי האלגוריתמים של תוכנות הכיווץ פועלים על טבלאות המנצלות תופעות לא אקראיות.
שיטה פרקטית להבחנה באקראיות 516019
אני דווקא רוצה לדעת אם גם מחוללים אלה מחוללים בכרמים בכלי לבן שאולים.
שיטה פרקטית להבחנה באקראיות 516020
כן, אבל אני חושב שאורך הטבלאות הללו הוא מוגבל. נדמה לי שהיתה הרבה ביקורת על הטכניקה שאתה מציע. כרגע אני מצליח למצוא רק את זה: http://www.cscs.umich.edu/~crshalizi/notebooks/cep-g...

אבל אני זוכר במעורפל מאמר סטטיסטי שעושה חוכא ואיטלולא מהטריק הזה. אני אפילו זוכר מקרה הפוך - מישהו השתמש בסימולציה שלו כאבן בוחן לטיב של מספרים אקראיים: http://www.worldscinet.com/journals/ijmpc/07/0703/S0...

כל מי שאי פעם התעסק במונטה קרלו באופן פסבדו רציני מכיר את המשפט מNumerical Recipes :
"be very , very suspicious of a system-supplied rand()"a
ומייד אחר כך
If all scientific papers whose results are in doubt because of bad rand()s were
to disappear from library shelves, there would be a gap on each shelf about as
big as your fist.
(מתוך http://www.fizyka.umk.pl/nrbook/c7-1.pdf)

אם הכל נכשל אפשר תמיד לנסות את "אם כל המחוללים":
שיטה פרקטית להבחנה באקראיות 516022
ליתר דיוק: אם הקובץ יתכווץ, הוא לא אקראי‏0. המסקנה ההפוכה לא בהכרח נכונה בגלל שגם תוכנת כיווץ יעילה לא יודעת למצוא את כל סוגי ה"מידע" או "סדר".

התפלגות האיברים היא רק מבחן פשוט אחד לאקראיות. היא לא תבחין במקרה הפשוט של הרצף 0, 1, 2, 3, 4, ... (וכשמגיעים למספר המקסימלי חוזרים ל־0. לדוגמה: אם מסתכלים על בתים אז אחרי 255 חוזרים לאפס). למעשה יש שיטות קידוד שבהן ההתפלגות האחידה היא דרישה בסיסית ללא קשר לשיקולי "אבטחה".

0 ליתר דיוק: "בהסתברות גבוהה". כלומר: אם אנחנו מקבלים כמה דגימות של הפלט של המחולל הנ"ל וכל אחת ואחת נדחסת, אז או שהיה לנו מזל ממש גרוע או שהמחולל אכן לא טוב.

ואגב, למיטב ידיעתי ההכללה שלך על "מובנים בשפה" לא ממש נכונה.
שיטה פרקטית להבחנה באקראיות 516085
כשכתבתי התפלגות לא התכוונתי לכמות המספרים מכל סוג, (אגב בקובץ בינארי מופיעים כמובן רק 0,1) אלא התכוונתי על כל מבחן שתעלי בדעתך. (למשל אם קיימת הסתברות גבוהה במיוחד שנמצא את התנך נוסח קורן רשום איפה שהוא בקובץ האקראי , אז אני מצפה שנמצא אותו שם - אגב חשבתם על זה שהתנך רשום ככתבו איפה שהוא בפאי?)
חוצמיזה הרצף הפשוט של 0,1,2,3,4 יתכווץ כדבעי
שיטה פרקטית להבחנה באקראיות 516089
לגבי הטענה על התנ''ך בפאי, אף אחד לא יודע אם זה נכון או לא. אנשים משערים שפאי הוא מספר נורמלי ובמקרה הזה הטענה שלך נכונה, אבל (למיטב ידיעתי, נכון להיום) לא ידועה הוכחה להשערה זו.
שיטה פרקטית להבחנה באקראיות 516091
הסיכוי קצת יותר גבוה, מכיוון שיש הרבה שיטות לקודד את התנך.

לדוגמה, אם הקידוד יהיה מספר ה־ISBN, הסיכוי הופך פתאום להיות טוב למדי.
שיטה פרקטית להבחנה באקראיות 516101
ואם הקידוד הוא 1 אז בכלל!
שיטה פרקטית להבחנה באקראיות 516093
כמובן שהבעיה היחידה היא שאין מספיק זמן להריץ "כל מבחן שתעלי בדעתך" :-(
שיטה פרקטית להבחנה באקראיות 516323
אם הקלט הוא סופי (ואורכו n) אז יש מספיק זמן.
אם נגדיר פלט אקראי כפלט שלא ניתן ניתן לכיווץ - כלומר לא קיים אלגוריתם ליצירת הפלט שאורכו קצר יותר מהפלט. כל שעלינו לעשות הוא לעבור על כל האלגוריתמים (העוצרים) מאורך n-1. (אם אני לא טועה - עבור כל אלגוריתם לא עוצר מאורך סופי קיימת הוכחה שהוא לא עוצר)
שיטה פרקטית להבחנה באקראיות 516324
וכמה אלגוריתמים כאלו יש? (סדר גודל)
שיטה פרקטית להבחנה באקראיות 516340
2 בחזקת n-1
שיטה פרקטית להבחנה באקראיות 516326
בכל מקרה קיומו של אלגוריתם כזה תלוי במודל החישובי, ואין רצף שיענה לתנאי שלך בכל המודלים ביחד.
שיטה פרקטית להבחנה באקראיות 516329
ליתר דיוק: השאלה שבאמת מעניינת אותנו היא לא "האם אפשר להבחין‏17 בין הפלט הזה לבין רעש אקראי?" אלא "האם אפשר להבחין‏17 בין הפלט הזה לבין רעש אקראי בזמן סביר?".

המושג התאורטי (שוב: תאורטי. לא מעשי. אבל במקרה הזה כבר יש לו קשר למציאות) המקובל לגבי "זמן סביר" הוא זמן ריצה פולינומי. כלומר זמן הריצה גדר רק כפונקציה פולינומית של N ולא משהו יותר גרוע מהסוג של פונקציה מעריכית. ר' לדוגמה חישוב יעיל [ויקיפדיה].

באמת קל לראות‏23 שיש דרך פשוטה אך עם זמן ריצה מעריכי להבדיל בין הפלט של האלגוריתם שלנו לבין רעש אמיתי (עם כמה הנחות סבירות על האלגוריתם שלנו).

17 בהסתברות גבוהה מספיק. לדוגמה: יש לנו מבחן שתופס רצף לא אקראי בהסתברות מסדר גודל של חצי ואחנו יכולים לחזור עליו בצורה בלתי־תלויה (כלומר: כשנחזור עליו שוב ההסתברות לתפוס רצף לא אקראי היא שוב מהסתברות חצי. ע"י מספיק חזרות אנחנו יכולים לקבל הסתברות טובה כרצונינו.

23 בעברית: שיעורי בית
שיטה פרקטית להבחנה באקראיות 516334
לכל קלט קיים אלגוריתם שמכווץ אותו לתו "1" בצורה שניתנת לשחזור אחר כך; כמובן שאותו אלגוריתם כנראה יפעל בצורה לא משהו על קלטים אחרים.

פרט לכך, חסם על אורך הקלט לא נותן לנו חסם על גודל הקידוד של האלגוריתם; בכלל, כל האלגוריתמים שאותם אנחנו מבינים בתור "סבירים" (כלומר, ניתנים להרצה על מחשב אמיתי) הם בעלי קידוד סופי, ויש רבים כאלו שאין לנו מושג אם הם עוצרים או לא. אולי התכוונת לומר שאם אלגוריתם יכול לעצור רק על מספר סופי של קלטים, אז אפשר להכריע, בהינתן קלט, האם האלגוריתם יעצור עליו או לא.
שיטה פרקטית להבחנה באקראיות 516359
לא הבנתי במה אנו חלוקים.
נתתי דוגמא איך ניתן תיאורתית לבדוק בזמן סופי (אמנם לא בצורה מעשית) האם סדרה כלשהי מאורך n היא אקראית.

למען הנוחות נדבר על אלגוריתמים שלא מקבלים כל קלט אלא מייד מייצרים לנו סדרה מאורך n. (הרי תמיד ניתן להכניס את הקלט כחלק מהקוד)
מבחינה תיאורתית ניתן בזמן סופי לעבור על כל האלגוריתמים העוצרים שאורך הקידוד שלהם קטן מ n ולבדוק האם אחד מהם פולט את הסדרה האקראית שלנו באורך n. (לגבי השאלה איך נידע אם אלגוריתם הוא אלגוריתם עוצר או לא, אמרתי, שכפי הזכור לי עבור כל אלגוריתם שלא מקבל קלט קיימת הוכחה אם הוא עוצר או לא (קיימת זה לא אומר שקל למצוא אותה, אבל אם היא קיימת ניתן לעבור על כל ההוכחות עד שנמצא אותה) ולכן אפשר לערוך רשימה של כל האלגוריתמים העוצרים מאורך n)
אם מצאנו אלגוריתם כזה אז הסדרה מתכווצת ולכן לא אקראית (על פי הגדרה) אחרת היא אקראית.
שיטה פרקטית להבחנה באקראיות 516360
אה, הבנתי. מה שאתה מציע כאן הוא להגדיר אקראיות בעזרת סיבוכיות קולמוגורוב (שזו גישה לגיטימית בהחלט, אבל לא הגישה שעליה דיברתי במאמר).

לרוע המזל, אני עדיין לא חושב שמה שאתה מציע הוא אפשרי, גם לא תיאורטית. שורש הבעיה נעוץ בכך שבהינתן אלגוריתם, אין לך דרך לדעת האם הוא עוצר או לא. אמנם, אם כל מה שאנחנו מדברים עליו הוא n יחיד, ספציפי, אז אפשר, תיאורטית, לדבר על "רשימת כל האלגוריתמים העוצרים מאורך קטן מ-n"; אבל זה לא מקדם אותנו לקראת אלגוריתם שמסוגל להגיד על *כל* מחרוזת אם היא אקראית (למעשה, אם אתה מגביל את האורך האפשרי של המחרוזות שהאלגוריתם צריך לטפל בהן, אז מבחינה תיאורטית הבעיה טריוויאלית - אני לא בטוח אם כדאי להיכנס לזה כרגע).
שיטה פרקטית להבחנה באקראיות 516366
לא הבנתי. למה זה לא מקדם אותנו? הרי אנחנו מדברים על רצף סופי. אם עבור כל n ניתן לדבר על "רשימת כל האלגוריתמים העוצרים מאורך קטן מ-n" (עבור כל n נכין את הרשימה מחדש - אם יש לנו מתכון הכנה כזה) אז ניתן להוכיח עבור כל רצף מאורך n שהוא רצף אקראי. כלומר יש לנו אלגוריתם ל"כל" מחרוזת סופית. מש"ל.
שיטה פרקטית להבחנה באקראיות 516368
שורש הבעיה נעוץ באמירה "נכין את הרשימה מחדש". אנחנו *לא* יודעים להכין את הרשימה; אנחנו רק יודעים שיש כזו, אבל אין לנו מושג מהי. אנחנו לא מסוגלים לייצר אותה באופן אלגוריתמי.

מה שאנחנו מדברים עליו עכשיו הוא אחת מהנקודות העדינות הבסיסיות בתורת החישוביות - ההבדל בין מודל חישוב יוניפורמי ללא יוניפורמי. אנסה לתת דוגמה שאולי תבהיר את זה: כל אלגוריתם אפשר לקודד באמצעות מספר טבעי. נבחר שיטת קידוד כלשהי. עכשיו, ברור שלכל מספר טבעי n קיים אלגוריתם שמכריע האם n הוא קידוד של תוכנית שעוצרת על הקלט הריק. האלגוריתם הזה הוא אחד משניים - או האלגוריתם שתמיד אומר "כן", או האלגוריתם שתמיד אומר "לא". לרוע המזל, אנחנו לא יודעים מי מהם הוא האלגוריתם הנכון, אבל ברור לנו שאחד מהם נכון - ולכן בפרט *קיים* אלגוריתם שפותר את הבעיה עבור ה-n הספציפי.

עכשיו לך תשלב את כל אינסוף האלגוריתמים הללו לאלגוריתם כללי שבהינתן n אומר האם n הוא קידוד של תוכנית שעוצרת על הקלט הריק (רמז: אי אפשר).
שיטה פרקטית להבחנה באקראיות 516370
''אנחנו לא מסוגלים לייצר אותה באופן אלגוריתמי''
אם אנחנו יודעים שקיימת הוכחה עבור כל אלגוריתם , אז ניתן לעבור על כל ההוכחות האפשריות.
שיטה פרקטית להבחנה באקראיות 516371
אין "הוכחה". יש אלגוריתם שעונה נכון, אבל אין לך בהכרח הוכחה שהוא עונה נכון (בפרט, אם התשובה לשאלה "האם האלגוריתם עוצר?" היא "לא", אין לזה הוכחה).
שיטה פרקטית להבחנה באקראיות 516372
אם כך אתה צודק, משום מה היה זכור לי שיש *הוכחה*. אנסה לנבור הלילה בספרים.
אגב, רמזת שאתה מכיר שיטה אחרת (לא פולינומיאלית) המוכיחה שמחרוזת סופית היא אקראית, אפשר בבקשה הפניה?
שיטה פרקטית להבחנה באקראיות 516375
מה הפירוש של הוכחת אקראיות של מחרוזת סופית? הרי *כל* מחרוזת באורך נתון תתקבל בסופו של דבר, בהסתברות 1, מדגימות בלתי תלויות מתוך התפלגות אחידה.

אפשר לחשב את האנתרופיה של המחורזת, אפשר לחשב היוריסטיקות שאמורות למדוד את הסיבוכיות האלגוריתמית שלה, ואפשר להפעיל מבחנים סטטיסטיים להערכת הסבירות שהמחרוזת תתקבל מדגימה אקראית - אבל אף אחד מהדברים האלה מן הסתם לא *מוכיח* שום דבר לגבי הדרך בה המחרוזת הופקה.

אגב, בבעיה בן דן המאמר שמעלינו התנאים שונים, וידוע בדיוק איך המחרוזת הופקה: תהליך דטרמיניסטי לחלוטין שגם הוא ידוע לחלוטין (עד כדי הגרעין).
שיטה פרקטית להבחנה באקראיות 516377
ההגדרה על פי סיבוכיות קולמוגורוב, ועיין לעיל
שיטה פרקטית להבחנה באקראיות 516378
אז מה השאלה? "איך מחשבים סיבוכיות אלגוריתמית"?
שיטה פרקטית להבחנה באקראיות 516381
אני מצטרף לתהיה. הפסיק להיות לי ברור מה השאלה לפני כמה תגובות (אבל מדי פעם כשמזכירים משהו מעניין אני מרגיש צורך להגיב, למשל לציין שאפשר להוכיח שאי אפשר להראות חסמים תחתונים לא טריוויאליים לסיבוכיות קולמוגורוב של מחרוזות, למעשה זו מדובר בהוכחה אלטרנטיבית למשפט אי השלמות של גדל).

בתגובה זו קיים אי דיוק (אחד שאני מודע אליו ואולי עוד). מושאר כתרגיל לקורא המשועמם.
שיטה פרקטית להבחנה באקראיות 516394
לא הסברתי את עצמי טוב. יש כמה גישות למושג האקראיות - אחת מסתמכת על סיבוכיות קולמוגורוב. אחרת מתבססת על אי קיום מבחין - ובמקרה הזה, אין משמעות לדבר על אקראיות של מחרוזת ספציפית, רק על האקראיות של המחולל.
שיטה פרקטית להבחנה באקראיות 516361
דווקא קיימת הוכחה שאין תוכנית שמסוגלת להכריע בזמן סופי האם אלגוריתם שרץ על הקלט הריק עוצר. הבעיה הזו היא שינוי קל (ולא מהותי) של בעיית העצירה [ויקיפדיה].
שיטה פרקטית להבחנה באקראיות 516365
אולי הוא מתבלבל עם אלגוריתמים בעלי זיכרון חסום, עבורם דווקא אפשר (ואפילו קל, בזמן אקספוננציאלי) לדעת אם הם עוצרים או לא (סאוויץ').
שיטה פרקטית להבחנה באקראיות 516369
לא קשור לסאוויץ' (שמדבר על הקשר בין דרישות הזכרון של אלגוריתם אי דטרמיניסטי ואלגוריתם דטרמיניסטי שקול), אלא סתם לכך שמספר הקונפיגורציות של אלגוריתם כזה הוא סופי.
שיטה פרקטית להבחנה באקראיות 516380
אצלי זה מתקשר משום מה אבל אתה צודק, זה לגמרי אוברקיל למקרה של מכונה דטרמיניסטית. אז חידה (אני מקוה שלא קלה מדי): מה סיבוכיות המקום הנדרשת על מנת להכריע אם מכונת טיורינג (דטרמיניסטית ללא קלט) בסיבוכיות מקום s עוצרת או לא?
שיטה פרקטית להבחנה באקראיות 516397
החסם העליון הסטנדרטי הוא אקספוננציאלי ב-s (במדויק, גודל האלפבית בחזקת s, ועוד לוג של s, ועוד לוג של גודל קבוצת המצבים). אני מפספס כאן משהו?
שיטה פרקטית להבחנה באקראיות 516421
סיבוכיות המקום.
שיטה פרקטית להבחנה באקראיות 516424
אוי, בעצם יש פתרון טריוויאלי למה ששאלתי. אז בואו נגיד שהאלגוריתם צריך לעבוד אפילו בלי לדעת את s.
שיטה פרקטית להבחנה באקראיות 516432
הפתרון הקודם שלי עשה מיש-מש - התחלתי מסיבוכיות הזמן, ואז עברתי לסיבוכיות המקום (אקספוננציאלי ב-s, אבל אז לוגריתמי ב-s?). מן הסתם סיבוכיות המקום, במקרה הקודם, היא s ועוד הלוגים הללו.

במקרה שאתה מתאר לא מספיק לספור קונפיגורציות אלא צריך לשמור את כולן, לא? זה מקפיץ אותנו שוב לסיבוכיות אקספוננציאלית, אלא אם אני שוב מפספס משהו.
שיטה פרקטית להבחנה באקראיות 516508
יופי, זו בדיוק החידה. סיבוכיות מקום אקספוננציאלית זה הרבה יותר מדי.
שיטה פרקטית להבחנה באקראיות 516576
המממ, אפשר לשמור מונה של מספר הצעדים ובנוסף לשמור את כמות המקום שהמכונה המסומלצת השתמשה בה עד כה. אם מספר הצעדים עובר מתישהו את מספר הקונפיגורציות האפשריות בהינתן כמות המקום הנוכחית, סיימנו. זה הרעיון?
שיטה פרקטית להבחנה באקראיות 516609
זה לא הרעיון שלי אבל זה עונה על השאלה. אני אנסה לחשוב על חידות יותר טובות בפעם הבאה...

מה שכן, האלגוריתם שהצעת עלול לקחת זמן רב הרבה יותר מהדרוש. אתה יודע לתת אלגוריתם עם סיבוכיות מקום טובה ועם סיבוכיות זמן כמו של האלגוריתם הנאיבי (כלומר פרופורציונית למספר המצבים בפועל של המכונה ולא לחסם העליון)? החידה הזו נעשית יותר מדי "תפורה", אני אבין אם תעדיף לפרוש.
שיטה פרקטית להבחנה באקראיות 516620
אפשר אולי להשתמש בתעלול הסטנדרטי למציאת אורך מעגל - מבצעים שתי ריצות במקביל שאחת מהן מהירה פי שתיים יותר מהשנייה, ובכל סיבוב בודקים אם יש ''התנגשות'' (ליתר דיוק, אם ההרצה המהירה עקפה את ההרצה האיטית).
שיטה פרקטית להבחנה באקראיות 516634
כן, זה מה שרציתי. כאמור, פעם הבאה יהיה (אולי) יותר טוב.
שיטה פרקטית להבחנה באקראיות 516637
זו חידה יפה דווקא, אם כי לא נראה לי שמי שלא מכיר את תעלול המעגל יחשוב על הפתרון שכיוונת אליו (נראה לי שהם כן יוכלו למצוא את הפתרון הנאיבי יותר של ספירת הקונפיגורציות).
שיטה פרקטית להבחנה באקראיות 516646
הנחמד בעיני (אתה הזכרת לי את זה בהערה שלך על סאוויץ') הוא המעבר בין השאלה החישובית לשאלה קומבינטורית/אלגוריתמית על גרף הקונפיגורציות.
שיטה פרקטית להבחנה באקראיות 517000
למרות שעכשיו ברור הפתרון, איך מנוסחת החידה על אורך מעגל?
שיטה פרקטית להבחנה באקראיות 517009
יש לך מעגל שנתון באמצעות רשימה מקושרת (כלומר, סדרה של מצביעים שכל אחד מצביע לכתובת של הבא). תמצא את האורך שלו.

מקום אחר, ופרקטי, שבו החידה צצה - מציאת מעגלים בפונקציות תמצות קריפטוגרפיות. כאן אתה מתחיל ממספר כלשהו, מפעיל עליו את הפונקציה שוב ושוב עד שאתה מגיע למספר שכבר "ביקרת" בו. אותו רעיון נמצא בשימוש גם באלגוריתם ה-rho של פולרד לפירוק לגורמים.
שיטה פרקטית להבחנה באקראיות 517024
יש לך דרך אלגנטית לחסום בניסוח החידה את הפתרון הטריוויאלי, לזכור את הכתובת הראשונה?

שמא לתת כנתון לא רק מעגל, אלא גרף קשיר שמכיל מעגל?
שיטה פרקטית להבחנה באקראיות 517026
אה... כן, זה כמובן מה שהתכוונתי אליו (גרף קשיר שמכיל מעגל).
שיטה פרקטית להבחנה באקראיות 517077
ואז, כשזיהית ששני ה"פועלים" שלך באותו מקום, כבר השלמת סיבוב, אבל צריך לעשות אותו שוב כדי לספור, נכון?
שיטה פרקטית להבחנה באקראיות 517079
אז מה. זה לא מוסיף לסיבוכיות (לכל היותר מעלה את זמן הביצוע פי 1.5 או משהו בסביבה).
שיטה פרקטית להבחנה באקראיות 517167
ברור. זה רק גורע, ואני קטנוני פה, שמץ של שמץ מהחן של הפתרון, בעיקר אם לפני-כן חשבת שנתון שאתה על המעגל, שאז זה לא נחוץ.
שיטה פרקטית להבחנה באקראיות 517199
העניין הוא שלא חושבים כך. למשל, בדוגמה שהתחילה את העניין (סימולציה של מכונת טיורינג עם חסם זכרון) לא ידוע אם בכלל יש מעגל, ומאוד לא סביר שנהיה עליו כבר בהתחלה.
שיטה פרקטית להבחנה באקראיות 517200
הנוסח שאני מכיר הוא למצוא אם רשימה מקושרת מכילה מעגל.
שיטה פרקטית להבחנה באקראיות 516367
אין תוכנית שמסוגלת להכריע עבור כל האלגוריתמים האפשריים, אבל לכל אלגוריתם ספציפי יש הוכחה משלו
שיטה פרקטית להבחנה באקראיות 516342
מאוד קל למצוא מבחן שמבדיל בין רצף המגיע ממחולל פסאודו-אקראי לרצף אקראי באמת. פשוט עוברים על כל הגלעינים האפשריים למחולל ובודקים אם אחד מהם מייצר את הרצף שבידינו. במילים אחרות: רצף ממחולל פסאודו-אקראי הוא תמיד דחיס לאורך הגלעין. ההוכחה שהאלגוריתם באמת מבחין - תרגיל לקורא.

המטרה במחולל מספרים אקראיים היא שלא יתקיים אלגוריתם יעיל שמצליח להבחין. אכן קל לראות שההצעה שלי רצה בזמן אקספוננציאלי באורך הגלעין ולכן לא מדובר באלגוריתם יעיל.
שיטה פרקטית להבחנה באקראיות 516351
הבעיה היא אם אין לך את המחולל אלא רק את הרצף.
שיטה פרקטית להבחנה באקראיות 516356
הרעיון (התיאורטי) במחולל הוא ש*אף אחד* לא מסוגל להבחין בצורה יעילה בין מה שהמחולל פולט למשהו אקראי אמיתי, ובכלל זה גם כאלו שיודעים בדיוק איך המחולל עובד.
שיטה פרקטית להבחנה באקראיות 518219
השאלה היא מה ההבדל בין משהו אקראי אמיתי למשהו שהמחולל פולט, גם אם יודעים איך המחולל עובד, הסבירות שתוכל להבחין בצורה יעילה הוא תיאורטי בלבד.
שיטה פרקטית להבחנה באקראיות 516096
מבחינה סטטיסטית, סביר להניח שהתנך מקודד במלואו ב ascii בסדרה רציפה של ספרות של פאי.
צריך רק לקחת מספיק ספרות אחרי הנקודה...
לא?
מחולל אלטרנטיבי 524156
שלום,
כתבתי לפני כשנה מחולל של מספרים אקריים בספת PHP משום שהמחולל המובנה גרוע עד מאוד.

<?php
function frand($to=100, $from=0, $if_float=0, $if_abs=true, $if_trace=false) {
$to++;
$tracer = microtime();
list($micro, $sec) = explode(" ", $tracer);
$tracer = " - $tracer";
$FLOAT = ";
$MUL = 1;
if ($if_float > 0) {$to--; $FLOAT = '.'.frand(pow(10, $if_float));}
if ($if_trace === false) { $tracer = ";}
if ($if_abs === false) { $MUL = frand(2) == 0 ? -1 : 1; }
$micro = pow($micro, 2) + $micro +41; // according to Euler's formula
$sec = pow($sec, 2) + $sec +41;
$precisement = strlen($to) +substr($micro, 0, 2) +2;
$ret = sprintf("[%.{$precisement}f]",($micro/$sec));
return ((((substr($ret, (strlen($to) > 3 ? (5+strlen($to))*(-1) : -5)) % ($to-$from)) + $from).$FLOAT)*$MUL).$tracer;
}
?>

המחולל שלי מבטיח שלא יהיו חזרות נשנות, את פשטותו ואת מהירותו. אני מתבסס על חילוק של שני מספרים ראשוניים שהאחד הוא מ'ס השניות מאז 1970 (UNIX time) והשני הוא מ'ס המילישניות ברגע (בשנייה) הנוכחי(ת); והנוסחה של Euler אשר הופכת כל מספר לראשוני.

כל הקטצ' הוא בזה שאם מפעילים את הארגומנט האחרון if_trace$ אז ניתן לראות מאילו מספרים חולל המ'ס שנפלט. זאת אומרת שאם יודעים באיזו שניה ומילישניה חולל המ'ס, אז ניתן לחולל את המ'ס הזה בדיוק בעת הצורך.

משמע, שאם אני שולח לך סדרה של מספרים "אקראיים", תוכל לנתב אותם לשני צורות - סדרה של שניות ומילישניות (ע"י חישוב מסויים של כמה מילישניות עוברות בין מ'ס למ'ס במחשב מסויים); או להפך, אני שולח לך את השניה והמילישניה הראשונה והאחרונה (וע"י אותו החישוב של פעולות המחשב) תוכל לקבל את הסדרה לעיל. :)
מחולל אלטרנטיבי 524160
אני מציע לך מאוד להיזהר. הנוסחה n^2+n+41 לא "הופכת כל מספר לראשוני". עבור n=40 תקבל 41 בריבוע. באופן כללי לא קיים פולינום שלכל ערך טבעי שמציבים בו נותן מספר ראשוני - תמיד אפשר להנדס קלט שיחזיר תוצאה פריקה.
מחולל אלטרנטיבי 524179
הייתי אומר, בזהירות, שזו הבעייה הכי קטנה של המחולל הזה. איני סבור שהוא יעבור איזשהו מבחן אקראיות פשוט המביט בזוגות עוקבים.

קוד פשוט וקצר עבור מחולל חזק מאוד יש כאן:

(יש לרדת במורד הפתיל עד להודעה של Marsaglia). לדעתו של זה האחרון מחולל זה עדיף על Mersenne Twister הפופולרי. אם PHP תומך בשלמים עם 64 ביטים, לא צריך להיות כל קושי לתרגם את הקוד הזה ל-PHP. כדי לאתחל את המערך Q אפשר להשתמש במחולל פשוט כלשהו עם seed של תו הזמן.
מחולל אלטרנטיבי 524184
אני מודה שלא טרחתי לקרוא את הקוד של המחולל, רק הסתקרנתי מהי אותה נוסחה של Euler אשר הופכת כל מספר לראשוני.
מחולל אלטרנטיבי 524188
תודה על ההערה, אבל עוד לא ניתקלתי ב N1 = 40 , וצריך לא לשכוח שיש N2 התלוי ב ()time שלא חוזר על עצמו. אתה כמובן צודק בקשר ל-‏40 הזה, אבל ישנם עוד כמה נוסחאות כאלה שאמורות להפוך מ'ס לראשוני, או שפשוט אפשר לחבר לN1 וN2, את המ'ס 42 ליתר ביטחון.

רק שלוש הערות לי אליך, כבודו :

1. המחולל המובנה של PHP כה עלוב שבשימוש נקי (בלי פונקציות פנימיות, כגון, (()rand(rand, וכדומה) יכול לפלוט חצי סדרה בת 10 איברים כאותו איבר (3,3,3,3,3,3,2,2,1,7 לדוגמה).

2. חשבתי ובניתי אותו לבד. פרסמתיו באתר http://www.phpclasses.org/browse/package/4974.html והורידו אותו 4574 אנשים בלי קשר לאתר זה ו203 אנשים הרשומים בו.

3. אני חושב שזה המחולל היחיד, שלפחות אני מקיר, שעובד עם מספרים שלמים, שברים עשרוניים, חיוביים ושליליים.
מחולל אלטרנטיבי 524191
אני חושב שאפסיק כאן. אני לא רוצה עוד דיון 1571.
מחולל אלטרנטיבי 524197
צר לי מאוד שהבנת אותי בדרך כה מבזה הוד גאונותך. אני מבין שסלדתי קצת מהנושא, אבל רק רציתי להראות מחולל מספרים אקראיים ע"י מטמטיקה פשוטה שיכול בגאווה לעמוד מול כל מחולל אחר. כמובן שאי אפשר בוודעות לדעת מה יצר מ'ס זה או אחר, מכיוון שזה אותו הדבר כצם לשאול איזה מ'ס אחרי מודולו 2 פלט 0 ?
אני לא מתיימר להיות גאון או חכם ממישהו. אבל עדיין, איך אנשים כותבים דוקטורטים חדשים מידי שנה (ויש בינהם נושאים מרתקים וחדשניים במיוחד), חידות ששנים ארוכות הרתיעו מטמטיקאים (כמו למשל "תאורמת פרמה") נפתרות, ואף אחד לא מתחיל להיתבלבל והמטמטיקה נשארת במקומה אם לא מתפתחת הלאה.
אם נותנים לך פתרון קצר יותר משלך לאותה הבעיה\שאלה לפעמים רצויי לאמץ אותו, ולא לעמוד על שלך כמו תייש ולהצהיר שגם התשובה שלך נותנת פתרון. ברור שאם יש בידיך פתרון אז הוא נכון, אבל אם הוא יותר ארוך ומסובך אז למה תהיתקע עליו ?

אני מצתער אם העלבתי את כבודו, אבל גם כבודו העליב אותי.
מחולל אלטרנטיבי 524201
שמור את הצער למקרי חירום, אתה קטן מכדי להעליב את גדי.
מחולל אלטרנטיבי 524203
מהו מבחינתך מחולל מספרים אקראיים טוב?

אילו תכונות צריכות להיות לו?
מחולל אלטרנטיבי 524207
1. שיהיה מהיר ככל האפשר.
2. שבקוד יהיה קצר ככל האפשר.
3. שבפלט לא יהיו שני מספרים זהים אחד אחרי השני.
מחולל אלטרנטיבי 524208
לגביי 3., אלא אם מ'ס האפשרויות קטן במיוחד, סמו סדרות בינריות וכדומה.
מחולל אלטרנטיבי 524213
(1) ו־(2) הן דרישות של יעילות. אני חושב שתסכים איתי שהקוד צריך קודם כל לעבוד היטב.

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

הנה רצף של ספרות (הקסדצימליות) אקראיות‏1 שקיבלתי מהמחשב שלי:

4de1 a457 d1ac f25c de18 22a3 6e41 69f0

הספרה 2 חזרה על עצמה. ואני מניח שאיך בכך פסול.

מה הבעיה בכך שמספר חוזר על עצמו?

1 לצורך העניין השתמשתי ב־‎/dev/random שהוא דרך לקבל ביטים אקראיים מ"מאגר האנטרופיה" של המערכת. ביטים (מספיק) אקראיים אפשר לקבל ממקורות כמו זמני הגישה לדיסק ותזמוני הקלדות המקלדת.
מחולל אלטרנטיבי 524219
יותר מכך - פלט שבו אין לפעמים חזרה על אותה ספרה הוא בבירור לא אקראי. בכלל, בפלט אקראי סביר לצפות לפעמים אפילו לחזרות ארוכות. או בקיצור: תגובה 522196.
מחולל אלטרנטיבי 524395
אחת החולשות שעזרו לפצח את האניגמה...
מחולל אלטרנטיבי 524223
מה דעתך על: 1 2 3 4 5 6 7 ... יותר יעיל, לא?
מחולל אלטרנטיבי 524289
1 0 1 0 1 0 ... יכול להיות יעיל אפילו יותר, ומקיים את דרישה 3 אפילו למקרה הבינארי!
מונטה קרלו בצל הקורונה 714663
אני מעריץ ותיק של עמוס הראל, כתב הצבא והבטחון של "הארץ". הוא תמיד יודע לסקר נושא ביסודיות, חוכמה, איזון, ובלי מיקרוגרם אחד של התלהמות. פעם בכמה זמן הוא גם כותב נהדר על מוזיקה, וזה עוד פלוס בשבילי.

לכן הצטערתי לקרוא את המובאה הבאה מתוך מאמר שלו מאתמול: "מדי יום מתפרסמים תרחישים במספרים, מהם רשמיים ומהם הערכות של מדענים ומומחי ביג דאטה. הקריאה באחדים מהם, כמו זה שהוגש לממשלת בריטניה, מעוררת צמרמורת. אך נדמה שכמה מהם מתאפיינים במה שמדענים קוראים לו סימולציות מונטה-קרלו: תרחישי ענק המבוססים על מספר עצום של משתנים היכולים להוביל לתוצאות שונות בתכלית, באופן שמזכיר קצת קזינו." ובכן, "שיטת מונטה קרלו" זה סתם ביטוי נרדף ל"סימולציה (הסתברותית)". אפשר לנתח בשיטת מונטה קרלו גם תרחישים פשוטים בתכלית, שהם לא "תרחישי ענק המבוססים על מספר עצום של משתנים היכולים להוביל לתוצאות שונות בתכלית" - למשל את תוחלת המספר המתקבל בהטלת קובייה.
מונטה קרלו בצל הקורונה 714669
אם כבר העלית את הנושא, אולי אתה יודע איך השיטה הזאת מנוצלת ע"י אלפא זירו ומוכן להסביר?
מונטה קרלו בצל הקורונה 714677
אין לי מושג, מצטער.
מונטה קרלו בצל הקורונה 714776
קראתי את Monte Carlo tree search [Wikipedia] ואז את זה (בלי להיכנס לעובי הנוסחאות, ודי ברפרוף על הפסאודו-קוד), ונדמה לי שדי הבנתי.
מונטה קרלו בצל הקורונה 714781
תודה.

באיזה שלב הם כותבים "עכשיו בוא נסתכל על המקרה הכללי"?
מונטה קרלו בצל הקורונה 714785
האמת שהמאמרון מדבר על אלפא גו זירו. אלפא זירו הוא כבר הכללה (אבל של משחקים, לא של מימדים אבסטרקטיים יותר של הבעיה. אפשר לחיות עם זה).

חזרה לעמוד הראשי פרסום תגובה למאמר

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים