Katta ehtimollik bilan - With high probability

Yilda matematika, sodir bo'lgan voqea yuqori ehtimollik bilan (ko'pincha qisqartiriladi w.h.p. yoki WHP) ehtimolligi ma'lum songa bog'liq bo'lgan kishidir n va 1 ga o'ting n cheksizlikka boradi, ya'ni uni 1 ga kerakli darajada yaqinlashtirib qilish mumkin n etarlicha katta.

Ilovalar

WHP atamasi ayniqsa ishlatiladi Kompyuter fanlari, tahlilida ehtimollik algoritmlari. Masalan, bilan grafikada ma'lum bir ehtimollik algoritmini ko'rib chiqing n tugunlar. Agar algoritm to'g'ri javobni qaytarish ehtimoli bo'lsa , keyin tugunlar soni juda katta bo'lganida, algoritm juda yaqin bo'lgan ehtimollik bilan to'g'ri keladi 1. Bu haqiqat qisqa vaqt ichida algoritm WHP to'g'ri deb aytiladi.

Ushbu atama ishlatiladigan ba'zi bir misollar:

  • Miller-Rabinning dastlabki sinovi: berilgan son yoki yo'qligini tekshirish uchun ehtimollik algoritmi n asosiy yoki kompozitdir. Agar n kompozitsion, test aniqlaydi n kompozit WHP sifatida. Bizning omadimiz yo'qligi ehtimoli kichik va sinov shunday deb o'ylaydi n asosiy hisoblanadi. Ammo, testni ko'p marta turli xil randomizatsiyalash bilan bajarish orqali xato ehtimolini cheksiz kamaytirish mumkin.
  • Freivalds algoritmi: matritsani ko'paytirishni tekshirish uchun tasodifiy algoritm. WHP deterministik algoritmlaridan tezroq ishlaydi.
  • Treap: tasodifiy ikkilik qidiruv daraxti. Uning balandligi logaritmik WHP. Birlashma daraxti tegishli ma'lumotlar tuzilishi.
  • Onlayn kodlar: foydalanuvchiga WHP asl xabarini tiklashga imkon beradigan tasodifiy kodlar.
  • BQP: WHP to'g'ri bo'lgan polinomial vaqt kvant algoritmlari mavjud bo'lgan muammolarning murakkabligi sinfi.
  • Ehtimol, taxminan to'g'ri o'rganish: Mashinada o'qitish jarayoni, unda o'rganilgan funktsiya kam umumlashma-xato WHPga ega.
  • G'iybat protokollari: a aloqa protokoli ichida ishlatilgan tarqatilgan tizimlar har bir tugundagi doimiy miqdordagi tarmoq resurslaridan foydalangan holda va bitta nosozlik nuqtasini ta'minlamagan holda xabarlarni butun klasterga ishonchli etkazib berish.

Shuningdek qarang

Adabiyotlar

  • Metivier, Y .; Robson, J. M .; Saheb-Djahromi, N .; Zemmari, A. (2010). "Optimal bit murakkabligi tasodifiy tarqatilgan MIS algoritmi". Tarqatilgan hisoblash. 23 (5–6): 331. doi:10.1007 / s00446-010-0121-5.
  • "Tarqatilgan hisoblash tamoyillari (7-ma'ruza)" (PDF). ETH Tsyurix. Olingan 21 fevral 2015.