تحديد حلقي

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

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

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

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

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