تصادفی یا غیر تصادفی؟ (۲)

در مطلب قبل، ضمن بیان برخی مزایای دست یابی به کمیت های تصادفی، به بررسی یکی از روش های تولید اعداد تصادفی، یعنی روش فیزیکی پرداختیم. همچنین بیان کردیم که این روش، اعداد تصادفی حقیقی (True Random Numbers) تولید می‌کند. نمونه ساده این روش، پرتاب تاس است.

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

نیاز به اعداد تصادفی

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

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

کاربرد اعداد تصادفی در طراحی بازی ها

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

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

چالش های روش فیزیکی

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

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

این محدودیت ها سبب می‌شود تا در به کارگیری روش فیزیکی با مشکل دچار شویم. اما اگر از زاویه دیگری با این موضوع برخورد کنیم، می‌بینیم که در بسیاری از موارد، تصادفی بودن اعداد از اهمیت بالایی برخوردار نیست. بدین معنی که اعداد مورد استفاده، لازم نیست کاملاً تصادفی باشند. برای نمونه، دوباره به مثال بازی ها توجه کنید. در یک بازی رایانه ای، محل قرار گیری شخصیت های دشمن لازم نیست کاملا تصادفی باشند (به حدی که ملزم به استفاده از روش های پیچیده فیزیکی شویم). بلکه صرفاً نیازمند انتخاب هایی هستیم که برای یک بازیکن به سادگی قابل تشخیص و الگویابی نباشند. بنابراین حتی یک الگوریتم مشخص، در صورت داشتن پیچیدگی لازم، کفایت خواهد کرد. تذکر این مطلب ضروری است که خروجی این الگوریتم ها، به دلیل اینکه حاصل عملیاتی از پیش تعیین شده است، تصادفی نیست، بلکه صرفاً شبیه خروجی های تصادفی است. این چنین خروجی هایی را که در مقابل «تصادفی حقیقی» (True Random) قرار میگیرند، «شبه تصادفی» (Pseudo-random) می نامند. همچنین، الگوریتم یا تابعی که این اعداد را تولید کند، «مولد اعداد شبه تصادفی» (Pseudo-Random Number Generator یا PRNG) نام دارد.

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

در ادامه به بررسی برخی از مولد های تولید اعداد شبه تصادفی می‌پردازیم.

مولد های اعداد شبه تصادفی (PRNG)

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

اکنون دو نمونه از الگوریتم ها و توابع مورد استفاده در مولد های تصادفی را بررسی می‌کنیم.

روش میان مربع (Middle-Square Method)

این الگوریتم ساده به ما کمک می‌کند تا دنباله ای از اعداد تصادفی n رقمی، که n عددی زوج باشد، تولید کنیم. نحوه کار این روش را با یک مثال شرح می‌دهیم. فرض کنید می‌خواهیم دنباله ای از اعداد تصادفی ۲ رقمی داشته باشیم. ابتدا باید یک عدد ۲ رقمی به عنوان خوراک اولیه انتخاب کنیم (مثلا ۲۴). سپس آن را به توان دو می‌رسانیم (۷۵۶ = ۲۴ × ۲۴). اگر حاصل ۲n رقم (در این مثال ۴ رقم) داشت، به مرحله بعد می رویم، در غیر این صورت رقم صفر را به سمت چپ آن اضافه میکنیم تا عدد ۲n رقمی بشود (در مثال ما، باید رقم صفر را به سمت چپ عدد اضافه کنیم تا عدد ۰۷۵۶ بدست آید). حال، n رقم وسط این عدد را انتخاب میکنیم (در عدد ۰۷۵۶ ، ۲ رقم وسط، ۷۵ خواهد بود). عدد n رقمی بدست آمده، خروجی الگوریتم است.

طرز کار روش میان مربع

در زیر، این فرایند را برای چند عدد نمایش داده ایم.

56 \rightarrow 56 \times 56 = 3136 \rightarrow 13

1234 \rightarrow 1234 \times 1234 = 1522756 \rightarrow 01522756 \rightarrow 5227

دلیل اینکه در ابتدا عدد n را زوج انتخاب کردیم این است که در نهایت بتوانیم n رقم از در وسط عددی 2n رقمی انتخاب بکنیم (می‌توانید امتحان کنید که برای اعداد فرد، این کار ممکن نیست).

در تصویر زیر، که برای n=2 طراحی شده است، هر پیکان نمایانگر این است که خروجی الگوریتم به ازای یک عدد چه خواهد بود.

نمودار روش میان مربع

مولد پیمانه ای خطی (Linear Congruential Generator)

کارکرد این نوع مولد ها، بر اساس حساب پیمانه ای است. طرز کار این الگوریتم به این صورت است که در مرحله اول، ورودی الگوریتم را در ضریب a ضرب می‌کنیم. سپس عدد c را به آن می افزاییم. در نهایت، باقی مانده حاصل را در تقسیم بر عدد m محاسبه میکنیم. این باقی مانده، خروجی الگوریتم خواهد بود. سه متغیر a و c و m توسط طراح الگوریتم تعیین می‌شوند و در طول فرآیند ثابت می‌مانند.

حال این توضیحات را به زبان ریاضی بیان میکنیم:

X_{n+1} = (aXn + c) \mod m

در این فرمول، X دنباله اعداد تصادفی است و منظور از X_i، عدد i ام در این دنباله است. خوراک اولیه، X_0 خواهد بود.

توجه داشته باشید که تمام خروجی های بدست آمده از این الگوریتم، کوچک تر از m خواهند بود. در این الگوریتم اگر c=0، به مولد طراحی شده، مولد پیمانه ای ضربی(Multiplicative Congruential Generator)، و در غیر این صورت، مولد پیمانه ای ترکیبی (Mixed Congruential Generator) گویند.

در این قسمت، سعی شد تا علاوه بر تکمیل بحث های قسمت قبل، موضوع اعداد شبه تصادفی و مولد های آنها به طور مختصر بررسی شود. در پایان، شما را دعوت میکنیم تا خودتان روش هایی برای تولید اعداد شبه تصادفی پیشنهاد کنید. این روش ها ممکن است به سادگی روش میان مربع که در بالا مطرح شد، باشند. ایده های خود را در بخش نظرات با ما در میان بگذارید.

برخی منابع استفاده شده در تهیه این مطلب:

Pseudorandom Number Generator

Linear Congruential Generator (LCG)

Middle-square Method

دیدگاه‌ها

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *