التفكير الخوارزمي

اختبار ورقة دَوَّار الشمس

كمدخل لهذا المجال، لنتأمل «اختبار ورقة دَوَّار الشمس» الذي هو من أولى التجارب التي ينفِّذها الطالب في مادة الكيمياء بالمرحلة الثانوية.

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

هذا «إجراء تقريري» يتعلَّمه الطلاب في المراحل المبكِّرة جدًّا من دراستهم لمادة الكيمياء، ويمكن وصفه بالطريقة التالية:

لاحظ أن منفِّذ التجربة ليس بحاجة إلى معرفة أي شيء عن سبب عمل اختبار ورقة دَوَّار الشمس بالطريقة يعمل بها. هو ليس بحاجة إلى معرفة ماهية «ورقة دَوَّار الشمس» — أي تركيبتها الكيميائية — ولا العملية الكيميائية التي تتسبَّب في تغيير لون الورقة. لتنفيذ التجربة، يكفي تمامًا أن يتعرَّف منفِّذ التجربة على ورقة دَوَّار الشمس عند رؤيتها، وأن يمكنه ربط تغيُّر لون الورقة بالأحماض أو القلويات.

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

هذه الخصائص المجمَّعة لاختبار ورقة دَوَّار الشمس — الذي هو إجراء آلي مضمون أنه سيعطي نتيجة صحيحة في مدة زمنية محددة — هي العناصر الأساسية التي تميِّز الخوارزميات.

متى يكون الإجراء خوارزمية؟

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

«المضي قُدُمًا وأداء عملية الضرب»

يرتبط مفهوم «التجريد» بمواصفات الخوارزميات. بعبارة أخرى، يمكن حل مسائل معينة باستخدام خوارزميات محددة على مستويين مختلفين أو أكثر من مستويات التجريد.

قبل اختراع حاسبات الجيب، كان الأطفال يتعلمون مسائل الضرب باستخدام الورقة والقلم. وما يلي هو ما تعلمته في صغري. ولأغراض التبسيط، لنفترض أن عددًا مكوَّنًا من ثلاثة أرقام (المضروب) يُضرب في عدد مكوَّن من رقمين (المضروب فيه).

لاحظ أن تنفيذ هذا الإجراء يتطلب أن يكون لدى الطفل بعض المعرفة المسبقة: أولًا، يجب أن يعرف طريقة ضرْب عدد مكوَّن من عدة أرقام في عدد مكوَّن من رقم واحد. ينطوي هذا على ضرورة حفظ جدول الضرب لعددين يتكوَّن كلٌّ منهما من رقم واحد، أو إمكانية الوصول إلى جدول الضرب. ثانيًا، لا بد أن يعرف طريقة جمع الأعداد المكوَّنة من رقمين أو أكثر، ويجب أن يعرف طريقة التعامل مع مسائل الجمع بالحمل. ثالثًا، يجب أن يعرف طريقة جمع عددين مكوَّنين من عدة أرقام.

لكن لاحظ دقة الخطوات. فما دام يتَّبع الشخص هذه الخطوات بالضبط كما هو مذكور، فسيكفل ذلك نجاحَ الإجراء بشرط توافر الشرطين الأول والثاني المذكورين فيما سبق في الشخص الذي ينفِّذ هذا الإجراء. من المؤَّكد أن ينتج عن هذه الخطوات النتيجة المطلوبة في مدة زمنية محدودة: وهذا من السمات الأساسية في الخوارزمية.

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

مستويات التجريد في هذا المثال تنطوي أيضًا على مستويات من «الجهل». فالطفل الذي يستخدم خوارزمية الورقة والقلم يعرف معلومات عن عملية الضرب أكثرَ من الشخص الذي يستخدم حاسبة الجيب.

ثبات الخوارزميات

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

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

الخوارزميات أدوات مجردة

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

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

الخوارزمية أداة مساعدة. وكما هو الحال مع معظم الأدوات المساعدة، كلما قل احتياج المستخدِم إلى معرفة المفاهيم النظرية في الخوارزمية، زادت فاعليتها بالنسبة إليه.

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

الخوارزميات معرفة «إجرائية»

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

في العلوم الطبيعية، نتعلم التعريفات والحقائق والنظريات والقوانين وغير ذلك. وفيما يلي بعض الأمثلة من مبادئ الفيزياء والكيمياء.

وفيما يلي مثال على المعرفة التقريرية في الرياضيات عن طريق التعريف:

على الجانب الآخر، لا تُعدُّ الخوارزمية تقريرية؛ بل هي إجراء يوضح كيفية إنجاز شيءٍ ما. إنها تصف عملًا من نوعٍ ما. وعليه، فإن الخوارزمية مثال على «المعرفة الإجرائية»، أو بالمعنى الدارج المعرفة «العملية».

وبالنسبة إلى عالِم الكمبيوتر، لا يكفيه أن يعرف أن مضروب العدد يُعرَّف بكذا وكذا. فهو يريد أن يعرف طريقةَ حساب مضروب عددٍ ما. بعبارة أخرى، هو بحاجة إلى خوارزمية. على سبيل المثال:

لاحظ أنه يمكن تقديم المفهوم ذاته — المضروب — بطريقة تقريرية (كما يفضِّل علماء الرياضيات) وبطريقة إجرائية (كما يحب علماء الكمبيوتر). في الحقيقة، يطرح الشكل التقريري «النظرية» الأساسية («ما المضروب؟») للشكل الإجرائي أو الخوارزمية («كيف نحسب المضروب؟»).

باختصار، تعبِّر الخوارزميات عن شكلٍ من أشكال المعرفة الإجرائية التي تتسم بالموضوعية أيضًا.

تصميم الخوارزميات

الكلمة المهمة في هذا المقام هي «إنشاء». إن عملية التصميم عملٌ إبداعي، وكما أوضح الباحثون في مجال الإبداع، فالعمل الإبداعي مزيجٌ معقَّد من الإدراك والمنطق والحَدْس والمعرفة وحسن التقدير والدهاء والاكتشافات التي تتم مصادفة. ومع ذلك يتحدَّث واضعو نظريات التصميم عن «علم التصميم» أو «منطق التصميم».

فهل يوجد إذن جانبٌ علمي في تصميم الخوارزميات؟ الإجابة هي: «إلى حدٍّ ما». توجد ثلاثة أوجه أساسية يدخل بها «المنهج العلمي» في تصميم الخوارزميات.

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

بعبارة أخرى، قد يكون لأشكال التفكير المختلفة تأثيرٌ في تصميم الخوارزمية بناءً على كمٍّ من المعرفة المقرَّرة أو المجرَّبة أو المثبَتة (والتي تكون تقريرية وإجرائية على حد سواء). سنطلق على ذلك اسم «عامل المعرفة» في تصميم الخوارزمية.

لكن مجرد التوصُّل إلى الخوارزمية ليس كافيًا. فهناك أيضًا ضرورة إقناع النفس والآخرين بأن الخوارزمية «صالحة». وتنطوي هذه الضرورة على اتباع التفكير المنهجي في توضيح أن الخوارزمية تستوفي المتطلبات الأصلية. سأطلق على ذلك اسم «عامل الصلاحية» في تصميم الخوارزميات.

وأخيرًا، وحتى لو ثبَت أن الخوارزمية صالحة، فربما لا يكون هذا كافيًا. فثمَّة مسألة أداء الخوارزمية: ما مدى كفاءة الخوارزمية؟ وسنطلق على ذلك اسم «عامل الأداء» في تصميم الخوارزمية.

تنطوي هذه «العوامل» الثلاثة على أنواع التفكير والمنطق وقواعد البرهان التي نربطها عادةً بالعلم. فلنتناول بشيء من الأمثلة كيفيةَ إسهامها في علم تصميم الخوارزميات.

مشكلة تحويل التعبيرات الحسابية

توجد فئةٌ من برامج الكمبيوتر تسمَّى «البرامج المترجِمة» ووظيفتها تحويل البرنامج المكتوب بلغة برمجة عالية المستوى (وهي لغة تكون مستقلة عن سمات أجهزة الكمبيوتر المادية الفعلية، مثل لغة فورتران أو سي++) إلى سلسلة تعليمات يمكن لأجهزة كمبيوتر مادية خاصة تنفيذها (تفسيرها) مباشرةً. ويطلق على سلسلة التعليمات الخاصة بالآلة اسم «لغة الآلة». (سنتناول لغات البرمجة في الفصل الرابع.)

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

على الجانب الآخر، إذا كان التعبير خاليًا من الأقواس كما يلي:

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

وثمَّة ترميزٌ لتحديد التعبيرات الحسابية من دون الحاجة إلى الأقواس من ابتكار عالِم المنطق البولندي يان ووكاسيفيتش (١٨٧٨–١٩٥٦)، ومن ثَم أصبح معروفًا باسم «الترميز البولندي». يطلق على إحدى صيغ هذا الترميز «الصيغة البولندية العكسية»، وفيها يأتي العامل الحسابي بعد المعاملَين مباشرةً في صورة تعبير بولندي عكسي. توضح الأمثلة التالية الصيغةَ البولندية العكسية لبعض التعبيرات المرتَّبة وسطيًّا.

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

الصيغة البولندية العكسية هي:

بالطبع سيكتب المبرمجون التعبيرات الحسابية بالصيغة المرتبة وسطيًّا المعتادة. وسينفذ البرنامج المترجِم خوارزمية ستحوِّل تلك الصيغ إلى صيغة بولندية عكسية أولًا، ثم يولِّد لغة آلة من التعبيرات البولندية العكسية.

مسألة تحويل التعبيرات من الصيغة المرتبة وسطيًّا إلى الصيغة البولندية العكسية توضِّح مدى إمكانية اجتماع أساس نظري سليم واستراتيجية تصميم مجربة أثناء تصميم خوارزمية يمكن إثبات صحتها.

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

لتوضيح كيف تعمل الخوارزمية مع المدخلات الفعلية، انظر الأمثلة التالية:

كفاءة الخوارزميات باعتبارها أدوات نفعية

قلنا سابقًا إن الأمر لا يقتصر على تصميم خوارزمية صحيحة. وكما هو الحال مع مصمم أي أداة نفعية، يجب أن يهتم مصمم الخوارزمية بمدى «كفاءة» هذه الخوارزمية؛ أي، مدى فاعليتها في القيام بمهامها. فهل يمكننا «قياس» كفاءة الخوارزمية بناءً على هذا المعنى؟ هل يمكننا عملُ مقارنة نوعية بشكلٍ ما بين خوارزميتين متنافستين تؤديان المهمة ذاتها؟

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

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

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

جماليات الخوارزميات

التجربة الجمالية — البحث عن الجمال — لا توجد في الفن والموسيقى والسينما والأدب فحسب، بل توجد في العلوم والرياضيات وحتى التكنولوجيا. استهل الشاعر جون كيتس الأبيات الأخيرة من قصيدة «قصيدة على جَرة إغريقية» التي كتبها عام ١٨٢٠ بقوله: «الجمال هو الحقيقة، والحقيقة هي الجمال». وقد رفض عالِم الرياضيات الإنجليزي جي إتش هاردي — محاكيًا كيتس — فكرةَ وجود «رياضيات قبيحة» رفضًا تامًّا.

تأمَّل لماذا يسعى علماء الرياضيات إلى إيجاد براهين مختلفة لمبرهنة بعينها. بمجرد أن يتوصَّل عالمٌ إلى برهان على مبرهنة، لماذا يكلِّف عالِم آخر نفسه عناءَ إيجاد برهان آخر مختلف؟ تكمُن الإجابة في أن علماء الرياضيات يبحثون عن براهينَ جديدة على المبرهنات حينما تكون البراهين الحالية غير جذابة من المنظور الجمالي. إنهم يبحثون عن الجمال في الرياضيات.

ينطبق الأمر بالقدْر نفسه على تصميم الخوارزميات. قد يوجد حلٌّ لمسألةٍ ما باستخدام خوارزميةٍ ما ولكنها نوعًا ما قبيحة؛ بمعنى أنها غير متقنة أو تستغرق وقتًا طويلًا. يتجلى هذا القبح في بعض الأحيان في كون الخوارزمية غيرَ فعَّالة. لذا، يبحث علماء الكمبيوتر — لا سيما ذوو الخلفية الرياضية — عن الجمال في الخوارزميات بنفس الشكل الذي يبحث به علماء الرياضيات عن الجمال في البراهين. ربما كان أفصح المتحدثين عن الجمال في الخوارزميات هم علماء الكمبيوتر إدسخر ديكسترا من هولندا وسي إيه آر هور من بريطانيا ودونالد كنوث من الولايات المتحدة. وكما أشار ديكسترا ذات مرة: «الجمال اختصاصنا.»

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

لنضرب المَثل بخوارزمية المضروب التي سبق ذكرها في هذا الفصل. قامت هذه الخوارزمية التكرارية على تعريف دالة المضروب كما يلي:

لكن يوجد تعريف ذاتي الاستدعاء لدالة المضروب:

وبذلك تصبح الخوارزمية المقابلة — في صورة دالة — بالشكل التالي:

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

المسائل المستعصية الحل («البالغة الصعوبة»)

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

يندرج فرع علم الكمبيوتر الذي يتعامل مع قابلية أو عدم قابلية المسائل الحوسبية للحل ضمن المجالات الرياضية الصورية ويسمَّى «نظرية التعقيد الحوسبي»، والذي تأسس في ستينيات وأوائل سبعينيات القرن العشرين في الغالب على يد العالم الإسرائيلي مايكل رابين والعالم الكندي ستيفن كوك، والعلماء الأمريكيين جوريس هارتمانيس وريتشارد ستيرنس وريتشارد كارب.

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

إذن، «كيف» يتكيف المرء مع هذه المسائل المستعصية على الحل؟ سنتناول أحد النُّهج الشهيرة في هذا الصدد في الفصل السادس.