الكشف عن الدورة

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
📷 يحتوي على 35 صور
الموسوعة الحرة

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

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

x0، x1=و(x0)، x2=و(x1)، ...، xأنا=و(xأنا-1)، ...{\displaystyle x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots }

يجب في النهاية استخدام القيمة نفسها مرتين: يجب أن يكون هناك زوج من المؤشرات المختلفة i و j بحيث يكون xᵢ = xⱼ . بمجرد حدوث ذلك، يجب أن يستمر التسلسل دوريًا ، بتكرار نفس تسلسل القيم من xᵢ إلى xⱼ - 1. اكتشاف الدورة هو مشكلة إيجاد i و j ، بمعلومية f و x₀ .

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

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

مثال

تحدد هذه الدالة الدورات {4} و {1، 6، 3}.

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

2، 0، 6، 3، 1، 6، 3، 1، 6، 3، 1، ....

الدورة في تسلسل القيم هذا هي 6، 3، 1 .

التعريفات

ليكن S أي مجموعة منتهية، و f أي دالة داخلية من S إلى نفسها، و x₀ أي عنصر من S. لأي i > 0 ، ليكن xᵢ = f ( xᵢ - 1 ) . ليكن μ أصغر دليل بحيث تتكرر القيمة xᵢμ عددًا لا نهائيًا من المرات ضمن متتالية القيم xᵢ ، وليكن λ (طول الحلقة ) أصغر عدد صحيح موجب بحيث xᵢμ = xᵢλ + μ . تتمثل مهمة اكتشاف الدورة في إيجاد λ و μ . [ 1 ]

يمكن النظر إلى المشكلة نفسها من منظور نظرية الرسم البياني ، وذلك بإنشاء رسم بياني وظيفي (أي رسم بياني موجه لكل رأس فيه حافة واحدة خارجية) تكون رؤوسه عناصر المجموعة S ، وحوافه تربط كل عنصر بقيمة الدالة المقابلة، كما هو موضح في الشكل. تشكل مجموعة الرؤوس التي يمكن الوصول إليها من رأس البداية x₀ رسمًا بيانيًا فرعيًا يشبه شكله الحرف اليوناني رو ( ρ ): مسار طوله μ من x₀ إلى دورة من λ رأسًا. [ 2 ]

لا تُحدد خوارزميات الكشف عن الدورات العملية قيمتي λ و μ بدقة. [ 1 ] فهي عادةً ما تُحدد حدين أدنى وأعلى μ <sub> l</sub> ≤ μ <sub>h</sub> ≤ μ <sub> h </sub> لبداية الدورة، ويجب إجراء بحث أكثر تفصيلًا في النطاق إذا لزم تحديد القيمة الدقيقة لـ μ . كذلك، لا تضمن معظم الخوارزميات إيجاد λ مباشرةً، ولكنها قد تجد قيمةً متعددةً kλ < μ + λ . (سيؤدي استمرار البحث لعدد إضافي kλ / q من الخطوات، حيث q هو أصغر قاسم أولي لـ kλ ، إما إلى إيجاد قيمة λ الحقيقية أو إثبات أن k = 1 ).

تمثيل الحاسوب

باستثناء الأمثلة التوضيحية المذكورة أعلاه، لن يتم تحديد f كجدول قيم. يتطلب هذا الجدول تعقيدًا مكانيًا من رتبة O ( | S | ) ، وإذا كان ذلك مسموحًا، فإن بناء مصفوفة الأسلاف ( مصفوفة ترابطية تربط xᵢ بـ i) أثناء تكرار f سيكشف عن القيمة المكررة الأولى عند زيارتها للمرة الثانية، حيث تكون القيمة في مصفوفة الأسلاف هي μ ويكون الفهرس الحالي هو μ + λ . بدلًا من ذلك، تُعطى خوارزمية كشف الدورات صندوقًا أسود لتوليد التسلسل xᵢ ، وتتمثل المهمة في إيجاد λ و μ باستخدام ذاكرة قليلة جدًا.

قد يتكون الصندوق الأسود من تطبيق للدالة التكرارية f ، ولكنه قد يخزن أيضًا حالة داخلية إضافية لزيادة كفاءة الحساب. على الرغم من أن xᵢ = f ( xᵢ - 1 ) يجب أن يكون صحيحًا من حيث المبدأ ، إلا أن حسابه مباشرةً قد يكون مكلفًا؛ إذ يمكن تعريف الدالة بدلالة اللوغاريتم المتقطع لـ xᵢ - 1 أو خاصية أخرى يصعب حسابها عمليًا ، ولا يمكن حسابها إلا بمعلومات إضافية. في مثل هذه الحالات، يصبح عدد الصناديق السوداء المطلوبة معيارًا يميز بين الخوارزميات.

ثمة سبب آخر لاستخدام إحدى هذه الخوارزميات، وهو أنها خوارزميات مؤشرات لا تُجري أي عمليات على عناصر المصفوفة S سوى اختبار التساوي. يتطلب تطبيق المصفوفة الترابطية حساب دالة تجزئة على عناصر S ، أو ترتيبها . لكن يمكن تطبيق اكتشاف الحلقات في الحالات التي يتعذر فيها أي من هذين الأمرين.

المثال الكلاسيكي هو خوارزمية رو لبولارد لتحليل الأعداد الصحيحة إلى عواملها الأولية ، والتي تبحث عن عامل p لعدد معطى n من خلال البحث عن القيمتين xᵢ و xᵢ + λ المتساويتين بتردد p دون معرفة p مسبقًا . يتم ذلك بحساب القاسم المشترك الأكبر للفرق xᵢ - xᵢ + λ مع مضاعف معروف لـ p ، وهو n . إذا كان القاسم المشترك الأكبر غير تافه (ليس 1 ولا n )، فإن القيمة تكون عاملًا حقيقيًا لـ n ، كما هو مطلوب. [ 2 ] إذا لم يكن n عددًا أوليًا، فلا بد أن يكون له عامل واحد على الأقل p ≤ √n ، وبحسب مفارقة عيد الميلاد ، فإن الدالة العشوائية f لها طول دورة متوقع (بتردد p ) يساوي √p ≤ 4√n . 

الخوارزميات

إذا تم إدخال البيانات على شكل روتين فرعي لحساب الدالة f ، فيمكن حل مشكلة اكتشاف الحلقات بسهولة باستخدام λ + μ تطبيقًا للدالة فقط، وذلك ببساطة عن طريق حساب تسلسل القيم xᵢ واستخدام بنية بيانات مثل جدول التجزئة لتخزين هذه القيم واختبار ما إذا كانت كل قيمة لاحقة قد تم تخزينها بالفعل. مع ذلك، فإن تعقيد المساحة لهذه الخوارزمية يتناسب طرديًا مع λ + μ ، وهو كبير بشكل غير ضروري. بالإضافة إلى ذلك، يتطلب تنفيذ هذه الطريقة كخوارزمية مؤشر تطبيق اختبار المساواة على كل زوج من القيم، مما ينتج عنه وقت إجمالي من الدرجة الثانية. لذلك، ركزت الأبحاث في هذا المجال على هدفين: استخدام مساحة أقل من هذه الخوارزمية البسيطة، وإيجاد خوارزميات مؤشر تستخدم عددًا أقل من اختبارات المساواة.

سلحفاة فلويد والأرنب

خوارزمية فلويد "السلحفاة والأرنب" للكشف عن الدورات، مطبقة على التسلسل 2، 0، 6، 3، 1، 6، 3، 1، ...

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

سُميت الخوارزمية نسبةً إلى روبرت دبليو فلويد ، الذي نُسب اختراعها إلى دونالد كنوث . [ 3 ] [ 4 ] مع ذلك، لم تظهر الخوارزمية في أعمال فلويد المنشورة، وقد يكون هذا خطأً في نسبتها إليه: فقد وصف فلويد خوارزميات لحصر جميع الدورات البسيطة في رسم بياني موجه في ورقة بحثية عام 1967، [ 5 ] لكن هذه الورقة لا تتناول مشكلة إيجاد الدورات في الرسوم البيانية الوظيفية، وهي موضوع هذه المقالة. في الواقع، يُعد تصريح كنوث (عام 1969)، الذي نسبها إلى فلويد دون توثيق، أول ظهور معروف لها في المطبوعات، وبالتالي قد تكون نظرية شائعة ، لا تُنسب إلى فرد واحد. [ 6 ]

يكمن جوهر الخوارزمية فيما يلي: إذا وُجدت دورة، فإنه لأي عددين صحيحين i ≥ μ و k ≥ 0 ، يكون xᵢ = xᵢ + kλ ، حيث λ هو طول الحلقة المطلوب إيجادها، و μ هو فهرس العنصر الأول في الدورة، و k عدد صحيح يمثل عدد الحلقات. بناءً على ذلك، يمكن إثبات أن i = kλ ≥ μ لبعض قيم k إذا وفقط إذا كان xᵢ = x₂ᵢ ( إذا كان xᵢ = x₂ᵢ في الدورة ، فإنه يوجد عدد صحيح k بحيث يكون 2ᵢ = i + kλ ، مما يعني أن i = kλ ؛ وإذا وُجد عددان صحيحان i و k بحيث يكون i = kλ ، فإن 2ᵢ = i + kλ و x₂ᵢ = xᵢ + kλ ) . وبالتالي، لا يحتاج الخوارزمية إلا إلى التحقق من القيم المتكررة من هذا الشكل الخاص، بحيث تكون إحداها أبعد عن بداية المتتالية بمقدار الضعف عن الأخرى، وذلك لإيجاد دورة ν لتكرار من مضاعفات λ . بمجرد إيجاد ν ، تعيد الخوارزمية تتبع المتتالية من بدايتها لإيجاد أول قيمة متكررة xμ في المتتالية، مستفيدةً من حقيقة أن λ يقسم ν ، وبالتالي فإن xμ = xμ + v . وأخيرًا، بمجرد معرفة قيمة μ ، يصبح من السهل إيجاد طول λ لأقصر دورة متكررة، وذلك بالبحث عن أول موضع μ + λ حيث xμ + λ = xμ .

وبالتالي ، يحتفظ الخوارزمية بمؤشرين في التسلسل المعطى، أحدهما (السلحفاة) عند xᵢ ، والآخر (الأرنب) عند xᵢ . في كل خطوة من خطوات الخوارزمية، يزيد i بمقدار واحد، مما يُحرك السلحفاة خطوة واحدة للأمام والأرنب خطوتين للأمام في التسلسل، ثم يقارن قيم التسلسل عند هذين المؤشرين. أصغر قيمة لـ i > 0 التي تُشير عندها السلحفاة والأرنب إلى قيم متساوية هي القيمة المطلوبة ν .

يوضح كود بايثون التالي كيفية تطبيق هذه الفكرة كخوارزمية.

دالة فلويد ( f , x0 ) -> ( int , int ): """خوارزمية فلويد لاكتشاف الدورات.""" # المرحلة الرئيسية للخوارزمية: إيجاد تكرار x_i = x_2i. # يتحرك الأرنب بسرعة ضعف سرعة السلحفاة، # وتزداد المسافة بينهما بمقدار 1 في كل خطوة. # في النهاية، سيكون كلاهما داخل الدورة، ثم # عند نقطة ما، ستكون المسافة بينهما # قابلة للقسمة على الدورة λ. tortoise = f ( x0 ) # f(x0) هو العنصر/العقدة المجاورة لـ x0. hare = f ( f ( x0 )) while tortoise != hare : tortoise = f ( tortoise ) hare = f ( f ( hare ))# عند هذه النقطة، يكون موضع السلحفاة، ν، والذي يساوي أيضًا # المسافة بين الأرنب والسلحفاة، قابلاً للقسمة على # الدورة λ. لذا، فإن الأرنب الذي يتحرك في دورة خطوة واحدة في كل مرة، # والسلحفاة (التي أعيد ضبطها إلى x0) التي تتحرك باتجاه الدورة، # سيتقاطعان في بداية الدورة. ولأن # المسافة بينهما ثابتة عند 2ν، وهي من مضاعفات λ، # فسوف يتفقان بمجرد أن تصل السلحفاة إلى المؤشر μ.# إيجاد موضع μ للتكرار الأول. μ = 0 السلحفاة = x0 طالما أن السلحفاة ≠ الأرنب : السلحفاة = f ( السلحفاة ) الأرنب = f ( الأرنب ) # يتحرك الأرنب والسلحفاة بنفس السرعة μ += 1# إيجاد طول أقصر دورة تبدأ من x_μ # يتحرك الأرنب خطوة واحدة في كل مرة بينما تبقى السلحفاة ثابتة. # يتم زيادة lam حتى يتم العثور على λ. lam = 1 hare = f ( tortoise ) while tortoise != hare : hare = f ( hare ) lam += 1عودة لام ، مو

لا يصل هذا الكود إلى التسلسل إلا عن طريق تخزين ونسخ المؤشرات، وتقييم الدوال، واختبارات المساواة؛ ولذلك، يُصنَّف كخوارزمية مؤشرات. تستخدم الخوارزمية O ( λ + μ ) عملية من هذه الأنواع، ومساحة تخزين O (1) . [ 7 ]

خوارزمية برنت

وصف ريتشارد ب. برنت خوارزمية بديلة للكشف عن الدورات، تشبه خوارزمية السلحفاة والأرنب، إذ لا تتطلب سوى مؤشرين في التسلسل. [8] إلا أنها تعتمد على مبدأ مختلف: البحث عن أصغر قوة للعدد 2ᵢ أكبر من كلٍّ من λ و μ . بالنسبة لـ i = 0، 1، 2، ... ، تقارن الخوارزمية xᵢ - 1 مع كل قيمة لاحقة في التسلسل حتى القوة التالية للعدد 2، وتتوقف عند العثور على تطابق. تتميز هذه الخوارزمية بميزتين مقارنةً بخوارزمية السلحفاة والأرنب: فهي تجد الطول الصحيح λ للدورة مباشرةً، دون الحاجة إلى البحث عنه في مرحلة لاحقة، وتتضمن خطواتها تقييمًا واحدًا فقط للدالة f بدلًا من ثلاثة. [ 9 ]

يوضح كود بايثون التالي كيفية عمل هذه التقنية بمزيد من التفصيل.

دالة برنت ( f , x0 ) -> ( int , int ): """خوارزمية برنت لاكتشاف الدورات.""" # المرحلة الرئيسية: البحث عن قوى متتالية للعدد اثنين power = lam = 1 tortoise = x0 hare = f ( x0 ) # f(x0) هو العنصر/العقدة المجاورة لـ x0. # يفترض هذا وجود دورة؛ وإلا فلن تنتهي هذه الحلقة while tortoise != hare : if power == lam : # هل حان وقت بدء قوة جديدة للعدد اثنين؟ tortoise = hare power *= 2 lam = 0 hare = f ( hare ) lam += 1# إيجاد موضع التكرار الأول بطول λ سلحفاة = أرنب = x0 لـ i في النطاق ( lam ): أرنب = f ( أرنب ) # المسافة بين الأرنب والسلحفاة هي الآن λ.# بعد ذلك، يتحرك الأرنب والسلحفاة بنفس السرعة حتى يتفقا، ويكون معدل الحركة ( μ ) مساويًا للصفر . طالما أن السلحفاة لا تساوي الأرنب : السلحفاة = f ( السلحفاة ) الأرنب = f ( الأرنب ) معدل الحركة (μ) += 1عودة لام ، مو

على غرار خوارزمية السلحفاة والأرنب، تُعد هذه خوارزمية مؤشر تستخدم O ( λ + μ ) من الاختبارات وتقييمات الدوال، ومساحة تخزين O (1) . من السهل إثبات أن عدد تقييمات الدوال لا يمكن أن يتجاوز خوارزمية فلويد. يدّعي برنت أن خوارزمية البحث عن الدورات التي ابتكرها تعمل، في المتوسط، أسرع بنحو 36% من خوارزمية فلويد، وأنها تُسرّع خوارزمية بولارد رو بنحو 24%. كما يُجري تحليلًا للحالة المتوسطة لنسخة عشوائية من الخوارزمية، حيث لا يكون تسلسل المؤشرات التي يتتبعها المؤشر الأبطأ من بين المؤشرين هو قوى العدد 2 نفسها، بل مُضاعفًا عشوائيًا لقوى العدد 2. على الرغم من أن تطبيقه الرئيسي المقصود كان في خوارزميات تحليل الأعداد الصحيحة إلى عواملها الأولية، إلا أن برنت يناقش أيضًا تطبيقات في اختبار مولدات الأرقام شبه العشوائية. [ 8 ]

خوارزمية جوسبر

تجد خوارزمية آر دبليو جوسبر [ 10 ] [ 11 ] الدورةλ{\displaystyle \lambda }، والحد الأدنى والحد الأعلى لنقطة البداية،μل{\displaystyle \mu _{l}}وμu{\displaystyle \mu _{u}}، من الدورة الأولى. الفرق بين الحد الأدنى والحد الأعلى هو من نفس رتبة الدورة، أيμل+λ≈μح{\displaystyle \mu _{l}+\lambda \approx \mu _{h}}.

تحتفظ الخوارزمية بمجموعة من السلاحفتيج{\displaystyle T_{j}}لكلxأنا{\displaystyle x_{i}}:

  • لكل0≤ج≤سجل2⁡أنا،{\displaystyle 0\leq j\leq \log _{2}i,}يقارنxأنا{\displaystyle x_{i}}لتيج{\displaystyle T_{j}}.
  • لوxأنا=تيج{\displaystyle x_{i}=T_{j}}تم اكتشاف دورة، بطولλ=(أنا-2ج)تعديل2ج+1+1.{\displaystyle \lambda =(i-2^{j}){\bmod {2}}^{j+1}+1.}
  • إذا لم يتم العثور على تطابق، فقم بتعيينتيك←xأنا{\displaystyle T_{k}\leftarrow x_{i}}، أينك{\displaystyle k}يمثل عدد الأصفار اللاحقة في التمثيل الثنائي لـأنا+1{\displaystyle i+1}أي أكبر قوة للعدد 2 التي تقسمأنا+1{\displaystyle i+1}.

إذا كان من غير الملائم تغيير عدد المقارنات كماأنا{\displaystyle i}مع زيادة عدد الحالات، يمكنك تهيئة جميعتيج=x0{\displaystyle T_{j}=x_{0}}ولكن يجب عليه بعد ذلك العودةλ=أنا{\displaystyle \lambda =i}لوxأنا=تيج{\displaystyle x_{i}=T_{j}}بينماأنا<2ج{\displaystyle i<2^{j}}.

المزايا

تتميز خوارزمية جوسبر بأنها اقتصادية في استخدام الذاكرة، واقتصادية للغاية في حساب دالة المولد، وتجد دائمًا طول الدورة بدقة (دون أي مضاعفات). لكن ثمنها يكمن في عدد كبير من مقارنات التساوي. يمكن وصفها تقريبًا بأنها نسخة متزامنة من خوارزمية برنت. فبينما تستخدم خوارزمية برنت سلحفاة واحدة، يُعاد تموضعها كلما مرّ الأرنب بقوة من قوى العدد اثنين، تستخدم خوارزمية جوسبر عدة سلاحف (يتم حفظ عدة قيم سابقة)، موزعة بشكل أسي تقريبًا. وفقًا للملاحظة الواردة في البند 132 من HAKMEM ، [ 11 ]، ستكتشف هذه الخوارزمية التكرار قبل الظهور الثالث لأي قيمة، أي أن الدورة ستتكرر مرتين على الأكثر. وينص HAKMEM أيضًا على أنه يكفي تخزين⌈سجل2⁡λ⌉{\displaystyle \lceil \log _{2}\lambda \rceil }القيم السابقة؛ ومع ذلك، فإن هذا لا يوفر أي توفير إلا إذا كنا نعرف مسبقًا أنλ{\displaystyle \lambda }أصغر بكثير منμ{\displaystyle \mu }. تخزن التطبيقات القياسية [ 10 ]⌈سجل2⁡(μ+2λ)⌉{\displaystyle \lceil \log _{2}(\mu +2\lambda )\rceil }القيم. على سبيل المثال، افترض أن قيم الدالة هي أعداد صحيحة من 32 بت، لذاμ+λ≤232{\displaystyle \mu +\lambda \leq 2^{32}}وμ+2λ≤233.{\displaystyle \mu +2\lambda \leq 2^{33}.} ثم ستجد خوارزمية جوسبر الدورة بعد أقل منμ+2λ{\displaystyle \mu +2\lambda }تقييمات الدوال (في الواقع، الأكثر احتمالاً هو3⋅231-1{\displaystyle 3\cdot 2^{31}-1}), بينما تستهلك مساحة 33 قيمة (كل قيمة عبارة عن عدد صحيح 32 بت).

تعقيد

علىأنا{\displaystyle i}في التقييم رقم - لدالة المولد، تقارن الخوارزمية القيمة المولدة معسجل2⁡أنا{\displaystyle \log _{2}i}القيم السابقة؛ لاحظ أنأنا{\displaystyle i}يصل إلى ما لا يقل عنμ+λ{\displaystyle \mu +\lambda }وعلى الأكثرμ+2λ{\displaystyle \mu +2\lambda }وبالتالي، فإن التعقيد الزمني لهذه الخوارزمية هويا((μ+λ)⋅سجل⁡(μ+λ)){\displaystyle O((\mu +\lambda )\cdot \log(\mu +\lambda ))}لأنه يخزنسجل2⁡(μ+2λ){\displaystyle \log _{2}(\mu +2\lambda )}القيم، وتعقيدها المكاني هوΘ(سجل⁡(μ+λ)){\displaystyle \Theta (\log(\mu +\lambda ))}هذا في ظل النموذج الثنائي المعتاد ، المفترض في جميع أنحاء هذه المقالة، حيث يكون حجم قيم الدالة ثابتًا. وبدون هذا الافتراض، نعلم أنه يتطلبΩ(سجل⁡(μ+λ)){\displaystyle \Omega (\log(\mu +\lambda ))}مساحة للتخزينμ+λ{\displaystyle \mu +\lambda }القيم المتميزة، لذا فإن التعقيد المكاني الإجمالي هوΩ(سجل2⁡(μ+λ)).{\displaystyle \Omega (\log ^{2}(\mu +\lambda )).}

المفاضلات بين الزمان والمكان

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

  • يصف برنت [ 8 ] بالفعل تنويعات لتقنيته حيث تكون مؤشرات قيم التسلسل المحفوظة قوىً لعدد R غير اثنين. باختيار R ليكون عددًا قريبًا من واحد، وتخزين قيم التسلسل عند مؤشرات قريبة من تسلسل قوى متتالية لـ R ، يمكن لخوارزمية كشف الدورات استخدام عدد من تقييمات الدالة يقع ضمن عامل صغير جدًا من القيمة المثلى λ + μ . [ 13 ] [ 14 ]
  • يقدم سيدجويك، وشيمانسكي، وياو [ 15 ] طريقة تستخدم M من خلايا الذاكرة ولا تتطلب في أسوأ الحالات سوى(λ+μ)(1+جم-1/2){\displaystyle (\lambda +\mu )(1+cM^{-1/2})}تُجرى تقييمات الدوال، لثابت ما c ، والتي تُثبت أنها مثالية. تتضمن هذه التقنية الاحتفاظ بمعامل عددي d ، وتخزين المواضع في الجدول فقط في التسلسل التي هي مضاعفات d ، ومسح الجدول ومضاعفة d كلما تم تخزين عدد كبير جدًا من القيم.
  • وصف العديد من المؤلفين طرقًا مميزة لتخزين قيم الدوال في جدول بناءً على معيار يتعلق بالقيم نفسها، بدلاً من الاعتماد على مواقعها (كما في طريقة سيدجويك وآخرون). على سبيل المثال، يمكن تخزين القيم التي تساوي صفرًا بتردد قيمة معينة d . [ 16 ] [ 17 ] وبعبارة أبسط، ينسب نيفاش [ 12 ] اقتراح تخزين عينة عشوائية من القيم التي سبق رؤيتها إلى دي بي وودروف، مع اختيار عشوائي مناسب في كل خطوة لضمان بقاء العينة عشوائية.
  • يصف نيفاش [ 12 ] خوارزمية لا تستخدم مقدارًا ثابتًا من الذاكرة، بل يكون مقدار الذاكرة المتوقع استخدامه (بافتراض أن دالة الإدخال عشوائية) لوغاريتميًا بالنسبة لطول التسلسل. تُخزَّن القيمة في جدول الذاكرة، باستخدام هذه التقنية، عندما لا توجد قيمة أصغر منها في أي عنصر لاحق. وكما يُبين نيفاش، يمكن الاحتفاظ بالعناصر باستخدام بنية بيانات المكدس ، ولا يلزم مقارنة كل قيمة متتالية في التسلسل إلا بأعلى المكدس. تنتهي الخوارزمية عند العثور على عنصر التسلسل المُكرَّر ذي القيمة الأصغر. يُتيح تشغيل الخوارزمية نفسها باستخدام مكدسات متعددة، مع استخدام تباديل عشوائية للقيم لإعادة ترتيبها داخل كل مكدس، مُوازنة بين الوقت والمساحة تُشابه الخوارزميات السابقة. مع ذلك، حتى نسخة هذه الخوارزمية ذات المكدس الواحد لا تُعد خوارزمية مؤشر، نظرًا للمقارنات اللازمة لتحديد أي القيمتين أصغر.

أي خوارزمية للكشف عن الدورات تخزن على الأكثر M قيمة من تسلسل الإدخال يجب أن تؤدي على الأقل(λ+μ)(1+1م-1){\displaystyle (\lambda +\mu )\left(1+{\frac {1}{M-1}}\right)}تقييمات الدوال. [ 18 ] [ 19 ]

التطبيقات

تم استخدام تقنية الكشف عن الدورات في العديد من التطبيقات.

مراجع

  1. 1 2 جو، أنطوان (2009)، "7. خوارزميات قائمة على تاريخ الميلاد للدوال"، التحليل الخوارزمي للشفرات ، مطبعة CRC، ص  223، ISBN 978-1-420-07003-3.
  2. 1 2 جوكس (2009 ، ص 224) . 
  3. 1 2 كنوت، دونالد إي. (1969)، فن برمجة الحاسوب، المجلد الثاني: الخوارزميات شبه العددية ، أديسون-ويسلي، ص 7، التمرينان 6 و7 
  4. ↑ يصف كتاب "دليل التشفير التطبيقي"، من تأليف ألفريد ج. مينيز، وبول س. فان أورشوت، وسكوت أ. فانستون، صفحة 125 ، هذه الخوارزمية وغيرها.
  5. ↑ فلويد، ر. و. (1967)، "الخوارزميات غير الحتمية"، مجلة ACM ، 14 (4): 636-644 ، doi : 10.1145/321420.321422 ، S2CID 1990464 
  6. ↑ وظيفة التجزئة بليك، بقلم جان فيليب أوماسون، وويلي ماير، رافائيل سي.دبليو. فان، لوكا هنزن (2015)، ص. 21 ، الحاشية 8
  7. ↑ Joux (2009) ، القسم 7.1.1 ، خوارزمية فلويد لإيجاد الدورة ، الصفحات 225-226.
  8. 1 2 3 4 برنت، آر بي (1980)، "خوارزمية محسّنة لتحليل مونت كارلو" (ملف PDF) ، مجلة BIT للرياضيات العددية ، 20 (2): 176-184 ، doi : 10.1007/BF01933190 ، S2CID 17181286 .
  9. ↑ Joux (2009) ، القسم 7.1.2 ، خوارزمية برنت لإيجاد الدورة ، الصفحات 226-227.
  10. 1 2 وارن، هنري س. الابن. "كاشفات الحلقات لفلويد وجوسبر" . هاكرز ديلايت . مؤرشف من الأصل في 14 أبريل 2016. تم الاسترجاع في 8 فبراير 2017 .
  11. 1 2 "حكمم - التدفقات والدوال المتكررة - مسودة، لم تُدقّق بعد" . مؤرشف من الأصل بتاريخ 18-03-2020 . تم الاطلاع عليه بتاريخ 02-05-2024 .
  12. 1 2 3 4 نيفاش، غابرييل (2004)، "الكشف عن الدورات باستخدام مكدس"، رسائل معالجة المعلومات ، 90 (3): 135-140 ، doi : 10.1016/j.ipl.2004.01.016.
  13. ↑ شنور، كلاوس ب .؛ لينسترا، هندريك و. (1984)، "خوارزمية تحليل مونت كارلو مع تخزين خطي"، رياضيات الحوسبة ، 43 (167): 289-311 ، doi : 10.2307/2007414 ، hdl : 1887/3815 ، JSTOR 2007414 .
  14. 1 2 تيسكي، إيدلين (1998)، "خوارزمية فعالة من حيث المساحة لحساب بنية المجموعة"، رياضيات الحساب ، 67 (224): 1637-1663 ، Bibcode : 1998MaCom..67.1637T ، doi : 10.1090/S0025-5718-98-00968-5.
  15. ↑ سيدجويك، روبرت ؛ شيمانسكي، توماس ج.؛ ياو، أندرو سي.-سي. (1982)، "تعقيد إيجاد الدورات في الدوال الدورية"، مجلة SIAM للحوسبة ، 11 (2): 376-390 ، doi : 10.1137/0211030.
  16. ↑ فان أورشوت، بول سي؛ وينر، مايكل جيه (1999)، "البحث المتوازي عن التصادم مع تطبيقات التحليل التشفيري" ، مجلة علم التشفير ، 12 (1): 1-28 ، doi : 10.1007/PL00003816 ، S2CID 5091635 .
  17. 1 2 كيسكواتر، جيه-جيه؛ ديليسكاي، جيه-بي (1990)، "ما مدى سهولة البحث عن التصادم؟ تطبيق على DES"، التقدم في علم التشفير - EUROCRYPT '89، ورشة عمل حول نظرية وتطبيق تقنيات التشفير ، سلسلة محاضرات في علوم الحاسوب، المجلد 434، سبرينغر-فيرلاغ، الصفحات 429-434 ، doi : 10.1007/3-540-46885-4_43 ، ISBN   978-3-540-53433-4.
  18. 1 2 فيش، فيث إلين (1981)، "الحدود الدنيا لمشكلة اكتشاف الدورة"، وقائع الندوة الثالثة عشرة لجمعية آلات الحوسبة حول نظرية الحوسبة ، ستوك 81، ص 96-105 ، doi : 10.1145/800076.802462 ، ISBN  978-1-4503-7392-0، S2CID 119742106 .
  19. ↑ أليندر، إريك دبليو .؛ كلاوي، ماريا إم. (1985)، "تحسين الحدود الدنيا لمشكلة اكتشاف الدورة"، علوم الحاسوب النظرية ، 36 ( 2-3 ): 231-237 ، doi : 10.1016/0304-3975(85)90044-1.
  20. ↑ بولارد، جيه إم (1975)، "طريقة مونت كارلو للتحليل إلى عوامل"، BIT ، 15 (3): 331-334 ، doi : 10.1007/BF01933667 ، S2CID 122775546 .
  21. ↑ بولارد، جيه إم (1978)، "طرق مونت كارلو لحساب المؤشر (mod p )"، رياضيات الحساب ، 32 (143)، الجمعية الرياضية الأمريكية: 918-924 ، doi : 10.2307/2006496 ، JSTOR 2006496 ، S2CID 235457090  .
  22. 1 2 كاليسكي، بيرتون إس. الابن؛ ريفست، رونالد إل .؛ شيرمان، آلان تي. (1988)، "هل معيار تشفير البيانات عبارة عن مجموعة؟ (نتائج تجارب التدوير على DES)"، مجلة علم التشفير ، 1 (1): 3-36 ، doi : 10.1007/BF00206323 ، S2CID 17224075 .
  23. ↑ Joux (2009) ، القسم 7.5، التصادمات في وظائف التجزئة، ص 242-245.
  24. ↑ فان جيلدر، ألين (1987)، "الكشف الفعال عن الحلقات في لغة برولوج باستخدام تقنية السلحفاة والأرنب"، مجلة برمجة المنطق ، 4 (1): 23-31 ، doi : 10.1016/0743-1066(87)90020-3.
  25. ↑ أوغستون، ميخائيل؛ هون، ميو هار (1997)، "تأكيدات لتحليل الشكل الديناميكي لهياكل بيانات القوائم"، AADEBUG '97، وقائع ورشة العمل الدولية الثالثة حول التصحيح التلقائي ، مقالات لينشوبينغ الإلكترونية في علوم الحاسوب والمعلومات، جامعة لينشوبينغ ، ص 37-42 .