خوارزمية التعداد

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

مشكلة تعداد${\displaystyle P}$يُعرَّف بأنه علاقة${\displaystyle R}$على سلاسل من أبجدية عشوائية${\displaystyle \Sigma }$:

${\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}$

تقوم خوارزمية بحل${\displaystyle P}$إذا كان لكل مدخل${\displaystyle x}$تنتج الخوارزمية سلسلة (قد تكون لانهائية)${\displaystyle y}$بحيث${\displaystyle y}$لا يوجد له نسخة مكررة و${\displaystyle z\in y}$إذا وفقط إذا${\displaystyle (x,z)\in R}$يجب أن تتوقف الخوارزمية إذا كان التسلسل${\displaystyle y}$محدود.

تمت دراسة مشاكل التعداد في سياق نظرية التعقيد الحسابي ، وتم تقديم العديد من فئات التعقيد لمثل هذه المشاكل.

تُعدّ فئة EnumP مثالًا عامًا جدًا على هذه الفئات ، ^{[ 1 ]} وهي فئة المسائل التي يُمكن التحقق من صحة مخرجاتها المحتملة في وقت متعدد الحدود بالنسبة للمدخلات والمخرجات. بصورة رسمية، بالنسبة لهذه المسألة، يجب أن توجد خوارزمية A تأخذ كمدخلات المسألة x ، والمخرجات المرشحة y ، وتحلّ مسألة القرار بشأن ما إذا كانت y مخرجات صحيحة للمدخل x ، في وقت متعدد الحدود بالنسبة لـ x و y . على سبيل المثال، تحتوي هذه الفئة على جميع المسائل التي تُعادل تعداد شهود مسألة في فئة NP .

تتضمن الفئات الأخرى التي تم تعريفها ما يلي. في حالة المسائل الموجودة أيضًا في EnumP ، يتم ترتيب هذه المسائل من الأقل تحديدًا إلى الأكثر تحديدًا:

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

• التراجع : أبسط طريقة لحصر جميع الحلول هي استكشاف فضاء النتائج الممكنة بشكل منهجي ( تقسيمه في كل خطوة متتالية). ^{[ 2 ]} مع ذلك، قد لا يضمن هذا الأسلوب تقليل التأخير بشكل كافٍ، أي أن خوارزمية التراجع قد تستغرق وقتًا طويلاً في استكشاف أجزاء من فضاء النتائج الممكنة التي لا تُفضي إلى حل كامل.
• بحث المصباح اليدوي : تُحسّن هذه التقنية من أسلوب التراجع من خلال استكشاف فضاء جميع الحلول الممكنة، مع حلّ مشكلة إمكانية توسيع الحل الجزئي الحالي إلى حل جزئي آخر في كل خطوة. ^{[ 1 ]} إذا كانت الإجابة بالنفي، يمكن للخوارزمية التراجع فورًا وتجنب إهدار الوقت، مما يُسهّل إثبات ضمانات التأخير بين أي حلين كاملين. وتُطبّق هذه التقنية بشكل خاص على المسائلذاتية الاختزال.
• الانغلاق في عمليات المجموعات : إذا أردنا تعداد اتحاد مجموعتين منفصلتين، فيمكننا حل المشكلة بتعداد المجموعة الأولى ثم الثانية. إذا كان الاتحاد غير منفصل، ولكن يمكن تعداد المجموعتين بترتيب تصاعدي ، فيمكن إجراء التعداد بالتوازي على كلتا المجموعتين مع حذف التكرارات أثناء العملية. أما إذا كان الاتحاد غير منفصل، ولم تكن المجموعتان مرتبتين، فيمكن حذف التكرارات على حساب زيادة استهلاك الذاكرة، مثلاً باستخدام جدول تجزئة . وبالمثل، يمكن تعداد حاصل الضرب الديكارتي لمجموعتين بكفاءة عن طريق تعداد مجموعة واحدة وضم كل نتيجة إلى جميع النتائج التي تم الحصول عليها عند تعداد المجموعة الثانية.

• مشكلة تعداد الرؤوس ، حيث يتم إعطاؤنا متعدد السطوح الموصوف كنظام من المتباينات الخطية ويجب علينا تعداد رؤوس متعدد السطوح.
• حصر أصغر المستعرضات في الرسم البياني الفائق . ترتبط هذه المسألة بالازدواجية الرتيبة وتتصل بالعديد من التطبيقات في نظرية قواعد البيانات ونظرية الرسوم البيانية . ^{[ 3 ]}
• حصر إجابات استعلام قاعدة البيانات ، على سبيل المثال استعلام اقتراني أو استعلام مُعبَّر عنه بصيغة أحادية من الدرجة الثانية . وقد وُجدت في نظرية قواعد البيانات توصيفاتٌ للاستعلامات الاقترانية التي يمكن حصرها باستخدام معالجة مسبقة خطية وتأخير ثابت . ^{[ 4 ]}
• مشكلة تعداد الزمر القصوى في رسم بياني مُدخل، على سبيل المثال، باستخدام خوارزمية برون-كيربوش
• سرد جميع عناصر الهياكل مثل الماترويدات والجريدويدات
• تتضمن العديد من المسائل المتعلقة بالرسوم البيانية، على سبيل المثال، تعداد المجموعات المستقلة ، والمسارات ، والقطع ، وما إلى ذلك.
• تعداد التعيينات المرضية لتمثيلات الدوال المنطقية ، على سبيل المثال، صيغة منطقية مكتوبة في الشكل الطبيعي الاقتراني أو الشكل الطبيعي الانفصالي ، أو مخطط قرار ثنائي مثل OBDD ، أو دائرة منطقية في فئات مقيدة تمت دراستها في تجميع المعرفة ، على سبيل المثال، NNF . ^{[ 5 ]}

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