باحتمالية عالية

في الرياضيات ، الحدث الذي يحدث باحتمالية عالية (غالباً ما يتم اختصاره إلى whp أو WHP ) هو الحدث الذي تعتمد احتماليته على عدد معين n ويقترب من 1 عندما يقترب n من اللانهاية، أي أن احتمال وقوع الحدث يمكن جعله أقرب ما يمكن إلى 1 عن طريق جعل n كبيرًا بما فيه الكفاية.

يُستخدم مصطلح WHP بشكل شائع في علوم الحاسوب ، وتحديدًا في تحليل الخوارزميات الاحتمالية . ^{[ 1 ]} على سبيل المثال، لنفترض وجود خوارزمية احتمالية معينة على رسم بياني مكون من n عقدة. إذا كان احتمال أن تُرجع الخوارزمية الإجابة الصحيحة هو${\displaystyle 1-1/n}$ثم عندما يكون عدد العقد كبيرًا جدًا، تكون الخوارزمية صحيحة باحتمالية قريبة جدًا من 1. ويمكن التعبير عن هذه الحقيقة باختصار بالقول إن الخوارزمية صحيحة WHP.

من الأمثلة على استخدام هذا المصطلح ما يلي:

• اختبار ميلر-رابين للأعداد الأولية : خوارزمية احتمالية لاختبار ما إذا كان العدد n أوليًا أم مركبًا. إذا كان n مركبًا، فسيكتشف الاختبار أنه مركب. هناك احتمال ضئيل أن يخطئ الاختبار ويصنف n على أنه أولي. ولكن، يمكن تقليل احتمال الخطأ إلى ما لا نهاية بإجراء الاختبار عدة مرات باستخدام عمليات عشوائية مختلفة .
• خوارزمية فريفالدز : خوارزمية عشوائية للتحقق من ضرب المصفوفات. وهي تعمل بشكل أسرع من الخوارزميات الحتمية WHP.
• شجرة البحث الثنائية العشوائية (Treap) : ارتفاعها لوغاريتمي (WHP). شجرة الاندماج (Fusion tree) هي بنية بيانات مشابهة.
• الرموز الإلكترونية : رموز عشوائية تسمح للمستخدم باستعادة رسالة WHP الأصلية.
• BQP : فئة من المسائل المعقدة التي توجد لها خوارزميات كمومية ذات وقت متعدد الحدود وهي صحيحة WHP.
• التعلم الصحيح تقريبًا : عملية للتعلم الآلي حيث يكون للدالة المتعلمة خطأ تعميم منخفض WHP.
• بروتوكولات النميمة : بروتوكول اتصال يستخدم في الأنظمة الموزعة لتوصيل الرسائل بشكل موثوق إلى المجموعة بأكملها باستخدام كمية ثابتة من موارد الشبكة على كل عقدة وضمان عدم وجود نقطة فشل واحدة.

• خوارزمية عشوائية
• من شبه المؤكد

• ميتيفيه، واي.؛ روبسون، جيه إم.؛ صاحب-جاهرومي، إن.؛ زماري، إيه. (2010). "خوارزمية MIS موزعة عشوائية ذات تعقيد بت مثالي". الحوسبة الموزعة . 23 ( 5-6 ): 331. doi : 10.1007/s00446-010-0121-5 .
• "مبادئ الحوسبة الموزعة (المحاضرة 7)" (ملف PDF) . المعهد الفدرالي السويسري للتكنولوجيا في زيورخ . تم الاطلاع عليه بتاريخ 21 فبراير 2015 .