mathematics
23rd September 2010, 07:06 PM
روش مونت-کارلو یک الگوریتم محاسباتی است که از نمونه‌گیری تصادفی برای محاسبه نتایج استفاده می‌کند. روشهای مونت-کارلو معمولاً برای شبیه‌سازی سیستم‌های فیزیکی، ریاضیاتی و اقتصادی استفاده می‌شوند.
به‌دیگر سخن روش مونت کارلو یک طبقه از الگوریتم‌های محاسبه گر می‌باشند که برای محاسبه نتایج خود بر نمونه گیری‌های تکرار شوند تصادفی اتکاء می‌کنند. روشهای مونته کارلو اغلب زمان انجام شبیه سازی یک سامانه ریاضیاتی یا فیزیکی می‌شوند استفاده می‌شوند. به دلیل اتکای آنها بر محاسبات تکراری و اعداد تصادفی یا تصادفی کاذب، روشها ی مونته کارو اغلب به گونه‌ای نتظیم می‌شوند که توسط رایانه اجرا شوند. گرایش به استفده از روشهای مونته کارلو زمانی بیشتر می‌شود که محاسبه پاسخ دقیق با کمک الگوریتم‌های قطعی ناممکن یا ناموجه باشد. روشهای شبیه سازی مونته کارلو مخصوصا در مطالعه سیستمهایی که در آن تعداد زیادی متغییر با درجه آزادی‌های دو به دو مرتبط وجود دارد مفید است، از جمله این سیستمها می‌توان به سیالات، جامداتی که به شدت کوپل شده‌اند، مواد بی نظم و ساختارهای سلولی (مدل سلولی پاتز – Potts- را ببیند) اشاره نمود. از آن گذشته، روشهای مونته کارلو برای شبیه سازی پدیده‌هایی که عدم قطعیت زیادی در ورودی‌های آنها وجود دارد نیز مفید هستند، مثلا محاسبه ریسک در تجارت. همچنین این روشها به طور گسترده‌ای در ریاضیات مورد استفاده قرار می‌گیرند: یک نمونه استفاده سنتی کاربرد این روشها در برآورد انتگرال‌های معین است، به خصوص انتگرال‌های چند بعدی با محدوده‌های مرزی پیچیده.واژه مونته کارلو در دهه ۱۹۴۰ (دهه ۱۳۱۰ شمسی) به وسیله فیزیکدانانی که روی پروژه ساخت یک سلاح اتمی در آزمایشگاه ملی لوس آلاموس آمریکا کار می‌کردند رایج شده‌است.
http://www.daneshju.ir/forum/images/statusicon/wol_error.gifاین عکس کوچک شده است برای مشاهده ی سایز اصلی کلیک کنیدhttp://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Monte_carlo_method.svg/334px-Monte_carlo_method.svg.png
توضیح عکس:
روش مونته کارلو را می‌توان به بازی نبرد کشتی‌ها تشبیه کرد. ابتدا یکی از بازیکنان شلیک‌های تصادفی را انجام می‌دهد. سپس بازیکن از الگوریتم استفاده می‌کند(مثلا یک کشتی جنگی به فاصله چهار خانه در جهت عمودی یا افقی قرار گرفته‌است). در نهایت بر اساس خروجی نمونه‌های تصادفی و الگوریتم، بازیگر می‌تواند محلهای احتمالی کشتی‌های جنگی بازیکن مقابل را حدس بزند
نگاه کلی
تنها یک روش مونته کارلو وجود ندارد، بلکه این واژه به گستره وسیعی از روشهایی که بسیار به کار گرفته می‌شوند اطلاق می‌گردد. به هر حال، این رویکردها یک الگوی مشخصی را پیروی می‌کنند:
1. محدوده‌ای از ورودی‌های ممکن را تعریف می‌کنند.
2. از آن محدوده ورودی‌های تصادفی را تولید می‌کنند.
3. با استفاده از ورودی‌های بدست آمده یک سری محاسبات مشخص را انجام می‌دهند.
4. نتایج هر یک از اجراهای محاسباتی را در پاسخ نهایی ادغام می‌کنند. برای مثال می‌توان مقدار عددπ را با استفاده از روش مونته کارلو محاسبه نمود.
5. یک مربع روی صفحه ترسیم کنید، سپس یک دایره را درون آن محاط کنید. در ادامه چندین شکل با اندازه یکسان را روی آن به طور یکنواختپخش کنید(برای مثال, دانه‌های شن یا برنج) در سرتاسر مربع.
6. سپس تعداد اشیاء درون دایره را بشمارید، در چهار ضرب کنید و عدد به دست آمده را بر تعداد کل اشیاء درون مربع تقسیم نمایید.
7. نسبت اشیاء درون دایره در مقابل اشیاء درون مربع تقریبا برابر خواهد بود با π/4 , که همان نسبت سطح دایره‌است به سطح مربع. بنابراین شما تخمینی از عدد π را به دست آورده‌اید.. توجه داشته باشید که چگونه تخمین عدد π پیروی می‌کند از یک الگوی مشخص شده در روش مونته کارلو. ابتدا ما یک محدوده از متغییرها را تعریف کردیم، که یک مربع بود که دایره ما را محاط کرده بود. سپس ورودی‌ها را به طور تصادفی تولید کردیم (پخش دانه‌ها به طور یکنواخت درون مربع), سپس محاسبات را برای هر ورودی انجام دادیم (بررسی کردیم که آیا دانه درون دایره هست یا نه). در آخر، تمام جوابها را در جواب نهایی ادغام نمودیم. همچنین به این نکته توجه داشته باشید که دو ویژگی مشترک دیگر روشهای مونته کارلو ایت است: اتکای محاسبات بر اعداد تصادفی خوب، و همگرایی تدریجی به سمت تخمین‌های بهتر در زمانی که داده‌های بیشتری شبیه سازی می‌شوند.
به‌دیگر سخن روش مونت کارلو یک طبقه از الگوریتم‌های محاسبه گر می‌باشند که برای محاسبه نتایج خود بر نمونه گیری‌های تکرار شوند تصادفی اتکاء می‌کنند. روشهای مونته کارلو اغلب زمان انجام شبیه سازی یک سامانه ریاضیاتی یا فیزیکی می‌شوند استفاده می‌شوند. به دلیل اتکای آنها بر محاسبات تکراری و اعداد تصادفی یا تصادفی کاذب، روشها ی مونته کارو اغلب به گونه‌ای نتظیم می‌شوند که توسط رایانه اجرا شوند. گرایش به استفده از روشهای مونته کارلو زمانی بیشتر می‌شود که محاسبه پاسخ دقیق با کمک الگوریتم‌های قطعی ناممکن یا ناموجه باشد. روشهای شبیه سازی مونته کارلو مخصوصا در مطالعه سیستمهایی که در آن تعداد زیادی متغییر با درجه آزادی‌های دو به دو مرتبط وجود دارد مفید است، از جمله این سیستمها می‌توان به سیالات، جامداتی که به شدت کوپل شده‌اند، مواد بی نظم و ساختارهای سلولی (مدل سلولی پاتز – Potts- را ببیند) اشاره نمود. از آن گذشته، روشهای مونته کارلو برای شبیه سازی پدیده‌هایی که عدم قطعیت زیادی در ورودی‌های آنها وجود دارد نیز مفید هستند، مثلا محاسبه ریسک در تجارت. همچنین این روشها به طور گسترده‌ای در ریاضیات مورد استفاده قرار می‌گیرند: یک نمونه استفاده سنتی کاربرد این روشها در برآورد انتگرال‌های معین است، به خصوص انتگرال‌های چند بعدی با محدوده‌های مرزی پیچیده.واژه مونته کارلو در دهه ۱۹۴۰ (دهه ۱۳۱۰ شمسی) به وسیله فیزیکدانانی که روی پروژه ساخت یک سلاح اتمی در آزمایشگاه ملی لوس آلاموس آمریکا کار می‌کردند رایج شده‌است.
http://www.daneshju.ir/forum/images/statusicon/wol_error.gifاین عکس کوچک شده است برای مشاهده ی سایز اصلی کلیک کنیدhttp://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Monte_carlo_method.svg/334px-Monte_carlo_method.svg.png
توضیح عکس:
روش مونته کارلو را می‌توان به بازی نبرد کشتی‌ها تشبیه کرد. ابتدا یکی از بازیکنان شلیک‌های تصادفی را انجام می‌دهد. سپس بازیکن از الگوریتم استفاده می‌کند(مثلا یک کشتی جنگی به فاصله چهار خانه در جهت عمودی یا افقی قرار گرفته‌است). در نهایت بر اساس خروجی نمونه‌های تصادفی و الگوریتم، بازیگر می‌تواند محلهای احتمالی کشتی‌های جنگی بازیکن مقابل را حدس بزند
نگاه کلی
تنها یک روش مونته کارلو وجود ندارد، بلکه این واژه به گستره وسیعی از روشهایی که بسیار به کار گرفته می‌شوند اطلاق می‌گردد. به هر حال، این رویکردها یک الگوی مشخصی را پیروی می‌کنند:
1. محدوده‌ای از ورودی‌های ممکن را تعریف می‌کنند.
2. از آن محدوده ورودی‌های تصادفی را تولید می‌کنند.
3. با استفاده از ورودی‌های بدست آمده یک سری محاسبات مشخص را انجام می‌دهند.
4. نتایج هر یک از اجراهای محاسباتی را در پاسخ نهایی ادغام می‌کنند. برای مثال می‌توان مقدار عددπ را با استفاده از روش مونته کارلو محاسبه نمود.
5. یک مربع روی صفحه ترسیم کنید، سپس یک دایره را درون آن محاط کنید. در ادامه چندین شکل با اندازه یکسان را روی آن به طور یکنواختپخش کنید(برای مثال, دانه‌های شن یا برنج) در سرتاسر مربع.
6. سپس تعداد اشیاء درون دایره را بشمارید، در چهار ضرب کنید و عدد به دست آمده را بر تعداد کل اشیاء درون مربع تقسیم نمایید.
7. نسبت اشیاء درون دایره در مقابل اشیاء درون مربع تقریبا برابر خواهد بود با π/4 , که همان نسبت سطح دایره‌است به سطح مربع. بنابراین شما تخمینی از عدد π را به دست آورده‌اید.. توجه داشته باشید که چگونه تخمین عدد π پیروی می‌کند از یک الگوی مشخص شده در روش مونته کارلو. ابتدا ما یک محدوده از متغییرها را تعریف کردیم، که یک مربع بود که دایره ما را محاط کرده بود. سپس ورودی‌ها را به طور تصادفی تولید کردیم (پخش دانه‌ها به طور یکنواخت درون مربع), سپس محاسبات را برای هر ورودی انجام دادیم (بررسی کردیم که آیا دانه درون دایره هست یا نه). در آخر، تمام جوابها را در جواب نهایی ادغام نمودیم. همچنین به این نکته توجه داشته باشید که دو ویژگی مشترک دیگر روشهای مونته کارلو ایت است: اتکای محاسبات بر اعداد تصادفی خوب، و همگرایی تدریجی به سمت تخمین‌های بهتر در زمانی که داده‌های بیشتری شبیه سازی می‌شوند.