الگوریتمهای تصادفی
از ویکیپدیا، دانشنامهٔ آزاد
 |
این مقاله به تمیزکاری نیاز دارد. لطفاً آن را تا جایی که ممکن است از نظر املا، انشا، چیدمان و درستی بهتر کنید. سپس این الگو را از بالای مقاله حذف کنید. محتویات این مقاله ممکن است غیرقابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
 |
در متن این مقاله از هیچ منبع و مأخذی نام برده نشدهاست. شما میتوانید با افزودن منابع بر طبق اصول اثباتپذیری و شیوهنامهٔ ارجاع به منابع، به ویکیپدیا کمک کنید. مطالب بیمنبع احتمالاً در آینده حذف خواهند شد. |
الگوریتم تصادفی الگوریتمی است که اجازهٔ گرداندن یک سکهٔ سالم را دارد. بدین معنی که ماشین پیاده کننده این الگوریتم به تولید کنندهٔ اعداد شبه تصادفی (pseudo-random number generator) دسترسی دارد. این الگوریتم نوعاً با هدف بالا بردن کارایی در حالتهای معمول از یک ورودی دودویی کمکی برای رفتارهای خود استفاده میکند. کارایی الگوریتم با یک متغیر تصادفی که به بیتهای تصادفی داده شده بستگی دارد، تغییر مییابد که (امیدوارانه) امید ریاضی خوبی را شامل میشود. احتمال وقوع بدترین حالت آنقدر کم است که میتوان از آن صرفنظر کرد.
به عنوان یک مثال جالب فرض کنید میخواهیم حرف «الف» را از میان آرایهٔ n خانهای پیدا کنیم در حالی که میدانیم نصف خانهها «ب» و نصف دیگر «الف» است. یک روش مشخص نگاه کردن به تمام خانههای آرایهاست که اگر «ب»ها اول باشند n/۲ حالت را باید برای پیدا کردن «الف» بررسی کنیم. در حقیقت با هر استراتژی جستجویی این احتمال ثابت است ولی اگر ما خانههای آرایه را تصادفی میآزمودیم، آنگاه میتوانستیم با هر ورودی سزیعا یک حرف «الف» را با احتمال بالایی پیدا کنیم.
الگوریتمهای تصادفی بویژه در مواردی استفاده دارند که با یک دشمن یا مهاجم بد خواهی! مواجهیم که از روی عناد ورودی بدی را برای ما فراهم میکند(آنالیز رقابتی). به همین دلیل انتخاب تصادفی پایه رمزنگاری را تشکیل میدهد.
در مثال بالا الگوریتم تصادفی همیشه درست جواب میدهد تنها احتمال کوچکی وجود دارد که زمان زیادی برای رسیدن به پاسخ صرف کند. در بعضی مواقع ما از الگوریتم با اجازه دادن ایجاد احتمال کمی خطا انتظار سرعت بالاتر را داریم. الگوریتمهای از نوع اول را لاس وگاس (Las Vegas algorithms) و نوع اخیر را مونت کارلو (Monte Carlo algorithms) مینامند. مشاهده میکنیم که هر الگوریتم لاس وگاس با گرفتن جوابی احتمالاً نادرست در زمانی مشخص و محدود شده به الگوریتم مونت کارلو تبدیل میشود. Quicksort معروفترین الگوریتم تصادفی کاربردی در جهان حقیقی است.
از الگوریتمهای تصادفی معمولا برای بررسی پدیدههایی مورد استفاده قرار میگیرند که در آنها تعداد زیاد باشد.برای مثال واپاشی یک هسته پرتوزا را در نظر میگیریم.برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی میکند ناچار به استفاده از احتمال هستیم.یعنی بهتر است بگوییم احتمال واپاشی این اتم چه قدر است.حالا اگر تعداد اتمها زیاد باشد، دیگر مسئله را از طریق تحلیلی نمیتوان حل کرد.بلکه باید به روشهای عددی روی آورد.در حقیقت الگوریتمهای تصادفی، راهی برای حل عددی اینگونه مسائل هستند.
در آزمایشگاه لوس آلاموس در آمریکا دانشمندانی که بر روی پروژه سری منهتن کار میکردند، برای بررسی سیستمهایی که درآنها تعداد ذرات بالااست، مجبور به ابداع روش و یا الگوریتمی شدند که بعدها نام «مونت کارلو» بر آن قرار دادند.این الگوریتم برای نمونه گیری آماری از سیستمهایی با تعداد فضای فاز بالا به کار میرود.همچنین از این الگوریتم برای حل معادلات دیفرانسیل و انتگرال گیری معین استفاده میشود. دوالگوریتم مشهور مونت کارلو عبارتند از:
- الگوریتم متروپلیس
- الگوریتم مونت کارلو جنبشی یا n-fold way.
این الگوریتمها بیشتر بر این مبنا کار میکنند که:ابتداء یک پیکر بندی از سیستم مورد بررسی انتخاب میشود.سپس راههای موجود برای اینکه سیستم به آنها گذار کند مشخص احتمال آنها محاسبه میشود.آنگاه با تولید یک عدد تصادفی احتمالات موجود مورد سنجش قرار میگیرند، و سیستم به یکی از حالات ممکن گذار میکند.دوباره قسمت دیگری از سیستم انتخاب شده و مراحل قبلی تکرار میشود.
