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