موضوع مقاله: شناسایی دور | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # شناسایی دور | مقدمه: در علوم کامپیوتر تشخیص دور یا یافتن دور مسئله‌ای الگوریتمی است که به بررسی پیدا کردن یک دور (تکرار) در توالی مقادیر یک تابع می‌کند. | ## بخش 1: شناسایی دور | برای هر تابع f که یک مجموعه متناهی S را به خودش، و هر مقدار اولیه در S را، با توالی مقادیر تابع به صورت زیر نگاشت می‌کند در نهایت مجبور به دو بار استفاده کردن از یک مقدار هستیم: باید جفت اندیس‌های مجزایی وجود داشته باشد به صورت i و j به‌طوری‌که . هنگامی که این اتفاق می‌افتد، توالی باید همچنان به صورت دوره‌ای، با همان دنباله‌ای از مقادیر از تا تکرار شود. چندین الگوریتم برای پیدا کردن دور به سرعت و با استفاده از حافظه اندک شناخته شده‌است. الگوریتم «لاک‌پشت و خرگوش» فلوید، الگوریتم حرکت دو اشاره گر در توالی مقادیر تابع با دو سرعت متفاوت می‌باشد تا در نهایت هر دو اشاره‌گر به یک مقدار برابر اشاره کنند. هر دو الگوریتم فلوید و برنت از تعداد ثابتی از سلول‌های حافظه استفاده می‌کنند، و هم چنین تعدادی از مقایسه و ارزیابی میان مقادیر تابع که متناسب با فاصله اولین تکرار از شروع توالی می‌باشد. دیگر الگوریتم‌ها استفاده بیشتر از حافظه در مقابل مقایسه‌های کمتر را پیشنهاد می‌دهند. شناسایی دور شامل تست کیفیت مولد اعداد شبه تصادفی و تابع درهمساز رمزنگارانه، الگوریتم های نظریه اعداد رایانشی، تشخیص حلقه بی‌نهایت در برنامه‌های کامپیوتری و پیکربندی‌های متناوب در اتوماتای سلولی،و داده ساختارهای لیست پیوندی است. اگر یک‌نفر از شروع کند و مکرراً f را مورد اعمال قرار دهد دنباله‌ای از مقادیر زیر را مشاهده می‌کند در این دنباله دور مورد نظر اعداد ۶٬۳٬۱ می‌باشند تعاریف S را مجموعه متناهی دلخواهی فرض کنید، f تابعی دلخواه از S به خودش، و هر عنصر دلخواه از Sباشد. فرض می‌کنیم μ کوچکترین اندیسی باشد به‌طوری‌که مقدار به‌طور بینهایت در دنباله مقادیر ظاهر شود، و فرض می‌کنیم λ (طول دور) باشد کوچکترین عدد صحیح مثبت باشد به‌طوری‌که . همین مسئله را در نظریه گراف،با ساخت یک گراف تابع (که یک گراف جهت دار خوانده می‌شودد که در آن هر راس دارای یک یال خارج شونده است) که رئوس آن عناصر S و یال‌های آن یک عنصر را به مقدار تابع مربوط به آن نگاشت می‌کنند، همان‌طور که در شکل نشان داده شده‌است. مجموعه رئوس قابل دسترسی با شروع از راس از یک زیر گراف با یک شکل شبیه رو (ρ): یک مسیر با طول μ از به یک دور با λ راس.. بیان کامپیوتری به‌طور کلی، f را نمی‌توان به صورت جدولی از مقادیر، طوری‌که در شکل بالا نشان داده شده نمایش داد. بلکه، یک الگوریتم تشخیص دور ممکن است یا با دنباله مقادیر ، یا یک تابع برای محاسبه f داده شود. هدف پیدا کردن λ و μ با بررسی چند مقدار از دنباله یا پیدا کردن مقدار تابع در چند مرتبه با کمترین استفاده از سلول‌های حافظه می‌باشد. به‌طور معمول، پیچیدگی فضا در مسئله تشخیص دور اهمیت دارد: ما مایل به حل این مسئله با استفاده ماز مقداری از حافظه هستیم که کمتر از حافظه مورد نیاز برای ذخیره کل دنباله اعداد می‌باشد. در برخی از برنامه‌ها، و به ویژه در الگوریتم رو پولارد برای تجزیه اعداد طبیعی،الگوریتم دسترسی محدودتری به S و f دارد. در الگوریتم پولارد، به عنوان مثال، S مجموعه‌ای از اعداد صحیح می‌باشد که عامل اول عدد مورد تجزیه به آن بخشپذیر است، بنابراین حتی اندازه S هم نامعلوم است. برای اینکه تشخیص دور با چنین اطلاعات محدودی قابل استفاده باشد، باید براساس توانایی‌های زیر بنا شوند. | ## بخش 2: شناسایی دور | در ابتدا فرض می‌شود الگوریتم حافظه مخصوص به خود را دارد که یک نشانگر به مقدار شروع یعنی دارد. در هر مرحله ممکن است یکی از سه عمل زیر را انجام دهد: ممکن است هر نشانگری را به شئ دیگری کپی کند، ممکن است f را اعمال کند و هرکدام از نشانگرهایش را با یک نشانگر به شئ بعدی جایگزین کند یا ممکن است با اجرای یک تابع تشخیص دهد که دو نشانگر به یک مقدار برابر در دنباله اشاره دارند یا نه. آزمون برابری می‌تواند بعضی از محاسبات غیربدیهی دربرداشته باشد: برای مثال، در الگوریتم پولارد رو، این عملیات این‌گونه پیاده می‌شود که آیا اختلاف بین دو مقدار ذخیره شده بزرگترین مقسوم علیه مشترک بغیر بدیهی با عدد مورد تجزیه دارد یا خیر. در این زمینه، با قیاس با مدل محاسباتی ماشین اشاره گر، یک الگوریتم که تنها از کپی کردن یک اشاره گر، پیشروی در دنباله، و آزمون‌های برابری استفاده می‌کند، الگوریتم اشاره‌گری نامیده می‌شود. الگوریتم‌ها اگر ورودی به عنوان یک رابطه برای محاسبه f داده شده باشد، مسئله تشخیص چرخه ممکن است به‌طور بدیهی با تنها اجرای تابع حل شود، به سادگی با محاسبه دنباله‌ای از مقادیر و با استفاده از یک ساختار دادهمانند یک جدول درهم ساز برای ذخیره این مقادیر و تست اینکه آیا هر مقدار در حال حاضر ذخیره شده‌است یا خیر. علاوه بر این برای اجرای این روش به عنوان یک الگوریتم اشاره‌گر، نیاز به استفاده از آزمون برابری برای هر جفت از مقادیر و در نتیجه به زمان از مرتبه دو می‌انجامد؛ بنابراین تحقیقات در این زمینه بر روی دو هدف متمرکز شده: استفاده از فضای کمتر از این الگوریتم ساده، و پیدا کردن الگوریتم‌های اشاره‌گری که با استفاده از آزمون برابری کمتر. الگوریتم یافتن دور فلوید الگوریتمی است که از دو اشاره‌گر استفاده می‌کند، که با سرعت‌های متفاوت در دنباله حرکت می‌کنند. همچنین به نام «الگوریتم لاک‌پشت و خرگوش» نامیده می‌شود با اشاره به حکایت لاک‌پشت و خرگوش از ازوپ. 21, footnote 8 نکته اصلی در درک این الگوریتم این است که، برای هر عدد صحیح و داریم که در آن λ طول حلقه یافت شده و μ اندیس اولین عنصر چرخه است. این الگوریتم تنها نیاز به بررسی مقادیر تکراری این فرم خاص، تا آنجا که یکی از مقادیر پس از شروع دنباله تکرار شود، برای یافتن دوره تناوبv برای تکرار که مضربی از λ می‌باشد. به محض اینکه v یافت شد، الگوریتم دنباله را دوباره از آغاز بررسی می‌کند تا اولین مقدار تکراری ، با توجه به این مسئله کهv بر λ بخشپزیر است به همین دلیل . سرانجام پس از یافتن مقدار μ به‌طور بدیهی به دنبال طول λ می‌گردیم که کوچکترین طول دور می‌باشد، با یافتن اولین مکان که در آن . این الگوریتم در نتیجه دو اشاره گر را در طول دنباله داده شده حفظ می‌کند، یکی (لاک‌پشت) در و دیگری (خرگوش) در . در هر مرحله از الگوریتم،i را با حرکت لاک‌پشت یک گام به جلو یک واحد افزایش می‌دهد و خرگوش دو گام به جلو در دنباله، و سپس مقدار دنباله در این دو اشاره گر را مقایسه می‌کند. کوچکترین مقدار که در آن نقطه مقدار لاک‌پشت و خرگوش برابر است که مقدار ν مورد نظر ماست. با این حال، بر اساس اصل مختلف دیگری بنا شده‌است: جستجو برای کوچکترین توان دو که بزرگتر از هر دو λ و μ باشد. برای ، الگوریتم را با هر یک از مقادیر پس از آن دنباله مقایسه می‌کند، و هر گاه عدد مورد نظر را یافت متوقف می‌شود. سخت نیست که نشان دهیم تعداد مقداریابی‌های تابع نسبت به الگوریتم فلوید هیچگاه بیشتر نمی‌شود. | ## بخش 3: شناسایی دور | برنت ادعا می‌کند که به‌طور متوسط الگوریتم یافتن دور او حدود ۳۶ درصد سریعتر از الگوریتم فلوید می‌باشد و الگوریتم پولارد رو را تا حدود ۲۴٪ تسربع می‌کند. او همچنین یک آنالیز حالت متوسط برای یک نسخه تصادفی الگوریتم اجرا کرد که در آن دنباله‌ای از شاخض‌های دنبال شده خود توانی از ۲ نبودند اما یک مضربی از توان دو به صورت تصادفی بودند. اگرچه برنامه اصلی او در رابطه با تجزیه عوامل اول اعداد صحیح بود، برنت همچنین در رابطه با برنامه تست کردن اعداد شبه تصادفی نیز بحث کرد. الگوریتم گسپر الگوریتم گسپر دوره تناوب را می‌یابد اما نقطه شروع اولین پریود را مشخص نمی‌کند. از ویژگی‌های اصلی آن است که هیچ‌گاه برای مقداریابی تابع مولد بر نمی‌گردد که این عمل از نظر زمانی و حافظه بهینه است. بررسی زمان و حافظه برخی از نویسندگان روش‌هایی را مورد بررسی قرار داده‌اند که نسبت به الگوریتم فلوید و برنت حافظهٔ بیشتری نیاز دارد اما دور را سریعتر شناسایی می‌کند. به‌طور کلی این روش‌ها دنباله‌ای از مقادیر از پیش محاسبه‌شده را ذخیره می‌کنند، و بررسی می‌کنند که آیا مقادیر جدید ما مقادیر قبلاً محاسبه شده برابرند یا خیر. به منظور انجام سریع آن‌ها، به‌طور معمول از یک جدول درهم‌سازی یا یک داده ساختار مشابه برای ذخیره مقادیر از قبل محاسبه شده‌استفاده می‌شود، و در نهایت هیچ الگوریتم اشاره‌گری در کار نیست: به‌طور خاص آن‌ها قابل پیاده شدن به روی الگوریتم پولارد نیستند. تفاوتی که این الگوریتم‌ها دارند در این است که کدام مقادیر برای ذخیره شدن انتخاب شوند. ما به بررسی این روش‌ها به‌طور خلاصه می‌پردازیم: مدل‌های مختلف روش برنت به این صورت است که اندیس‌های دنباله‌های ذخیره شده توانی از یک عدد نزدیک به یک R به غیر از ۲ باشد. این روش شامل حفظ یک پارامتر عددی مانند d، ذخیره کردن مکان‌هایی از دنباله که مضربی از d می‌باشند در یک جدول، و پاک کردن جدول و دو برابر کردن مقدار d هر زمان که مقادیر زیادی ذخیره شد. تعدادی از نویسندگان روش‌های نقاط متمایز را توصیف کرده‌اند که مقادیر تابع را در یک جدول بنابر معیارهایی مثل مقدار آن‌ها (به حای مکان آنها) ذخیره می‌کنند. Nivasch الگوریتمی را توصیف می‌کند که از مقدار حافظه معین و ثابت استفاده نمی‌کند اما مقدار حافظه مورد انتظارش (تحت این فرض که ورودی تابع تصادفی می‌باشد) به صورت لگاریتمی از طول دنباله می‌باشد. در این روش یک بخش زمانی در جدول حافظه ذخیره می‌شود به‌طوری‌که هیچ‌کدام از بخش‌های بعدی مقدار کوچکتری از آن نداشته باشند. همان‌طور که Nivasch نمایش داد، می‌توان آیتم‌های این روش را با استفاده از داده ساحتار پشته حفظ کرد، و در برای هر عضو متوالی دنباله کافی است تنها آن را با عنصر روی پشته مقایسه کنیم. با اجرای الگوریتم مشابه در چندین پشته، با استفاده از جایگشت‌های تصادفی مقادیر دنباله برای ترتیب‌های محتلف آن‌ها در پشته، منجر به یک بهینگی زمانی یا حافظه می‌شود همانند الگوریتم‌های قبلی. حتی نسخه‌ای از این الگوریتم که با یک پشته است یک الگوریتم اشاره‌گری نیست، با توجه به این که نیاز به مقایسه برای تعیین مقدار کوچکتر از میان دو مقدار را دارد. این کاربرد برای اولین برا توسط دانلد کنوت هنگامی که الگوریتم فلوید را بررسی می‌کرده‌است بیان شده‌است. | ## جمع‌بندی | پیکربندی‌های تناوبی موجود در شبیه‌سازی‌های اتوماتای سلولی را می‌توان با به کاربردن الگوریتم تشخیص دور در دنباله‌ای از حالت‌های اتوماتون به دست آورد.