خوارزمية عشوائية

الخوارزمية العشوائية هي خوارزمية تستخدم درجة من العشوائية كجزء من منطقها أو إجراءاتها. تستخدم هذه الخوارزمية عادةً بتات عشوائية موزعة بانتظام كمدخل مساعد لتوجيه سلوكها، على أمل تحقيق أداء جيد في "الحالة المتوسطة" لجميع الخيارات الممكنة للعشوائية التي تحددها هذه البتات العشوائية؛ وبالتالي، فإن وقت التشغيل أو المخرجات (أو كليهما) متغيرات عشوائية.

يوجد فرق بين الخوارزميات التي تستخدم مدخلات عشوائية بحيث تنتهي دائمًا بالإجابة الصحيحة، ولكن يكون وقت تشغيلها المتوقع محدودًا ( مثل خوارزميات لاس فيغاس ، كخوارزمية الفرز السريع ^{[ 1 ]} )، والخوارزميات التي لديها احتمال لإنتاج نتيجة خاطئة ( مثل خوارزميات مونت كارلو ، كخوارزمية مونت كارلو لمسألة MFAS [ ^{2 ] )} أو الفشل في إنتاج نتيجة إما بالإشارة إلى فشل أو بالفشل في الإنهاء. في بعض الحالات، تُعد الخوارزميات الاحتمالية الوسيلة العملية الوحيدة لحل المشكلة. ^{[ 3 ]}

في الممارسة الشائعة، يتم تقريب الخوارزميات العشوائية باستخدام مولد أرقام شبه عشوائي بدلاً من مصدر حقيقي للبتات العشوائية؛ قد ينحرف هذا التنفيذ عن السلوك النظري المتوقع والضمانات الرياضية التي قد تعتمد على وجود مولد أرقام عشوائية حقيقي مثالي.

تحفيز

كمثال تحفيزي، فكر في مشكلة إيجاد الحرف ' a ' في مصفوفة مكونة من n عنصرًا.

المدخلات : مصفوفة من n ≥2 عنصر، نصفها من النوع ' a ' والنصف الآخر من النوع ' b '.

الناتج : ابحث عن الحرف ' a ' في المصفوفة.

نقدم نسختين من الخوارزمية، إحداهما خوارزمية لاس فيغاس والأخرى خوارزمية مونت كارلو .

خوارزمية لاس فيغاس:

دالة `findingA_LV` ( المصفوفة A ، n ) تبدأ بـ: كرر: اختر عنصرًا واحدًا عشوائيًا من بين n عنصرًا حتى يتم العثور على 'a' . تنتهي الدالة.

تنجح هذه الخوارزمية باحتمالية 1. يختلف عدد التكرارات ويمكن أن يكون كبيرًا بشكل تعسفي، ولكن العدد المتوقع للتكرارات هو

\lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2

وبما أنه ثابت، فإن وقت التشغيل المتوقع على مدى العديد من المكالمات هو $\Theta (1)$ (انظر إلى رمز ثيتا الكبير )

خوارزمية مونت كارلو:

دالة `findingA_MC` ( المصفوفة A ، n ، k ) تبدأ بـ i := 0، ثم تكرر: اختر عنصرًا واحدًا عشوائيًا من بين n عنصرًا . i : = i + 1 حتى i = k أو يتم العثور على ' a' .

إذا تم العثور على الحرف ' a '، تنجح الخوارزمية، وإلا تفشل. بعد k تكرار، يكون احتمال العثور على الحرف ' a ' هو:

$\Pr[\mathrm {find~a} ]=1-(1/2)^{k}$

لا تضمن هذه الخوارزمية النجاح، لكن زمن التشغيل محدود. عدد التكرارات دائمًا أقل من أو يساوي k. بافتراض ثبات k، يكون زمن التشغيل (المتوقع والمطلق) هو $\Theta (1)$ .

تُعدّ الخوارزميات العشوائية مفيدةً للغاية عند مواجهة "خصم" خبيث أو مهاجم يحاول عمدًا إدخال بيانات خاطئة إلى الخوارزمية (انظر: تعقيد أسوأ الحالات والتحليل التنافسي (خوارزمية عبر الإنترنت) )، كما هو الحال في معضلة السجين . لهذا السبب، تُعدّ العشوائية عنصرًا أساسيًا في علم التشفير . في تطبيقات التشفير، لا يُمكن استخدام الأرقام شبه العشوائية، لأن الخصم يستطيع التنبؤ بها، مما يجعل الخوارزمية حتمية فعليًا. لذلك، يلزم إما مصدر للأرقام العشوائية الحقيقية أو مولد أرقام شبه عشوائية آمن تشفيريًا . ومن المجالات الأخرى التي تتسم بالعشوائية، الحوسبة الكمومية .

في المثال أعلاه، تُخرج خوارزمية لاس فيغاس دائمًا الإجابة الصحيحة، لكن زمن تشغيلها متغير عشوائي. أما خوارزمية مونت كارلو (المرتبطة بطريقة مونت كارلو للمحاكاة) فهي مضمونة الإنجاز في زمن يمكن تحديده بدالة تعتمد على حجم المدخلات ومعاملها k ، مع السماح باحتمالية خطأ ضئيلة . لاحظ أنه يمكن تحويل أي خوارزمية لاس فيغاس إلى خوارزمية مونت كارلو (باستخدام متباينة ماركوف )، وذلك بجعلها تُخرج إجابة عشوائية، قد تكون خاطئة، إذا لم تُكمل عملها خلال زمن محدد. في المقابل، إذا وُجدت آلية تحقق فعّالة للتأكد من صحة الإجابة، فيمكن تحويل خوارزمية مونت كارلو إلى خوارزمية لاس فيغاس بتشغيل خوارزمية مونت كارلو بشكل متكرر حتى الحصول على إجابة صحيحة.

التعقيد الحسابي

تُصوّر نظرية التعقيد الحسابي الخوارزميات العشوائية كآلات تورينغ احتمالية . وتُدرس خوارزميتا لاس فيغاس ومونت كارلو ، بالإضافة إلى عدة فئات من التعقيد . تُعدّ فئة RP أبسط فئات التعقيد العشوائي ، وهي فئة مسائل القرار التي يوجد لها خوارزمية عشوائية فعّالة (زمنها كثير الحدود) (أو آلة تورينغ احتمالية) تُحدّد حالات "لا" بيقين مطلق، وتُحدّد حالات "نعم" باحتمالية لا تقل عن 1/2. وتُعدّ فئة co-RP الفئة المُكمّلة لفئة RP. أما فئات المسائل التي تحتوي على خوارزميات (قد تكون غير منتهية) ذات زمن تشغيل متوسط كثير الحدود، والتي يكون ناتجها صحيحًا دائمًا، فتُصنّف ضمن فئة ZPP .

تُسمى فئة المسائل التي يُسمح فيها بتحديد كل من حالات "نعم" و"لا" مع وجود هامش خطأ معين، فئة BPP . وتعمل هذه الفئة كمكافئ عشوائي للمسألة P ، أي أن BPP تمثل فئة الخوارزميات العشوائية الفعالة.

التاريخ المبكر

فرز

اكتشف توني هوار خوارزمية الفرز السريع عام 1959، ونُشرت لاحقًا عام 1961. ^{[ 4 ]} وفي العام نفسه، نشر هوار خوارزمية الاختيار السريع ، ^{[ 5 ]} التي تجد العنصر الوسيط في قائمة ما في زمن خطي متوقع. وظل السؤال مطروحًا حتى عام 1973 حول ما إذا كانت هناك خوارزمية حتمية ذات زمن خطي. ^{[ 6 ]}

نظرية الأعداد

في عام ١٩١٧، قدّم هنري كابورن بوكلينغتون خوارزمية عشوائية تُعرف بخوارزمية بوكلينغتون لإيجاد الجذور التربيعية بكفاءة للأعداد الأولية. ^{[ ٧ ]} وفي عام ١٩٧٠، قدّم إلوين بيرلكامب خوارزمية عشوائية لحساب جذور كثير الحدود بكفاءة على حقل منتهٍ. ^{[ ٨ ]} وفي عام ١٩٧٧، اكتشف روبرت م. سولوفاي وفولكر ستراسن اختبارًا عشوائيًا لتحديد أولية الأعداد في زمن متعدد الحدود (أي تحديد أولية عدد ما). وبعد ذلك بوقت قصير، أثبت مايكل أو. رابين إمكانية تحويل اختبار ميلر لأولية الأعداد لعام ١٩٧٦ إلى خوارزمية عشوائية في زمن متعدد الحدود. في ذلك الوقت، لم تكن هناك خوارزميات حتمية قابلة للإثبات لاختبار أولية الأعداد في زمن متعدد الحدود معروفة.

هياكل البيانات

تُعدّ جداول التجزئة من أوائل هياكل البيانات العشوائية ، وقد طُرحت عام 1953 على يد هانز بيتر لونه في شركة آي بي إم . ^{[ 9 ]} استخدم جدول التجزئة الخاص بلونه تقنية التسلسل لحلّ التصادمات، وكان أيضًا من أوائل تطبيقات القوائم المتصلة . ^{[ 9 ]} لاحقًا، في عام 1954، قدّم كلٌّ من جين أمدال ، وإيلين إم. ماكجرو ، وناثانيال روتشستر ، وآرثر صموئيل من قسم الأبحاث في شركة آي بي إم، تقنية الاستكشاف الخطي ، ^{[ 9 ]} على الرغم من أن أندريه إرشوف كان لديه الفكرة نفسها بشكل مستقل عام 1957. ^{[ 9 ]} في عام 1962، أجرى دونالد كنوث أول تحليل صحيح للاستكشاف الخطي، ^{[ 9 ]} مع أن المذكرة التي تتضمن تحليله لم تُنشر إلا بعد ذلك بكثير. ^{[ 10 ]} أما أول تحليل منشور فكان من نصيب كونهايم ووايس عام 1966. ^{[ 11 ]}

افترضت الدراسات المبكرة حول جداول التجزئة إما إمكانية الوصول إلى دالة تجزئة عشوائية تمامًا أو أن المفاتيح نفسها عشوائية. ^{[ 9 ]} في عام 1979، قدم كارتر وويغمان دوال التجزئة الشاملة ، ^{[ 12 ]} والتي أظهرا أنه يمكن استخدامها لتنفيذ جداول التجزئة المتسلسلة بزمن متوقع ثابت لكل عملية.

لم تقتصر الأعمال المبكرة على هياكل البيانات العشوائية على جداول التجزئة فحسب، بل امتدت لتشمل مجالات أخرى. ففي عام 1970، قدم بيرتون هوارد بلوم هيكل بيانات يعتمد على العضوية التقريبية يُعرف باسم مرشح بلوم . ^{[ 13 ]} وفي عام 1989، قدم رايموند سيدل وسيسيليا ر. أراغون شجرة بحث متوازنة عشوائية تُعرف باسم شجرة البحث المتوازنة العشوائية (treap) . ^{[ 14 ]} وفي العام نفسه، قدم ويليام بو شجرة بحث عشوائية أخرى تُعرف باسم قائمة التخطي . ^{[ 15 ]}

الاستخدامات الضمنية في علم التوافيق

قبل شيوع استخدام الخوارزميات العشوائية في علوم الحاسوب، ساهم بول إيردوس في نشر استخدام الإنشاءات العشوائية كتقنية رياضية لإثبات وجود الكائنات الرياضية. عُرفت هذه التقنية باسم الطريقة الاحتمالية . ^{[ 16 ]} قدّم إيردوس أول تطبيق له للطريقة الاحتمالية عام 1947، عندما استخدم إنشاءً عشوائيًا بسيطًا لإثبات وجود رسوم بيانية رامزي. ^{[ 17 ]} وفي عام 1959، استخدم خوارزمية عشوائية أكثر تطورًا لإثبات وجود رسوم بيانية ذات محيط كبير وعدد لوني عالٍ. ^{[ 18 ]}^{[ 16 ]}

أمثلة

فرز سريع

تُعدّ خوارزمية الفرز السريع خوارزميةً مألوفةً وشائعة الاستخدام، حيث يُمكن أن يكون للعشوائية دورٌ هام. تتطلب العديد من النسخ الحتمية لهذه الخوارزمية زمنًا قدره O ( n² ⁾ لفرز n عددًا لفئة مُحددة جيدًا من المدخلات المُنحلة (مثل مصفوفة مُرتبة مُسبقًا)، وتُحدد بروتوكولات اختيار العناصر المحورية فئة المدخلات التي تُنتج هذا السلوك. مع ذلك، إذا اختارت الخوارزمية العناصر المحورية عشوائيًا وبشكلٍ مُنتظم، فإن احتمالية إتمامها في زمن قدره O ( n log n ) عاليةٌ بشكلٍ مُثبت، بغض النظر عن خصائص المُدخلات.

الإنشاءات التزايدية العشوائية في الهندسة

في الهندسة الحسابية ، تتمثل إحدى التقنيات القياسية لبناء بنية مثل الغلاف المحدب أو تثليث ديلاوناي في تبديل نقاط الإدخال عشوائيًا ثم إدخالها واحدة تلو الأخرى في البنية الموجودة. يضمن هذا التوزيع العشوائي أن يكون عدد التغييرات المتوقعة في البنية الناتجة عن الإدخال صغيرًا، وبالتالي يمكن تحديد الحد الأقصى لوقت تشغيل الخوارزمية. تُعرف هذه التقنية باسم البناء التزايدي العشوائي . ^{[ 19 ]}

قطع صغير

المدخلات : رسم بياني G ( V , E )

الناتج : قطع يقسم الرؤوس إلى L و R ، مع الحد الأدنى من عدد الحواف بين L و R.

تذكر أن انكماش عقدتين، u و v ، في رسم بياني (متعدد) ينتج عنه عقدة جديدة u ' ذات حواف تمثل اتحاد الحواف المتصلة إما بـ u أو v ، باستثناء أي حافة (حواف) تربط u و v . يوضح الشكل 1 مثالاً على انكماش الرأسين A و B. بعد الانكماش، قد يحتوي الرسم البياني الناتج على حواف متوازية، ولكنه لا يحتوي على حلقات ذاتية.

الشكل 2: تشغيل ناجح لخوارزمية كارغر على رسم بياني مكون من 10 رؤوس. يبلغ حجم القطع الأدنى 3 ويتم الإشارة إليه بألوان الرؤوس.

خوارزمية كارغر الأساسية ^{[ 20 ]} :

يبدأ i = 1 كرر كرر خذ حافة عشوائية (u,v) ∈ E في G استبدل الحرفين u و v بالاختصار u' حتى تبقى عقدتان فقط احصل على نتيجة القطع المقابلة C _i i = i + 1 حتى i = m أخرج الحد الأدنى للقطع بين C1 _، C2 _، ...، _Cm . نهاية

في كل تنفيذ للحلقة الخارجية، تُكرر الخوارزمية الحلقة الداخلية حتى يتبقى عقدتان فقط، ويتم الحصول على القطع المقابل. زمن تشغيل التنفيذ الواحد هو $O(n)$ ، حيث يُمثل n عدد الرؤوس. بعد تنفيذ الحلقة الخارجية m مرة، نُخرج أصغر قطع من بين جميع النتائج. يُوضح الشكل 2 مثالًا على تنفيذ واحد للخوارزمية. بعد التنفيذ، نحصل على قطع بحجم 3.

اللمة 1 - ليكن k هو الحد الأدنى لحجم القطع، وليكن $C = {e 1, e 2, ..., e k}$ هو الحد الأدنى للقطع. إذا لم يتم اختيار أي حافة $e$ $\in$ $C$ للتقليص خلال التكرار i ، فإن $C$ $i$ $=$ $C$ .

دليل

إذا لم يكن الرسم البياني G متصلاً، فيمكن تقسيمه إلى L و R دون وجود أي حافة بينهما. لذا، فإن القطع الأدنى في الرسم البياني غير المتصل يساوي صفرًا. الآن، لنفترض أن G متصل. ليكن $V = L \cup R$ هو تقسيم V الناتج عن $C : C = { {u, v} \in E : u \in L, v \in R$ } (معرّف جيدًا لأن G متصل). لنعتبر الحافة { u , v } من C. في البداية، u و v رأسان مختلفان. طالما أننا نختار حافة ⁠ $f\neq e$ لا يتم دمج u و v. بالتالي ، $في$ نهايةالخوارزمية، لدينا عقدتان مركبتان تغطيان الرسم البياني بأكمله، إحداهما تتكون من رؤوسLوالأخرى من رؤوسR. $كما هو موضح$ في الشكل 2، حجم القطع الأدنى هو 1، وC= {(A,B)}. إذا لم نختر (A,B) للانكماش، فسنحصل على القطع الأدنى.

اللمة 2 - إذا كان G عبارة عن رسم بياني متعدد الرؤوس يحتوي على p رأسًا وكان القطع الأدنى له حجم k ، فإن G يحتوي على pk /2 حافة على الأقل .

دليل

بما أن القطع الأدنى هو k ، فإن كل رأس v يجب أن يحقق الشرط التالي: درجة( v ) ≥ k . بالتالي، فإن مجموع الدرجات يساوي على الأقل pk . ولكن من المعروف أن مجموع درجات الرؤوس يساوي 2 | E | . ومن ثمّ، تُستنتج اللمة.

تحليل الخوارزمية

احتمال نجاح الخوارزمية هو 1 - احتمال فشل جميع المحاولات. وبحسب مبدأ الاستقلال، فإن احتمال فشل جميع المحاولات هو $\prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).$

بحسب اللمة 1، فإن احتمال أن يكون $C i = C$ j هو احتمال عدم اختيار أي حافة من C i خلال التكرار i . لنفترض الحلقة الداخلية، ولنرمز بـ $G j$ إلى الرسم البياني بعد j انقباضات للحواف، حيث $j \in {0, 1, \dots, n - 3}$ . يحتوي $G j$ $على n - j$ رأسًا. نستخدم قاعدة السلسلة للاحتمالات الشرطية . احتمال أن تكون الحافة المختارة في التكرار j ليست من C j، علمًا بأنه لم يتم اختيار أي حافة من C j من قبل، هو $1-{\frac {k}{|E(G_{j})|}}$ لاحظ أن $G j$ لا يزال لديه قطع أدنى بحجم k ، لذا وفقًا للنتيجة 2، فإنه لا يزال لديه على الأقل ${\frac {(nj)k}{2}}$ الحواف.

هكذا، $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{nj}}={\frac {nj-2}{nj}}$ .

وبناءً على قاعدة السلسلة، فإن احتمال إيجاد القطع الأدنى C هو $\Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).$

إلغاء $\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}$ وبالتالي، فإن احتمال نجاح الخوارزمية هو على الأقل $1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}$ . ل $m={\frac {n(n-1)}{2}}\ln n$ وهذا يعادل $1-{\frac {1}{n}}$ تجد الخوارزمية القطع الأدنى باحتمالية $1-{\frac {1}{n}}$ مع مرور الوقت $O(mn)=O(n^{3}\log n)$ .

إلغاء العشوائية

يمكن النظر إلى العشوائية كمورد، كالمساحة والوقت. وتُعرف عملية إزالة العشوائية بأنها عملية التخلص من العشوائية (أو استخدام أقل قدر ممكن منها). ^{[ 21 ]}^{[ 22 ]} ولا يُعرف حاليًا ما إذا كان بالإمكان إزالة العشوائية من جميع الخوارزميات دون زيادة وقت تشغيلها بشكل ملحوظ. ^[²³^] فعلى سبيل المثال، في التعقيد الحسابي ، من غير المعروف ما إذا كان P = BPP ، ^[²³^] أي أننا لا نعرف ما إذا كان بإمكاننا أخذ خوارزمية عشوائية تعمل في وقت متعدد الحدود باحتمالية خطأ صغيرة، وإزالة عشوائيتها لتشغيلها في وقت متعدد الحدود دون استخدام العشوائية.

توجد طرق محددة يمكن استخدامها لإزالة العشوائية من خوارزميات عشوائية معينة:

طريقة الاحتمالات الشرطية ، وتعميمها، المقدرات التشاؤمية
نظرية التباين (التي تُستخدم لإزالة العشوائية من الخوارزميات الهندسية)
استغلال الاستقلال المحدود في المتغيرات العشوائية المستخدمة بواسطة الخوارزمية، مثل الاستقلال الزوجي المستخدم في التجزئة الشاملة ^{[ 24 ]}
استخدام الرسوم البيانية الموسعة (أو المشتتات بشكل عام) لتضخيم كمية محدودة من العشوائية الأولية (يشار إلى هذا النهج الأخير أيضًا باسم توليد بتات شبه عشوائية من مصدر عشوائي، ويؤدي إلى الموضوع ذي الصلة وهو العشوائية الزائفة).
يتم تغيير الخوارزمية العشوائية لاستخدام دالة تجزئة كمصدر للعشوائية في مهامها، ثم إزالة العشوائية من الخوارزمية عن طريق تجربة جميع المعاملات (البذور) الممكنة لدالة التجزئة. تُستخدم هذه التقنية عادةً للبحث الشامل في فضاء العينة وجعل الخوارزمية حتمية (مثل خوارزميات الرسوم البيانية العشوائية).

حيث تساعد العشوائية

عندما يقتصر نموذج الحوسبة على آلات تورينج ، يبقى السؤال مطروحًا حول ما إذا كانت القدرة على اتخاذ خيارات عشوائية تسمح بحل بعض المسائل في وقت متعدد الحدود، والتي لا يمكن حلها في وقت متعدد الحدود بدون هذه القدرة؛ وهذا هو السؤال عما إذا كان P = BPP. مع ذلك، في سياقات أخرى، توجد أمثلة محددة لمسائل تُحقق فيها العشوائية تحسينات ملحوظة.

استنادًا إلى المثال التحفيزي الأولي: بالنظر إلى سلسلة طويلة بشكل أسي مكونة من 2 ^k حرفًا، نصفها a ونصفها b، فإن آلة الوصول العشوائي تتطلب 2 ^{k −1} عملية بحث في أسوأ الحالات للعثور على فهرس a ؛ إذا سُمح لها بإجراء اختيارات عشوائية، فيمكنها حل هذه المشكلة في عدد كثير الحدود المتوقع من عمليات البحث.
تتمثل الطريقة الطبيعية لإجراء العمليات الحسابية العددية في الأنظمة المدمجة أو الأنظمة السيبرانية الفيزيائية في تقديم نتيجة تقارب النتيجة الصحيحة باحتمالية عالية (أو ما يُعرف بالحساب الصحيح التقريبي المحتمل). ويمكن معالجة المشكلة المعقدة المرتبطة بتقييم فرق التباين بين النتيجة التقريبية والنتيجة الصحيحة بفعالية من خلال اللجوء إلى العشوائية ^{[ 25 ].}
في مجال تعقيد الاتصالات ، يمكن التحقق من تساوي سلسلتين إلى حد معين من الموثوقية باستخدام $\log n$ أجزاء من الاتصال ببروتوكول عشوائي. أي بروتوكول حتمي يتطلب $\Theta (n)$ ^[²⁶^]
يمكن تقدير حجم جسم محدب بدقة اختيارية باستخدام خوارزمية عشوائية في وقت متعدد الحدود. ^{[ 27 ]} وقد أثبت باراني وفوريدي أنه لا توجد خوارزمية حتمية قادرة على فعل الشيء نفسه. ^[²⁸^] وهذا صحيح بشكل مطلق، أي دون الاعتماد على أي افتراضات نظرية التعقيد، بافتراض أن الجسم المحدب لا يمكن الاستعلام عنه إلا كصندوق أسود.
من الأمثلة الأكثر تعقيدًا من منظور نظرية التعقيد، حيث يبدو أن العشوائية تُسهم في الحل، فئة IP . تتألف IP من جميع اللغات التي يمكن قبولها (باحتمالية عالية) من خلال تفاعل طويل متعدد الحدود بين مُثبت ذي قدرة مطلقة ومُدقِّق يُنفِّذ خوارزمية BPP. IP = PSPACE . ^{[ 29 ]} مع ذلك، إذا كان من المطلوب أن يكون المُدقِّق حتميًا، فإن IP = NP .
في شبكة التفاعلات الكيميائية (مجموعة محدودة من التفاعلات مثل A + B → 2C + D التي تحدث على عدد محدود من الجزيئات)، يمكن تحديد إمكانية الوصول إلى حالة هدف معينة من حالة ابتدائية، بينما حتى تقريب احتمالية الوصول إلى حالة هدف معينة (باستخدام الاحتمالية القياسية القائمة على التركيز للتفاعل التالي) غير قابل للتحديد. وبشكل أكثر تحديدًا، يمكن محاكاة آلة تورينج محدودة باحتمالية عالية جدًا للعمل بشكل صحيح طوال الوقت، فقط في حالة استخدام شبكة تفاعلات كيميائية عشوائية. أما مع شبكة تفاعلات كيميائية بسيطة غير حتمية (حيث يمكن أن يحدث أي تفاعل تالي)، فإن القدرة الحسابية تقتصر على الدوال التكرارية الأولية . ^{[ 30 ]}

انظر أيضاً

ملحوظات

↑ هوار، كار (يوليو 1961). "الخوارزمية 64: الفرز السريع". مجلة الاتصالات ACM . 4 (7): 321–. doi : 10.1145/366622.366644 . ISSN 0001-0782 .
↑ كوديليتش، روبرت (2016-04-01). "خوارزمية مونت كارلو العشوائية لمسألة مجموعة أقواس التغذية الراجعة الدنيا". الحوسبة اللينة التطبيقية . 41 : 235-246 . doi : 10.1016/j.asoc.2015.12.018 .
↑ «عند اختبار أولية أعداد كبيرة جدًا مختارة عشوائيًا، يكون احتمال العثور على قيمة تُخادع اختبار فيرما أقل من احتمال تسبب الإشعاع الكوني في ارتكاب الحاسوب خطأً أثناء تنفيذ خوارزمية "صحيحة". إن اعتبار خوارزمية ما غير كافية للسبب الأول دون الثاني يُوضح الفرق بين الرياضيات والهندسة.» هال أبيلسون وجيرالد ج. سوسمان (1996). بنية وتفسير برامج الحاسوب . مطبعة معهد ماساتشوستس للتكنولوجيا ، القسم 1.2. مؤرشف في 3 سبتمبر 2006 على موقع Wayback Machine .
↑ هوار، كار (يوليو 1961). "الخوارزمية 64: الفرز السريع" . اتصالات رابطة آلات الحوسبة . 4 (7): 321. doi : 10.1145/366622.366644 . ISSN 0001-0782 .
↑ هوار، سي إيه آر (يوليو 1961). "الخوارزمية 65: البحث" . اتصالات رابطة آلات الحوسبة . 4 (7): 321-322 . doi : 10.1145/366622.366647 . ISSN 0001-0782 .
↑ بلوم، مانويل؛ فلويد، روبرت و.؛ برات، فوغان؛ ريفست، رونالد ل.؛ تارجان، روبرت إي. (أغسطس 1973). "الحدود الزمنية للاختيار" . مجلة علوم الحاسوب والنظم . 7 (4): 448-461 . doi : 10.1016/S0022-0000(73)80033-9 .
↑ ويليامز، إتش سي ؛ شاليت، جيه أو (1994)، "تحليل الأعداد الصحيحة قبل الحواسيب"، في غاوتشي، والتر (محرر)، رياضيات الحوسبة 1943-1993: نصف قرن من الرياضيات الحاسوبية؛ أوراق من ندوة التحليل العددي والندوة المصغرة حول نظرية الأعداد الحاسوبية التي عُقدت في فانكوفر، كولومبيا البريطانية، 9-13 أغسطس 1993 ، وقائع ندوات في الرياضيات التطبيقية، المجلد 48، الجمعية الأمريكية للرياضيات، بروفيدنس، رود آيلاند، الصفحات 481-531 ، doi : 10.1090/psapm/048/1314885 ، ISBN 978-0-8218-0291-5MR 1314885 انظر الصفحة 504، "ربما يستحق بوكلينجتون أيضًا الفضل كمخترع للخوارزمية العشوائية".
↑ بيرلكامب، إي آر (1971). "تحليل كثيرات الحدود على الحقول المنتهية الكبيرة" . وقائع ندوة ACM الثانية حول المعالجة الرمزية والجبرية - SYMSAC '71 . لوس أنجلوس، كاليفورنيا، الولايات المتحدة: مطبعة ACM. ص 223. doi : 10.1145/800204.806290 . ISBN 9781450377867. S2CID 6464612 .
1 2 3 4 5 6 كنوت، دونالد إي. (1998). فن برمجة الحاسوب، المجلد 3: (الطبعة الثانية) الفرز والبحث . الولايات المتحدة الأمريكية: شركة أديسون ويسلي لونغمان للنشر، الصفحات 536-549 . ISBN 978-0-201-89685-5.
↑ كنوت، دونالد (1963)، ملاحظات حول العنونة "المفتوحة" ، مؤرشفة من الأصل في 2016-03-03
↑ كونهايم، آلان ج.؛ فايس، بنيامين (نوفمبر 1966). "منهجية الإشغال وتطبيقاتها" . مجلة SIAM للرياضيات التطبيقية . 14 (6): 1266-1274 . doi : 10.1137/0114101 . ISSN 0036-1399 .
↑ كارتر، ج. لورانس؛ ويغمان، مارك ن. (1979-04-01). "الفئات العامة لدوال التجزئة" . مجلة علوم الحاسوب والأنظمة . 18 (2): 143-154 . doi : 10.1016/0022-0000(79)90044-8 . ISSN 0022-0000 .
↑ بلوم، بيرتون هـ. (يوليو 1970). "المفاضلات بين المساحة والوقت في ترميز التجزئة مع الأخطاء المسموح بها" . اتصالات رابطة آلات الحوسبة . 13 (7): 422-426 . doi : 10.1145/362686.362692 . ISSN 0001-0782 . S2CID 7931252 .
↑ أراغون، سي آر؛ سيدل، آر جي (أكتوبر 1989). "أشجار البحث العشوائية". الندوة السنوية الثلاثون حول أسس علوم الحاسوب . الصفحات 540-545 . doi : 10.1109/SFCS.1989.63531 . ISBN 0-8186-1982-1.
↑ بو، ويليام (أبريل 1989). الصيانة المتزامنة لقوائم التخطي (PS، PDF) (تقرير فني). قسم علوم الحاسوب، جامعة ميريلاند. CS-TR-2222.
1 2 ألون، نوغا ؛ سبنسر، جويل هـ. (2016). المنهج الاحتمالي ( الطبعة الرابعة). هوبوكين، نيو جيرسي: وايلي. ISBN 978-1-119-06195-3. OCLC 910535517 .
↑ P. Erdős: بعض الملاحظات حول نظرية الرسوم البيانية، نشرة الجمعية الأمريكية للرياضيات 53 (1947)، 292-294 MR 8,479d؛ Zentralblatt 32,192.
↑ إردوس، ب. (1959). "نظرية الرسم البياني والاحتمالات" . المجلة الكندية للرياضيات . 11 : 34-38 . doi : 10.4153/CJM-1959-003-9 . ISSN 0008-414X . S2CID 122784453 .
↑ Seidel R. التحليل العكسي للخوارزميات الهندسية العشوائية .
↑ كارغر، ديفيد ر. (1999). "المعاينة العشوائية في مسائل القطع والتدفق وتصميم الشبكات". رياضيات بحوث العمليات . 24 (2): 383-413 . CiteSeerX 10.1.1.215.794 . doi : 10.1287/moor.24.2.383 .
↑ "محاضرة 22 من مقرر 6.046J: إزالة العشوائية | تصميم وتحليل الخوارزميات | الهندسة الكهربائية وعلوم الحاسوب" . MIT OpenCourseWare . تاريخ الاسترجاع: 27-12-2024 .
↑ لوبي، مايكل؛ ويغدرسون، آفي (يوليو 1995). الاستقلال الزوجي وإزالة العشوائية (تقرير). الولايات المتحدة الأمريكية: جامعة كاليفورنيا في بيركلي.
1 2 "ملاحظات المحاضرة، الفصل 3. تقنيات إزالة العشوائية الأساسية" . people.seas.harvard.edu . تم الاطلاع عليه بتاريخ 27-12-2024 .
↑ شازيل، ب.؛ فريدمان، ج. (1990-09-01). "نظرة حتمية لأخذ العينات العشوائية واستخدامها في الهندسة" . كومبيناتوريكا . 10 (3): 229-249 . doi : 10.1007/BF02122778 . ISSN 1439-6912 .
↑ أليبي، سيزار (2014)، الذكاء للأنظمة المدمجة ، سبرينغر، ISBN 978-3-319-05278-6.
↑ كوشيليفيتز، إيال؛ نيسان، نوام (2006)، تعقيد الاتصال ، مطبعة جامعة كامبريدج، رقم ISBN 9780521029834. للاطلاع على الحد الأدنى الحتمي، انظر الصفحة 11؛ للاطلاع على الحد الأعلى العشوائي اللوغاريتمي، انظر الصفحات 31-32.
↑ داير، م.؛ فريز، أ.؛ كانان، ر. (1991)، "خوارزمية عشوائية متعددة الحدود لتقريب حجم الأجسام المحدبة" (ملف PDF) ، مجلة ACM ، 38 (1): 1-17 ، doi : 10.1145/102782.102783 ، S2CID 13268711
↑ فوريدي، ز .؛ باراني، إ. (1986)، "حساب الحجم أمر صعب"، وقائع الندوة الثامنة عشرة لجمعية الحوسبة الآلية حول نظرية الحوسبة (بيركلي، كاليفورنيا، 28-30 مايو 1986) (ملف PDF) ، نيويورك، نيويورك: جمعية الحوسبة الآلية، الصفحات 442-447 ، CiteSeerX 10.1.1.726.9448 ، doi : 10.1145/12130.12176 ، ISBN 0-89791-193-8، S2CID 17867291
↑ شامير، أ. (1992)، "IP = PSPACE"، مجلة ACM ، 39 (4): 869-877 ، doi : 10.1145/146585.146609 ، S2CID 315182
↑ كوك، ماثيو ؛ سولوفيتشيك، ديفيد؛ وينفري، إريك ؛ بروك، يهوشوا (2009)، "قابلية برمجة شبكات التفاعلات الكيميائية"، في كوندون، آن ؛ هاريل، ديفيد ؛ كوك، جوست ن.؛ سالوما، أرتو ؛ وينفري، إريك (محررون)، العمليات الحيوية الخوارزمية (ملف PDF) ، سلسلة الحوسبة الطبيعية، سبرينغر-فيرلاغ، الصفحات 543-584 ، doi : 10.1007/978-3-540-88869-7_27 ، ISBN 978-3-540-88868-0.

مراجع

توماس هـ. كورمن ، تشارلز إي. ليسرسون ، رونالد ل. ريفست ، وكليفورد شتاين . مقدمة في الخوارزميات ، الطبعة الثانية. مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، 1990. ISBN 0-262-03293-7الفصل الخامس: التحليل الاحتمالي والخوارزميات العشوائية، الصفحات 91-122.
ديرك دراهيم. " دلالات حساب لامدا الاحتمالي المكتوب (دلالات سلسلة ماركوف، وسلوك الإنهاء، والدلالات الدلالية). " سبرينغر، 2017.
جون كلاينبرغ وإيفا تاردوس . تصميم الخوارزميات . الفصل 13: "الخوارزميات العشوائية".
فاليس، د. (2000). "موثوقية الخوارزميات العشوائية". المجلة البريطانية لفلسفة العلوم . 51 (2): 255-271 . doi : 10.1093/bjps/51.2.255 .
م. ميتزنماخر وإ . أوبفال . الاحتمالات والحوسبة: الخوارزميات العشوائية والتحليل الاحتمالي . مطبعة جامعة كامبريدج، نيويورك (نيويورك)، 2005.
راجيف موتاني وب. راغافان. الخوارزميات العشوائية . مطبعة جامعة كامبريدج، نيويورك (نيويورك)، 1995.
راجيف موتاني وب. راغافان. الخوارزميات العشوائية . دراسة استقصائية حول الخوارزميات العشوائية.
كريستوس باباديميتريو (1993)، التعقيد الحسابي ( الطبعة الأولى)، أديسون ويسلي، رقم ISBN 978-0-201-53082-7الفصل 11: الحساب العشوائي، الصفحات 241-278.
رابين، مايكل أو. (1980). "خوارزمية احتمالية لاختبار أولية الأعداد" . مجلة نظرية الأعداد . 12 : 128-138 . doi : 10.1016/0022-314X(80)90084-0 .
AA Tsay, WS Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems , Mathematics of Operations Research, 24(2):383–413, 1999.
"الخوارزميات العشوائية للحوسبة العلمية" (RASC)، OSTI.GOV (10 يوليو 2021).

[1] هوار، كار (يوليو 1961). "الخوارزمية 64: الفرز السريع". مجلة الاتصالات ACM . 4 (7): 321–. doi : 10.1145/366622.366644 . ISSN 0001-0782 .

[2] كوديليتش، روبرت (2016-04-01). "خوارزمية مونت كارلو العشوائية لمسألة مجموعة أقواس التغذية الراجعة الدنيا". الحوسبة اللينة التطبيقية . 41 : 235-246 . doi : 10.1016/j.asoc.2015.12.018 .

[3] «عند اختبار أولية أعداد كبيرة جدًا مختارة عشوائيًا، يكون احتمال العثور على قيمة تُخادع اختبار فيرما أقل من احتمال تسبب الإشعاع الكوني في ارتكاب الحاسوب خطأً أثناء تنفيذ خوارزمية "صحيحة". إن اعتبار خوارزمية ما غير كافية للسبب الأول دون الثاني يُوضح الفرق بين الرياضيات والهندسة.» هال أبيلسون وجيرالد ج. سوسمان (1996). بنية وتفسير برامج الحاسوب . مطبعة معهد ماساتشوستس للتكنولوجيا ، القسم 1.2. مؤرشف في 3 سبتمبر 2006 على موقع Wayback Machine .

[4] هوار، كار (يوليو 1961). "الخوارزمية 64: الفرز السريع" . اتصالات رابطة آلات الحوسبة . 4 (7): 321. doi : 10.1145/366622.366644 . ISSN 0001-0782 .

[5] هوار، سي إيه آر (يوليو 1961). "الخوارزمية 65: البحث" . اتصالات رابطة آلات الحوسبة . 4 (7): 321-322 . doi : 10.1145/366622.366647 . ISSN 0001-0782 .

[6] بلوم، مانويل؛ فلويد، روبرت و.؛ برات، فوغان؛ ريفست، رونالد ل.؛ تارجان، روبرت إي. (أغسطس 1973). "الحدود الزمنية للاختيار" . مجلة علوم الحاسوب والنظم . 7 (4): 448-461 . doi : 10.1016/S0022-0000(73)80033-9 .

[7] ويليامز، إتش سي ؛ شاليت، جيه أو (1994)، "تحليل الأعداد الصحيحة قبل الحواسيب"، في غاوتشي، والتر (محرر)، رياضيات الحوسبة 1943-1993: نصف قرن من الرياضيات الحاسوبية؛ أوراق من ندوة التحليل العددي والندوة المصغرة حول نظرية الأعداد الحاسوبية التي عُقدت في فانكوفر، كولومبيا البريطانية، 9-13 أغسطس 1993 ، وقائع ندوات في الرياضيات التطبيقية، المجلد 48، الجمعية الأمريكية للرياضيات، بروفيدنس، رود آيلاند، الصفحات 481-531 ، doi : 10.1090/psapm/048/1314885 ، ISBN 978-0-8218-0291-5MR 1314885 انظر الصفحة 504، "ربما يستحق بوكلينجتون أيضًا الفضل كمخترع للخوارزمية العشوائية".

[8] بيرلكامب، إي آر (1971). "تحليل كثيرات الحدود على الحقول المنتهية الكبيرة" . وقائع ندوة ACM الثانية حول المعالجة الرمزية والجبرية - SYMSAC '71 . لوس أنجلوس، كاليفورنيا، الولايات المتحدة: مطبعة ACM. ص 223. doi : 10.1145/800204.806290 . ISBN 9781450377867. S2CID 6464612 .

[:0-9] 1 2 3 4 5 6 كنوت، دونالد إي. (1998). فن برمجة الحاسوب، المجلد 3: (الطبعة الثانية) الفرز والبحث . الولايات المتحدة الأمريكية: شركة أديسون ويسلي لونغمان للنشر، الصفحات 536-549 . ISBN 978-0-201-89685-5.

[10] كنوت، دونالد (1963)، ملاحظات حول العنونة "المفتوحة" ، مؤرشفة من الأصل في 2016-03-03

[11] كونهايم، آلان ج.؛ فايس، بنيامين (نوفمبر 1966). "منهجية الإشغال وتطبيقاتها" . مجلة SIAM للرياضيات التطبيقية . 14 (6): 1266-1274 . doi : 10.1137/0114101 . ISSN 0036-1399 .

[12] كارتر، ج. لورانس؛ ويغمان، مارك ن. (1979-04-01). "الفئات العامة لدوال التجزئة" . مجلة علوم الحاسوب والأنظمة . 18 (2): 143-154 . doi : 10.1016/0022-0000(79)90044-8 . ISSN 0022-0000 .

[13] بلوم، بيرتون هـ. (يوليو 1970). "المفاضلات بين المساحة والوقت في ترميز التجزئة مع الأخطاء المسموح بها" . اتصالات رابطة آلات الحوسبة . 13 (7): 422-426 . doi : 10.1145/362686.362692 . ISSN 0001-0782 . S2CID 7931252 .

[14] أراغون، سي آر؛ سيدل، آر جي (أكتوبر 1989). "أشجار البحث العشوائية". الندوة السنوية الثلاثون حول أسس علوم الحاسوب . الصفحات 540-545 . doi : 10.1109/SFCS.1989.63531 . ISBN 0-8186-1982-1.

[15] بو، ويليام (أبريل 1989). الصيانة المتزامنة لقوائم التخطي (PS، PDF) (تقرير فني). قسم علوم الحاسوب، جامعة ميريلاند. CS-TR-2222.

[:1-16] 1 2 ألون، نوغا ؛ سبنسر، جويل هـ. (2016). المنهج الاحتمالي ( الطبعة الرابعة). هوبوكين، نيو جيرسي: وايلي. ISBN 978-1-119-06195-3. OCLC 910535517 .

[17] P. Erdős: بعض الملاحظات حول نظرية الرسوم البيانية، نشرة الجمعية الأمريكية للرياضيات 53 (1947)، 292-294 MR 8,479d؛ Zentralblatt 32,192.

[18] إردوس، ب. (1959). "نظرية الرسم البياني والاحتمالات" . المجلة الكندية للرياضيات . 11 : 34-38 . doi : 10.4153/CJM-1959-003-9 . ISSN 0008-414X . S2CID 122784453 .

[19] Seidel R. التحليل العكسي للخوارزميات الهندسية العشوائية .

[20] كارغر، ديفيد ر. (1999). "المعاينة العشوائية في مسائل القطع والتدفق وتصميم الشبكات". رياضيات بحوث العمليات . 24 (2): 383-413 . CiteSeerX 10.1.1.215.794 . doi : 10.1287/moor.24.2.383 .

[21] "محاضرة 22 من مقرر 6.046J: إزالة العشوائية | تصميم وتحليل الخوارزميات | الهندسة الكهربائية وعلوم الحاسوب" . MIT OpenCourseWare . تاريخ الاسترجاع: 27-12-2024 .

[22] لوبي، مايكل؛ ويغدرسون، آفي (يوليو 1995). الاستقلال الزوجي وإزالة العشوائية (تقرير). الولايات المتحدة الأمريكية: جامعة كاليفورنيا في بيركلي.

[:2-23] 1 2 "ملاحظات المحاضرة، الفصل 3. تقنيات إزالة العشوائية الأساسية" . people.seas.harvard.edu . تم الاطلاع عليه بتاريخ 27-12-2024 .

[24] شازيل، ب.؛ فريدمان، ج. (1990-09-01). "نظرة حتمية لأخذ العينات العشوائية واستخدامها في الهندسة" . كومبيناتوريكا . 10 (3): 229-249 . doi : 10.1007/BF02122778 . ISSN 1439-6912 .

[25] أليبي، سيزار (2014)، الذكاء للأنظمة المدمجة ، سبرينغر، ISBN 978-3-319-05278-6.

[26] كوشيليفيتز، إيال؛ نيسان، نوام (2006)، تعقيد الاتصال ، مطبعة جامعة كامبريدج، رقم ISBN 9780521029834. للاطلاع على الحد الأدنى الحتمي، انظر الصفحة 11؛ للاطلاع على الحد الأعلى العشوائي اللوغاريتمي، انظر الصفحات 31-32.

[27] داير، م.؛ فريز، أ.؛ كانان، ر. (1991)، "خوارزمية عشوائية متعددة الحدود لتقريب حجم الأجسام المحدبة" (ملف PDF) ، مجلة ACM ، 38 (1): 1-17 ، doi : 10.1145/102782.102783 ، S2CID 13268711

[28] فوريدي، ز .؛ باراني، إ. (1986)، "حساب الحجم أمر صعب"، وقائع الندوة الثامنة عشرة لجمعية الحوسبة الآلية حول نظرية الحوسبة (بيركلي، كاليفورنيا، 28-30 مايو 1986) (ملف PDF) ، نيويورك، نيويورك: جمعية الحوسبة الآلية، الصفحات 442-447 ، CiteSeerX 10.1.1.726.9448 ، doi : 10.1145/12130.12176 ، ISBN 0-89791-193-8، S2CID 17867291

[29] شامير، أ. (1992)، "IP = PSPACE"، مجلة ACM ، 39 (4): 869-877 ، doi : 10.1145/146585.146609 ، S2CID 315182

[30] كوك، ماثيو ؛ سولوفيتشيك، ديفيد؛ وينفري، إريك ؛ بروك، يهوشوا (2009)، "قابلية برمجة شبكات التفاعلات الكيميائية"، في كوندون، آن ؛ هاريل، ديفيد ؛ كوك، جوست ن.؛ سالوما، أرتو ؛ وينفري، إريك (محررون)، العمليات الحيوية الخوارزمية (ملف PDF) ، سلسلة الحوسبة الطبيعية، سبرينغر-فيرلاغ، الصفحات 543-584 ، doi : 10.1007/978-3-540-88869-7_27 ، ISBN 978-3-540-88868-0.

[ 1 ]

2 ] )

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ ٧ ]

[ ٨ ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 24 ]

[ 25 ].

[

[ 27 ]

[

[ 29 ]

[ 30 ]