طريقة مونتى كارلو تصيب-أو-تخيب

 تصور اننا نريد حساب تكامل دالة f(x) فى مجال [A,B]. مثلا نأخذ الدالة المعطاة بالخط الازرق فى الصورة.

الخطوات بسيطة و تسمى خوازرمية تصيب-أو-تخيب hit-and-miss algorithm.

هذه الخوارزمية اكتشفها جون فون نيومان John von Neumann آخر عظماء الرياضيات و الأب الرياضى للميكانيك الكمومى (بالخصوص المنطق الكمومى) و أب الوعى الكمومى (فهو أول من تكلم عن دور الوعى فى الميكانيك الكمومى) و هو ايضا احد الآباء الاوائل لعلوم الحاسوب.

اذن هذه خوارزمية اكتشفها فون نيومان بالاشتراك مع ستانسيلو اولام Stanislaw Ulam عندما كانا يعملان فى اطار مشروع مانهاتن Manhattan project للقنبلة الذرية-ثم-الهيدروجينية تحت رئاسة الفيزيائى الكمومى-النووى روبرت اوبنهايمر Robert Oppenheimer احد اباء الميكانيك الكمومى فى ناحية تطبيقاته التاريخية الهائلة فى الفيزياء الذرية و الفيزياء النووية.

الفيزياء و الفيزياء النظرية و الميكانيك الكمومى لا يمكن ان يتنفس الجميع بدون الرياضيات و الرياضيات لا يمكن ان تتنفس بدون الحساب و اهم مسألة حسابية هو حساب التكاملات.

اذن نحن عموما نريد ان نحسب تكامل دالة (ليس بالضرورة فى بعد واحد) و عموما فانه ليس امامنا اى مجال لاجراءها بشكل تحليلى.

اذن نستنجد بالتحليل العددى و بالفيزياء الحاسوبية و بالخوزرمة و بالتشفير بهذا الترتيب. من لا يريد ان يفهم يمكنه استخدام التطبيقات المتوفرة و هى كثيرة جدا. و من يريد ان يذهب بعيدا -فى الفيزياء النظرية و الرياضيات و علوم الحاسوب و الذكاء الاصطناعى- فعليه ان يفهم كيف تعمل الخوارزميات التى تعمل فى هذه التطبيقات؟

خطوات هذه الخوازمية البسيطة هى كما يلى.

-نقوم اولا بتوليد عدد عشوائى random (او بالاحرى شبه-عشوائى pseudo-random) x موزع بشكل منتظم uniformly فى مجال التكامل [A,B].

اى مولد generator للاعداء العشوائية سيعطيك عدد عشوائى r موزع بانتظام بين 0 و 1 اذن عليكم تحويله الى المجال [A,B] بالعلاقة x=(B-A)*x+A (تأكدوا من هذه العلاقة البسيطة).

-ثانيا نقوم بتوليد عدد عشوائى y موزع بانتظام فى مجال الدالة اى بين مثلا 0 و القيمة القصوية Max كما فى الصورة.

مرة اخرى نقوم بتحويل العدد العشوائى المولد فى المجال [0,1] الى المجال [0,Max] بعلاقة مماثلة للمعادلة اعلاه.

هذا العدد العشوائى سيلعب دور قيم الدالة.

اذن لدينا ازواج عشوائية مولدة فى مستطيل بطول و عرض يساويان [A,B] و [0,Max].

اذن هناك ازواج عشوائية (x,y) ستقع تحت منحنى الدالة و هناك ازواج ستقع فوق منحنى الدالة.

-الخطوة الثالثة. نقوم بحساب عدد الازتصور اننا نريد حساب تكامل دالة f(x) فى مجال [A,B]. مثلا نأخذ الدالة المعطاة بالخط الازرق فى الصورة. الخطوات بسيطة و تسمى خوازرمية تصيب-و-تخيب hit-and-miss algorithm. هذه الخوارزمية اكتشفها جون فون نيومان John von Neumann آخر عظماء الرياضيات و الأب الرياضى للميكانيك الكمومى (بالخصوص المنطق الكمومى) و أب الوعى الكمومى (فهو أول من تكلم عن دور الوعى فى الميكانيك الكمومى) و هو ايضا احد الآباء الاوائل لعلوم الحاسوب. اذن هذه خوارزمية اكتشفها فون نيومان بالاشتراك مع ستانسيلو اولام Stanislaw Ulam عندما كانا يعملان فى اطار مشروع مانهاتن Manhattan project للقنبلة الذرية-ثم-الهيدروجينية تحت رئاسة الفيزيائى الكمومى-النووى روبرت اوبنهايمر Robert Oppenheimer احد اباء الميكانيك الكمومى فى ناحية تطبيقاته التاريخية الهائلة فى الفيزياء الذرية و الفيزياء النووية. الفيزياء و الفيزياء النظرية و الميكانيك الكمومى لا يمكن ان يتنفس الجميع بدون الرياضيات و الرياضيات لا يمكن ان تتنفس بدون الحساب و اهم مسألة حسابية هو حساب التكاملات. اذن نحن عموما نريد ان نحسب تكامل دالة (ليس بالضرورة فى بعد واحد) و عموما فانه ليس امامنا اى مجال لاجراءها بشكل تحليلى. اذن نستنجد بالتحليل العددى و بالفيزياء الحاسوبية و بالخوزرمة و بالتشفير بهذا الترتيب. من لا يريد ان يفهم يمكنه استخدام التطبيقات المتوفرة و هى كثيرة جدا. و من يريد ان يذهب بعيدا -فى الفيزياء النظرية و الرياضيات و علوم الحاسوب و الذكاء الاصطناعى- فعليه ان يفهم كيف تعمل الخوارزميات التى تعمل فى هذه التطبيقات؟ خطوات هذه الخوازمية البسيطة هى كما يلى. -نقوم اولا بتوليد عدد عشوائى random (او بالاحرى شبه-عشوائى pseudo-random) x موزع بشكل منتظم uniformly فى مجال التكامل [A,B]. اى مولد generator للاعداء العشوائية سيعطيك عدد عشوائى r موزع بانتظام بين 0 و 1 اذن عليكم تحويله الى المجال [A,B] بالعلاقة x=(B-A)*x+A (تأكدوا من هذه العلاقة البسيطة). -ثانيا نقوم بتوليد عدد عشوائى y موزع بانتظام فى مجال الدالة اى بين مثلا 0 و القيمة القصوية Max كما فى الصورة. مرة اخرى نقوم بتحويل العدد العشوائى المولد فى المجال [0,1] الى المجال [0,Max] بعلاقة مماثلة للمعادلة اعلاه. هذا العدد العشوائى سيلعب دور قيم الدالة. اذن لدينا ازواج عشوائية مولدة فى مستطيل بطول و عرض يساويان [A,B] و [0,Max]. اذن هناك ازواج عشوائية (x,y) ستقع تحت منحنى الدالة و هناك ازواج ستقع فوق منحنى الدالة. -الخطوة الثالثة. نقوم بحساب عدد الازواج التى تقع تحت منحنى الدالة و ليكن هذا العدد L. -الخطوة الرابعة. التكامل يساوى L على N حيث ان N هو العدد الكلى للاعداد العشوائية المولدة. اما البرهان فهم يعتمد على البرهان على طرق (الاستعيان الأهم importance sampling) التى هى (سلسلة ماركوفية Markov chain) من امثلتها الشهيرة جدا خوازرمية ميتروبوليس Metropolis algorithm التى هى اشهر طرق مونتى كارلو Monte Carlo methods.تصور اننا نريد حساب تكامل دالة f(x) فى مجال [A,B]. مثلا نأخذ الدالة المعطاة بالخط الازرق فى الصورة. الخطوات بسيطة و تسمى خوازرمية تصيب-و-تخيب hit-and-miss algorithm. هذه الخوارزمية اكتشفها جون فون نيومان John von Neumann آخر عظماء الرياضيات و الأب الرياضى للميكانيك الكمومى (بالخصوص المنطق الكمومى) و أب الوعى الكمومى (فهو أول من تكلم عن دور الوعى فى الميكانيك الكمومى) و هو ايضا احد الآباء الاوائل لعلوم الحاسوب. اذن هذه خوارزمية اكتشفها فون نيومان بالاشتراك مع ستانسيلو اولام Stanislaw Ulam عندما كانا يعملان فى اطار مشروع مانهاتن Manhattan project للقنبلة الذرية-ثم-الهيدروجينية تحت رئاسة الفيزيائى الكمومى-النووى روبرت اوبنهايمر Robert Oppenheimer احد اباء الميكانيك الكمومى فى ناحية تطبيقاته التاريخية الهائلة فى الفيزياء الذرية و الفيزياء النووية. الفيزياء و الفيزياء النظرية و الميكانيك الكمومى لا يمكن ان يتنفس الجميع بدون الرياضيات و الرياضيات لا يمكن ان تتنفس بدون الحساب و اهم مسألة حسابية هو حساب التكاملات. اذن نحن عموما نريد ان نحسب تكامل دالة (ليس بالضرورة فى بعد واحد) و عموما فانه ليس امامنا اى مجال لاجراءها بشكل تحليلى. اذن نستنجد بالتحليل العددى و بالفيزياء الحاسوبية و بالخوزرمة و بالتشفير بهذا الترتيب. من لا يريد ان يفهم يمكنه استخدام التطبيقات المتوفرة و هى كثيرة جدا. و من يريد ان يذهب بعيدا -فى الفيزياء النظرية و الرياضيات و علوم الحاسوب و الذكاء الاصطناعى- فعليه ان يفهم كيف تعمل الخوارزميات التى تعمل فى هذه التطبيقات؟ خطوات هذه الخوازمية البسيطة هى كما يلى. -نقوم اولا بتوليد عدد عشوائى random (او بالاحرى شبه-عشوائى pseudo-random) x موزع بشكل منتظم uniformly فى مجال التكامل [A,B]. اى مولد generator للاعداء العشوائية سيعطيك عدد عشوائى r موزع بانتظام بين 0 و 1 اذن عليكم تحويله الى المجال [A,B] بالعلاقة x=(B-A)*x+A (تأكدوا من هذه العلاقة البسيطة). -ثانيا نقوم بتوليد عدد عشوائى y موزع بانتظام فى مجال الدالة اى بين مثلا 0 و القيمة القصوية Max كما فى الصورة. مرة اخرى نقوم بتحويل العدد العشوائى المولد فى المجال [0,1] الى المجال [0,Max] بعلاقة مماثلة للمعادلة اعلاه. هذا العدد العشوائى سيلعب دور قيم الدالة. اذن لدينا ازواج عشوائية مولدة فى مستطيل بطول و عرض يساويان [A,B] و [0,Max]. اذن هناك ازواج عشوائية (x,y) ستقع تحت منحنى الدالة و هناك ازواج ستقع فوق منحنى الدالة. -الخطوة الثالثة. نقوم بحساب عدد الازواج التى تقع تحت منحنى الدالة و ليكن هذا العدد L. -الخطوة الرابعة. التكامل يساوى L على N حيث ان N هو العدد الكلى للاعداد العشوائية المولدة. اما البرهان فهم يعتمد على البرهان على طرق (الاستعيان الأهم importance sampling) التى هى (سلسلة ماركوفية Markov chain) من امثلتها الشهيرة جدا خوازرمية ميتروبوليس Metropolis algorithm التى هى اشهر طرق مونتى كارلو Monte Carlo methods.واج التى تقع تحت منحنى الدالة و ليكن هذا العدد L.

-الخطوة الرابعة. التكامل يساوى L على N حيث ان N هو العدد الكلى للاعداد العشوائية المولدة.

اما البرهان فهم يعتمد على البرهان على طرق (الاستعيان الأهم importance sampling) التى هى (سلسلة ماركوفية Markov chain) من امثلتها الشهيرة جدا خوازرمية ميتروبوليس Metropolis algorithm التى هى اشهر طرق مونتى كارلو Monte Carlo methods.