الگوریتم چیست و آشنایی با الگوریتم تصادفی

به‌طور خلاصه، تحلیل احتمالی، استفاده از احتمال در تحلیل مسئله می‌باشد این موضوع معمولاً موقعی به کار می‌رود که بدترین حالت اجرای یک الگوریتم دارای احتمال ناچیزی باشد و می خواهیم کارایی برنامه را در حالت متوسط بدست بیاوریم و این موضوع را می‌توان با تحلیل احتمالی به راحتی بدست آورد. الگوریتم تصادفی به الگوریتمی گفته می‌شود که رفتارش نه تنها به اندازه ورودی بلکه با مقادیر تولید شده توسط یک مولد تصادفی تعیین می‌شود. بنابراین در این نوع الگوریتم فرض می‌کنیم ماشینی که در آن الگوریتم خود را پیاده‌سازی می‌کنیم باید قابلیت تولیدکننده یاعداد تصادفی را داشته باشد.

امید ریاضی چیست؟

امید ریاضی (Expected value) یا امید ریاضی در نظریه احتمالات، که با نام‌های میانگین مقدار مورد انتظار یا ارزش مورد انتظار نیز شناخته می‌شود، مقدار قابل انتظاری است از یک متغیر تصادفی ِگسسته که برابر است با مجموع حاصل‌ضرب احتمال وقوع هر یک از حالات ممکن در مقدار آن حالت. در نتیجه میانگین برابر است با مقداری که به‌طور متوسط از یک فرایند تصادفی با بی‌نهایت تکرار انتظار می‌رود. به بیان ساده‌تر، مقدار چشم داشتی از یک متغیر تصادفی، مقدارِ میانگینِ تعداد دفعاتِ مشاهده شده یک وضعیت است. به عنوان مثال، در پرتاب یک سکه، برای بدست آوردن احتمال مشاهده هر سمت از یک سکه (شیر یا خط)، می‌توان این کار را به دفعات زیاد انجام داد. اکنون میانگین تعداد دفعات مشاهده هرکدام از حالت‌ها (شیر یا خط)، برابر است با مقدار امید ریاضی (Expected value). به‌طور مثال برای تاس داریم:

یعنی اگر بی‌نهایت بار تاس را پرت کنیم، مقدار میانگین بدست آمده به سمت عدد ۳٫۵ میل خواهد کرد.

الگوریتم چیست؟

الگوریتم یا خوارزمی مجموعه‌ای متناهی از دستورالعمل‌ها است، که به ترتیب خاصی اجرا می‌شوند و مسئله‌ای را حل می‌کنند. به عبارت دیگر یک الگوریتم، روشی گام به گام برای حل مسئله است. شیوه محاسبه معدل در مدرسه، یکی از نمونه‌های الگوریتم است. تمام الگوریتم‌ها (خوارزمی‌ها) باید شرایط و معیارهای زیر را دارا باشند:

ورودی: یک الگوریتم باید هیچ یا حد اقل یک پارامتر را به عنوان ورودی بپذیرد؛

خروجی: الگوریتم بایستی حداقل یک کمیت به عنوان خروجی (نتیجه عملیات) تولید کند؛

قطعیت: دستورهای الگوریتم باید با زبانی دقیق، و بی‌ابهام بیان شوند. هر دستورالعمل نیز باید انجام‌پذیر باشد. دستورهایی نظیر «مقدار ۶ یا ۷ را به x اضافه کنید» یا «حاصل تقسیم پنج بر صفر را محاسبه کنید» مجاز نیستند؛ چرا که در مورد مثال اول، معلوم نیست که بالاخره چه عددی باید انتخاب شود، و در خصوص مثال دوم هم تقسیم بر صفر در ریاضیات تعریف نشده‌است.

محدودیت: الگوریتم باید دارای شروع و پایان مشخصی باشد، به نحوی که اگر دستورهای آن را دنبال کنیم، برای تمامی حالت‌ها، الگوریتم پس از طی مراحل، خاتمه یابد. به علاوه، زمان لازم برای خاتمه الگوریتم هم باید به گونه‌ای معقول و کوتاه باشد.

عوامل مؤثر در ارائه یک الگوریتم

به‌طور کلی جهت ارائه یک الگوریتم کامل به ۵ مؤلفه اصلی مقادیر معلوم، خواسته مسئله، عملیات محاسباتی، دستورهای شرطی و دستورهای تکرار (حلقه‌ها) نیاز داریم.

اطلاعات اولیه‌ای که در اختیار ما قرار می‌گیرد و با استفاده از آن‌ها به ارائه راه حل می‌پردازیم شامل مقادیر معلوم مسئله هستند و نتایجی که بر اثر انجام عملیات محاسباتی به‌دست می‌آیند خواسته‌های مسئله نامیده می‌شوند. از آنجایی که هدف اصلی طراحی الگوریتم برای حل یک مسئله دستیابی به خواسته‌های مسئله می‌باشد بنابراین طی مراحل ۵ گانه بالا در ارائه الگوریتم الزامی است. یک الگوریتم شامل دستورالعمل‌های پشت سر هم است که جهت ارائه یک خروجی معتبر باید به ترتیب اجرا شوند، از این رو رعایت ترتیب در مولفه‌های اصلی نیز مؤثر است، چرا که اساساً بدون وجود خواسته مسئله عملیات محاسباتی نیز وجود نخواهد داشت. با به‌کارگیری دستورهای شرطی می‌توان خروجی و رفتار یک الگوریتم را با توجه به شرایط از پیش تعیین شده مسئله کنترل کرد، از سوی دیگر استفاده از دستورهای تکرار (حلقه‌ها) به برنامه‌نویس کمک می‌کنند یک دستور تکراری را چندین بار اجرا کند.

تحلیل الگوریتم چیست؟

معمولاً برای حل یک مسئله، روش‌ها و الگوریتم‌های گوناگونی وجود دارند؛ یک الگوریتم ممکن است عمل مورد نظر را با دستورهای مختلف در مدت زمان یا کار کمتر یا بیشتری نسبت به الگوریتم دیگر انجام دهد. به همین دلیل، انتخاب الگوریتم مناسب و کارا اهمیت زیادی در موفق بودن و کارایی برنامه رایانه‌ای دارد. الگوریتم‌ها به عنوان یک فناوری مطرح هستند و دانشمندان آن‌ها را طراحی، تحلیل، و مطالعه می‌کنند. مطالعه الگوریتم‌ها زمینه‌های متعددی را در بر می‌گیرد. در زیر به چند نمونه اشاره می‌کنیم که می‌توان آن‌ها را چرخه حیات یک الگوریتم نامید.

1. طراحی الگوریتم‌ها: روش‌های مختلفی برای طراحی الگوریتم‌ها وجود دارد که عبارتند از: روشهای تقسیم و غلبه، روش‌های حریصانه، روش‌های برنامه‌نویسی پویا، روش‌های پسگرد و روش‌های انشعاب و تحدید.

2. معتبر سازی یا اثبات درستی الگوریتم‌ها:بعد از طراحی باید اثبات شود که الگوریتم مزبور درست است. الگوریتمی درست است که به ازای هر ورودی مناسب خروجی صحیحی بدهد. اثبات درستی الگوریتم‌ها به اثبات قضایا در ریاضی می‌ماند و مرحله بسیار مهمی در زمینه مطالعه الگوریتم‌ها است

3. تحلیل الگوریتم‌ها (تحلیل مقدم، ارزیابی کارایی الگوریتم‌ها):یک الگوریتم در زمان اجرا از واحد پردازش مرکزیِ رایانه برای اجرای دستورالعمل‌ها و از حافظه برای ذخیره‌سازی برنامه و داده‌ها استفاده می‌کند. تحلیل یک الگوریتم مشخص می‌کند که الگوریتم در زمان اجرا برای چه مدتی از CPU برای اجرای دستورالعمل (پیچیدگی زمانی) استفاده کرده و چه مقدار از حافظه (چه اصلی و چه جانبی) برای ذخیره‌سازی برنامه و داده‌ها (پیچیدگی فضایی) به کار برده‌است. تحلیل الگوریتم بیان‌گر آن است که، یک الگوریتم به چه میزان پیچیدگی زمانی و پیچیدگی فضایی نیاز دارد.

4. پیاده‌سازی الگوریتم‌ها:پیاده‌سازی یک الگوریتم نوشتن آن به زبان برنامه‌نویسی خاص است که معمولاً بعد از تحلیل مقدم آن صورت می‌گیرد و نام برنامه به آن اطلاق می‌شود.

5. تست برنامه:تست یک برنامه شامل۱:اشکال زدایی و ۲:تحلیل مؤخر (اندازه‌گیری کارایی) است. اندازه‌گیری کارایی عبارت است از فرایند اجرای الگوریتم صحیح بر روی داده‌های نمونه‌گیری شده برای به دست آوردن زمان و حافظه مورد نیاز توسط کامپایلر. زمان اجرای یک الگوریتم به پارامترهای مختلفی بستگی دارد که از جمله می‌توان به نوع دستورالعمل‌ها (دستورالعمل‌های جمع، ضرب، نوشتن، خواندن، شرطی و…)کامپایلر مورد استفاده، زبان برنامه‌نویسی، سخت‌افزار به کار رفته و پارامتری مثل nکه می‌تواند معرف تعداد ورودی‌ها و خروجی‌ها یا هر دو باشد اشاره کرد. تحلیل الگوریتم‌ها رشته‌ای است که به بررسی کارایی الگوریتم‌ها می‌پردازد. تحلیل الگوریتم‌ها یعنی پیش‌بینی منابع مورد نیاز برای اجرای یک الگوریتم، همچون: حافظه، پهنای‌باند ارتباطی، سخت‌افزار، و از همه مهمتر، زمان.[۹] کارایی یا پیچیدگی هر الگوریتم را با تابعی نشان می‌دهند که تعداد مراحل لازم برای اجرای الگوریتم را برحسب طول داده ورودی، یا میزان محل‌های لازم حافظه را بر حسب طول داده ورودی نشان می‌دهد.

الگوریتم تصادفی

الگوریتمی است که در آن ماشین به تولید اعداد تصادفی دسترسی دارد و از آن در الگوریتم خود استفاده می‌کند. این الگوریتم نوعاً با هدف بالا بردن کارایی در حالت‌های معمول از یک ورودی دودویی کمکی برای رفتارهای خود استفاده می‌کند. کارایی الگوریتم با یک متغیر تصادفی که به بیت‌های تصادفی داده شده‌است بستگی دارد و تغییر می‌یابد که باعث مشود امید ریاضی خوبی را شامل شود. احتمال وقوع بدترین حالت بسیار کم است و می‌توان از آن صرفنظر کرد.

میزان واقعیت الگوریتم های تصادفی

همان طور که در شکل سمت چپ مشخص است با افزایش محور افقی و با احتمال نزدیک به ۱۰۰ درصد نتیجه حاصل نزدیک به واقعیت است. مرتب‌سازی سریع یکی از مهم‌ترین اهداف الگوریتم‌های تصادفی است که  وقوع بدترین حالت خیلی کم است و با تحلیل احتمالی این موضوع را نشان می‌دهیم. علاوه بر این نوع Randomize Quick Sort که یک الگوریتم تصادفی است فقط به ورودی آرایه‌ای مربوط نیست بلکه به یک عدد تصادفی تولید شده نیز مربوط است. به عنوان مثال فرض کنید در آرایه‌ای که شامل اعداد صفر و یک می‌باشد به‌طوری که نصف آن‌ها صفر و نیمی دیگر یک هستند می خواهیم با عمل جستجو کردن از ابتدای آرایه اولین عنصر با مقدار بک را بیابیم. این مسئله در بدترین حالت باید (N/2) نیمی از خانه های آرایه را بررسی کنیم تا اولین یک را پیدا کنیم احتمال وقوع چنین حالتی بسیار کم است . از طرفی در حالت متوسط تعداد عمل جستجو برای این آرایه و پیدا کردن اولین یک کمتر از پیدا کردن اولین یک در حالت بدترین است.

موارد استفاده الگوریتمهای تصادفی

۱. الگوریتم‌های تصادفی به ویژه در مواردی استفاده دارند که با یک دشمن یا مهاجم بد خواهی! مواجهیم که از روی عناد ورودی بدی را برای ما فراهم می‌کند(آنالیز رقابتی). به همین دلیل انتخاب تصادفی پایه رمزنگاری را تشکیل می‌دهد. این بدین معنی است که دشمن شما(!) نمی‌تواند با یک ورودی خاص بدترین حالت (Worst Case)شما را پدید بیاورد چون که به اعداد تصادفی تولید شده نیز مربوط می‌باشد.

۲. از الگوریتم‌های تصادفی معمولاً برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آن‌ها تعداد زیاد باشد. برای مثال واپاشی یک هسته پرتوزا را در نظر می‌گیریم. برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم. یعنی بهتر است بگوییم احتمال واپاشی این اتم چه قدر است. حالا اگر تعداد اتم‌ها زیاد باشد، دیگر مسئله را از طریق تحلیلی نمی‌توان حل کرد. بلکه باید به روش‌های عددی روی آورد. در حقیقت الگوریتم‌های تصادفی، راهی برای حل عددی اینگونه مسائل هستند.

انواع الگوریتم‌های تصادفی

در مثال بالا الگوریتم تصادفی همیشه درست جواب می‌دهد تنها احتمال کوچکی وجود دارد که زمان زیادی برای رسیدن به پاسخ صرف کند. در بعضی مواقع ما از الگوریتم با اجازه دادن ایجاد احتمال کمی خطا انتظار سرعت بالاتر را داریم. الگوریتم‌های از نوع اول را لاس وگاس (Las Vegas algorithms) و نوع اخیر را مونت کارلو (Monte Carlo algorithms) می‌نامند. مشاهده می‌کنیم که هر الگوریتم لاس وگاس با گرفتن جوابی احتمالاً نادرست در زمانی مشخص و محدود شده به الگوریتم مونت کارلو تبدیل می‌شود.

از الگوریتم‌های تصادفی معمولاً برای بررسی پدیده‌هایی مورد استفاده قرار می‌گیرند که در آن‌ها تعداد زیاد باشد. برای مثال واپاشی یک هسته پرتوزا را در نظر می‌گیریم. برای بررسی این پدیده که چه زمانی یک اتم از آن واپاشی می‌کند ناچار به استفاده از احتمال هستیم. یعنی بهتر است بگوییم احتمال واپاشی این اتم چه قدر است. حالا اگر تعداد اتم‌ها زیاد باشد، دیگر مسئله را از طریق تحلیلی نمی‌توان حل کرد. بلکه باید به روش‌های عددی روی آورد. در حقیقت الگوریتم‌های تصادفی، راهی برای حل عددی اینگونه مسائل هستند. در آزمایشگاه لوس آلاموس در آمریکا دانشمندانی که بر روی پروژه سری منهتن کار می‌کردند، برای بررسی سیستم‌هایی که درآن‌ها تعداد ذرات بالااست، مجبور به ابداع روش یا الگوریتمی شدند که بعدها نام «مونت کارلو» بر آن قرار دادند. این الگوریتم برای نمونه‌گیری آماری از سیستم‌هایی با تعداد فضای فاز بالا به کار می‌رود. همچنین از این الگوریتم برای حل معادلات دیفرانسیل و انتگرال‌گیری معین استفاده می‌شود. دو الگوریتم مشهور مونت کارلو عبارتند از:

الگوریتم متروپلیس

این الگوریتم‌ها بیشتر بر این مبنا کار می‌کنند که:ابتدا یک پیکر بندی از سیستم مورد بررسی انتخاب می‌شود. سپس راه‌های موجود برای اینکه سیستم به آن‌ها گذار کند مشخص احتمال آن‌ها محاسبه می‌شود. آنگاه با تولید یک عدد تصادفی احتمالات موجود مورد سنجش قرار می‌گیرند، و سیستم به یکی از حالات ممکن گذار می‌کند. دوباره قسمت دیگری از سیستم انتخاب شده و مراحل قبلی تکرار می‌شود.

مسئله استخدام

فرض کنید شما به استخدام یک منشی در شرکت خود نیاز دارید و چون تلاش‌های گذشتهی شما بی نتیجه مانده است از یک آژانس کاریابی کمک می‌گیرید. این آژانس هر روز برای شما یک داوطلب استخدام می‌فرستد. شما با فرد متقاضی مصاحبه کرده و تصمیم می‌گیرید که او را استخدام کنید یا نه. شما هر بار برای مصاحبه با یک نفر باید مبلغ کمی به آژانس پرداخت کنید. شما می‌خواهید هر بار بهترین فرد ممکن را به عنوان منشی استخدام کنید و این کار با اخراج منشی قبلی و استخدام فرد جدید و پرداخت پول هم راه است. برای آن که همیشه بهترین فرد منشی استخدامی شما باشد بعد از مصاحبه با هر نفر اگر او از فرد قبلی بهتر بود او را استخدام می‌کنید. شما می‌خواهید هزینه این کار را قبل از شروع استخدام تخمین بزنید. در زیر یک الگوریتم ساده که گویای این عملیات است ارائه شده‌است:

مصاحبه کردن برای استخدام قیمت کمی را در بر دارد که آن را با ci عنوان می‌کنیم ولی آگهی استخدام قیمت بالایی در بر دارد که با ch نشان می‌دهیم. اگر از بین n نفر m تایشان استخدام شوند هزینه کل برابر با حالت زیر است:

O(nci + Onch) l

در بدترین حالت ما باید همه داوطلبان را استخدام کنیم که هزینه برابر حالت زیر است

O(nch)l

برای آن که بتوانیم متوسط هزینه استخدام را تخمین بزنیم فرض می‌کنیم داوطلبان به صورت رندوم می‌آیند. این به این معناست که ما گویی قبل از ورود داوطلبان جایگاه هر کدام از نظر خوب تر بودن را به ترتیب می‌دانیم و هرروز به صورت رندوم از میان این n نفر یکی را انتخاب می‌کنیم.(می دانیم که این انتخاب ما به صورت رندوم یک انتخاب خوب است) برای محاسبهٔ هزینه میانگین با این توضیحات از ایدهٔ متغیر تصادفی استفاده می‌کنیم.