تحديد حلقي

في علوم الكمبيوتر، تحديد الحلقة أو إيجاد الحلقة عبارة عن مشكلة خوارزمية لايجاد حلقة في تسلسل لقيم مكررة.

بالنسبة لأي دالة f تقوم بربط مجموعة منتهية S بذاتها، وبأي قيمة أولية x₀في S ، فإن تسلسل قيم الدوال المكررة كالتالي

$x_0,x_1=f(x_0),x_2=f(x_1),\dots ,x_i=f(x_{i-1}),\dots$

يجب في النهاية استخدام نفس القيمة مرتين: يجب أن يكون هناك زوج من المؤشرات المميزة i و j بحيث يكون x_i = x_jيجب أن يستمر التسلسل بشكل دوري، من خلال تكرار نفس سلسة القيم من x_iإلى x_{j − 1}. تحديد الحلقة هو مشكلة إيجاد i و j، إذا كان لدينا فرضاً f و x₀.

يوجد العديد من الخوارزميات المعروفة لتحديد الحلقات بسرعة وبقليل من الذاكرة. تحرك خوارزمية السلحفاة والأرنب روبرت دبليو فلويد مؤشرين بسرعات مختلفة من خلال سلسلة من القيم حتى يشير كلاهما إلى قيم متساوية. عوضاً عن ذلك، تعتمد خوارزمية برينت Brent على فكرة البحث الأسي. تستخدم كل من خوارزميات فلويد وبرنت عددًا ثابتًا من خلايا الذاكرة، وتأخذ عددًا من تقييمات الدوال التي تتناسب مع المسافة من بداية السلسلة إلى التكرار الأول. تقوم العديد من الخوارزميات بمقايضة كميات أكبر من الذاكرة من أجل تقييم أقل للدوال.

تشمل تطبيقات التحديد الحلقي اختبار جودة مولدات الأرقام العشوائية الزائفة (شبه عشوائية) و دوال هاش للتشفير، وخوارزميات نظرية العدد الحاسوبي، والكشف عن الحلقات اللانهائية في برامج الكمبيوتر والتكوينات الدورية في الأتمتة الخلوية، وتحليل الشكل الآلي لهياكل بيانات القائمة المتصلة .

مثال

دالة من وإلى المجموعة {0،1،2،3،4،5،6،7،8} والرسم البياني الوظيفي (الدالي) المناسب

يوضح الشكل دالة f التي تربط المجموعة $S={0^{″}}^{,}$ بذاتها. إذا بدأنا بالتعيين من x₀ = 2و التطبيق بشكل متكرر f ،فسنرى سلسلة القيم كالتالي

$2,0,6,3,1,6,3,1,6,3,1,....$

الحلقة في سلسلة القيم هذه هي $6,3,1$.

روابط خارجية

• غابرييل نيفاش، مشكلة اكتشاف الدورة وخوارزمية المكدس
• السلحفاة والأرنب البري ، مستودع نمط بورتلاند
• خوارزمية الكشف عن دورة فلويد (السلحفاة والأرنب البري)
• خوارزمية اكتشاف دورة برنت (السلحفاة عن بعد)