الفصل الأول

ما هي الخوارزمية؟

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

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

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

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

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

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

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

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

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

طريقة لإنجاز المهام

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

كلمة «خوارزمية» في ذاتها لا توضِّح معناها. الاسم مشتق من اسم محمد بن موسى الخوارزمي (من عام ٧٨٠ إلى عام ٨٥٠ تقريبًا)، وهو عالِم فارسي في الرياضيات والفلك والجغرافيا. تعدَّدت إسهامات الخوارزمي وانتشرت على نطاق واسع. فمصطلح «الجبر» مشتقٌّ من العنوان العربي لأكثرِ كتبه تأثيرًا وهو كتاب «المختصر في حساب الجبر والمقابلة». كان ثاني كتبه تأثيرًا كتاب «عن الحساب بالأرقام الهندية»؛ إذ تناول العمليات الحسابية وقدَّم نظام الأعداد العربية-الهندية إلى العالَم الغربي من خلال ترجمته إلى اللاتينية. أُدخل اسم الخوارزمي إلى اللغة اللاتينية وصار Algorismus والذي أصبح يشير إلى طريقة الحساب العددي باستخدام الأعداد العشرية. تأثَّر المصطلح اللاتيني Algorismus بالكلمة اليونانية arithmos وتعني «العدد» (مثل كلمة arithmetic وتعني علم الحساب)، ومِن ثَم أصبحت algorithm بمعنى خوارزمية، وظلت تشير إلى العمليات الحسابية العشرية، قبل أن تكتسب معناها الحديث في القرن التاسع عشر.
قد يميل المرء إلى الاعتقاد بأن الخوارزميات شيء نقوم به بواسطة أجهزة الكمبيوتر، ولكن هذا الاعتقاد خاطئ. ويُعزى خطؤه إلى أن الخوارزميات كانت موجودة قبل اختراع أجهزة الكمبيوتر بزمن طويل. فيعود تاريخ أول خوارزميات معروفة إلى الحضارة البابلية القديمة.2 كذلك يُعزى الخطأ إلى أن الخوارزميات ليس لها علاقة بالمسائل المرتبطة بأجهزة الكمبيوتر. فالخوارزميات تدور حول فعل شيءٍ ما بطريقة محدَّدة وباتباع سلسلة خطوات معينة. هنا يكمن بعض الغموض. فقد تتساءل، ما نوع تلك الخطوات؟ وما تلك الطريقة المحددة؟ يمكننا تبديد هذا الغموض برمَّته وتقديم تعريف رياضي دقيق لمعنى الخوارزمية وما تقوم به — وهذا التعريف موجود بالفعل — ولكننا لسنا بحاجةٍ إلى كل هذا. قد تُسرُّ عندما تعرف أن الخوارزمية مجموعةُ خطوات يمكن أن تتَّبعها باستخدام ورقة وقلم، ويمكن أن تطمئن إلى أن هذا الوصف الذي يبدو مبسطًا قريبٌ من التعريفات التي يستخدمها علماء الرياضيات وعلوم الكمبيوتر.

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

ومِن ثَم يمكننا البدء في شرح الخوارزمية بمسألةٍ يمكن حلُّها باستخدام الكتابة فقط. لنفترض أن لدينا مجموعتين من الأشياء، ونريد توزيع المجموعة الأولى من الأشياء بين الأشياء في المجموعة الثانية بالتساوي قدْر الإمكان. سنستخدم علامة (×) للتعبير عن الأشياء في المجموعة الأولى وعلامة (•) للتعبير عن الأشياء في المجموعة الثانية. نريد أن نوزِّع علامات (×) بين علامات (•).
إذا كان إجمالي عدد الأشياء يقبل القسمة على عدد علامات ×، فهذا سهل. ما علينا سوى توزيع علامات (×) على علامات • وكأننا نُجري عملية قسمة. على سبيل المثال، إذا كان إجمالي عدد الأشياء يساوي ١٢، منها ثلاثة أشياء تعبِّر عنها العلامة × وتسعة أشياء تعبِّر عنها العلامة •، فإننا نضع علامة × واحدة يليها ثلاث علامات •، ثم علامة × واحدة يليها ثلاث علامات •، وفي النهاية علامة × واحدة يليها ثلاث علامات •:
لكن ماذا لو كان إجمالي عدد الأشياء — مجموع علامات × وعلامات • — لا يقبل القسمة الصحيحة على عدد علامات ×؟ ماذا يمكن أن نفعل إذا كان لدينا خمس علامات × وسبع علامات •؟
نبدأ بوضع كل علامات × يليها كل علامات • في صف واحد كما يلي:
ثم نأخذ خمسًا من علامات • ونضعها تحت علامات × كما يلي:

نلاحظ في النمط الذي ظهر لنا أنه يتبقى عمودان جهة اليمين. نأخذ العمودين المتبقيين اللذين يشتمل كل واحد منهما على علامة • واحدة، ونضعهما تحت أول عمودين بحيث يشكِّلان صفًّا ثالثًا:

نلاحظ الآن أنه قد تبقى ثلاثة أعمدة. نأخذ العمودين جهة اليمين ونضعهما تحت العمودين جهة اليسار:

الآن، لا يتبقى سوى عمود واحد، ومِن ثَم نتوقَّف هنا. نضع الأعمدة في سلسلة تبدأ من اليسار إلى اليمين كما يلي:

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

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

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

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

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

هذا إيقاع بوسا نوفا مقلوبٌ. يبدأ إيقاع بوسا نوفا الأصلي بالصوت البادئ الثالث؛ ومِن ثَم فالنمط المطابق المثالي له هو:

وإذا بدأنا بثلاثة أصوات بادئة وأربعة أصوات صامتة، فسنحصل على النمط التالي:

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

يمكن اشتقاق العديد من الإيقاعات الأخرى على هذا النحو عن طريق وضع علامات × وعلامات • في أعمدة ثم تحريكها بالطريقة التي أوضحناها للتو. وقد أوضحنا الإجراء عن طريق قياس الأعمدة المتبقية، ولكن هذه الطريقة تعكس ما يحدث في الواقع. فبدلًا من إنشاء الأعمدة واتباع ما يمليه علم الهندسة، وتحريك الأعمدة، يمكننا فعْل الشيء نفسه بمزيد من المنهجية باستخدام عمليات عددية بسيطة. لتوضيح الأمر، لنرجع إلى مثال الأصوات الصامتة اﻟ ١٢ والأصوات البادئة السبعة. نبدأ بقسمة ١٢ على ٧، الذي يعطينا خارج القسمة ١ مع تبقي ٥:
12 = 1 × 7 + 5

هذا المثال يبيِّن لنا أن نضع سبعة أصوات بادئة في البداية، منشئين بذلك سبعة أعمدة من الأصوات البادئة، يتبعها الأصوات غير المشددة الخمسة المتبقية من عملية القسمة:

نعيد القسمة مرة أخرى، ولكن هذه المرة نقسم المقسوم عليه في عملية القسمة السابقة وهو العدد ٧، على الباقي في القسمة السابقة نفسها وهو العدد ٥. ويكون ناتج القسمة ١ مرة أخرى، بينما يكون الباقي ٢:

7 = 1 × 5 + 2

وهذا يعني أن علينا أن نأخذ الأعمدة الخمسة جهة اليمين ونضعها تحت الأعمدة الخمسة جهة اليسار، ونترك الباقي وهما ٢:

نكرِّر الخطوة نفسها: نقسم المقسوم عليه في مسألة القسمة السابقة وهو العدد ٥، على الباقي في القسمة السابقة نفسها وهو العدد ٢. فيكون ناتج القسمة ٢ والباقي ١:

5 = 2 × 2 + 1

تلك العملية تخبرنا بأن نأخذ «ضعف» العمودين جهة اليمين ونضعهما تحت العمودين جهة اليسار، ونترك الباقي ١:

لاحظ أن كلمة «ضعف» تعني أن هذا يعادل ما كنَّا سنفعله في خطوتين لو اتبعنا طريقة الحل السابقة من دون استخدام عملية القسمة. ومِن ثَم سننتقل من النمط:

إلى النمط التالي أولًا:

ثم إلى النمط:

وإذا جمعنا الأعمدة في سلسلة، فسنحصل على إيقاع إمبيري:

الخوارزمية الأولى

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

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

بالرغم من ذلك، بإمكان هذه الخوارزمية أن تفعل ما هو أكثر من ذلك. وما دمنا نتحدَّث عن قسمة عددين، لنفكر في المسألة العامة التالية: إذا كان لدينا عددان، وهما العدد والعدد ، فما أكبر عدد يقبل القسمة على العددين؟ هذا العدد يسمَّى «العامل المشترك الأكبر» للعددين. لقد تعرَّفنا على العامل المشترك الأكبر في مادة الحساب بالمرحلة الابتدائية في مسائلَ كالمسألة التالية: إذا كان لدينا ١٢ عبوة من الرقائق و٤ عبوات من الجبن، فكيف سنوزِّعها على سلالٍ بحيث يتساوى عدد عبوات الرقائق والجبن في كل سلة؟ بما أن ١٢ تقبل القسمة على ٤، فسيكون لدينا ٤ سلال، تحتوي كل سلَّة منها على ثلاث عبوات من الرقائق وعبوة من الجبن؛ إذن فالعامل المشترك الأكبر للعددين ١٢ و٤ هو ٤. تزداد الأمور إثارةً إذا كان لدينا ١٢ عبوة من الرقائق و٨ عبوات من الجبن. لا يمكنك قسمة عدد على الآخر، ولكن أكبر عدد يقبل العددان ١٢ و٨ القسمة عليه هو ٤، بمعنى أنك ستصنع أربع سلال مرة أخرى تحتوي كلُّ سلة منها على ثلاث عبوات من الرقائق وعبوتين من الجبن.
إذن كيف يمكن إيجاد العامل المشترك الأكبر لأي عددين صحيحين؟ رأينا أنه إذا كان لدينا عددان أحدهما يقبل القسمة على الآخر، فالمقسوم عليه هو العامل المشترك الأكبر. أما إذا لم يقبل أحدهما القسمة على الآخر، فلا نحتاج سوى إيجاد العامل المشترك الأكبر للعدد الباقي من قسمة العددين والعدد الثاني من أجل إيجاد العامل المشترك الأكبر. يسهل فهْم هذا باستخدام الرموز. إذا كان لدينا عددان صحيحان، هما و، فالعامل المشترك الأكبر للعدد والعدد يساوي العامل المشترك الأكبر لباقي ناتج القسمة و. وهذا يعود بنا إلى مسألة الإيقاعات. «الطريقة التي أوجدنا بها الإيقاعات هي نفسها الطريقة التي نستخدمها لإيجاد العامل المشترك الأكبر بين عددين.»
يُطلق على طريقة إيجاد العامل المشترك الأكبر بين عددين «خوارزمية إقليدس» نسبةً إلى عالم الرياضيات اليوناني القديم إقليدس، الذي وصفها للمرة الأولى في كتابه «العناصر» (حوالي سنة ٣٠٠ قبل الميلاد). وتقوم الفكرة الأساسية لها على أن العامل المشترك الأكبر بين عددين لا يتغيَّر إذا وضعنا العدد الأكبر منهما محلَّ حاصل طرحه من العدد الأصغر. لنضرب مثالًا بالعددين ٥٦ و٢٤. العامل المشترك الأكبر بين العددين هو ٨، وهو أيضًا العامل المشترك الأكبر لحاصل طرح ٥٦ − ٢٤ = ٣٢ والعدد ٢٤، والأمر نفسه ينطبق على العددين ٣٢ و٢٤، وهكذا. إن عملية الطرح المتكرر هي في حقيقتها عملية قسمة؛ ومِن ثَم يمكن وصف خوارزمية إقليدس بالخطوات التالية:
  • (١)
    لإيجاد العامل المشترك الأكبر للعددين و، نقسم العدد على العدد . سيعطينا ذلك ناتج قسمة وباقيًا. إذا عبَّرنا عن ناتج القسمة بالحرف وعن الباقي بالحرف ، فستصبح المسألة بالشكل التالي: .
  • (٢)
    إذا كان الباقي يساوي صفرًا، فسنتوقف هنا، وسيصبح العامل المشترك الأكبر للعدد والعدد هو . أما لو كان غير ذلك، فسنعود إلى الخطوة ١، ولكن في هذه المرة ستحل قيمة مكان قيمة وستحل قيمة مكان قيمة . أو بعبارة أخرى، سنعود إلى الخطوة ١، ونجعل تساوي ونجعل تساوي .

تلك هي الخطوات التي اتبعناها بالضبط من قبل. الفرق الوحيد هو أننا عند إيجاد الإيقاعات، نتوقَّف عندما يصبح الباقي ٠ أو ١ في الخطوة الثانية، بينما تتوقَّف خوارزمية إقليدس عندما يكون الباقي صفرًا. إن الأمر سيان في الواقع؛ فإذا كان الباقي يساوي ١، فعند تكرار الخطوة ١ مرة أخرى سيكون الباقي صفرًا؛ لأن أيَّ عدد صحيح يقبل القسمة على ١. لنجرِّب العددين ٩ و٥: ٩ = ١ × ٥ + ٤، ومِن ثَم ننتقل إلى ٥ = ١ × ٤ + ١، ثم إلى ٤ = ١ × ٤ + ٠، وبذلك يكون العامل المشترك الأكبر بين العددين ٩ و٥ هو ١.

قد يكون من المفيد رؤية الخوارزمية في مثال عملي حيث ، و في الجدول التالي، المماثل للجدول الذي رأيناه من قبل في مثال الإيقاعات. نجد أن العامل المشترك الأكبر بين العددين ١٣٦ و٥٦ هو العدد ٨:
كما أشرنا في مثال العددين ٩ و٥، تعمل خوارزمية إقليدس على نحو صحيح في جميع الحالات، حتى عندما لا يكون بين العددين أيُّ عامل مشترك غير العدد ١. هذا ما حدث مع المثال و. يمكنك أن ترى بنفسك ما يحدث إذا جرَّبت تطبيق خطوات الخوارزمية مع المثال و؛ سيستغرق هذا المثال بضع خطوات، ولكن ستنتهي الخوارزمية إلى أن العامل المشترك الوحيد هو العدد ١.
تنفَّذ خطوات خوارزمية إقليدس بترتيب محدَّد ودقيق. ويوضح وصف الخوارزمية الطريقة التي تندمج بها خطواتها:
  • (١)

    توضع الخطوات في «تسلسل».

  • (٢)

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

  • (٣)

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

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

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

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

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

الخوارزميات وأجهزة الكمبيوتر والرياضيات

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

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

البرمجة هي نظامٌ لتحويل أهدافنا إلى رموزٍ يستطيع جهاز الكمبيوتر فهْمها. نطلق على تلك الرموز «لغة البرمجة».

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

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

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

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

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

كل البرامج تنفِّذ مجموعة من الخطوات لتنفيذِ مهمةٍ ما، ومِن ثَم يمكننا القول إن كل البرامج عبارة عن خوارزميات. ولكننا نتمتع بقدرٍ أكبر قليلًا من الدقة ونريد لخطواتنا أن تلبي خصائص معينة:4
  • (١)

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

  • (٢)

    يجب أن تكون الخطوات دقيقة بحيث يمكن تنفيذها دون ارتباك أو حيرة.

  • (٣)

    قد تعمل الخوارزمية على بعض المدخلات؛ كخوارزمية إقليدس التي تعمل على عددين صحيحين.

  • (٤)

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

  • (٥)

    يجب أن تكون الخوارزمية فعَّالة. يجب أن يتمكَّن الإنسان من تنفيذ كل خطوة في قدرٍ معقول من الوقت باستخدام الورقة والقلم.

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

هنا يكمن فارق جوهري بين الخوارزميات والرياضيات. معظم علماء الكمبيوتر الأوائل كانوا علماء في الرياضيات، وعلم الكمبيوتر يستخدم كمًّا هائلًا من الرياضيات، ولكنه ليس منهجًا رياضيًّا. فعالِم الرياضيات يريد إثبات «نتيجةٍ ما»؛ أما عالِم الكمبيوتر فيريد لتلك النتيجة «أن تؤتي ثمارها».

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

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

توجد ستة مسارات بطول ٤، ومِن ثَم يمكننا اختيار أي مسار منها.

لكننا لسنا مقيدين بشبكاتٍ تتكوَّن من ٣ × ٣ نقاط. يمكن أن يكون لدينا شبكات مكونة من ٤ × ٤ نقاط أو ٥ × ٥ نقاط أو حتى أكبر. ومِن ثَم نكتشف أن تلك الطريقة لا تصلح في جميع الحالات. يوجد ١٨٤ مسارًا من الركن العلوي جهة اليسار إلى الركن السفلي جهة اليمين في شبكة تتكوَّن من ٤ × ٤ نقاط؛ وإذا انتقلنا إلى شبكة تتكوَّن من ٥ × ٥ نقاط، فسيزيد عدد المسارات إلى ٨٥١٢ مسارًا. يستمر عدد المسارات في الزيادة بسرعة — بل يزيد بخطًى متسارعة باستمرار — وحتى عدُّ تلك المسارات أمرٌ صعب. فعندما نصل إلى شبكة مكونة من ٢٦ × ٢٦ نقطة، يصبح لدينا ٨ ٤٠٢ ٩٧٤ ٨٥٧ ٨٨١ ١٣٣ ٤٧١ ٠٠٧ ٠٨٣ ٧٤٥ ٤٣٦ ٨٠٩ ١٢٧ ٢٩٦ ٠٥٤ ٢٩٣ ٧٧٥ ٣٨٣ ٥٤٩ ٨٢٤ ٧٤٢ ٦٢٣ ٩٣٧ ٠٢٨ ٤٩٧ ٨٩٨ ٢١٥ ٢٥٦ ٩٢٩ ١٧٨ ٥٧٧ ٠٨٣ ٩٧٠ ٩٦٠ ١٢١ ٦٢٥ ٦٠٢ ٥٠٦ ٠٢٧ ٣١٦ ٥٤٩ ٧١٨ ٤٠٢ ١٠٦ ٤٩٤ ٠٤٩ ٩٧٨ ٣٧٥ ٦٠٤ ٢٤٧ ٤٠٨ من المسارات. يحتوي هذا الرقم على ١٥١ عددًا عشريًّا، ووُجد هذا الناتج باستخدام برنامج كمبيوتر يستخدم خوارزمية؛ نعم، نحن نستخدم خوارزمية لفهْم سلوك خوارزمية أخرى.5

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

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

قياس الخوارزميات

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

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

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

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

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

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

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

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

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

يوجد تعريف للتعقيد ثبتت فائدته من الناحية العملية. وهو يحتوي أيضًا على رمز واسم. نكتب ونسميه ترميز Big O. داخل ترميز Big O في مكان النقطة، نكتب مقدارًا جبريًّا. يعني الرمز أن الخوارزمية ستستغرق وقتًا يساوي مضاعف المقدار الجبري في الأغلب. لنرَ ما يعنيه ذلك:
  • إذا كنت تريد البحث عن شيء في سلسلة عناصر — يوجد عدد من العناصر — وسلسلة العناصر ليست مرتَّبة بأي صورة، فإن التعقيد يساوي . وهذا يعني، بالنسبة إلى العدد من العناصر، أن الوقت اللازم لإيجاد عنصر معيَّن في تلك السلسلة لن يزيد على مضاعف ضرب عدد العناصر.
  • إذا كنت تريد ضرب عددين مكوَّنين من من الأرقام باستخدام عملية ضرب مطولة، فإن التعقيد يساوي . وهذا يعني أن الوقت اللازم لإنجاز عملية الضرب لن يزيد على مضاعف مربع حجم العددين.
إذا كان لدينا خوارزمية درجة تعقيدها ، فإننا نتوقَّع لمدخل بحجم ١٠٠٠٠ أن يحتاج إلى مضاعف عشرة آلاف خطوة. وإذا كانت درجة التعقيد في الخوارزمية تساوي ، فإننا نتوقَّع، بالنسبة إلى حجم مدخل مساوٍ للسابق، أن تحتاج إلى مائة مليون خطوة. ولا يعتبر هذا الحجم كبيرًا بالنسبة إلى العديد من المسائل. فعادةً ما ترتب أجهزة الكمبيوتر ١٠٠٠٠ عنصر. ولكنك ترى أن نطاق عدد الخطوات الذي يمثله تعقيد الخوارزمية يمكن أن يزيد.
فيما يلي بعض الأمثلة التي قد تساعدك في تقدير حجم بعض الأرقام التي سنتعرض لها. لنأخذ العدد ١٠٠ مليار، أو ١٠١١، الذي يتكوَّن من الرقم ١ وخلفه ١١ صفرًا. إذا أخذت ١٠٠ مليار شطيرة هامبرجر ووضعتها متلاصقة بعضها بجانب بعض، يمكنك أن تلف الكرة الأرضية ٢١٦ مرة وتصل إلى القمر وتعود مرة أخرى.
عادة ما يُطلق على المليار من الشيء «جيجا»، على الأقل في أجهزة الكمبيوتر. بعد المليار — أو الجيجا — يأتي التريليون — أو «التيرا» — الذي يساوي ١٠٠٠ مليار، أو ١٠١٢. إذا بدأت العدَّ بعددٍ واحد في الثانية، فستحتاج إلى ٣١٠٠٠ سنة كي تصل إلى تريليون واحد. بالضرب في ١٠٠٠ أخرى، نصل إلى الكوادريليون، أو ١٠١٥، أو «البيتا»؛ يتراوح إجمالي النمل الذي يعيش على الأرض بين ١ و١٠ كوادريليون نملة، على حد قول عالِم الأحياء إي أو ويلسون. بعبارة أخرى، يتراوح عدد النمل على كوكب الأرض بين ١ و١٠ بيتا نملة.
بعد الكوادريليون، يأتي الكوينتليون أو «إكسا»؛ يساوي الكوينتليون ١٠١٨ وهو العدد التقريبي لحبيبات الرمال في ١٠ شواطئ كبرى. على سبيل المثال، تحتوي عشرة شواطئ بحجم شاطئ كوباكابانا على واحد إكسا من حبات الرمال. بالضرب مرة أخرى، نصل إلى ١٠٢١، أو واحد سكستليون، أو «زيتا». يبلغ عدد النجوم في الكون المرئي لنا واحد زيتا نجم. ننتهي من البادئات بعد «يوتا»، التي ترمز إلى ١٠٢٤، أي واحد سيبتليون. لكن الأعداد لا تتوقَّف عن الزيادة. فيُطلق على العدد ١٠١٠٠ «جوجول» — نعم، ربما تعرف شركة أطلقت على نفسها اسم هذا العدد بخطأ إملائي مقصود. بعد ذلك يأتي العدد ١٠ مرفوعًا إلى مقام الأُس للعدد جوجول — — ويساوي واحد جوجولبليكس.6

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

فئات التعقيد

تتألَّف أسرع فئة بين جميع فئات الخوارزميات من الخوارزميات التي تعمل في وقتٍ لا يتعدى الوقت الثابت، مهما كان حجم المدخلات. ونشير إلى هذا التعقيد بالرمز ؛ على سبيل المثال، خوارزمية تتحقَّق إن كان الرقم الأخير في عددٍ ما فرديًّا أو زوجيًّا لن تتأثر بحجم العدد وستعمل خلال الوقت الثابت. الرقم ١ في الرمز نابع من حقيقة أن الرمز يعني أن الخوارزمية لا تحتاج في تشغيلها إلى أكثر من مضاعف خطوة واحدة؛ أي عدد ثابت من الخطوات.
قبل أن نتناول فئة التعقيد التالية، نحتاج إلى الاطلاع سريعًا على طريقةٍ خاصة يمكن من خلالها أن تزيد العناصر أو تتقلص. إذا جمعت شيئًا مع نفسه عدة مرات، فأنت بذلك تضاعفه. وإذا ضربت شيئًا في نفسه عدة مرات، فأنت بذلك ترفعه إلى قوة أسية. وقد رأينا لتونا مدى الضخامة التي يمكن أن تصل إليها الأرقام ذات الأس، مثل ١٠١٢ (أو أكبر). ما قد لا يتضح على الفور هو مدى السرعة التي تؤدي بها عملية الرفع إلى الأس إلى تصاعد مذهل، وتلك ظاهرة تسمَّى «النمو الأسي».
سوف تتضح تلك النقطة من خلال قصة اختراع الشطرنج التي يرجَّح أن تكون ملفَّقة. طلب حاكم البلد الذي اختُرع فيه الشطرنج من مخترعه أن يطلب أيَّ هدية يريدها (للأسف في هذه القصص يكون البطل رجلًا). فأجاب أنه يريد حبَّة واحدة من الأرز في المربع الأول من لوحة الشطرنج، وحبتين في المربع الثاني، وأربعًا في المربع الثالث، وهكذا. ظن الملك أنه قد أفلت من الأمنية بسهولة وأعطاه ما أراد. ولكن للأسف، سرعان ما ساءت الأمور. فالسلسلة تزيد بمعدل أس ٢: ٢٠ = ١ في المربع الأول، ٢١ = ٢ في المربع الثاني، ٢٢ = ٤ في المربع الثالث، ومن ثم سيبلغ عدد الحبات في المربع الأخير ٢٦٣، وهو كمٌّ لا يمكن بلوغه بأي حال (إذ يساوي ٩٫٢٢٣٫٣٧٢٫٠٣٦٫٨٥٤٫٧٧٥٫٨٠٨ أو ما يقرب من ٩ كوينتليون).
يمكن أن يساعدنا النمو الأسي أيضًا في فهْم السبب وراء الصعوبة البالغة في طي قطعة من الورق عدة مرات. ففي كل مرة تطوي فيها الورقة، يتضاعف عدد طبقات الورقة المطوية. وبعد عشر طيات، ستحصل على ٢١٠ = ١٠٢٤ طبقة. وإذا كان سُمك الورقة ٠٫١ ملِّيمتر، فستحصل على رزمة مطوية يزيد سُمكها على ١٠ سنتيمترات. بصرف النظر عن القوة التي ستحتاج إليها لطي الورقة إلى طبقتين؛ فقد يستحيل طيها من المنظور الفيزيائي؛ لأن طول الشيء لا بد أن يكون أكبر من سُمكه حتى يمكن طيه.7
النمو الأسي هو السبب في زيادة قدرات أجهزة الكمبيوتر أكثر وأكثر على مدى السنين. فطبقًا لقانون مور، يتضاعف عدد الترانزستورات في الدائرة المدمجة كل عامين تقريبًا. وقد سُمي القانون بهذا الاسم نسبة إلى جوردون مور الذي أسَّس شركتي فيرتشايلد لأشباه الموصلات وإنتل. وقد قدَّم تلك الملاحظة في عام ١٩٦٥؛ وثبتت صحة القانون، ومِن ثَم انتقلنا من نحو ٢٠٠٠ ترانزستور في المعالج عام ١٩٧١ (معالج Intel 4004) إلى أكثر من ١٩ مليار ترانزستور في عام ٢٠١٧ (معالج 32-core AMD Epyc).8
بعدما اطلعنا على النمو، لنتناول العكس الآن. إذا كان لديك حاصل ضرب شيءٍ ما، فستستخدم القسمة لعكس العملية والحصول على القيمة الأصلية. إذا كان لديك القوة الأسية لشيءٍ ما، ، فكيف لنا أن نعكس العملية؟ إن معكوس الرفع إلى الأس هو «اللوغاريتم».

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

اللوغاريتم هو الإجابة على سؤال: «إلى أي قوة أسية ينبغي أن أرفع العدد كي أحصل على القيمة التي أريدها؟» والعدد الذي نرفعه يسمَّى «أساس» اللوغاريتم. فإذا كان السؤال هو: «إلى أي قوة أسية ينبغي أن أرفع العدد ١٠ للحصول على العدد ١٠٠٠؟» فستكون الإجابة هي ٣؛ لأن ١٠٣ = ١٠٠٠. بالطبع قد نريد رفع عدد مختلف، بمعنى أن نستخدم أساسًا مختلفًا. رمز اللوغاريتمات هو ، وهذا يتطابق مع السؤال: «إلى أي قوة أسية ينبغي أن أرفع العدد كي أحصل على النتيجة ؟» عندما تكون ، فإننا نسقط الرمز المنخفض فقط؛ لأن الأساس ١٠ مشترك في اللوغاريتمات، وبدلًا من كتابة ، نكتب ببساطة.
يوجد أيضًا أساسان مشتركان آخران. عندما يكون الأساس هو الثابت الرياضي ، فإننا نكتب . ويُطلق على الثابت الرياضي اسم «عدد أويلر» ويساوي تقريبًا ٢٫٧١٨٢٨. في العلوم الطبيعية، نقابل الرمز كثيرًا، وهذا يفسِّر تسميتها ﺑ «اللوغاريتم الطبيعي». أما الأساس المشترك الآخر فهو العدد ٢، وبدلًا من كتابة فإننا نكتب . تكثر اللوغاريتمات ذات الأساس ٢ في علوم الكمبيوتر والخوارزميات، ولكن ربما لا تُستخدم في غير هذين المجالين، على الرغم من أننا تعرَّضنا لها بالفعل. في مثال طي الورقة، إذا كانت لفيفة ورق تحتوي على ١٠٢٤ طبقة، فقد طُوِيَت مرات. وفي مثال لعبة الشطرنج، نتج عدد حبات الأرز عن عدد المضاعفات التي أجريناها، وهي .
والسبب في ظهور الرمز كثيرًا في الخوارزميات هو أنه يظهر عندما نحل مسألة عن طريق تقسيمها إلى مسألتين فرعيتين متساويتين؛ وتسمَّى هذه الخوارزمية «فرِّق تسُد» وتشبه في عملها طي ورقة إلى طبقتين. وتُعد أفضل الطرق فاعلية وكفاءة للبحث عن شيء وسط مجموعة عناصر مرتَّبة تحتوي على التعقيد . هذا مذهل إلى حدٍّ ما؛ فهو يعني أنه لكي تعثر على شيء ضمن مليار عنصر مرتَّب، فلست بحاجة إلا إلى عملية استكشاف دقيق وسط العناصر.
تأتي الخوارزميات التي تحتوي على تعقيد لوغاريتمي في المرتبة الثانية من حيث الأفضلية بعد الخوارزميات التي تعمل ضمن وقت ثابت. وتليهما الخوارزميات ذات التعقيد ، التي تسمَّى خوارزميات «الوقت الخطي»؛ لأن زمنها يزيد تناسبيًّا مع قيمة ؛ وهذا يعني أنها تزيد كمضاعفات لقيمة . لقد رأينا أن البحث عن عنصرٍ في مجموعةٍ غير مرتبة من العناصر يتطلب وقتًا يتناسب مع عدد العناصر، . انظر كيف زاد التعقيد مقارنة بالوقت الذي كانت فيه العناصر مرتَّبة؛ فقد يكون لتنظيم البيانات في المسألة تأثيرٌ كبير في طريقة حلها. وبوجه عام، يعتبر الوقت الخطي هو السلوك الأفضل الذي يمكن أن نتوقَّعه من الخوارزمية إذا كانت مضطرة إلى قراءة كل مدخلات المسألة؛ إذ ستتطلب تلك العملية الوقت من أجل العدد من المدخلات.
إذا جمعنا الوقت الخطي والوقت اللوغاريتمي، فسنحصل على خوارزميات «الوقت اللوغاريتمي الخطي»، حيث يزداد وقت تلك الخوارزميات بمقدار حاصل ضرب قيمة في اللوغاريتم الخاص بها، أي . وأفضل خوارزميات الفرز والترتيب — أي تنظيم العناصر — تحتوي على التعقيد . قد يبدو هذا مفاجئًا بعض الشيء؛ وعلى كل حال، ربما يتضح أنك إذا كان لديك العدد من العناصر وأردت مقارنة كل عنصر مع كل العناصر الأخرى، فسيتطلب هذا المقدار من الوقت، وهو أكبر من .9 إضافة إلى ذلك، إذا كان لديك العدد من العناصر وتريد ترتيبها، فبالتأكيد تحتاج إلى مقدار الوقت كي تفحص كل العناصر. إن ترتيب تلك العناصر يحتاج إلى ضرب ذلك العدد في عاملٍ أصغر من قيمة نفسها. وسنعرف كيف يمكن تنفيذ ذلك في موضعٍ لاحق في الكتاب.
الفئة التالية من التعقيد الحسابي هي مرفوعة إلى قوة أسية ثابتة، ؛ وتسمَّى هذه الفئة «التعقيد المتعدد الحدود». وتُعد خوارزميات الوقت المتعدد الحدود خوارزمياتٍ فعَّالة إلا إذا كانت قيمة كبيرة، ولكن نادرًا ما يحدث ذلك. عندما نحاول حل مسألة حسابية، فعادة ما نبتهج إذا توصَّلنا إلى خوارزمية ذات وقت متعدد الحدود.
يُطلق على التعقيد ذي الصيغة اسم «التعقيد الأسي». لاحظ الفرق بينه وبين التعقيد المتعدد الحدود حيث كان الأس ثابتًا، أما هنا فالأس هو الذي يتغير. لقد رأينا السرعة الهائلة للنمو الأسي. لن يبقى الكون طويلًا بما يكفي كي يرى إجابة الخوارزميات الأسية للمدخلات غير التافهة. تلك الخوارزميات مثيرة للاهتمام من الناحية النظرية؛ لأنها تبيِّن أنه يمكن العثور على حل. يمكننا بعد ذلك البحث عن خوارزميات أفضل ذات تعقيد أقل، أو ربما نتمكَّن من إثبات أنه لا يوجد خوارزميات أفضل، وفي تلك الحالة يمكننا أن نركن إلى شيء لا يرتقي إلى المثالية، مثل الحلول التقريبية.
يوجد شيء يتنامى أسرع من القوة الأسية، وهذا الشيء هو «المضروب». إذا كنت لم تصادف المضروب من قبل، فهو عبارة عن عدد طبيعي — نعبِّر عنه بالرمز ! — ناتج ببساطة عن حاصل ضرب جميع الأعداد الطبيعية من ١ إلى ذلك العدد بما فيها العدد نفسه: ١٠٠! = ١ × ٢ × ٣ × × ١٠٠. حتى لو لم تكن قد رأيت العدد ١٠٠! فربما رأيت العدد ٥٢! حتى من دون أن تعرفه. فهذا الرقم يعبِّر عن عمليات ترتيب عشوائي مختلفة لأوراق اللعب. وتحتوي الخوارزميات التي يُقاس وقت تشغيلها بالمضروب على «تعقيد مضروب».
على الرغم من أن الأعداد مثل ١٠٠! قد تبدو غريبة، فإنها تظهر في العديد من المواضع غير الغريبة وليس في ألعاب الورق فقط. لننظر إلى المسألة التالية على سبيل المثال: «إذا كانت لديك قائمة بعدة مدن والمسافات بين كل مدينتين فيها، فما أقصر طريق محتمل يجب أخذه لزيارة كل مدينة مرة واحدة ثم العودة إلى المدينة الأصلية؟» يُطلق على هذا المثال «مسألة البائع المتجول» والطريقة البديهية لحلها هي دراسة كل طريق محتمل يمرُّ على جميع المدن. للأسف، للتعبير عن العدد من المدن، سنكتب الرمز ! وسيتعذر التعامل مع المسألة بعد، لنقل، ٢٠ مدينة. توجد بعض الخوارزميات التي تحل المسألة بطريقةٍ أفضل بعض الشيء من ، ولكنها ليست عملية بالدرجة الكافية. قد يبدو ذلك مفاجئًا بالنسبة إلى مسألة مباشرة كتلك، ولكن الطريقة الوحيدة التي يمكن حلها بها خلال قدرٍ مقبول ومنطقي من الوقت هي إيجاد حلٍّ قد لا يكون الأمثل، ولكنه قريب إليه بدرجةٍ كافية. هناك العديد من المسائل الأخرى ذات الأهمية العملية الكبيرة التي «يستعصي حلها»، بمعنى أننا لا نعرف خوارزمية عملية لحلها حلًّا دقيقًا. على الرغم من ذلك، فالسعي وراء خوارزميات «تقريب» أفضل يُعد من المجالات النشطة في علوم الكمبيوتر.
في الجدول التالي، يمكن أن ترى قيمةَ دوالٍ متعددةٍ تندرج تحت فئات التعقيد التي تناولناها، تعبِّر عن قيمٍ مختلفة للرمز . يوضح الصف الأول قيم ويعبِّر أيضًا عن التعقيد الخطي؛ أما الصفوف التالية فتوضح فئات التعقيد المتصاعد. بما أن قيمة تتصاعد، فهذا يعني تصاعد قيم الدوال، ولكن مع اختلاف الطرق التي تتصاعد بها. فتنقلنا الدالة من المليون إلى الكوينتليون، ولكنها لا تُقارن بأي حال بالدالة ٢١٠٠ أو الدالة ١٠٠! وقد تركنا صفًّا فارغًا بعد الصف للفصل بين الخوارزميات العملية وغير العملية. والحد الذي يفصل بين النوعين هو الخوارزميات المتعددة الحدود، التي تبيَّن أنها عملية في الاستخدام كما رأينا. أما الخوارزميات ذات التعقيد الأعلى، فعادة ما لا تكون عملية في الاستخدام.
1000000 1000 100 10 1
19.93 9.97 6.64 3.32 0
1.9 × 107 9965.78 664.39 33.22 0
1012 1000000 10000 100 1
1018 109 1000000 1000 1
1
10105.5 10301 1.3 × 1030 1024 2
10106.7 4 × 102567 9.33 × 10157 3628800 1

جميع الحقوق محفوظة لمؤسسة هنداوي © ٢٠٢٢