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

Misollar:
Quicksort tasodifiy foydali bo'lishi mumkin bo'lgan tanish, tez-tez ishlatiladigan algoritm. Ushbu algoritmning ko'pgina deterministik versiyalari talab qilinadi O (n2) saralash vaqti n degeneratsiyalangan kirishlarning ba'zi bir aniq belgilangan klassi (masalan, allaqachon saralangan qator) uchun, pivotni tanlash uchun protokol bilan aniqlangan ushbu xatti-harakatni keltirib chiqaradigan maxsus kirish sinfiga ega bo'lgan raqamlar. Ammo, agar algoritm burilish elementlarini tasodifiy ravishda bir xil tanlasa, unda tugatish ehtimoli katta O(n jurnaln) kirish xususiyatlaridan qat'iy nazar vaqt.
Geometriyadagi tasodifiy qo'shimcha qurilishlar
Yilda hisoblash geometriyasi, a kabi tuzilishni qurish uchun standart texnika qavariq korpus yoki Delaunay uchburchagi kirish nuqtalarini tasodifiy ravishda almashtirish va keyin ularni mavjud tuzilishga birma-bir kiritishdir. Tasodifiylashtirish qo'shimchadan kelib chiqqan holda tuzilishdagi kutilayotgan o'zgarishlar sonining ozligini ta'minlaydi va shuning uchun algoritmning kutilayotgan ish vaqti yuqoridan chegaralanishi mumkin. Ushbu texnika sifatida tanilgan tasodifiy qo'shimcha qurilish.[5]
Min kesilgan
Asosiy maqola: Karger algoritmi
Kiritish: A grafik G(V,E)
Chiqish: A kesilgan tepaliklarni qismlarga ajratish L va R, orasidagi minimal qirralarning soni bilan L va R.
Eslatib o'tamiz qisqarish ikkita tugunning, siz va v, (multi-) grafikada yangi tugun hosil bo'ladi siz Ikkala tomonga tushadigan qirralarning birlashishi bo'lgan qirralar bilan siz yoki v, bog'laydigan har qanday chekka (lar) bundan mustasno siz va v. 1-rasmda tepalikning qisqarishiga misol keltirilgan A va BSiqilgandan so'ng, natijada olingan grafik parallel qirralarga ega bo'lishi mumkin, lekin o'z-o'zidan halqalarni o'z ichiga olmaydi.
1-rasm: A va B tepaliklarning qisqarishi
2-rasm: Karger algoritmini 10 vertikal grafada muvaffaqiyatli bajarish. Minimal kesma 3 o'lchamga ega va tepalik ranglari bilan ko'rsatilgan.
boshlash i = 1 takrorlang takrorlang G ning tasodifiy qirrasini oling (u, v) ∈ E, u va v ni qisqarish bilan almashtiring u ' qadar faqat ikkita tugun qoladi, natijada tegishli kesilgan natijani oladi Cmen i = i + 1 qadar i = m C orasidagi minimal kesimni chiqaradi1, C2, ..., Cm.oxiri.
Tashqi tsiklning har bir bajarilishida algoritm ichki tsiklni faqat 2 ta tugun qolguncha takrorlaydi, tegishli kesma olinadi. Bitta ijroning ishlash vaqti va n tepalar sonini bildiradi.After m tashqi tsiklning qatl etish vaqtini, biz barcha natijalar orasida minimal kesmani chiqaramiz. 2-rasmda algoritmning bitta bajarilishining misoli keltirilgan. Amalga oshirilgandan so'ng biz 3 o'lchamdagi kesmani olamiz.
Lemma 1: Ruxsat bering k eng kichik o'lchamda bo'ling va ruxsat bering C = {e1,e2,...,ek} min kesilgan bo'lishi. Agar takrorlash paytida men, chekkasi yo'q e ∈ C qisqarish uchun tanlanadi, keyin Cmen = C.
Isbot: Agar G ulanmagan, keyin G bo'linishi mumkin L va R ularning orasidagi chekkasiz. Shunday qilib, uzilgan grafikada min kesma 0 ga teng. Endi, faraz qiling G ulangan. Ruxsat bering V=L∪R bo'linishi V tomonidan qo'zg'atilgan C : C={ {siz,v} ∈ E : siz ∈ L,v ∈ R } (beri aniqlangan G ulangan). Chegarani ko'rib chiqing {siz,v} ning C. Dastlab, siz,v alohida tepaliklar. Biz bir chekkani tanlagan ekanmiz , siz va v birlashtirilmang. Shunday qilib, algoritm oxirida biz butun grafigini qoplaydigan ikkita birikma tuguniga egamiz, bittasi L va ikkinchisi R. 2-rasmda bo'lgani kabi, min kesmaning o'lchami 1, va C = {(A,B)}. Agar biz tanlamasak (A,B) qisqarish uchun biz min kesmani olishimiz mumkin.
Lemma 2: Agar G bilan multigraf p tepaliklar va ularning min kesimi hajmi bor k, keyin G kamida bor pk/ 2 chekka.
Isbot: Chunki min kesilgan k, har bir tepalik v darajani qondirishi kerak (v) ≥ k. Shuning uchun daraja yig'indisi hech bo'lmaganda pk. Ammo vertikal darajalar yig'indisi 2 | ga teng ekanligi hammaga ma'lumE|. Lemma quyidagicha.
Algoritmni tahlil qilish: Algoritm muvaffaqiyatga erishish ehtimoli 1 ga teng - barcha urinishlar muvaffaqiyatsiz bo'lish ehtimoli. Mustaqillik bilan barcha urinishlar muvaffaqiyatsizlikka uchraydi.

Derandomizatsiya.
Tasodifiylikni makon va vaqt kabi manba sifatida ko'rish mumkin. Derandomizatsiya - bu jarayon olib tashlash tasodifiylik (yoki undan iloji boricha kamroq foydalanish). Barcha algoritmlarni ish vaqtini sezilarli darajada oshirmasdan derandomizatsiya qilish mumkinmi, hozircha ma'lum emas. Masalan, ichida hisoblash murakkabligi, yo'qmi noma'lum P = BPP, ya'ni polinom vaqtida ishlaydigan o'zboshimchalik bilan tasodifiy algoritmni kichik xato ehtimoli bilan qabul qilishimiz va tasodifiylikni ishlatmasdan polinom vaqtida ishlashimiz uchun derandomizatsiya qilishimiz mumkinligini bilmaymiz.
Muayyan randomizatsiyalangan algoritmlarni derandomizatsiya qilish uchun ishlatilishi mumkin bo'lgan maxsus usullar mavjud:
The shartli ehtimollar usuli va uni umumlashtirish, pessimistik taxminchilar
nomuvofiqlik nazariyasi (bu geometrik algoritmlarni derandomizatsiya qilish uchun ishlatiladi)
kabi algoritm tomonidan ishlatiladigan tasodifiy o'zgaruvchilarda cheklangan mustaqillikning ekspluatatsiyasi juftlik mustaqilligi ichida ishlatilgan universal xeshlash
foydalanish kengaytiruvchi grafikalar (yoki tarqatuvchilar umuman) to kuchaytirish cheklangan miqdordagi dastlabki tasodifiylik (bu so'nggi yondashuv, shuningdek, hosil qilish deb ham ataladi pseudorandom tasodifiy manbadan bitlar va pseudorandomness mavzusiga olib keladi).
Tasodifiylik yordam beradigan joyda.
Hisoblash modeli cheklangan bo'lsa Turing mashinalari, hozirda tasodifiy tanlov qilish qobiliyati ba'zi bir muammolarni polinom vaqtida echishga imkon beradimi yoki yo'qmi, bu qobiliyatsiz polinom vaqtida echib bo'lmaydi; bu P = BPP bo'ladimi degan savol. Biroq, boshqa kontekstlarda, randomizatsiyalash qat'iy yaxshilanishlarni keltirib chiqaradigan muammolarning aniq misollari mavjud.
Dastlabki rag'batlantiruvchi misol asosida: 2 ga teng bo'lgan uzunlikdagi uzunlik berilgank belgilar, yarim a va yarim b, a tasodifiy kirish mashinasi 2 talab qiladik−1 indeksini topish uchun eng yomon holatda qidiruv a; agar tasodifiy tanlov qilishga ruxsat berilsa, bu muammoni kutilgan qidiruv polinom sonida hal qilishi mumkin.
Raqamli hisoblashni amalga oshirishning tabiiy usuli o'rnatilgan tizimlar yoki kiber-fizik tizimlar to'g'ri natijani yuqori ehtimollik bilan taxmin qiladigan natijani ta'minlash (yoki, ehtimol, taxminan to'g'ri hisoblash (PACC)). Taxminiy va to'g'ri hisoblash o'rtasidagi kelishmovchilik yo'qolishini baholash bilan bog'liq qiyin muammo randomizatsiyaga murojaat qilish orqali samarali echilishi mumkin.[7]
Yilda aloqa murakkabligi, ikkita satrning tengligi yordamida ishonchliligiga qadar tekshirilishi mumkin tasodifiy protokol bilan aloqa qismlari. Har qanday deterministik protokol talab qiladi kuchli raqibdan himoya qilsa bit.[8]
Qavariq tananing hajmini tasodifiy algoritm bilan polinom vaqtidagi ixtiyoriy aniqlikka qarab baholash mumkin.[9] Borany va Furedi hech qanday deterministik algoritm buni qila olmasligini ko'rsatdi.[10] Bu so'zsiz to'g'ri, ya'ni hech qanday murakkablik-nazariy taxminlarga tayanmasdan, agar konveks tanasi faqat qora quti sifatida so'ralishi mumkin bo'lsa.
Tasodifiylik yordam beradigan joyning yanada murakkabligi-nazariy misoli bu sinf IP. IP juda kuchli prover va BPP algoritmini amalga oshiruvchi tekshiruvchi o'rtasida polinomial uzoq ta'sir o'tkazish orqali qabul qilinishi mumkin bo'lgan (katta ehtimollik bilan) barcha tillardan iborat. IP = PSPACE.[11] Ammo, agar tekshiruvchining deterministik bo'lishi talab etilsa, u holda IP = NP.
A kimyoviy reaktsiya tarmog'i (cheklangan miqdordagi molekulalarda ishlaydigan A + B → 2C + D kabi reaktsiyalarning cheklangan to'plami), ma'lum bir maqsad holatiga har doim boshlang'ich holatidan erishish qobiliyati hal qilinadi, shu bilan birga har doim ma'lum bir maqsadga erishish ehtimolini taxmin qiladi. holat (reaktsiya keyingi sodir bo'lishi uchun standart kontsentratsiyaga asoslangan ehtimollikdan foydalangan holda) hal qilish mumkin emas. Aniqrog'i, cheklangan Turing mashinasini har doim o'zboshimchalik bilan to'g'ri ishlash ehtimoli bilan simulyatsiya qilish mumkin, faqat tasodifiy kimyoviy reaktsiya tarmog'idan foydalanilganda. Oddiy bo'lmagan kimyoviy reaktsiya tarmog'i bilan (har qanday reaktsiya keyin sodir bo'lishi mumkin), hisoblash quvvati cheklangan ibtidoiy rekursiv funktsiyalar.
Xulosa:
Men tasodifiy algoritmlarni tahlil qilish va loyihalash. Umumiy ko'rinish, usullar, topshiriqlarga misolla mavzuyimda internet olami hamda kitoblardan kerakli ma`lumotlar izlab o`zbilimlarimni mustahkamladim hamda shunga asoslanib refarat tayorladim.