طريقة الروس الأربعة

في علوم الحاسوب ، تُعرف طريقة الروس الأربعة أو "تسريع الروس الأربعة" ^{[ 1 ]} بأنها تقنية لتسريع الخوارزميات التي تتضمن المصفوفات المنطقية ، أو بشكل عام الخوارزميات التي تتضمن المصفوفات التي يمكن أن تأخذ كل خلية فيها عددًا محدودًا فقط من القيم الممكنة.

تعتمد الفكرة الرئيسية لهذه الطريقة على تقسيم المصفوفة إلى مربعات صغيرة بحجم t × t ، حيث t قيمة ثابتة ، واستخدام جدول بحث لتنفيذ الخوارزمية بسرعة داخل كل مربع. يُشفّر فهرس جدول البحث قيم خلايا المصفوفة في الزاوية العلوية اليسرى لحدود المربع قبل تنفيذ عملية معينة من الخوارزمية، بينما تُشفّر نتيجة جدول البحث قيم خلايا الحدود في الزاوية السفلية اليمنى للمربع بعد تنفيذ العملية. بالتالي، يمكن تنفيذ الخوارزمية بالكامل بالعمل على ( n / t ) ^² مربع فقط بدلاً من n² خلية مصفوفة، حيث n هو طول ضلع المصفوفة. وللحفاظ على حجم جداول البحث (والوقت اللازم لتهيئتها) صغيرًا بما يكفي، يُختار t عادةً ليكون من ^رتبة O (log n ) .

يمكن إنشاء جداول البحث في زمن قدره O ( n × t² ⁾ ، وإذا تم ضبط t على log n ، فإن ذلك ينتج عنه تعقيد زمني قدره O ( n (log n ) ^² ) لإنشاء الجداول. ومع ذلك، يظل زمن البحث O(n²/ ( log n ) ² ) هو ^{المهيمن} على هذا الزمن (بافتراض أن تكلفة ذاكرة الوصول ^{العشوائي} هي تكلفة الوحدة). ^{[ 1 ]}

تشمل الخوارزميات التي يمكن تطبيق طريقة الروس الأربعة عليها ما يلي:

• حساب الإغلاق المتعدي للرسم البياني،
• ضرب المصفوفات المنطقية ،
• حساب مسافة التحرير ،
• محاذاة التسلسل ،
• حساب المؤشر لمطابقة الأنماط الثنائية المبعثرة .

في كل حالة من هذه الحالات، يؤدي ذلك إلى تسريع الخوارزمية بعامل أو عاملين لوغاريتميين .

تم تطبيق خوارزمية عكس المصفوفة "طريقة الروس الأربعة" التي نشرها بارد في مكتبة M4RI لإجراء عمليات حسابية سريعة على المصفوفات الكثيفة على F² _. وتستخدم مكتبة SageMath ومكتبة PolyBoRi مكتبة M4RI. ^{[ 2 ]}

تم تقديم الخوارزمية بواسطة VL Arlazarov و EA Dinic و MA Kronrod و IA Faradžev في عام 1970. ^{[ 3 ]} أصل الاسم غير معروف؛ يشرح Aho و Hopcroft و Ullman (1974) ما يلي:

أما الطريقة الثانية، والتي تسمى غالبًا خوارزمية "الروس الأربعة"، نسبة إلى عدد وجنسية مخترعيها، فهي أكثر "عملية" إلى حد ما من الخوارزمية الواردة في النظرية 6.9. ^{[ 4 ]}

عمل المؤلفون الأربعة جميعهم في موسكو، روسيا في الاتحاد السوفيتي آنذاك، ^{[ 5 ]} ومع ذلك، كان أرلازاروف فقط هو الروسي؛ لذلك قيل إن الاسم يعكس "المستوى العام من الجهل لدى الغرب بشأن الأعراق في الاتحاد السوفيتي آنذاك". ^{[ 1 ]}

• أرلازاروف، ف .؛ دينيتش، إ.؛ كرونرود، م.؛ فارادزيف، إ. (1970)، "حول البناء الاقتصادي للإغلاق المتعدي للرسم البياني الموجه"، دوكل. أكاد. ناوك إس إس إس آر ، 194 (11). العنوان الأصلي: "التنمية الاقتصادية العابرة للحدود الشرقية" نشرت في أكاديميات دوكلادي هاوك إس آر إس 134 (3)، 1970.
• أهو، ألفريد ف .؛ هوبكروفت، جون إي.؛ أولمان ، جيفري د. (1974). تصميم وتحليل خوارزميات الحاسوب . أديسون-ويسلي. ISBN 978-0-201-00029-0. OCLC 1147299 . 
• بارد، غريغوري ف. (2009)، التحليل الجبري للشفرات ، سبرينغر، رقم ISBN 978-0-387-88756-2
• غوسفيلد، دان (1997). خوارزميات على السلاسل والأشجار والمتتاليات: علوم الحاسوب وعلم الأحياء الحاسوبي . كامبريدج: مطبعة جامعة كامبريدج. الصفحات  302-307 (القسم 12.7). ISBN 978-0-521-58519-4.