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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

משפחות של אלגוריתמים אקראיים[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

יצירה של מספרים אקראיים[עריכת קוד מקור | עריכה]

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

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

שימושים לאלגוריתמים אקראיים[עריכת קוד מקור | עריכה]

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

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