مرجع
آخر الزيارات

اختبار الخاصية

605 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في علوم الحاسوب، خوارزمية اختبار الخاصية لمشكلة قرار هي الخوارزمية التي يكون فيها تعقيد تساؤلها لمدخلاتها أصغر بكثير من حجم المشكلة. تجد هنا «التعريف والمتغيرات» و«خصائص وحدود».
المحتويات
  1. التعريف والمتغيرات
  2. خصائص وحدود

تعريفًا بالموضوع، في علوم الحاسوب، خوارزمية اختبار الخاصية لمشكلة قرار هي الخوارزمية التي يكون فيها تعقيد تساؤلها لمدخلاتها أصغر بكثير من حجم المشكلة. وعادة ما يتم استخدام خوارزميات اختبار الخاصية لتقرر ما إذا كان بعض الكينونات الرياضية (مثل رسم بياني أو وظيفة بولياني) لديها خاصية «عالمية»، أو أنها «بعيدة» عن امتلاك هذه الخاصية، وذلك باستخدام عدد قليل من التساؤلات «المحلية» للكائن. وفيما يلي تفاصيل أوسع عن ذلك.

خوارزميات اختبار الخاصية مهمة في نظرية PCP.

وفي السياق ذاته، فمثلًا، مشكلة الوعد التالية تُدخل خوارزمية تعقيد تساؤلها مستقل عن الحجم (لثابت تعسفي ε > 0):

ومن جهة أخرى، "وبالنظر إلى الرسم البياني G على رؤوس n، قرر ما إذا كان G مخطط ثنائي، أواذا كان لا يصلح لـ G أن تكون مخطط ثنائي حتى بعد إزالة مجموعة فرعية تعسفية في الأكثر من حواف G"

التعريف والمتغيرات

كذلك، ويقال أن خوارزمية اختبار الخاصية لها خطأ من جانب واحد إذا استوفى الشرط الأقوى عند قبول احتمالية حالات x ∈ L هو 1 بدلا من ⅔.

كذلك، وتعني «x تبعد عن L مسافة ε» أن مسافة هامنج بين x وأي خط على L يبعد على الأقل |x| ε.

علاوةً على ذلك، ويقال أن خوارزمية اختبار الخاصية غير قابلة للتكيف إذا كانت تنفذ جميع الاستفسارات قبل أن «تلاحظ» أي إجابات على الاستفسارات السابقة. ومثل هذه الخوارزمية يمكن رؤيتها على أنها تعمل على النحو التالي. أولا تتلقى الخوارزمية مدخلاتها. وقبل النظر إلى المدخلات، وذلك باستخدام العشوائية الداخلية، تقرر الخوارزمية أي رموز يُستفسر عنها. ثم، تلاحظ الخوارزمية هذه الرموز. وأخيرا، وبدون إجراء أية استفسارات إضافية (ولكن ربما باستخدام العشوائية الخاصة بها)، تقرر الخوارزمية ما إذا كانت تقبل أو ترفض الإدخال.

كذلك، إذا كانت x تبعد عن L مسافة ε، سترفض الخوارزمية x باحتمالية ⅔.

من جانب آخر، رسميا، تعتبر خوارزمية اختبار الخاصية ذات تعقيد استفسار q(n) ومعامل قرب ε لمشكلة قرار L كـ خوارزميةعشوائية حيث، عند مدخل x (كمثال على L) ينتج عن q(|x|) لـ x وتتصرف على النحو التالي:

إذا كانت x في L، تتقبل الخوارزمية x باحتمالية ⅔.

خصائص وحدود

علاوةً على ذلك، ان معامل الكفاءة الخاص بخوارزمية اختبار الخاصية هو تعقيد التساؤل، وهو الحد الأقصى لعدد رموز المدخلات المعاينة على جميع المدخلات محددة الطول (وجميع الاختيارات العشوائية بواسطة الخوارزمية). وتصميم الخوارزميات ذات تعقيد التساؤل الصغير هو شيء ممتع. في كثير من الحالات يكون وقت عمل خوارزميات اختبار الخاصية فرعية الخط في طول الاقتراح. وعادة، فان الهدف الأول هو جعل تعقيد التساؤل في أصغر حجم ممكن كوظيفة اقتراح حجم n، ومن ثم دراسة الاعتماد على معامل ε.

إضافةً إلى ذلك، وبعكس إعدادات التعقيدات النظرية الأخرى، يتأثر مقارب تعقيد التساؤل لخوارزميات اختبار الخاصية إلى حدّ كبير بطريقة تمثيل الاقتراحات. فمثلًا، عندما يكون ε= 0.01، تُدخِل مشكلة اختبار انقسام الرسوم البيانية المتراكمة (التي تمثلها المصفوفات المتصلة) خوارزمية ذات تعقيد تساؤل ثابت. وفي المقابل، تتطلب الرسوم البيانية المتناثره على القمم n (التي تمثلها قائمة متصلة) خوارزميات اختبار خاصية ذات تعقيد تساؤل .

إضافةً إلى ذلك، تعقيد التساؤل في خوارزميات اختبار الخاصية ينمو كلما صغر معامل التقارب ε لجميع الخصائص الغير عادية. وهذا الاعتماد على ε ضروري حيث أن التغيير في أقل من ε من الرموز في المدخلات لا يمكن الكشف عنه مع احتمال ثابت باستخدام عدد أقل من الاستعلامات O(1/ ε). ويمكن اختبار الكثير من خصائص الرسوم البيانية الكثيفة المثيرة للاهتمام عن طريق استخدام تعقيد تساؤل يعتمد فقط على ε وليس على حجم الرسم البياني n. ومع ذلك، فيمكن أن تنمو تعقيد التساؤل بسرعة هائلة كوظيفة ε. ومثلًا، كانت أفضل خوارزمية معروفة لوقت طويل لاختبار ما إذا كان الرسم البياني لا يحتوي على مثلث كان لديه تعقيد تساؤل والذي كان في شكل دالة برجية poly(1/ε)، وفقط في عام 2010 تم تحسينه إلى دالة برجية log(1/ε).

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.