موضوع مقاله: الگوریتم تصادفی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم تصادفی | مقدمه: چکیده به‌طور خلاصه، تحلیل احتمالی، استفاده از احتمال در تحلیل مسئله می‌باشد این موضوع معمولاً موقعی به کار می‌رود که بدترین حالت اجرای یک الگوریتم دارای احتمال ناچیزی باشد و می خواهیم کارایی برنامه را در حالت متوسط بدست بیاوریم و این موضوع را می‌توان با تحلیل احتمالی به راحتی بدست آورد. | ## بخش 1: الگوریتم تصادفی | الگوریتم تصادفی به الگوریتمی گفته می‌شود که رفتارش نه تنها به اندازهٔ ورودی بلکه همچنین با مقادیر تولید شده توسط یک مولد تصادفی تعیین می‌شود. بنابراین در این نوع الگوریتم فرض می‌کنیم ماشینی که در آن الگوریتم خود را پیاده‌سازی می‌کنیم باید قابلیت تولیدکننده یاعداد تصادفی را داشته باشد. الگوریتم تصادفی الگوریتمی است که در آن ماشین به تولید اعداد تصادفی دسترسی دارد و از آن در الگوریتم خود استفاده می‌کند. این الگوریتم نوعاً با هدف بالا بردن کارایی در حالت‌های معمول از یک ورودی دودویی کمکی برای رفتارهای خود استفاده می‌کند. کارایی الگوریتم با یک متغیر تصادفی که به بیت‌های تصادفی داده شده‌است بستگی دارد و تغییر می‌یابد که باعث مشود امید ریاضی خوبی را شامل شود. frame|600px|میزان نزدیکی به واقعیت در مورد الگوریتم های تصادفی میزان واقعیت الگوریتم های تصادفی همان طور که در شکل سمت چپ مشخص است با افزایش محور افقی و با احتمال نزدیک به ۱۰۰ درصد نتیجهٔ حاصل نزدیک به واقعیت می‌باشد. (برای اطلاعات بیشتر از نحوهٔ بدست آوردن این صفحه می‌توانید به لینک آن مراجعه نمایید.) مرتب‌سازی سریع یکی از مهم‌ترین الگوریتم‌های تصادفی می‌باشد که وقوع بدترین حالت خیلی کم است و با تحلیل احتمالی این موضوع را نشان می‌دهیم و همچنین نوع Randomize Quick Sort که یک الگوریتم تصادفی است فقط به ورودی آرایه‌ای مربوط نمی‌باشد بلکه به یک عدد تصادفی تولید شده نیز مربوط است. به عنوان مثال فرض کنید در آرایه‌ای که شامل اعداد صفر و یک می‌باشد به‌طوری که نصف آن‌ها صفر و نیمی دیگر یک هستند می خواهیم با عمل جستجو کردن از ابتدای آرایه اولین عنصر با مقدار بک را بیابیم. این مسئله در بدترین حالت باید (N/2) نیمی از خانه های آرایه را بررسی کنیم تا اولین یک را پیدا کنیم احتمال وقوع چنین حالتی بسیار کم است. از طرفی در حالت متوسط تعداد عمل جستجو برای این آرایه و پیدا کردن اولین یک کمتر از پیدا کردن اولین یک در حالت بدترین است. الگوریتم‌های تصادفی به ویژه در مواردی استفاده دارند که با یک دشمن یا مهاجم بد خواهی! این بدین معنی است که دشمن شما(!) نمی‌تواند با یک ورودی خاص بدترین حالت (Worst Case)شما را پدید بیاورد چون که به اعداد تصادفی تولید شده نیز مربوط می‌باشد. | ## بخش 2: الگوریتم تصادفی | از الگوریتم‌های تصادفی معمولاً برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آن‌ها تعداد زیاد باشد. برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم. در برخی بازی‌های مدرن و دیجیتال، از الگوریتم‌های تصادفی برای تولید اعداد شبه‌تصادفی استفاده می‌شود که رفتار نمودارهای درون بازی را تعیین می‌کنند. در این سازوکار، پیش از آغاز هر دور، عددی به‌عنوان «ضریب رشد» با استفاده از تولیدکننده عدد شبه‌تصادفی (PRNG) تولید می‌شود و سپس از طریق توابع هش رمزنگاری قفل می‌گردد. ترکیب الگوریتم‌های تصادفی با توابع هش رمزنگاری، مانند الگوریتم SHA-2 سازوکاری فراهم می‌سازد که ضمن جلوگیری از تقلب، قابلیت راستی‌آزمایی نتایج را نیز تضمین می‌کند. انواع الگوریتم‌های تصادفی در مثال بالا الگوریتم تصادفی همیشه درست جواب می‌دهد تنها احتمال کوچکی وجود دارد که زمان زیادی برای رسیدن به پاسخ صرف کند. در بعضی مواقع ما از الگوریتم با اجازه دادن ایجاد احتمال کمی خطا انتظار سرعت بالاتر را داریم. مشاهده می‌کنیم که هر الگوریتم لاس وگاس با گرفتن جوابی احتمالاً نادرست در زمانی مشخص و محدود شده به الگوریتم مونت کارلو تبدیل می‌شود. از الگوریتم‌های تصادفی معمولاً برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آن‌ها تعداد زیاد باشد. برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم. در آزمایشگاه لوس آلاموس در آمریکا دانشمندانی که بر روی پروژه سری منهتن کار می‌کردند، برای بررسی سیستم‌هایی که درآن‌ها تعداد ذرات بالااست، مجبور به ابداع روش یا الگوریتمی شدند که بعدها نام «مونت کارلو» بر آن قرار دادند. این الگوریتم برای نمونه‌گیری آماری از سیستم‌هایی با تعداد فضای فاز بالا به کار می‌رود. | ## بخش 3: الگوریتم تصادفی | همچنین از این الگوریتم برای حل معادلات دیفرانسیل و انتگرال‌گیری معین استفاده می‌شود. این الگوریتم‌ها بیشتر بر این مبنا کار می‌کنند که:ابتدا یک پیکر بندی از سیستم مورد بررسی انتخاب می‌شود. سپس راه‌های موجود برای اینکه سیستم به آن‌ها گذار کند مشخص احتمال آن‌ها محاسبه می‌شود. آنگاه با تولید یک عدد تصادفی احتمالات موجود مورد سنجش قرار می‌گیرند، و سیستم به یکی از حالات ممکن گذار می‌کند. مثال: مسئله استخدام فرض کنید شما به استخدام یک منشی در شرکت خود نیاز دارید و چون تلاش‌های گذشتهی شما بی نتیجه مانده است از یک آژانس کاریابی کمک می‌گیرید. شما می‌خواهید هر بار بهترین فرد ممکن را به عنوان منشی استخدام کنید و این کار با اخراج منشی قبلی و استخدام فرد جدید و پرداخت پول هم راه است. برای آن که همیشه بهترین فرد منشی استخدامی شما باشد بعد از مصاحبه با هر نفر اگر او از فرد قبلی بهتر بود او را استخدام می‌کنید. در بدترین حالت ما باید همهٔ داوطلبان را استخدام کنیم که هزینه از O(nch)l می‌شود. برای آن که بتوانیم متوسط هزینه استخدام را تخمین بزنیم فرض می‌کنیم داوطلبان به صورت رندوم می‌آیند. این به این معناست که ما گویی قبل از ورود داوطلبان جایگاه هر کدام از نظر خوب تر بودن را به ترتیب می‌دانیم و هرروز به صورت رندوم از میان این n نفر یکی را انتخاب می‌کنیم.(می دانیم که این انتخاب ما به صورت رندوم یک انتخاب خوب است) برای محاسبهٔ هزینه میانگین با این توضیحات از ایدهٔ متغیر تصادفی استفاده می‌کنیم. | ## جمع‌بندی | تحلیل X را یک متغیر تصادفی می‌گیریم که برابر است با تعداد دفعاتی که ما یک منشی استخدام می‌کنیم.