الفرق بين المراجعتين ل"Algorithms/Randomized Algorithms"
(أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:الخوارزميات العشوائية}}</noinclude> الخوارزمية العشوائية هي الخوارزمية التي تستخدم...') |
|||
| سطر 13: | سطر 13: | ||
<source lang="text"> P(A|B) = \frac{P(B|A)P(A)}{P(B)} </source> | <source lang="text"> P(A|B) = \frac{P(B|A)P(A)}{P(B)} </source> | ||
| − | == المتغيرات العشوائية == | + | === المتغيرات العشوائية === |
المتغير العشوائي هو دالة تربط نتائج حدث عشوائي (مثل رمي العملة المعدنية) بقيمة حقيقية. | المتغير العشوائي هو دالة تربط نتائج حدث عشوائي (مثل رمي العملة المعدنية) بقيمة حقيقية. | ||
| سطر 27: | سطر 27: | ||
<source lang="text">Points = +50 if Head | <source lang="text">Points = +50 if Head | ||
-50 if Tail </source> | -50 if Tail </source> | ||
| − | == القيمة المتوقعة للمتغير العشوائي == | + | === القيمة المتوقعة للمتغير العشوائي === |
يمكن تعريف القيمة المتوقعة للمتغير العشوائي <code>R</code> بأنّها: | يمكن تعريف القيمة المتوقعة للمتغير العشوائي <code>R</code> بأنّها: | ||
<source lang="text"> E[R] = r1*p1 + r2*p2 + ... rk*pk </source> | <source lang="text"> E[R] = r1*p1 + r2*p2 + ... rk*pk </source> | ||
| − | تمثل <code>ri</code> قيمة <code>R</code> مع الاحتمالية <code>pi</code>.<br /> | + | تمثل <code>ri</code> قيمة <code>R</code> مع الاحتمالية <code>pi</code>.<br />ويمكن القول بأنّ القيمة المتوقعة هي مجموع حاصل ضرب الطرفين التاليين (لجميع الأحداث الممكنة): |
| − | |||
| − | ويمكن القول بأنّ القيمة المتوقعة هي مجموع حاصل ضرب الطرفين التاليين (لجميع الأحداث الممكنة): | ||
| − | |||
# احتمالية الحدث | # احتمالية الحدث | ||
# قيمة R في ذلك الحدث. | # قيمة R في ذلك الحدث. | ||
| سطر 44: | سطر 41: | ||
* والقيمة المتوقعة لرمي زهر سداسي الوجوه = = 1''(1/6) + 2''(1/6) + .... + 6*(1/6) = 3.5 | * والقيمة المتوقعة لرمي زهر سداسي الوجوه = = 1''(1/6) + 2''(1/6) + .... + 6*(1/6) = 3.5 | ||
| − | == خطية التوقع == | + | === خطية التوقع Linearity of Expectations === |
لنفترض أن <code>R1</code> و <code>R2</code> متغيران عشوائيان مجرّدان في فضاء احتمالية معين، فإنّ: | لنفترض أن <code>R1</code> و <code>R2</code> متغيران عشوائيان مجرّدان في فضاء احتمالية معين، فإنّ: | ||
| سطر 51: | سطر 48: | ||
القيمة المتوقعة لمجموع الأرقام الناتجة من رمي الزهر ثلاث مرات = <code>3 * 7/2 = 10.5</code> | القيمة المتوقعة لمجموع الأرقام الناتجة من رمي الزهر ثلاث مرات = <code>3 * 7/2 = 10.5</code> | ||
| − | == عدد المحاولات المتوقع قبل تحقيق النجاح == | + | === عدد المحاولات المتوقع قبل تحقيق النجاح === |
إذا كانت احتمالية النجاح في كل محاولة هي <code>p</code> فإن العدد المتوقع للمحاولات قبل تحقيق النجاح هو <code>1/p</code>. | إذا كانت احتمالية النجاح في كل محاولة هي <code>p</code> فإن العدد المتوقع للمحاولات قبل تحقيق النجاح هو <code>1/p</code>. | ||
مراجعة 15:22، 17 نوفمبر 2019
الخوارزمية العشوائية هي الخوارزمية التي تستخدم عددًا عشوائيًا لتقرّر الخطوة التالية في سير عملها، فعلى سبيل المثال خوارزمية الترتيب السريع العشوائية Randomized Quick Sort، تستخدم الخوارزمية عددًا عشوائيًا لاختيار المحور التالي (أو لتغيير مواقع العناصر في المصفوفة عشوائيًا). يُستفاد من العشوائية عادةً في التقليل من التعقيد الزمني والتعقيد المكاني في الخوارزميات العادية.
مقدمة رياضية
الاحتمالية المشروطة P(A | B) هي احتمالية وقوع الحدث 'A' على افتراض وقوع الحدث 'B' قبله.
P(A|B) = \frac{P(A\cup B)}{P(B)}
يمكن الاستعانة بالشكل التالية لفهم الصيغة السابقة، إذ لمّا كان الحدث 'B' قد وقع بالفعل، فإنّ فضاء العينة سيتقلّص إلى 'B' فقط؛ ولهذا فإنّ احتمالية وقوع الحدث 'A' ستصبح P(A ∩ B) مقسومًا على P(B).
تربط علاقة بايس Bayes’s forumla بين الاحتماليتين المشروطتين P(A|B) و P(B|A).
P(A|B) = \frac{P(B|A)P(A)}{P(B)}
المتغيرات العشوائية
المتغير العشوائي هو دالة تربط نتائج حدث عشوائي (مثل رمي العملة المعدنية) بقيمة حقيقية.
مثال:
لعبة رمي القطعة النقدية:
في هذه اللعبة يحصل اللاعب على 50 نقطة إن كانت نتيجة رمي القطعة النقدية (النقش) ويخسر 50 نقطة إن كانت النتيجة (الكتابة).
يمكن تعريف المتغير العشوائي لعدد النقاط النهائي الذي سيحصل عليه اللاعب كما يلي:
Points = +50 if Head
-50 if Tail
القيمة المتوقعة للمتغير العشوائي
يمكن تعريف القيمة المتوقعة للمتغير العشوائي R بأنّها:
E[R] = r1*p1 + r2*p2 + ... rk*pk
تمثل ri قيمة R مع الاحتمالية pi.
ويمكن القول بأنّ القيمة المتوقعة هي مجموع حاصل ضرب الطرفين التاليين (لجميع الأحداث الممكنة):
- احتمالية الحدث
- قيمة R في ذلك الحدث.
أمثلة:
- القيمة المتوقعة للنقاط في المثال السابق = 50 * (1/2) + (-50) * (1/2) = 0
- والقيمة المتوقعة لرمي زهر سداسي الوجوه = = 1(1/6) + 2(1/6) + .... + 6*(1/6) = 3.5
خطية التوقع Linearity of Expectations
لنفترض أن R1 و R2 متغيران عشوائيان مجرّدان في فضاء احتمالية معين، فإنّ:
E[R1 + R2] = E[R1] + E[R2]
القيمة المتوقعة لمجموع الأرقام الناتجة من رمي الزهر ثلاث مرات = 3 * 7/2 = 10.5
عدد المحاولات المتوقع قبل تحقيق النجاح
إذا كانت احتمالية النجاح في كل محاولة هي p فإن العدد المتوقع للمحاولات قبل تحقيق النجاح هو 1/p.
لنفترض أنّ سنرمي زهرًا سداسي الوجوه إلى حين الحصول على الرقم 5، فإنّ عدد الرميات المتوقعة قبل الحصول على الرقم 5 هو 6 رميات. لاحظ بأنّ احتمالية الحصول على الرقم 5 هي 1/6 في كل رمية، وبهذا يكون عدد المحاولة 1/(1/6) = 6.
وفي خوارزمية الترتيب السريع والتي تبحث فيها الخوارزمية عن العناصر المحورية إلى أن تختار العنصر الوسطي n/2 فإنّ عدد المحاولات المتوقعة للعثور لاختيار العنصر الوسطي سيكون 2 وذلك لأنّ احتمالية اختيار أحد العناصر الوسطية هو 1/2.
مصادر
- صفحة Randomized Algorithms | Set 0 (Mathematical Background) في توثيق الخوارزميات في موقع GeeksforGeeks.