ویرگول
ورودثبت نام
rohola zandie
rohola zandie
rohola zandie
rohola zandie
خواندن ۴ دقیقه·۷ سال پیش

عدد تصادفی چیست؟

رای همه ما پیش آمده است که با سوالاتی مانند پیدا کردن ادامه دنباله ای عددی مانند دنباله زیر روبرو شویم:

5,1,1,2,5,3,3,8,2,4,…

گاهی اوقات با تلاش زیاد می توانیم ادامه دنباله را حدس بزنیم و گاهی هم شکست میخوریم در آن لحظه ممکن است تصور کنیم که دنباله هیچ "الگوی" مشخصی ندارد و کاملا تصادفی است که ناگهان متوجه میشویم دوست باهوش تر ما ادامه دنباله را یافته است! نتیجه گیری منطقی و طبیعی که به ذهن می رسد این است که هیچ گاه نمی توان ادعا کرد که یک دنباله تصادفی است چرا که "شاید الگویی دارد که ما نمی دانیم" در مواردی این ممکن است به مغلطه توسل به جهل هم منجر شود!(فکر کنید چرا)

مشکلاتی مانند این بسیاری از ریاضیدانانی که بر روی نظریه پیچیدگی محاسباتی کار می کردند را بر آن داشت تا تعریفی ریاضی از "تصادفی بودن" ارائه دهند. تعریف کولموگروف(Kolmogrov) در این میان از همه بیشتر مورد قبول قرار گرفت. این تعریف شهودی، جامع و زیبا است. بر اساس این تعریف دنباله ای تصادفی است که حجم کدی که برای تولید آن دنباله رندم تولید می شود( به صورت مجانبی) بیشتر یا مساوی با خود دنباله باشد. در اینجا منظور از "حجم کد" دقیقا به بایت است. به عبارت ساده تر وقتی هیچ الگوریتمی وجود نداشته باشد که حجم آن از حجم دنباله کمتر باشد دنباله هم قاعدتا هیچ الگویی ندارد.(تعریف algorithmically random)

این تعریف بسیار دقیق و از لحاظ تئوریک غنی است اما در کاربرد های واقعی ما به یک تعریف عملیاتی تر نیاز داریم. تعریف عملیاتی دنباله ی تصادفی، بر اساس مفهوم "از لحاظ آماری تصادفی"(statistically random) قرار دارد. بر اساس این تعریف هر دنباله ی تصادفی می بایست تعدادی تست آماری را با موفقیت پشت سر بگذارد تا بتوان نام "رندم" بر آن نهاد. در اینجا وارد جزییات نمی شویم ولی ویژگی هایی مانند پیروی کردن از توزیع یکنواخت(یعنی تمام اعداد شانس مساوی برای حضور در دنباله داشته باشند) یا ویژگی بیشینه آنتروپی از آن دسته اند.

حالا چطور اعداد تصادفی را در کامپیوتر ایجاد کنیم؟ هر گاه این سوال را از دانشجویانم میپرسم ابتدا کمی در فکر فرو می روند و سپس شوکه می شوند. چرا که بر خلاف دسترسی راحتی که برنامه ها به تولید اعداد تصادفی ایجاد می کنند یافتن الگوریتم ساخت اعداد تصادفی، غیر ممکن به نظر می رسد!

در واقع بیشتر این برنامه ها اصلا اعداد تصادفی واقعی تولید نمی کنند. آن ها اعداد شبه تصادفی تولید می کنند. اعداد شبه تصادفی دارای فرمول هستند و دنباله ای که ایجاد می کنند تست های آماری را با موفقیت پشت سر می گذارند. یکی از معروف ترین الگوریتم های در این زمینه linear congruent generator است که از یک رابطه بازگشتی مانند زیر استفاده می کند:

مقادیر m معمولا بزرگ است(مانند m=2^64) و a و c هم به مقادیری ست می شوند که در پکیج های مختلف متفاوت است. یکی از مهمترین قسمت های این فرمول بازگشتی مقدار اولیه ای است که به آن داده می شود و به عنوان دانه(seed) اولیه الگوریتم شناخته می شود. هر دانه دنباله ای کاملا متفاوت ایجاد می کند. با آنکه الگوریتم ایجاد اعداد شبه تصادفی در تقریبا تمامی نرم افزار ها(حتی اپل) به صورت عمومی در دسترس است، این الگوریتم برای نرم افزار متلب نامشخص است و تنها به گفتن: "تولید اعداد شبه تصادفی" اکتفا شده است.

در قسمت بعد به جزییات اعداد تصادفی در متلب می پردازیم. اما قبل از آن به تولید اعداد تصادفی واقعی در کامپیوتر فکر کنید!

ریاضیاتعلوم کامپیوتر
۴
۰
rohola zandie
rohola zandie
شاید از این پست‌ها خوشتان بیاید