با احتمال بالا

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

کاربردها

اصطلاح WHP به خصوص در علوم کامپیوتر و در تحلیل الگوریتم‌های تصادفی استفاده می‌شود. برای مثال یک الگوریتم تصادفی خاص در گرافی با 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.