برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: این شکل یک تابع f که مقادیر مجموعه را می‌نگارد نشان می‌دهد {s= {۰ ٬ ۱ ٬ ۲ ٬ ۳ ٬ ۴ ٬ ۵ ٬ ۶ ٬ ۷ ٬ ۸ را به خود. اگر یک‌نفر از x ۰ = ۲ شروع کند و مکررا f را مورد اعمال قرار دهد دنباله‌ای از مقادیر زیر را مشاهده می‌کند s را مجموعه متناهی دلخواهی فرض کنید، f تابعی دلخواه از s به خودش، و x ۰ هر عنصر دلخواه از sباشد. برای هر i> ۰، فرض می‌کنیم xi = f (xi − ۱). فرض می‌کنیم μ کوچکترین اندیسی باشد به‌طوری‌که مقدار xμ به‌طور بینهایت در دنباله مقادیر xi ظاهر شود، و فرض می‌کنیم λ (طول دور) باشد کوچکترین عدد صحیح مثبت باشد به‌طوری‌که xμ = xλ + μ. تشخیص دور مسئله یافتن λ و μ می‌باشد. همین مسئله را در نظریه گراف، با ساخت یک گراف تابع (که یک گراف جهت‌دار خوانده می‌شودد که در آن هر راس دارای یک یال خارج شونده است) که رئوس آن عناصر s و یال‌های آن یک عنصر را به مقدار تابع مربوط به آن نگاشت می‌کنند، همان‌طور که در شکل نشان داده شده‌است. مجموعه رئوس قابل‌دسترسی با شروع از راس x ۰ از یک زیر گراف با یک‌شکل شبیه رو (ρ): یک مسیر با طول μ از x ۰ به یک دور با λ راس. به‌طور کلی، f را نمی‌توان به صورت جدولی از مقادیر، طوری‌که در شکل بالا نشان داده‌شده نمایش داد. بلکه، یک الگوریتم تشخیص دور ممکن است یا با دنباله مقادیر xi، یا یک تابع برای محاسبه f داده شود. هدف پیدا کردن λ و μ با بررسی چند مقدار از دنباله یا پیدا کردن مقدار تابع در چند مرتبه با کمترین استفاده از سلول‌های حافظه می‌باشد. به‌طور معمول، پیچیدگی فضا در مسئله تشخیص دور اهمیت دارد: ما مایل به حل این مسئله با استفاده ماز مقداری از حافظه هستیم که کمتر از حافظه مورد نیاز برای ذخیره کل دنباله اعداد می‌باشد. در برخی از برنامه‌ها، و به ویژه در الگوریتم رو پولارد برای تجزیه اعداد طبیعی، الگوریتم دسترسی محدودتری به s و f دارد. در الگوریتم پولارد، به عنوان مثال، s مجموعه‌ای از اعداد صحیح می‌باشد که عامل اول عدد مورد تجزیه به آن بخشپذیر است، بنابراین حتی اندازه s هم نامعلوم است. برای اینکه تشخیص دور با چنین اطلاعات محدودی قابل‌استفاده باشد، باید براساس توانایی‌های زیر بنا شوند. در ابتدا فرض می‌شود الگوریتم حافظه مخصوص به خود را دارد که یک نشانگر به مقدار شروع یعنی x ۰ دارد. همچنین به نام «الگوریتم لاک‌پشت و خرگوش» نامیده می‌شود با اشاره به حکایت لاک‌پشت و خرگوش از ازوپ. الگوریتم پس …
برداشت:
در علوم کامپیوتر تشخیص دور (به انگلیسی : cycle detection) یا یافتن دور (به انگلیسی : cycle finding) مسئله‌ای الگوریتمی است که به بررسی پیدا کردن یک دور (تکرار) در توالی مقادیر یک تابع می‌کند . برای هر تابع f که یک مجموعه متناهی s را به خودش ، و هر مقدار اولیه x۰ در s را ، با توالی مقادیر تابع به صورت زیر نگاشت می‌کنددر نهایت مجبور به دو بار استفاده کردن از یک مقدار هستیم : باید جفت اندیس‌های مجزایی وجود داشته باشد به صورت i و j به‌طوری‌که xi = xj . هنگامی که این اتفاق می‌افتد ، توالی باید همچنان به صورت دوره‌ای ، با همان دنباله‌ای از مقادیر از xi تا xj − ۱ تکرار شود .