تحديد حلقي

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

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

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

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

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

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

مثال

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

يوضح الشكل دالة قالب:Mvar التي تربط المجموعة $S=0^{″},1,2,3,4,5,6,7,8$ بذاتها. إذا بدأنا بالتعيين من قالب:تعبير رياضيو التطبيق بشكل متكرر قالب:Mvar ،فسنرى سلسلة القيم كالتالي

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

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

روابط خارجية

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