تحديد حلقي

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

هذه المقالة يتيمة إذ لا تصل إليها مقالة أخرى. ساعد بإضافة وصلة إليها في مقالة متعلقة بها. (يونيو 2020)

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

${\displaystyle 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 على فكرة البحث الأسي. تستخدم كل من خوارزميات فلويد وبرنت عددًا ثابتًا من خلايا الذاكرة، وتأخذ عددًا من تقييمات الدوال التي تتناسب مع المسافة من بداية السلسلة إلى التكرار الأول. تقوم العديد من الخوارزميات بمقايضة كميات أكبر من الذاكرة من أجل تقييم أقل للدوال.

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