Tasodifiy algoritmlar

Tasodifiy algoritmlarni tahlil qilish va loyihalash. Umumiy ko'rinish, usullar, topshiriqlarga misollar.
"Tasodifiy algoritmlar" bu erga yo'naltiriladi. Bu bilan aralashmaslik kerak Algoritmik tasodifiylik.
A tasodifiy algoritm bu algoritm darajasida ishlaydigan tasodifiylik uning mantig'ining bir qismi sifatida. Algoritm odatda foydalanadi bir xil tasodifiy tasodifiy bitlarning barcha mumkin bo'lgan tanlovlari bo'yicha "o'rtacha holatda" yaxshi ko'rsatkichlarga erishish umidida, uning xatti-harakatlarini boshqaradigan yordamchi kirish sifatida bitlar. Rasmiy ravishda algoritmning ishlashi a bo'ladi tasodifiy o'zgaruvchi tasodifiy bitlar bilan belgilanadi; Shunday qilib, ish vaqti yoki chiqishi (yoki ikkalasi) tasodifiy o'zgaruvchidir.

Tasodifiy kiritishni ishlatadigan algoritmlarni har doim to'g'ri javob bilan tugatishi uchun ajratish kerak, ammo kutilgan ish vaqti cheklangan va noto'g'ri natijaga olib keladigan algoritmlar (Monte-Karlo algoritmlari, masalan Monte-Karlo algoritmi MFAS muammo yoki nosozlik haqida signal berish yoki tugatmaslik bilan natija bermaydi. Ba'zi hollarda, ehtimollik algoritmlari muammoni hal qilishning yagona amaliy vositasidir.

(Las-Vegas algoritmlari, masalan Quicksort)

Umumiy amaliyotda tasodifiy algoritmlar a yordamida taxminiylashtiriladi pseudorandom tasodifiy generator tasodifiy bitlarning haqiqiy manbai o'rnida; bunday amalga oshirish kutilgan nazariy xulq-atvordan chetga chiqishi mumkin.

Tasodifiy algoritmlar zararli "dushman" yoki duch kelganda ayniqsa foydalidir tajovuzkor qasddan algoritmga yomon kirishni berishga harakat qiladigan (qarang) eng yomon murakkablik va raqobatbardosh tahlil (onlayn algoritm) kabi Mahbusning ikkilanishi. Aynan shu sababli tasodifiylik hamma joyda mavjud kriptografiya. Kriptografik dasturlarda psevdo-tasodifiy sonlardan foydalanish mumkin emas, chunki dushman ularni oldindan aytib bera oladi va algoritmni samarali deterministik qiladi. Shuning uchun, yoki chindan ham tasodifiy sonlarning manbai yoki a kriptografik xavfsiz psevdo-tasodifiy sonlar generatori zarur. Tasodifiylikka xos bo'lgan yana bir yo'nalish kvant hisoblash.

Yuqoridagi misolda Las-Vegas algoritmi doimo to'g'ri javobni chiqaradi, ammo uning ishlash vaqti tasodifiy o'zgaruvchidir. Monte-Karlo algoritmi (. Bilan bog'liq Monte-Karlo usuli simulyatsiya uchun) funktsiya kirish hajmi va uning parametri bilan chegaralanishi mumkin bo'lgan vaqt ichida bajarilishi kafolatlanadi k, lekin ruxsat beradi kichik xato ehtimoli. Las-Vegasdagi har qanday algoritmni Monte-Karlo algoritmiga aylantirish mumkinligiga e'tibor bering (orqali Markovning tengsizligi ), agar u belgilangan vaqt ichida bajarilmasa, o'zboshimchalik bilan, ehtimol noto'g'ri javob berishi mumkin. Aksincha, agar javobning to'g'ri yoki yo'qligini tekshirish uchun samarali tekshirish protsedurasi mavjud bo'lsa, unda Monte Karlo algoritmini Monte Karlo algoritmini to'g'ri javob olinmaguncha qayta-qayta ishlatib Las-Vegas algoritmiga aylantirish mumkin.

Hisoblashning murakkabligi
Hisoblash murakkabligi nazariyasi sifatida tasodifiy algoritmlarni modellar ehtimoliy Turing mashinalari. Ikkalasi ham Las-Vegas va Monte-Karlo algoritmlari va bir nechta hisoblanadi murakkablik sinflari o'rganilmoqda. Murakkablikning eng asosiy tasodifiy klassi RP, bu sinf qaror bilan bog'liq muammolar buning uchun tasodifiy algoritm (yoki polinomiy vaqt) mavjud bo'lib, u NO-misollarni mutlaq aniqlik bilan taniydi va kamida 1/2 ehtimollik bilan YES-misollarni taniydi. RP uchun komplement sinf ko-RP hisoblanadi. Bilan algoritmlarga ega (ehtimol tugatilmagan) muammo sinflari polinom vaqti chiqishi har doim to'g'ri bo'lgan o'rtacha ish vaqti, deyiladi ZPP.

YES va NO-misollarini biron bir xato bilan aniqlashga ruxsat berilgan muammolar sinfi deyiladi BPP. Ushbu sinf ning tasodifiy ekvivalenti vazifasini bajaradi P, ya'ni BPP samarali randomizatsiyalangan algoritmlar sinfini anglatadi.

Tarix
Tarixiy jihatdan birinchi tasodifiy algoritm tomonidan ishlab chiqilgan usul bo'lgan Maykl O. Rabin uchun eng yaqin juftlik muammosi yilda hisoblash geometriyasi.[4]Tasodifiy algoritmlarni o'rganish 1977 yilda a randomizatsiyalangan dastlabki sinov (ya'ni. ni aniqlash birinchi darajali sonning) tomonidan Robert M. Solovay va Volker Strassen. Ko'p o'tmay Maykl O. Rabin 1976 yil ekanligini namoyish etdi Millerning dastlabki sinovi tasodifiy algoritmga aylantirilishi mumkin. O'sha paytda, amaliy emas deterministik algoritm chunki ustunlik ma'lum edi.