الگوریتمهای تصادفی
الگوریتمهای تصادفی در طول اجرا انتخابهای تصادفی انجام میدهند تا کارایی، سادگی یا استحکام را به دست آورند، با عملکرد و صحت که به صورت تضمینهای احتمالی بیان میشوند تا قطعیتهای بدترین حالت.
Definition
یک الگوریتم تصادفی، الگوریتمی است که از منبعی از بیتهای تصادفی برای اتخاذ برخی از تصمیمات خود استفاده میکند، به طوری که زمان اجرا، خروجی یا هر دو متغیرهای تصادفی هستند که با امید ریاضی یا توزیع احتمال آنها تحلیل میشوند.
Scope
این موضوع الگوریتمهایی را پوشش میدهد که از تصادفی بودن به عنوان یک منبع محاسباتی استفاده میکنند: مدل لاس وگاس (همیشه صحیح، زمان اجرای تصادفی) و مدل مونت کارلو (زمان اجرای ثابت، احتمال خطای محدود)، مثالهای متعارف مانند مرتبسازی سریع تصادفی، انتخاب تصادفی، آزمون اول بودن، و ساختارهای داده تصادفی مانند لیستهای پرشی، و ابزارهای تحلیل احتمالی (امید ریاضی، واریانس، نابرابریهای دنباله و تمرکز) که برای استدلال در مورد آنها استفاده میشوند.
Core questions
- چگونه معرفی تصادفی بودن میتواند یک الگوریتم را سریعتر یا سادهتر از هر الگوریتم قطعی شناخته شدهای کند؟
- تفاوت بین الگوریتمهای لاس وگاس و مونت کارلو چیست؟
- چگونه زمان اجرای مورد انتظار یا احتمال خطا تحلیل میشود؟
- چگونه نابرابریهای تمرکز احتمال نتایج بد را محدود میکنند؟
- چگونه میتوان خطای یک الگوریتم مونت کارلو را با تکرار کاهش داد؟
Key concepts
- بیتهای تصادفی به عنوان یک منبع
- الگوریتم لاس وگاس
- الگوریتم مونت کارلو
- زمان اجرای مورد انتظار
- احتمال خطا و تقویت
- نابرابریهای تمرکز
- مرتبسازی سریع تصادفی
- لیستهای پرشی
Key theories
- لاس وگاس در مقابل مونت کارلو
- الگوریتمهای لاس وگاس همیشه نتیجه صحیح تولید میکنند اما زمان اجرای تصادفی (تحلیل شده در امید ریاضی) دارند، در حالی که الگوریتمهای مونت کارلو در یک زمان ثابت اجرا میشوند اما ممکن است با احتمال محدود نتیجه نادرست تولید کنند، که تکرار میتواند آن را کاهش دهد.
- آزمون اول بودن احتمالی
- آزمونهای تصادفی مانند میلر-رابین اول بودن را با اطمینان بالا در زمان چندجملهای با بررسی شاهدان تصادفی تأیید میکنند؛ یک عدد مرکب توسط اکثر شاهدان آشکار میشود، بنابراین آزمایشهای مکرر احتمال خطا را ناچیز میکند.
Clinical relevance
الگوریتمهای تصادفی به طور گستردهای به کار گرفته میشوند: آزمون اول بودن میلر-رابین زیربنای رمزنگاری کلید عمومی است، هشینگ تصادفی و توازن بار سیستمهای توزیعشده را کارآمد نگه میدارند، مرتبسازی سریع تصادفی و انتخاب سریع تصادفی عملکرد مورد انتظار قوی را ارائه میدهند، و نمونهبرداری تصادفی و ترسیم (sketching) پردازش جریانهای داده عظیم را ممکن میسازند.
History
الگوریتمهای احتمالی در دهه 1970 با آزمونهای اول بودن سولوی-استراسن و میلر-رابین به شهرت رسیدند، که تصادفی بودن را به یک ابزار محاسباتی قابل احترام تبدیل کرد. دهههای 1980 و 1990 شاهد ساختارهای داده تصادفی (لیستهای پرشی، تریپها)، الگوریتمهای گراف و هندسی تصادفی، و نظریه سیستماتیک کدگذاری شده در کتاب درسی 1995 موتانی و راگاوان بود.
Key figures
- Michael Rabin
- Robert Solovay
- Volker Strassen
- Rajeev Motwani
- Prabhakar Raghavan
Related topics
Seminal works
- motwani1995
- rabin1980
- cormen2009
Frequently asked questions
- چگونه میتوان به یک الگوریتم مونت کارلو اعتماد کرد اگر ممکن است اشتباه کند؟
- احتمال خطای آن محدود و شناخته شده است، و برای الگوریتمهای خطای یکطرفه میتوان آن را با اجرای چندین باره الگوریتم با تصادفی بودن مستقل، به طور دلخواه کوچک کرد. پس از تکرارهای کافی، احتمال پاسخ اشتباه بسیار کمتر از احتمال خرابی سختافزاری است.
- چرا مرتبسازی سریع تصادفی به مرتبسازی سریع قطعی ترجیح داده میشود؟
- مرتبسازی سریع قطعی میتواند به دلیل انتخابهای ضعیف محور (pivot)، در ورودیهای خصمانه یا از قبل مرتب شده به بدترین حالت O(n^2) خود برسد. انتخاب تصادفی محورها، این بدترین حالت را صرف نظر از ورودی، بسیار بعید میکند و عملکرد مورد انتظار O(n log n) را در هر ورودی ارائه میدهد.