مبدأ ياو

**مبدأ ياو** أو **مبدأ ياو للحد الأدنى الأقصى** أو **مبدأ ليما ياو** هو مبدأ في نظرية التعقيد الحسابي يُستخدم بشكل أساسيّ لتحليل كفاءة الخوارزميات العشوائية وتحديد الحدود الدنيا لأدائها عن طريق ربطها بالخوارزميات الحتمية (غير العشوائية).

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

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

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

## الصياغة
يُصاغ مبدأ ياو بدلالة مقياس تكلفة حقيقي القيمة اختياري c(A,x) لخوارزمية A على مُدخل x مثل زمن تشغيلها، حيث يُراد دراسة القيمة المتوقعة لها على خوارزميات عشوائية ومُدخلات عشوائية. يتمّ اختيار الخوارزميات المُستخدمة في مقياس التكلفة هذا من مجموعة منتهية \mathcal{A} من الخوارزميات الحتمية؛ ومن الطرق الشائعة لجعل المسألة تحتوي على مجموعة محدودة فقط من الخوارزميات هو تقييد مُدخلاتها بحجم واحد. يجب أيضًا اختيار المُدخلات من مجموعة محدودة \mathcal{X}، والتي يُمكن جعلها محدودة بنفس الطريقة. يتوافق بعد ذلك كل توزيع احتمالي يُطبّق على مجموعة الخوارزميات \mathcal{A} مع خوارزمية عشوائية تقوم أولًا باختيار عشوائي من مجموعة الخوارزميات \mathcal{A} وفقًا لهذا التوزيع، ثم تُتبع الخوارزمية المختارة؛ بهذه الطريقة، يمكن نمذجة فئة الخوارزميات العشوائية لنفس المسألة على أنها الفئة \mathcal{R} لجميع التوزيعات الاحتمالية المُطبّقة على مجموعة الخوارزميات \mathcal{A}. وأخيرًا، تتضمن صياغة مبدأ ياو فئة جميع التوزيعات الاحتمالية على المدخلات الموجودة في المجموعة المنتهية \mathcal{X}، والتي يُرمز لها بالرمز \mathcal{D}.

## التطبيقات والأمثلة

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

### المقارنات
غالبًا ما يُدرس التعقيد الزمني لخوارزميات الفرز والاختيار القائمة على المقارنة باستخدام عدد المقارنات بين أزواج عناصر البيانات كمؤشر للزمن الكلي. عند دراسة هذه المشكلات على مجموعة ثابتة من العناصر، يمكن التعبير عن مدخلاتها على هيئة تباديل، ويمكن التعبير عن الخوارزمية الحتمية على هيئة شجرة قرار. بهذه الطريقة، تُشكّل كلٌّ من المدخلات والخوارزميات مجموعاتٍ منتهية، كما يقتضي مبدأ ياو. تُحدّد حجة التناظر أصعب توزيعات المدخلات: وهي التباديل العشوائية، أي التوزيعات على n عنصرًا متميزًا، حيث تكون جميع التباديل متساوية الاحتمال. وذلك لأنه لو كان أي توزيع آخر هو الأصعب، فإن حساب متوسطه مع جميع تباديل نفس التوزيع الصعب سيكون بنفس الصعوبة، وسينتج عنه توزيع التباديل العشوائية. يُوسّع مبدأ ياو الحدود الدنيا لعدد المقارنات في الحالة المتوسطة التي تُجريها الخوارزميات الحتمية، للتباديل العشوائية، ليشمل تحليل أسوأ الحالات لخوارزميات المقارنة العشوائية. من بين الأمثلة التي قدمها ياو تحليل خوارزميات إيجاد أكبر عنصر k من مجموعة n من القيم المُعطاة. أثبت العالمان والتر كونتو وإيان مونرو لاحقًا، وبناءً على عمل ياو، أنه بالنسبة للتباديل العشوائية، يجب على أي خوارزمية حتمية أن تُجري على الأقل عددًا متوقّعًا من المُقارنات يُساوي:

n+\min(k,n-k)-O(1)

ويجب على الخوارزميات العشوائية، تبعًا لمبدأ ياو، إجراء نفس عدد المقارنات على أسوأ حالة إدخال لها. وتأتي خوارزمية فلويد-ريفست ضمنO(\sqrt{n\log n}) عددًا من المقارنات من هذا الحد.

## مراجع

تصنيف:خوارزميات
تصنيف:علوم الحاسب
تصنيف:نظرية الألعاب
تصنيف:نظرية التعقيد الحسابي