التبلور

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

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

من الأمثلة الشائعة لخوارزمية التمركز حول النواة، تمركز مسألة تغطية الرؤوس التي وضعها س. بوس حول النواة. ^{[ 1 ]} في هذه المسألة، يكون المدخل عبارة عن رسم بياني غير موجه.${\displaystyle G}$بالإضافة إلى عدد${\displaystyle k}$الناتج عبارة عن مجموعة من العناصر على الأكثر${\displaystyle k}$تُحدد هذه المجموعة الرؤوس التي تتضمن نقطة نهاية لكل حافة في الرسم البياني، إن وُجدت، أو تُصدر استثناءً في حال عدم وجودها. تُصنف هذه المسألة ضمن المسائل الصعبة حسابيًا (NP-hard) . مع ذلك، يمكن استخدام قواعد الاختزال التالية لتبسيطها:

1. لو${\displaystyle k>0}$و${\displaystyle v}$هو رأس من درجة أكبر من${\displaystyle k}$، يزيل${\displaystyle v}$من الرسم البياني وانخفاض${\displaystyle k}$واحداً تلو الآخر. كل غطاء رأس بحجم${\displaystyle k}$يجب أن يحتوي على${\displaystyle v}$لأنه بخلاف ذلك، سيتطلب الأمر اختيار عدد كبير جدًا من جيرانها لتغطية الحواف المتصلة. وبالتالي، يمكن تكوين غطاء رؤوس مثالي للرسم البياني الأصلي من غطاء للمسألة المختزلة عن طريق إضافة${\displaystyle v}$العودة إلى الغلاف.
2. لو${\displaystyle v}$إذا كان رأسًا معزولًا، فقم بإزالته. لا يمكن للرأس المعزول أن يغطي أي حواف، لذلك في هذه الحالة${\displaystyle v}$لا يمكن أن يكون جزءًا من أي تغطية تأمينية دنيا.
3. إذا كان أكثر من${\displaystyle k^{2}}$إذا بقيت الحواف في الرسم البياني، ولم يكن بالإمكان تطبيق أي من القاعدتين السابقتين، فلا يمكن أن يحتوي الرسم البياني على غطاء رأس بحجم${\displaystyle k}$لأنه بعد حذف جميع الرؤوس ذات الدرجة الأكبر من${\displaystyle k}$، لا يمكن لكل رأس متبقٍ أن يغطي أكثر من${\displaystyle k}$حواف ومجموعة من${\displaystyle k}$لا يمكن أن تغطي الرؤوس إلا على الأكثر${\displaystyle k^{2}}$الحواف. في هذه الحالة، يمكن استبدال المثال بمثال له رأسان وحافة واحدة، و${\displaystyle k=0}$والتي ليس لها حل أيضاً.

إن الخوارزمية التي تطبق هذه القواعد بشكل متكرر حتى يتعذر إجراء المزيد من الاختزالات تنتهي بالضرورة بنواة تحتوي على أكثر من${\displaystyle k^{2}}$الحواف (ولأن كل حافة لها نقطتا نهاية على الأكثر ولا توجد رؤوس معزولة) على الأكثر${\displaystyle 2k^{2}}$الرؤوس. يمكن تنفيذ هذه العملية في زمن خطي . بمجرد إنشاء النواة، يمكن حل مشكلة تغطية الرؤوس باستخدام خوارزمية بحث شاملة تختبر ما إذا كانت كل مجموعة فرعية من النواة تمثل غطاءً لها. وبالتالي، يمكن حل مشكلة تغطية الرؤوس في زمن خطي.${\displaystyle O(2^{2k^{2}}+n+m)}$بالنسبة للرسم البياني مع${\displaystyle n}$الرؤوس و${\displaystyle m}$الحواف، مما يسمح بحلها بكفاءة عندما${\displaystyle k}$صغير حتى لو${\displaystyle n}$و${\displaystyle m}$كلاهما كبيران.

على الرغم من أن هذا الحد قابل للمعالجة باستخدام معلمات ثابتة، إلا أن اعتماده على هذه المعلمات أعلى من المطلوب. يمكن لأساليب التجزئة الأكثر تعقيدًا تحسين هذا الحد، من خلال إيجاد نوى أصغر، على حساب زيادة وقت التشغيل في خطوة التجزئة. في مثال تغطية الرؤوس، من المعروف أن خوارزميات التجزئة تُنتج نوى ذات حد أقصى لا يتجاوز${\displaystyle 2k}$الرؤوس. تستغل إحدى الخوارزميات التي تحقق هذا الحد المحسن خاصية التكامل النصفي لتخفيف البرنامج الخطي لتغطية الرؤوس، والتي تعود إلى نيمهاوزر وتروتر. ^{[ 2 ]} تعتمد خوارزمية أخرى للتجزئة إلى نواة، تحقق هذا الحد، على ما يُعرف بقاعدة اختزال التاج، وتستخدم وسائط المسار المتناوب . ^{[ 3 ]} أما خوارزمية التجزئة إلى نواة الأكثر شهرة حاليًا من حيث عدد الرؤوس، فهي من ابتكار لامبيس (2011)، وتحقق${\displaystyle 2k-c\log k}$الرؤوس لأي ثابت ثابت${\displaystyle c}$.

لا يمكن، في هذه المسألة، إيجاد نواة بحجم${\displaystyle O(\log k)}$ما لم يكن P = NP ، فإن استخدام نواة كهذه سيؤدي إلى خوارزمية ذات زمن متعدد الحدود لحل مشكلة تغطية الرؤوس الصعبة من فئة NP. ومع ذلك، يمكن إثبات حدود أقوى بكثير على حجم النواة في هذه الحالة: ما لم يكن coNP${\displaystyle \subseteq }$NP/poly (يعتقد علماء نظرية التعقيد أنه غير مرجح )، لكل${\displaystyle \epsilon >0}$من المستحيل في وقت متعدد الحدود إيجاد النوى مع${\displaystyle O(k^{2-\epsilon })}$الحواف. ^{[ 4 ]} من غير المعروف بالنسبة لتغطية الرؤوس ما إذا كانت النوى ذات${\displaystyle (2-\epsilon )k}$رؤوس لبعض${\displaystyle \epsilon >0}$لن يكون لها أي عواقب غير محتملة في نظرية التعقيد.

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

تكون المشكلة قابلة للحل باستخدام معلمات ثابتة إذا وفقط إذا كانت قابلة للتجزئة وقابلة للتقرير .

يمكن ملاحظة أن المسألة القابلة للتجزئة والتقرير هي مسألة قابلة للحل باستخدام معلمات ثابتة من التعريف أعلاه: أولاً، خوارزمية التجزئة، التي تعمل في وقت${\displaystyle O(|x|^{c})}$يتم استدعاء الدالة لبعض قيم c لإنشاء نواة بحجم${\displaystyle f(k)}$ثم يتم حل النواة بواسطة الخوارزمية التي تثبت أن المسألة قابلة للتقرير. إجمالي وقت تشغيل هذه العملية هو${\displaystyle g(f(k))+O(|x|^{c})}$، أين${\displaystyle g(n)}$يمثل زمن تشغيل الخوارزمية المستخدمة لحل النوى.${\displaystyle g(f(k))}$يمكن حسابها، على سبيل المثال باستخدام الافتراض التالي:${\displaystyle f(k)}$قابلة للحساب وتختبر جميع المدخلات الممكنة ذات الطول${\displaystyle f(k)}$وهذا يعني أن المشكلة قابلة للحل باستخدام معلمات ثابتة.

أما الاتجاه الآخر، وهو أن المسألة القابلة للحل ذات المعاملات الثابتة قابلة للتجزئة والتقرير، فهو أكثر تعقيدًا بعض الشيء. لنفترض أن المسألة غير تافهة، أي أن هناك حالة واحدة على الأقل موجودة في اللغة، تُسمى${\displaystyle I_{yes}}$ومثال واحد على الأقل غير موجود في اللغة، يُسمى${\displaystyle I_{no}}$وإلا، فإن استبدال أي مثال بسلسلة فارغة يُعدّ تحويلًا صحيحًا إلى نواة. افترض أيضًا أن المشكلة قابلة للحل باستخدام معلمات ثابتة، أي أن لها خوارزمية تعمل في زمن لا يتجاوز${\displaystyle f(k)\cdot |x|^{c}}$خطوات على الحالات${\displaystyle (x,k)}$، لبعض الثوابت${\displaystyle c}$وبعض الوظائف${\displaystyle f(k)}$لتحويل المدخلات إلى نواة، قم بتشغيل هذه الخوارزمية على المدخلات المعطاة لمدة لا تتجاوز${\displaystyle |x|^{c+1}}$الخطوات. إذا انتهت العملية بإجابة، فاستخدم تلك الإجابة لتحديد أحد الخيارين${\displaystyle I_{yes}}$أو${\displaystyle I_{no}}$كما هو الحال في النواة. أما إذا تجاوزت،${\displaystyle |x|^{c+1}}$حدد عدد الخطوات دون إنهاء العملية، ثم أعد${\displaystyle (x,k)}$نفسها كنواة. لأن${\displaystyle (x,k)}$لا يتم إرجاعها كنواة إلا للمدخلات التي تحتوي على${\displaystyle f(k)\cdot |x|^{c}>|x|^{c+1}}$وبالتالي، فإن حجم النواة المنتجة بهذه الطريقة هو على الأكثر${\displaystyle \max\{|I_{yes}|,|I_{no}|,f(k)\}}$يمكن حساب هذا الحد الأقصى للحجم، بافتراض قابلية المعالجة ذات المعلمات الثابتة أن${\displaystyle f(k)}$قابل للحساب.

• تغطية الرؤوس المُعَلمة بحجم تغطية الرؤوس: تحتوي مسألة تغطية الرؤوس على نوى ذات حجم لا يتجاوز${\displaystyle 2k}$الرؤوس و${\displaystyle O(k^{2})}$الحواف. ^{[ 5 ]} علاوة على ذلك، لأي${\displaystyle \varepsilon >0}$، لا يحتوي غطاء الرأس على نوى مع${\displaystyle O(k^{2-\varepsilon })}$الحواف ما لم${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$[ ^{4 ] مسائل تغطية} الرؤوس في${\displaystyle d}$تحتوي الرسوم البيانية الفائقة المنتظمة على نوى مع${\displaystyle O(k^{d})}$حواف باستخدام لِمّا عباد الشمس ، ولا تحتوي على نوى بحجم${\displaystyle O(k^{d-\varepsilon })}$إلا إذا${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$[ ^{4 ]​}
• مجموعة رؤوس التغذية الراجعة المُعَلمة بحجم مجموعة رؤوس التغذية الراجعة: تحتوي مشكلة مجموعة رؤوس التغذية الراجعة على نوى مع${\displaystyle 4k^{2}}$الرؤوس و${\displaystyle O(k^{2})}$الحواف. ^{[ 6 ]} علاوة على ذلك، لا تحتوي على نوى ذات${\displaystyle O(k^{2-\varepsilon })}$الحواف ما لم${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$[ ^{4 ]​}
• ${\displaystyle k}$-المسار: الـ${\displaystyle k}$تتمثل مشكلة المسار في تحديد ما إذا كان الرسم البياني المعطى يحتوي على مسار بطول لا يقل عن${\displaystyle k}$تحتوي هذه المسألة على نوى ذات حجم أسي في${\displaystyle k}$ولا تحتوي على نوى ذات حجم متعدد الحدود في${\displaystyle k}$إلا إذا${\displaystyle {\text{coNP}}\subseteq {\text{NP/poly}}}$[ ^{7 ]​}
• المسائل ثنائية الأبعاد: تحتوي العديد من النسخ المعلمة للمسائل ثنائية الأبعاد على نوى خطية على الرسوم البيانية المستوية، وبشكل أكثر عمومية، على الرسوم البيانية باستثناء رسم بياني ثابت كجزيء صغير . ^{[ 8 ]}

بينما المعلمة${\displaystyle k}$في الأمثلة السابقة، تم اختيار حجم الحل المطلوب، وهذا ليس شرطًا. من الممكن أيضًا اختيار مقياس التعقيد الهيكلي للمدخلات كقيمة للمعامل، مما يؤدي إلى ما يُسمى بالمعاملات الهيكلية. يُعد هذا النهج مفيدًا للحالات التي يكون فيها حجم الحل كبيرًا، ولكن يكون فيها مقياس تعقيد آخر محدودًا. على سبيل المثال، عدد رؤوس التغذية الراجعة في رسم بياني غير موجه.${\displaystyle G}$يُعرَّف بأنه الحد الأدنى لعدد رؤوس مجموعة الرؤوس التي يؤدي حذفها إلى${\displaystyle G}$غير دوري. مسألة تغطية الرؤوس، المُعَلمة بعدد رؤوس التغذية الراجعة للرسم البياني المُدخل، لها نواة متعددة الحدود: ^{[ 9 ]} توجد خوارزمية زمنية متعددة الحدود، تُعطى رسمًا بيانيًا${\displaystyle G}$رقم رأس التغذية الراجعة الخاص به هو${\displaystyle k}$، يُخرج رسمًا بيانيًا${\displaystyle G'}$على${\displaystyle O(k^{3})}$الرؤوس التي تشكل غطاءً أدنى للرؤوس في${\displaystyle G'}$يمكن تحويلها إلى غطاء رأسي أدنى لـ${\displaystyle G}$في وقت متعدد الحدود. وبالتالي، تضمن خوارزمية النواة أن الحالات ذات عدد رؤوس التغذية الراجعة الصغير${\displaystyle k}$يتم اختزالها إلى حالات صغيرة.

• الضغط التكراري ، تقنية تصميم مختلفة للخوارزميات القابلة للمعالجة ذات المعلمات الثابتة
• في مسائل التحسين ، قد تفقد النواة عاملاً معيناً في جودة الحل.

• أبو خزام، فيصل ن.؛ كولينز، ريبيكا ل.؛ فيلوز، مايكل ر .؛ لانغستون، مايكل أ .؛ سوترز، دبليو. هنري؛ سيمونز، كريس ت. (2004)، خوارزميات النواة لمسألة تغطية الرؤوس: النظرية والتجارب (ملف PDF) ، جامعة تينيسي.
• بودليندر، هانز ل .؛ داوني، رود ج .؛ فيلوز، مايكل ر .؛ هيرملين، داني (2009)، "حول المسائل التي لا تحتوي على نواة متعددة الحدود"، مجلة علوم الحاسوب والأنظمة ، 75 (8): 423-434 ، doi : 10.1016/j.jcss.2009.04.001.
• بوس، جوناثان ف.؛ جولدسميث، جودي (1993)، "اللا حتمية في${\displaystyle P^{*}}$، مجلة SIAM للحوسبة ، 22 (3): 560-572 ، doi : 10.1137/0222038 ، S2CID 43081484 .
• تشن، جيانر. كنج، إياد أ.؛ جيا، ويجيا (2001)، “غطاء قمة الرأس: مزيد من الملاحظات والمزيد من التحسينات” ، مجلة الخوارزميات ، 41 (2): 280–301 ، دوى : 10.1006/jagm.2001.1186 ، S2CID 13557005 .
• ديل، هولجر؛ فان ميلكبيك، ديتر (2010)، "لا تسمح قابلية الإرضاء بأي تبسيط غير تافه إلا إذا انهار التسلسل الهرمي ذو الوقت متعدد الحدود" (ملف PDF) ، وقائع الندوة الثانية والأربعين لجمعية الحوسبة الآلية حول نظرية الحوسبة (STOC 2010) (ملف PDF) ، الصفحات 251-260 ، doi : 10.1145/1806689.1806725 ، ISBN  978-1-4503-0050-6، S2CID 1117711 .
• داوني، آر جي ؛ فيلوز، إم آر (1999)، التعقيد المُعَلم ، سلسلة دراسات في علوم الحاسوب، سبرينغر، doi : 10.1007/978-1-4612-0515-9 ، ISBN 0-387-94883-X، MR 1656112 ، S2CID 15271852  .
• فلوم، يورغ. جروهي ، مارتن (2006)، نظرية التعقيد ذات المعلمات ، سبرينغر، ISBN 978-3-540-29952-3تم الاطلاع عليه بتاريخ 2010-03-05.
• فومين، فيدور ف.؛ لوكشتانوف، دانيال؛ سوراب، ساكيت؛ ثيليكوس، ديميتريوس م. (2010)، "الثنائية الأبعاد والنوى"، وقائع الندوة الحادية والعشرين لجمعية آلات الحوسبة والجمعية الصناعية للرياضيات التطبيقية حول الخوارزميات المنفصلة (SODA 2010) ، الصفحات 503-510 .
• يانسن، بارت إم بي؛ بودليندر، هانز إل. (2013)، "إعادة النظر في تجزئة غطاء الرؤوس - حدود عليا وسفلى لمعامل مُحسَّن"، نظرية أنظمة الحوسبة ، 53 (2): 263-299 ، arXiv : 1012.4701 ، doi : 10.1007/s00224-012-9393-4،
• لامبيس، مايكل (2011)، "نواة من الرتبة 2k − c log k لتغطية الرؤوس"، رسائل معالجة المعلومات ، 111 ( 23-24 ): 1089-1091 ، doi : 10.1016/j.ipl.2011.09.003    .
• توماسيه، ستيفان (2010)، " نواة 4k2 لمجموعة رؤوس التغذية الراجعة"، ^{معاملات} ACM في الخوارزميات ، 6 (2): 1-8 ، doi : 10.1145/1721837.1721848 ، S2CID 7510317 .
• نيدرماير، رولف (2006)، دعوة إلى خوارزميات المعلمات الثابتة ، مطبعة جامعة أكسفورد، CiteSeerX 10.1.1.2.9618 ، ISBN  0-19-856607-7تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 24 سبتمبر 2008 ، وتمت معاينته بتاريخ 1 يونيو 2017..

• فومين، فيدور ف.؛ لوكشتانوف، دانيال؛ سوراب، ساكيت؛ زهافي، ميراف (2019)، التكوينل: نظرية المعالجة المسبقة المُعَلمة ، مطبعة جامعة كامبريدج، ص  528، doi : 10.1017/9781107415157 ، ISBN 978-1107057760
• نيدرماير، رولف (2006)، دعوة إلى خوارزميات المعلمات الثابتة ، مطبعة جامعة أكسفورد، الفصل 7، ISBN 0-19-856607-7تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 29 سبتمبر 2007 ، وتمت معاينته بتاريخ 1 يونيو 2017.
• سيجان، ماريك؛ فومين، فيدور الخامس؛ كواليك، لوكاش؛ لوكشتانوف، دانيال؛ ماركس، دانيال؛ بيليبتشوك، مارسين؛ بيليبتشوك، ميشال؛ سوراب، ساكيت (2015)، الخوارزميات ذات المعلمات ، سبرينغر، الفصلان 2 و 9، ISBN 978-3-319-21274-6