ما هي الخوارزميات؟ من المهمة إلى خطوات قابلة للتتبع

من التعريف إلى مهمة محددة

يعرّف مقرر الجامعة المفتوحة الخوارزمية بقائمة تعليمات متدرجة مصوغة بدقة. ويميز دليل كانتربري بين المهمة التي نريد حلها وطريقة حلها. [1] [2]

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

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

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

اتفاق المدخل والمخرج

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

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

لا نستعمل شكل الكتابة دليلًا كافيًا للصلاحية. العدد سبعة قيمة عددية صحيحة في مثالنا، أما النص «7» فهو نص رغم تشابه مظهرهما على الشاشة. كذلك فالعدد أربعة ونصف خارج نوع الأعداد الذي سمحنا به، حتى لو وقع بين حدود الانتقاء. بهذا القرار لا نحتاج إلى قاعدة مستترة لتحويل نص أو تقريب كسر؛ تغيير القرار لاحقًا يتطلب اتفاقًا جديدًا واختبارات جديدة.

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

مرحلتان لا تتداخلان

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

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

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

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

اقرأ سجل القائمة الرئيسية

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

في الموضع الثاني نقرأ سبعة فنضيف الزوج الثاني وقيمته سبعة. يصبح القبول واحدًا والاستبعاد واحدًا. عند الموضع الثالث نضيف الزوج الثالث وقيمته ثلاثة؛ القبول اثنان والاستبعاد واحد. في الموضع الرابع نقرأ تسعة ونستبعدها؛ لا نمحو الزوجين السابقين، بل نرفع الاستبعاد إلى اثنين. وفي الخامس نضيف زوجًا جديدًا قيمته سبعة، فيصبح القبول ثلاثة والاستبعاد اثنين.

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

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

حالات فارغة ومخالفة وحدية

في القائمة الفارغة لا يوجد موضع أول نقرأ منه قيمة. ينجح اختبار النهاية في بداية الفحص، ثم ينجح اختبار النهاية في بداية الانتقاء، ونعيد نجاحًا مع مخرج خال وعدادي قبول واستبعاد يساويان صفرًا. لا نختلق قيمة افتراضية لملء فراغ القائمة. هذا المسار يظهر لماذا وضعنا اختبار النهاية قبل القراءة، لا بعدها.

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

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

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

ما الذي يبقى صحيحًا أثناء الانتقاء؟

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

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

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

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

التقدم والتوقف في هذا الإجراء

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

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

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

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

البرنامج وسجل التعليمات

يوضح دليل كانتربري أن البرنامج تنفيذ لخوارزمية بلغة برمجة معينة؛ ويمكن التعبير عن الإجراء بصياغة شبه برمجية توضح الأفعال دون تفاصيل اللغة. [1]

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

نفذنا الإجراء المرجعي الخاص بهذا المثال آليًا، وفحصنا سجلات القبول والاستبعاد ومخرجات حالات الحدود والفارغ والمخالفة. يتيح لك السجل المنشور في الرسم المقارنة مع التنفيذ اليدوي للقائمة الرئيسية. لا تحتاج أن تحفظ كتابة لغة بعينها لتحدد أين يختلف سجلان؛ اسأل في كل موضع عن القيمة المقروءة والفعل والمخرج بعده. إذا توافق المخرج النهائي واختلف سجل الأفعال، فافحص هل يمثلان ترتيبًا آخر مسموحًا أم اختلافًا عن الإجراء المعلن.

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

اختبر تغييرًا واحدًا وحدد أثره

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

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

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

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

ما الذي تثبته مراجعتنا؟

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

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

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