با احتمال بالا - ویکی‌پدیا، دانشنامهٔ آزاد

در ریاضیات، رویدادی که با احتمال بالا (به اختصار w.h.p یا WHP) رخ می‌دهد، رویدادی است که احتمال آن به متغیری همچون n وابسته است و با میل n به سمت بینهایت، احتمال رویداد مورد نظر به ۱ میل می‌کند. یعنی می‌توان با انتخاب n به اندازه‌ی کافی بزرگ، مقدار آن را به اندازه‌ی دلخواه به ۱ نزدیک کرد.

کاربردها[ویرایش]

اصطلاح WHP به خصوص در علوم کامپیوتر و در تحلیل الگوریتم‌های تصادفی استفاده می‌شود. برای مثال یک الگوریتم تصادفی خاص در گرافی با n گره را در نظر بگیرید. اگر احتمال این که الگوریتم پاسخ صحیح بازگرداند، $1-1/n$ باشد، هنگامی که تعداد گره‌ها بسیار بزرگ باشد، الگوریتم با احتمال خیلی نزدیک به ۱ صحیح است. بدین ترتیب گفته می‌شود که الگوریتم با احتمال بالا (یا WHP) صحیح است.

برخی از الگوریتم‌هایی که از این اصطلاح استفاده می‌کنند:

آزمون تست اول بودن میلر-رابین: یک الگوریتم تصادفی برای تست اینکه آیا عدد داده شده ای مثل n، اول است یا مرکب استفاده می‌شود. اگر n مرکب باشد، آزمون n را با احتمال بالا (یا WHP) مرکب شناسایی می‌کند. احتمال اندکی هم وجود دارد که خوش شانس نباشیم و آزمون n را اول تشخیص دهد. با این حال، احتمال خطا را می‌توان به طور نامحدود با اجرای چندین باره آزمون کاهش داد.
الگوریتم Freivald: یک الگوریتم تصادفی برای تأیید ضرب ماتریس هاست که از الگوریتم‌های قطعی سریعتر اجرا می‌شود و با احتمال بالا پاسخ درست را برمی‌گرداند.
داده ساختار تریپ: یک درخت جستجوی دودویی تصادفی است. ارتفاع آن با احتمال بالا لگاریتمی است. درخت تلفیقی داده ساختار مرتبط با تریپ است.
کدهای آنلاین: کدهای تصادفی هستند که امکان بازیابی پیام اصلی را با احتمال بالا در اختیار می‌گذارند.
BQP: یک کلاس پیچیدگی از مسئله هاست که برای آن‌ها الگوریتم‌های با زمان اجرای چندجمله‌ای کوانتومی وجود دارند که با احتمال بالا پاسخ صحیح را برمی‌گردانند.
یادگیری احتمالاً تقریباً صحیح (Probably approximately correct learning): یک فرایند یادگیری-ماشین است که در آن تابع آموزش داده شده، با احتمال بالا خطای Generalization پایینی دارد.
پروتکل شایعه: پروتکل ارتباطی مورد استفاده در سیستم‌های توزیع شده برای تحویل پیام با قابلیت اعتماد بالا به کل خوشه (Cluster) با استفاده از مقدار ثابتی از منابع تحت شبکه ثابت در هر گره است.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

Métivier, Y.; Robson, J. M.; Saheb-Djahromi, N.; Zemmari, A. (2010). "An optimal bit complexity randomized distributed MIS algorithm". Distributed Computing. 23 (5–6): 331. doi:10.1007/s00446-010-0121-5.
"Principles of Distributed Computing (lecture 7)" (PDF). ETH Zurich. Archived from the original (PDF) on 21 February 2015. Retrieved 21 February 2015.