אלגוריתם אקראי

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

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

משפחות של אלגוריתמים אקראיים

מקובל לחלק אלגוריתמים אקראיים לשתי משפחות עיקריות:

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

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

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

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

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

יצירה של מספרים אקראיים

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

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

שימושים לאלגוריתמים אקראיים

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

לאקראיות ולאלגוריתמים אקראיים שימושים רבים, ובהם:

קישורים חיצוניים

גדעון לב, פרס טיורינג יוענק לפרופ' אבי ויגדרזון על תרומתו לחקר האקראיות במחשוב, באתר הארץ, 10 באפריל 2024