Referat mavzu: Tasodifiy algoritmlarni tahlil qilish va loyihalash. Umumiy ko'rinish, usullar, topshiriqlarga misollar

TOSHKENT AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI FARG`ONA FILIALI

Kompyuter injineringi
613-21 guruh talabasi:Shamamatova Sayyora Jo`raboy qizi
ALGORITMLARNI LOYIHALASH fanidan tayorlagan

REFERAT

Mavzu: Tasodifiy algoritmlarni tahlil qilish va loyihalash. Umumiy ko'rinish, usullar, topshiriqlarga misollar.
Reja:

1. 
   Tasodifiy algoritmlar haqida umumiy ma`lumot.
   
2. 
   Umumiy ko'rinish.
   
3. 
   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 (Las-Vegas algoritmlari, masalan Quicksort[1]) va noto'g'ri natijaga olib keladigan algoritmlar (Monte-Karlo algoritmlari, masalan Monte-Karlo algoritmi MFAS muammo[2]) yoki nosozlik haqida signal berish yoki tugatmaslik bilan natija bermaydi. Ba'zi hollarda, ehtimollik algoritmlari muammoni hal qilishning yagona amaliy vositasidir.[3]
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.
Rag'batlantiruvchi misol sifatida "topish" muammosini ko'rib chiqing. An qator ning n elementlar.
Kiritish: Bir qator n≥2 element, ularning yarmi ‘aNing yarmi vabNing.
Chiqish: ‘Ni topinga'Qatorda.
Algoritmning ikkita versiyasini beramiz, bittasi Las-Vegas algoritmi va bitta Monte-Karlo algoritmi.
Las-Vegas algoritmi:
topish A_LV(qator A, n)boshlash takrorlang Tasodifiy tanlang bitta element chiqib ning n elementlar. qadar "a" bu topildioxiri
Ushbu algoritm ehtimollik bilan muvaffaqiyatga erishadi. Takrorlashlar soni turlicha va o'zboshimchalik bilan katta bo'lishi mumkin, ammo takrorlanishning kutilayotgan soni
U doimiy bo'lgani uchun, ko'plab qo'ng'iroqlar davomida kutilayotgan ish vaqti hisoblanadi. (Qarang Big O notation )
Monte-Karlo algoritmi:
topish A_MC(qator A, n, k)boshlash men=0 takrorlang Tasodifiy tanlang bitta element chiqib ning n elementlar. men = men + 1 qadar men=k yoki "a" bu topildioxiri
Agar "a'Topildi, algoritm muvaffaqiyatli bo'ladi, aks holda algoritm muvaffaqiyatsiz bo'ladi. Keyin k takrorlash, 'topish ehtimoli Bu: Pr[find a]=1-(1/2)k
Ushbu algoritm muvaffaqiyatni kafolatlamaydi, ammo ishlash muddati cheklangan. Takrorlashlar soni har doim k dan kam yoki tengdir. Ish vaqtini doimiy bo'lishini kutish (kutilgan va mutlaq) .
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:
arixiy 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.
Miller-Rabinning dastlabki sinovi ikkita musbat tamsayı o'rtasidagi ikkilik munosabatlarga asoslanadi k va n buni shu bilan ifodalash mumkin k "kompozitsiyaning guvohidir" n. Buni ko'rsatish mumkin
Agar kompozitsiyaning guvohi bo'lsa n, keyin n kompozitsion (ya'ni, n emas asosiy ) va
Agar n dan tashkil topgan bo'lsa, u holda tabiiy sonlarning kamida to'rtdan uchi kamroq n uning kompozitsiyasining guvohlari va
Berilgan tezkor algoritm mavjud k va n, yo'qligini aniqlaydi k kompozitsiyasining guvohidir n. Shuni e'tiborga olingki, bu birinchi darajadagi muammo Co-RP.
Agar shunday bo'lsa tasodifiy kompozit sondan 100 ta sonni kamroq tanlaydi n, unda bunday "guvoh" topilmaslik ehtimoli (1/4)100 shuning uchun ko'pgina amaliy maqsadlar uchun bu birinchi darajali sinovdir. Agar n katta, boshqa amaliy sinov bo'lmasligi mumkin. Xatolik ehtimoli etarli darajada mustaqil testlarni o'tkazish orqali o'zboshimchalik darajasiga tushirilishi mumkin.
Shuning uchun, amalda, kichik bir xato ehtimolini qabul qilish bilan bog'liq jazo yo'q, chunki biroz ehtiyotkorlik bilan xato ehtimolini astronomik jihatdan kichik qilish mumkin. Darhaqiqat, bundan keyin deterministik polinom-vaqt primality testi topilgan bo'lsa ham (qarang AKS dastlabki sinovi ), u eski ehtimollik testlarini almashtirmadi kriptografik dasturiy ta'minot yaqin kelajak uchun ham buni qilish kutilmaydi.