التفكير الخوارزمي
كمثل الشخصية في مسرحية موليير التي لم تكن تعرف أنها تتحدَّث الشِّعر طوال حياتها، قد لا يدرك الكثيرون أنهم كانوا ينفِّذون «خوارزمية» وهم أطفال حينما كانوا يحلون مسألةَ ضرْب أعداد متعددة الأرقام أو يحلون مسألة قسمة مطوَّلة. في الحقيقة، ربما كان الوضع قبل ستينيات القرن العشرين أن القليل ممن هم من خارج أوساط الحوسبة والرياضيات كانوا يعرفون كلمة «خوارزمية». لكن منذ ذلك الحين، وكما هو الحال مع كلمة «النموذج الفكري» (وهو مصطلح ظهر في المجالات النخبوية لفلسفة العلم)، وجدت كلمة «خوارزمية» طريقها إلى اللغة الدارجة كي تعني الصيغ أو القواعد أو الوصفات أو الإجراءات المنهجية لحل المسائل. هذا يرجع إلى حد كبير إلى الارتباط الوثيق — في العقود الخمسة الماضية أو نحو ذلك — بين الحوسبة والخوارزميات.
دونالد كنوث (الذي لربما كان باعه أطولَ من غيره في جعل الخوارزميات جزءًا من وعي عالِم الكمبيوتر) وصف في إحدى المرات علم الكمبيوتر بأنه دراسة الخوارزميات. لن يتفق كل علماء الكمبيوتر على هذا الرأي، ولكن لا يتصور أحدٌ علم الكمبيوتر من دون أن تكون الخوارزميات في صلب موضوعاته. إنها تشبه نظرية التطور التي وضعها داروين في علم الأحياء؛ إذ يبدو أن كل الطرق في الحوسبة تؤدي إلى الخوارزميات. وإذا كان التفكير من وجهة نظر أحيائية يعني التفكير من وجهة نظر تطوريَّة، فالتفكير من وجهة نظر حوسبيَّة يعني اكتسابَ عادة التفكير الخوارزمي.
اختبار ورقة دَوَّار الشمس
كمدخل لهذا المجال، لنتأمل «اختبار ورقة دَوَّار الشمس» الذي هو من أولى التجارب التي ينفِّذها الطالب في مادة الكيمياء بالمرحلة الثانوية.
توجد مادة سائلة غير معروفة في أنبوب اختبار أو دورق. يغمس منفِّذ التجربة قطاعًا من ورقة دَوَّار شمس زرقاء في هذه المادة السائلة. إذا تحوَّلت إلى اللون الأحمر، دلَّت على أن المادة السائلة حمضية؛ وإذا بقيت باللون الأزرق، دلَّت على أن المادة السائلة ليست حمضية. في الحالة الثانية، يغمس منفِّذ التجربة قطاعًا من ورقة دَوَّار شمس حمراء في المادة السائلة. وإذا تحوَّلت إلى اللون الأزرق، دلَّت على أن المادة السائلة قلوية، وإذا لم تتحوَّل كانت المادة السائلة محايدة.
لاحظ أن منفِّذ التجربة ليس بحاجة إلى معرفة أي شيء عن سبب عمل اختبار ورقة دَوَّار الشمس بالطريقة يعمل بها. هو ليس بحاجة إلى معرفة ماهية «ورقة دَوَّار الشمس» — أي تركيبتها الكيميائية — ولا العملية الكيميائية التي تتسبَّب في تغيير لون الورقة. لتنفيذ التجربة، يكفي تمامًا أن يتعرَّف منفِّذ التجربة على ورقة دَوَّار الشمس عند رؤيتها، وأن يمكنه ربط تغيُّر لون الورقة بالأحماض أو القلويات.
أصبح مصطلح «اختبار ورقة دَوَّار الشمس» استعارةً تدُل على حالة محددة أو اختبار حاسم. ولأسباب وجيهة، فإن نجاح هذه الطريقة مضمون. «ستكون» ثمة نتيجة لا لبس فيها، ولا سبيل إلى وجود الشك. إضافة إلى ذلك، لا يستغرق اختبار ورقة دَوَّار الشمس أجلًا غير مسمًّى؛ فمنفِّذ التجربة على يقين بأن الاختبار سيعطي نتيجةً بعد «مدة محددة من الزمن».
هذه الخصائص المجمَّعة لاختبار ورقة دَوَّار الشمس — الذي هو إجراء آلي مضمون أنه سيعطي نتيجة صحيحة في مدة زمنية محددة — هي العناصر الأساسية التي تميِّز الخوارزميات.
متى يكون الإجراء خوارزمية؟
Step 1: | |||
Step 3: | |||
Step 1: | |||
Step 2: |
Step 1: | |||
Step 3: | |||
Step 1: | |||
Step 3: | |||
Step 1: | |||
Step 3: | |||
Step 1: | |||
Step 2: |
أما بشأن الفاعلية، فيجب أن تكون كل العمليات التي سيجري تنفيذها بسيطةً لدرجة أنه يمكن تنفيذها في مدة زمنية محدودة. في هذه الحالة الخاصة، العمليات مبسطة لدرجة أنه يمكن تنفيذها على ورقة مثلما جرى.
«المضي قُدُمًا وأداء عملية الضرب»
يرتبط مفهوم «التجريد» بمواصفات الخوارزميات. بعبارة أخرى، يمكن حل مسائل معينة باستخدام خوارزميات محددة على مستويين مختلفين أو أكثر من مستويات التجريد.
قبل اختراع حاسبات الجيب، كان الأطفال يتعلمون مسائل الضرب باستخدام الورقة والقلم. وما يلي هو ما تعلمته في صغري. ولأغراض التبسيط، لنفترض أن عددًا مكوَّنًا من ثلاثة أرقام (المضروب) يُضرب في عدد مكوَّن من رقمين (المضروب فيه).
- الخطوة ١: نكتب العددين بحيث يكون المضروب في الصف العلوي والمضروب فيه في الصف السفلي، ونحاذي رقم آحاد المضروب فيه بحيث يكون تحت رقم آحاد المضروب بالضبط.
- الخطوة ٢: نرسم خطًّا أفقيًّا تحت المضروب فيه.
- الخطوة ٣: نضرب المضروب في رقم آحاد المضروب فيه ونكتب الناتج (حاصل الضرب الجزئي) تحت الخط الأفقي، ونكتب الناتج بحيث نحاذي كل أرقام الآحاد.
- الخطوة ٤: نضع تحت رقم آحاد حاصل الضرب الجزئي الذي حصلنا عليه من الخطوة الثالثة.
- الخطوة ٥: نضرب المضروب في رقم عشرات المضروب فيه ونكتب الناتج (حاصل الضرب الجزئي) في الصف الثاني تحت الخط الأفقي على يسار الرقم .
- الخطوة ٦: نرسم خطًّا أفقيًّا آخر تحت حاصل الضرب الجزئي الثاني.
- الخطوة ٧: نجمع حاصلَي الضرب الجزئيَّين، ونكتب ناتج الجمع تحت الخط الأفقي الثاني.
- الخطوة ٨: تنتهي المسألة. فالعدد تحت الخط الأفقي الثاني هو حاصل الضرب المطلوب.
لاحظ أن تنفيذ هذا الإجراء يتطلب أن يكون لدى الطفل بعض المعرفة المسبقة: أولًا، يجب أن يعرف طريقة ضرْب عدد مكوَّن من عدة أرقام في عدد مكوَّن من رقم واحد. ينطوي هذا على ضرورة حفظ جدول الضرب لعددين يتكوَّن كلٌّ منهما من رقم واحد، أو إمكانية الوصول إلى جدول الضرب. ثانيًا، لا بد أن يعرف طريقة جمع الأعداد المكوَّنة من رقمين أو أكثر، ويجب أن يعرف طريقة التعامل مع مسائل الجمع بالحمل. ثالثًا، يجب أن يعرف طريقة جمع عددين مكوَّنين من عدة أرقام.
لكن لاحظ دقة الخطوات. فما دام يتَّبع الشخص هذه الخطوات بالضبط كما هو مذكور، فسيكفل ذلك نجاحَ الإجراء بشرط توافر الشرطين الأول والثاني المذكورين فيما سبق في الشخص الذي ينفِّذ هذا الإجراء. من المؤَّكد أن ينتج عن هذه الخطوات النتيجة المطلوبة في مدة زمنية محدودة: وهذا من السمات الأساسية في الخوارزمية.
- الخطوة ١: نُدخل المضروب.
- الخطوة ٢: نضغط على علامة ×.
- الخطوة ٣: نُدخل المضروب فيه.
- الخطوة ٤: نضغط على علامة =.
- الخطوة ٥: نتوقَّف. يظهر حاصل الضرب على الشاشة.
هذه أيضًا خوارزمية ضرب. تعطي الخوارزميتان حاصل الضرب ذاته ولكنهما على مستويين مختلفين من التجريد. ولا يعرف المستخدِم ما الذي يحدث تحديدًا عند تنفيذ الخطوات من الأولى إلى الرابعة في الخوارزمية الثانية. ربما الحاسبة تنفِّذ الخوارزمية ذاتها التي تنفَّذ بالورقة والقلم. وربما أيضًا تستخدم طريقةَ تنفيذ مختلفة. فالمستخدم لا يرى هذه المعلومات.
مستويات التجريد في هذا المثال تنطوي أيضًا على مستويات من «الجهل». فالطفل الذي يستخدم خوارزمية الورقة والقلم يعرف معلومات عن عملية الضرب أكثرَ من الشخص الذي يستخدم حاسبة الجيب.
ثبات الخوارزميات
تمتاز الخوارزميات بخاصية مريحة وهي أن أداءها لا يعتمد على منفِّذها، ما دام توافر في المنفِّذ شروط المعرفة الثلاثة التي سبق ذكْرها. فما دام لم تتغير المدخلات إلى الخوارزمية، فلن تتغير المخرجات بغض النظر عمن (أو ما) ينفِّذها. إضافة إلى ذلك، ستعطي الخوارزمية الناتج ذاته بغض النظر عن وقت تنفيذها. وبوجه عام، تشير هاتان السمتان إلى أن الخوارزميات تتسم بخاصية الثبات.
هذا يفسِّر عدم اعتبار الوصفات المذكورة في كتب الطهي ضمن الخوارزميات؛ فكثيرًا ما تتضمَّن هذه الوصفات خطوات غامضة، ومن ثَم تقوِّض معيار الوضوح الشديد. على سبيل المثال، قد تتضمَّن هذه الوصفات تعليمات لإضافة مكونات «مهروسة قليلًا» أو «مبشورة بشرًا ناعمًا» أو نصيحة «للطهي على نار هادئة». هذه التعليمات بالغة الغموض ولا تفي بالشروط التي ينبغي توافرها في الخوارزمية. بل إنها تُترك لحَدْس الطاهي وخبرته وحكمه كي يفسِّرها. وهذا يفسِّر سببَ اختلاف مذاق الطبق ذاته الذي أعدَّه طاهيان مختلفان بالوصفة ذاتها، أو لماذا يختلف مذاق الوصفة ذاتها التي أعدَّها شخص واحد في مناسبتين مختلفتين. فهذه الوصفات تخلُّ بمبدأ الحسم.
الخوارزميات أدوات مجردة
لا شك أن الخوارزمية أداة؛ فقد صمَّمها الإنسان أو ابتكرها كي يحقق أهدافه أو احتياجاته. وبقدرِ ما أنها تعالج البنيات الرمزية (كما في حالة خوارزميتي الضرب والعامل المشترك الأكبر)، فإنها أدوات حوسبية. (ليست جميع الخوارزميات تعالج البنيات الرمزية؛ فاختبار ورقة دَوَّار الشمس يتطلَّب كيانات مادية — أنبوب سائل الاختبار، وشريحة ورقة دَوَّار الشمس — باعتبارهما المدخلات، وينتج حالة فيزيائية — لون شريحة ورقة دَوَّار الشمس — باعتبارها المخرجات. إن اختبار ورقة دَوَّار الشمس عبارة عن خوارزمية يدوية تعمل بناءً على كيانات فيزيائية وكيميائية وليس بنيات رمزية؛ ومن ثَم لا يجدُر بنا اعتبارها أداة حوسبية.)
لكن الخوارزميات في حد ذاتها ليس لها وجود مادي، سواء أكانت حوسبية أم غير ذلك. فالإنسان لا يستطيع لمسها أو إمساكها أو تحسُّسها أو تذوُّقها أو سماعها. وهي لا تخضع لقوانين علوم الفيزياء ولا الكيمياء ولا حتى قوانين الهندسة. بل هي «أدوات مجردة». إنها تتألَّف من البنيات الرمزية التي — شأنها شأن كل البنيات الرمزية — تمثِّل أشياء في العالم، وقد تكون هذه الأشياء مادية (كورقة دَوَّار الشمس، والمواد الكيميائية، والأزرار في حاسبة الجيب، وغيرها) أو مجردة (كالأعداد الصحيحة، والعمليات المنفذة على الأعداد الصحيحة، والعلاقات مثل التساوي، وغير ذلك).
الخوارزمية أداة مساعدة. وكما هو الحال مع معظم الأدوات المساعدة، كلما قل احتياج المستخدِم إلى معرفة المفاهيم النظرية في الخوارزمية، زادت فاعليتها بالنسبة إليه.
هذا يثير النقطة التالية: يمكن اعتبار الخوارزمية أداة لها وجهان مثل يانوس. (يانوس هو إله البوابات الروماني الذي كان ينظر في اتجاهين معاكسين في آن واحد.) يتطلب «تصميم» الخوارزمية أو «ابتكارها» إبداعًا في العموم، ولكن «استخدامها» عبارة عن عمل ميكانيكي صِرف ويتطلب القليل من التفكير الإبداعي. وإن جاز التعبير، فالخوارزمية شكلٌ من أشكال التفكير غير الواعي.
الخوارزميات معرفة «إجرائية»
الخوارزميات أدواتٌ ينشئها المستخدِمون لحل المسائل. وبمجرد صياغتها وإتاحتها للعامة، تصبح ملكًا للعالم. هذا ما يجعل الخوارزميات أدواتٍ موضوعية (وكذلك ثابتة). لكن الخوارزميات تُعَد تجسيدًا للمعرفة أيضًا. وحيث إنها أدوات موضوعية، فهي تجسيدٌ لما يطلق عليه فيلسوف العلم كارل بوبر «المعرفة الموضوعية». (قد يبدو متناقضًا إذا قلنا إن مستخدم الخوارزمية «مفكِّر غير واعٍ» وفي نفس الوقت «كائن عالم»، ولكن حتى التفكير غير الواعي يظل تفكيرًا، والتفكير يستلزم البناء على المعرفة بأحد أشكالها.) لكن ما نوع المعرفة التي تمثِّلها الخوارزمية؟
في العلوم الطبيعية، نتعلم التعريفات والحقائق والنظريات والقوانين وغير ذلك. وفيما يلي بعض الأمثلة من مبادئ الفيزياء والكيمياء.
-
(١)
سرعة الضوء المتَّجهة في فراغ تساوي ألف ميل في الثانية.
-
(٢)
التسارع هو معدَّل تغيُّر السرعة المتجهة.
-
(٣)
الوزن الذري للهيدروجين يساوي .
-
(٤)
للمادة أربع حالات وهي الصلبة والسائلة والغازية والبلازما.
-
(٥)
عند تنظيم العناصر الكيميائية حسب ترتيب أعداد الذرات، فإنه يوجد نمط دوري (متكرر) لخصائص العناصر.
-
(٦)
الاحتراق يتطلب وجود الأكسجين.
أي خاصية تنطبق على الصفر وكذلك على العدد التالي مباشرةً لعددٍ تتوافر به هذه الخاصية، تنطبق على كل الأعداد.
في المثلث القائم الزاوية، مربع الوتر يساوي مجموع مربعَي طولَي الضلعين الآخرين.
وفيما يلي مثال على المعرفة التقريرية في الرياضيات عن طريق التعريف:
على الجانب الآخر، لا تُعدُّ الخوارزمية تقريرية؛ بل هي إجراء يوضح كيفية إنجاز شيءٍ ما. إنها تصف عملًا من نوعٍ ما. وعليه، فإن الخوارزمية مثال على «المعرفة الإجرائية»، أو بالمعنى الدارج المعرفة «العملية».
لاحظ أنه يمكن تقديم المفهوم ذاته — المضروب — بطريقة تقريرية (كما يفضِّل علماء الرياضيات) وبطريقة إجرائية (كما يحب علماء الكمبيوتر). في الحقيقة، يطرح الشكل التقريري «النظرية» الأساسية («ما المضروب؟») للشكل الإجرائي أو الخوارزمية («كيف نحسب المضروب؟»).
باختصار، تعبِّر الخوارزميات عن شكلٍ من أشكال المعرفة الإجرائية التي تتسم بالموضوعية أيضًا.
تصميم الخوارزميات
الكلمة المهمة في هذا المقام هي «إنشاء». إن عملية التصميم عملٌ إبداعي، وكما أوضح الباحثون في مجال الإبداع، فالعمل الإبداعي مزيجٌ معقَّد من الإدراك والمنطق والحَدْس والمعرفة وحسن التقدير والدهاء والاكتشافات التي تتم مصادفة. ومع ذلك يتحدَّث واضعو نظريات التصميم عن «علم التصميم» أو «منطق التصميم».
فهل يوجد إذن جانبٌ علمي في تصميم الخوارزميات؟ الإجابة هي: «إلى حدٍّ ما». توجد ثلاثة أوجه أساسية يدخل بها «المنهج العلمي» في تصميم الخوارزميات.
بادئ ذي بدء، لا تأتي مسألة التصميم من فراغ. فهي تؤطَّر في سياق كمٍّ من المعرفة (سنطلق عليه «فضاء المعرفة») ذي صلة بالمسألة ويحوزها المصمم. ولدى تصميم خوارزمية جديدة، يصبح فضاء المعرفة هذا ذا صلة. على سبيل المثال، قد يُكتشف وجه تشابه بين المسألة المطروحة والمسألة التي حُلت بخوارزمية موجودة حاليًّا (والتي هي جزء من فضاء المعرفة)، ومن ثَم يمكن نقل الأسلوب المطبَّق في المسألة الثانية إلى المسألة الراهنة. وهذه إحدى حالات «التفكير القياسي». أو ربما تبدو استراتيجية تصميم معروفة مناسبة للمسألة القائمة على وجه الخصوص، ومن ثَم يمكن تجربة هذه الاستراتيجية وإن كان بغير ضمان على نجاحها. وهذه إحدى حالات «التفكير الاستدلالي». أو ربما توجد نظرية صورية ذات صلة بالمجال الذي تنتمي إليه المسألة؛ ومن ثَم يمكن أخذُ النظرية في الاعتبار. وهذه إحدى حالات «التفكير النظري».
بعبارة أخرى، قد يكون لأشكال التفكير المختلفة تأثيرٌ في تصميم الخوارزمية بناءً على كمٍّ من المعرفة المقرَّرة أو المجرَّبة أو المثبَتة (والتي تكون تقريرية وإجرائية على حد سواء). سنطلق على ذلك اسم «عامل المعرفة» في تصميم الخوارزمية.
لكن مجرد التوصُّل إلى الخوارزمية ليس كافيًا. فهناك أيضًا ضرورة إقناع النفس والآخرين بأن الخوارزمية «صالحة». وتنطوي هذه الضرورة على اتباع التفكير المنهجي في توضيح أن الخوارزمية تستوفي المتطلبات الأصلية. سأطلق على ذلك اسم «عامل الصلاحية» في تصميم الخوارزميات.
وأخيرًا، وحتى لو ثبَت أن الخوارزمية صالحة، فربما لا يكون هذا كافيًا. فثمَّة مسألة أداء الخوارزمية: ما مدى كفاءة الخوارزمية؟ وسنطلق على ذلك اسم «عامل الأداء» في تصميم الخوارزمية.
تنطوي هذه «العوامل» الثلاثة على أنواع التفكير والمنطق وقواعد البرهان التي نربطها عادةً بالعلم. فلنتناول بشيء من الأمثلة كيفيةَ إسهامها في علم تصميم الخوارزميات.
مشكلة تحويل التعبيرات الحسابية
توجد فئةٌ من برامج الكمبيوتر تسمَّى «البرامج المترجِمة» ووظيفتها تحويل البرنامج المكتوب بلغة برمجة عالية المستوى (وهي لغة تكون مستقلة عن سمات أجهزة الكمبيوتر المادية الفعلية، مثل لغة فورتران أو سي++) إلى سلسلة تعليمات يمكن لأجهزة كمبيوتر مادية خاصة تنفيذها (تفسيرها) مباشرةً. ويطلق على سلسلة التعليمات الخاصة بالآلة اسم «لغة الآلة». (سنتناول لغات البرمجة في الفصل الرابع.)
واجه كتَّاب البرامج المترجِمة الأوائل (في أواخر خمسينيات القرن العشرين وستينياته) مشكلةً تقليدية وهي صياغة خوارزميات تحوِّل «التعبيرات الحسابية» التي تظهر في البرنامج إلى لغة آلة. ومن الأمثلة على ذلك التعبير:
- (أ) في حالة غياب الأقواس، تكون الأسبقية لعاملَي الضرب والقسمة / على عاملَي الجمع + والطرح –.
- (ب) عاملا الضرب والقسمة / يستويان في مستوى الأسبقية، وعاملا الجمع + والطرح – يستويان في مستوى الأسبقية.
- (جـ)
إذا ظهر في التعبير عوامل ذات مستوى أسبقية واحد، يصبح ترتيب الأسبقية من اليسار إلى اليمين. بمعنًى آخر، تطبَّق العوامل على المعاملات بالترتيب الموجودة به من اليسار إلى اليمين.
- (د)
التعبيرات الموجودة داخل الأقواس لها أعلى درجات الأسبقية.
- (أ) نفِّذ . وأطلق على النتيجة .
- (ب) نفِّذ . وأطلق على النتيجة .
- (جـ) نفِّذ . وأطلق على النتيجة .
- (د) نفِّذ .
على الجانب الآخر، إذا كان التعبير خاليًا من الأقواس كما يلي:
- (١) نفِّذ . وأطلق على النتيجة .
- (٢) نفِّذ . وأطلق على النتيجة .
- (٣) نفِّذ . وأطلق على النتيجة .
- (٤) نفِّذ .
يمكن تصميم خوارزمية لإنشاء لغة آلة بحيث تقيِّم عند تنفيذها التعبيرات الحسابية المرتبة وسطيًّا تقييمًا صحيحًا طبقًا لقواعد الأسبقية. (ستعتمد الطبيعة المحددة للخوارزمية على طبيعة التعليمات المعتمدة على الآلة، والتي تختلف حسب جهاز الكمبيوتر المادي المحدد.) ومن ثَم وبناءً على قواعد الأسبقية، تستعين الخوارزمية بقواعدَ دقيقة هي جزء من فضاء المعرفة ذات الصلة بالمسألة. كذلك ولأن الخوارزمية تعتمد على قواعد الأسبقية اعتمادًا مباشرًا، فإن إثبات صلاحية الخوارزمية سيصبح يسيرًا إلى حد بعيد. لكن وكما توضِّح الأمثلة السابقة، تزيد الأقواس إلى حدٍّ ما من تعقيد عملية تحويل التعبير المرتَّب وسطيًّا.
وثمَّة ترميزٌ لتحديد التعبيرات الحسابية من دون الحاجة إلى الأقواس من ابتكار عالِم المنطق البولندي يان ووكاسيفيتش (١٨٧٨–١٩٥٦)، ومن ثَم أصبح معروفًا باسم «الترميز البولندي». يطلق على إحدى صيغ هذا الترميز «الصيغة البولندية العكسية»، وفيها يأتي العامل الحسابي بعد المعاملَين مباشرةً في صورة تعبير بولندي عكسي. توضح الأمثلة التالية الصيغةَ البولندية العكسية لبعض التعبيرات المرتَّبة وسطيًّا.
-
(أ)
بالنسبة إلى التعبير ، الصيغة البولندية العكسية هي .
-
(ب)
بالنسبة إلى التعبير ، الصيغة البولندية العكسية هي .
-
(جـ)
بالنسبة إلى التعبير ، الصيغة البولندية العكسية هي .
-
(د)
بالنسبة إلى التعبير ، الصيغة البولندية العكسية هي .
يتقدَّم تقييم التعبير البولندي العكسي من اليسار إلى اليمين بطريقة مباشرة، ومن ثَم يزيد من سهولة مسألة الترجمة. تنص القاعدة على أن العوامل الحسابية الواردة في التعبير تنطبق على معاملاتها السابقة عليها حسب ترتيب ظهور العوامل، من اليسار إلى اليمين. على سبيل المثال، في حالة التعبير المرتَّب وسطيًّا:
الصيغة البولندية العكسية هي:
- (١) نفِّذ وأطلق على النتيجة . ومن ثَم يكون التعبير الناتج هو .
- (٢) نفِّذ وأطلق على النتيجة . ومن ثَم يكون التعبير الناتج هو .
- (٣) نفِّذ وأطلق على النتيجة . ومن ثَم يكون التعبير الناتج هو .
- (٤) نفِّذ .
بالطبع سيكتب المبرمجون التعبيرات الحسابية بالصيغة المرتبة وسطيًّا المعتادة. وسينفذ البرنامج المترجِم خوارزمية ستحوِّل تلك الصيغ إلى صيغة بولندية عكسية أولًا، ثم يولِّد لغة آلة من التعبيرات البولندية العكسية.
مسألة تحويل التعبيرات من الصيغة المرتبة وسطيًّا إلى الصيغة البولندية العكسية توضِّح مدى إمكانية اجتماع أساس نظري سليم واستراتيجية تصميم مجربة أثناء تصميم خوارزمية يمكن إثبات صحتها.
انظر الآن في مسألة تحويل التعبيرات من الصيغة المرتبة وسطيًّا إلى الصيغة البولندية العكسية في الخوارزميات. وهذه المسألة قائمة على مجموعة من القواعد الصورية:
- (أ) إذا كان معاملًا فرديًّا هو ، فستكون الصيغة البولندية العكسية هي .
- (ب) إذا كان تعبيرًا مرتبًا وسطيًّا وكان أحد عناصر ، فإن التعبير البولندي العكسي المقابل له هو .
- (جـ) إذا كان تعبيرًا مرتبًا وسطيًّا، فستكون صيغته البولندية العكسية هي .
لتوضيح كيف تعمل الخوارزمية مع المدخلات الفعلية، انظر الأمثلة التالية:
كفاءة الخوارزميات باعتبارها أدوات نفعية
قلنا سابقًا إن الأمر لا يقتصر على تصميم خوارزمية صحيحة. وكما هو الحال مع مصمم أي أداة نفعية، يجب أن يهتم مصمم الخوارزمية بمدى «كفاءة» هذه الخوارزمية؛ أي، مدى فاعليتها في القيام بمهامها. فهل يمكننا «قياس» كفاءة الخوارزمية بناءً على هذا المعنى؟ هل يمكننا عملُ مقارنة نوعية بشكلٍ ما بين خوارزميتين متنافستين تؤديان المهمة ذاتها؟
عامل الكفاءة الجليُّ هو مقدار الوقت الذي تستغرقه الخوارزمية في تنفيذ المهمة. لكن الخوارزمية أداة مجرَّدة. فلا يمكننا قياسها بالزمن الفعلي؛ لا يمكننا قياس الزمن على ساعة حقيقية؛ حيث إن الخوارزمية كخوارزمية لا تتضمن أيَّ شيء مادي. فإذا كنت أنا الإنسان أنفِّذ خوارزمية، فيُفترض أن بإمكاني قياسَ مقدار الوقت الذي استغرقته في تنفيذ الخوارزمية ذهنيًّا (ربما باستخدام الورقة والقلم). لكن هذا ليس إلا قياسًا «لأدائي أنا» للخوارزمية بناءً على مجموعة معينة من المعطيات. واهتمامنا ينصبُّ على قياس أداء الخوارزمية عبْر كل مُدخلاتها المحتملة وبغضِّ النظر عمن ينفِّذ الخوارزمية.
متوسط تعقيد الوقت هو مقياس الكفاءة الأكثر واقعية، ولكنه يتطلب استخدام الاحتمالات، ومن ثَم تزيد صعوبة تحليله. وفي هذا المقام، لن نتناول غير سيناريو أسوأ الحالات.
أبسط طريقة هي البدء من عند رأس القائمة ومطابقة كل جزء من الاسم بالعنصر المعطَى من اسم الطالب، والتقدُّم عبْر القائمة اسمًا باسم حتى نجد تطابقًا، ثم نخرج عنوان البريد الإلكتروني المقابل له. (لغرض التبسيط، سنفترض أن اسم الطالب المعطى في مكانٍ ما بالقائمة.) يُطلق على هذه الخوارزمية اسم «خوارزمية البحث الخطي».