https://3rabica.org/index.php?action=history&feed=atom&title=%D8%AA%D8%AD%D8%AF%D9%8A%D8%AF_%D8%AD%D9%84%D9%82%D9%8Aتحديد حلقي - تاريخ المراجعة2026-06-09T03:26:26Zتاريخ التعديل لهذه الصفحة في الويكيMediaWiki 1.43.7https://3rabica.org/index.php?title=%D8%AA%D8%AD%D8%AF%D9%8A%D8%AF_%D8%AD%D9%84%D9%82%D9%8A&diff=3250179&oldid=prevعبد العزيز: بوت: إصلاح أخطاء فحص أرابيكا من 1 إلى 1042023-07-23T02:22:44Z<p>بوت: إصلاح أخطاء فحص أرابيكا من 1 إلى 104</p>
<p><b>صفحة جديدة</b></p><div>{{يتيمة|تاريخ=يونيو 2020}}<br />
<br />
في [[علم الحاسوب|علوم الكمبيوتر]]، '''تحديد الحلقة''' أو '''إيجاد الحلقة''' عبارة عن مشكلة [[خوارزمية]] لايجاد حلقة في [[متتالية|تسلسل]] لقيم مكررة.<br />
<br />
بالنسبة لأي [[دالة]] {{Mvar|f}} تقوم بربط مجموعة [[مجموعة منتهية|منتهية]] {{Mvar|S}} بذاتها، وبأي قيمة أولية {{تعبير رياضي|''x''<sub>0</sub>}}في {{Mvar|S}} ، فإن تسلسل قيم الدوال المكررة كالتالي<br />
<br />
: <math> x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots</math><br />
<br />
يجب في النهاية استخدام نفس القيمة مرتين: يجب أن يكون هناك زوج من المؤشرات المميزة {{Mvar|i}} و {{Mvar|j}} بحيث يكون {{تعبير رياضي|1=''x<sub>i</sub>'' = ''x<sub>j</sub>''}}يجب أن يستمر التسلسل بشكل دوري، من خلال تكرار نفس سلسة القيم من {{تعبير رياضي|''x<sub>i</sub>''}}إلى {{تعبير رياضي|''x''<sub>''j'' − 1</sub>}}. تحديد الحلقة هو مشكلة إيجاد {{Mvar|i}} و {{Mvar|j}}، إذا كان لدينا فرضاً {{Mvar|f}} و {{تعبير رياضي|''x''<sub>0</sub>}}.<br />
<br />
يوجد العديد من الخوارزميات المعروفة لتحديد الحلقات بسرعة وبقليل من الذاكرة. تحرك خوارزمية السلحفاة والأرنب [[روبرت فلويد|روبرت دبليو فلويد]] مؤشرين بسرعات مختلفة من خلال سلسلة من القيم حتى يشير كلاهما إلى قيم متساوية. عوضاً عن ذلك، تعتمد خوارزمية برينت Brent على فكرة البحث الأسي. تستخدم كل من خوارزميات فلويد وبرنت عددًا ثابتًا من خلايا الذاكرة، وتأخذ عددًا من تقييمات الدوال التي تتناسب مع المسافة من بداية السلسلة إلى التكرار الأول. تقوم العديد من الخوارزميات بمقايضة كميات أكبر من الذاكرة من أجل تقييم أقل للدوال.<br />
<br />
تشمل تطبيقات التحديد الحلقي اختبار جودة [[مولد أعداد شبه عشوائية|مولدات الأرقام العشوائية الزائفة (شبه عشوائية)]] [[دالة تجزئة بيان معمى|و دوال هاش للتشفير]]، وخوارزميات [[نظرية الأعداد الحاسوبية|نظرية العدد الحاسوبي]]، والكشف عن [[حلقة لامتناهية|الحلقات اللانهائية]] في برامج الكمبيوتر والتكوينات الدورية في [[أتمتة خلوية|الأتمتة الخلوية]]، وتحليل الشكل الآلي لهياكل بيانات [[قائمة متصلة|القائمة المتصلة]] .<ref>{{استشهاد بدورية محكمة|عنوان=Nondeterministic Algorithms|مسار= https://dl.acm.org/doi/abs/10.1145/321420.321422|صحيفة=Journal of the ACM (JACM)|تاريخ=1967-10-01|DOI=10.1145/321420.321422|لغة=EN|الأول=FloydRobert|الأخير=W|مسار أرشيف= https://web.archive.org/web/20200623003812/https://dl.acm.org/doi/abs/10.1145/321420.321422|تاريخ أرشيف=2020-06-23}}</ref><br />
<br />
== مثال ==<br />
[[ملف:Functional_graph.svg|تصغير|دالة من وإلى المجموعة {0،1،2،3،4،5،6،7،8} والرسم البياني الوظيفي (الدالي) المناسب |بديل=|197x197بك]]<br />
يوضح الشكل دالة {{Mvar|f}} التي تربط المجموعة <math>''S = {0,1,2,3,4,5,6,7,8}''</math> بذاتها. إذا بدأنا بالتعيين من {{تعبير رياضي|1=''x''<sub>0</sub> = 2}}و التطبيق بشكل متكرر {{Mvar|f}} ،فسنرى سلسلة القيم كالتالي<br />
<br />
:<math>2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....</math><br />
<br />
الحلقة في سلسلة القيم هذه هي <math>6, 3, 1</math>.<br />
<br />
== المراجع ==<br />
{{مراجع|30em}}<br />
<br />
== روابط خارجية ==<br />
<br />
* غابرييل نيفاش، [http://www.gabrielnivasch.org/fun/cycle-detection مشكلة اكتشاف الدورة وخوارزمية المكدس]<br />
* [http://wiki.c2.com/?TortoiseAndHare السلحفاة والأرنب البري] ، مستودع نمط بورتلاند<br />
* [http://www.siafoo.net/algorithm/10 خوارزمية الكشف عن دورة فلويد (السلحفاة والأرنب البري)]<br />
* [http://www.siafoo.net/algorithm/11 خوارزمية اكتشاف دورة برنت (السلحفاة عن بعد)]<br />
{{شريط بوابات|علم الحاسوب}}<br />
<br />
[[تصنيف:برمجة|*]]</div>عبد العزيز