مستخرج (رياضيات)

أن${\displaystyle (N,M,D,K,\epsilon )}$- المستخرج عبارة عن رسم بياني ثنائي الأجزاء مع${\displaystyle N}$العقد على اليسار و${\displaystyle M}$العقد على اليمين بحيث يكون لكل عقدة على اليسار${\displaystyle D}$الجيران (على اليمين)، والتي تتميز بخاصية إضافية وهي أنه لأي مجموعة جزئية${\displaystyle A}$من الرؤوس اليسرى بحجم لا يقل عن${\displaystyle K}$، التوزيع على الرؤوس اليمنى الذي تم الحصول عليه عن طريق اختيار عقدة عشوائية في${\displaystyle A}$ثم اتباع حافة عشوائية للحصول على عقدة x على الجانب الأيمن هو${\displaystyle \epsilon }$- قريب من التوزيع المنتظم من حيث مسافة التباين الكلي .

المُشتِّت هو رسم بياني ذو صلة .

يمكن النظر إلى المستخرج بطريقة مكافئة باعتباره دالة ثنائية المتغيرات

${\displaystyle E:[N]\times [D]\rightarrow [M]}$

بالطريقة الطبيعية. ومن هذا المنظور، يتضح أن خاصية المستخرج تعادل: لأي مصدر للعشوائية${\displaystyle X}$وهذا يعطي${\displaystyle n}$بتات ذات إنتروبيا دنيا${\displaystyle \log K}$، التوزيع${\displaystyle E(X,U_{D})}$يكون${\displaystyle \epsilon }$-قريب من${\displaystyle U_{M}}$، أين${\displaystyle U_{T}}$يشير إلى التوزيع المنتظم على${\displaystyle [T]}$.

تُعدّ المستخلصات مثيرة للاهتمام عندما يمكن بناؤها باستخدام مكونات صغيرة.${\displaystyle K,D,\epsilon }$بالنسبة إلى${\displaystyle N}$و${\displaystyle M}$أقرب ما يكون إلى${\displaystyle KD}$(العشوائية الكلية في مصادر الإدخال) قدر الإمكان.

تم البحث في دوال الاستخراج في الأصل كوسيلة لاستخراج العشوائية من مصادر عشوائية ضعيفة. انظر مستخرج العشوائية .

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

• رونين شالتيل، التطورات الحديثة في أجهزة الاستخراج - دراسة استقصائية