نموذج الخصم

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

الخصوم الثلاثة الشائعون هم الخصم الغافل، والخصم المتكيف عبر الإنترنت، والخصم المتكيف خارج الإنترنت.

يُشار أحيانًا إلى الخصم الغافل بالخصم الضعيف. يعرف هذا الخصم شفرة الخوارزمية، لكنه لا يعرف نتائجها العشوائية.

يُطلق على الخصم التكيفي عبر الإنترنت أحيانًا اسم الخصم المتوسط. يجب على هذا الخصم اتخاذ قراره الخاص قبل أن يُسمح له بمعرفة قرار الخوارزمية.

يُطلق على الخصم المتكيف غير المتصل بالإنترنت أحيانًا اسم الخصم القوي. هذا الخصم يعرف كل شيء، حتى مولد الأرقام العشوائية. إنه قوي لدرجة أن العشوائية لا تُجدي نفعًا ضده.

من إس. بن ديفيد، أ. بورودين ، ر. كارب ، ج. تاردوس ، أ. ويغدرسون لدينا:

• إذا كانت هناك خوارزمية عشوائية تنافسية من النوع α ضد أي خصم تكيفي غير متصل بالإنترنت، فإنه يوجد أيضًا خوارزمية حتمية تنافسية من النوع α.
• إذا كانت G خوارزمية عشوائية تنافسية من النوع c ضد أي خصم متكيف عبر الإنترنت، وكانت هناك خوارزمية عشوائية تنافسية من النوع d ضد أي خصم غافل، فإن G هي خوارزمية عشوائية تنافسية من النوع (c * d) ضد أي خصم متكيف خارج الإنترنت.

• تحليل المنافسة (خوارزمية عبر الإنترنت)
• مشكلة خادم K
• خوارزمية الإنترنت

• بورودين، أ .؛ اليانيف، ر. (1998). الحوسبة عبر الإنترنت والتحليل التنافسي . مطبعة جامعة كامبريدج. ISBN 978-0-521-56392-5.
• س. بن ديفيد؛ أ. بورودين؛ ر. كارب ؛ ج. تاردوس؛ أ. ويغدرسون. (1994). "حول قوة العشوائية في الخوارزميات عبر الإنترنت" (ملف PDF) . مجلة Algorithmica . 11 : 2-14 . doi : 10.1007/BF01294260 .

• قائمة مراجع الأبحاث المتعلقة بالخوارزميات عبر الإنترنت