الخوارزمية

خوارزميه

Algorithm - Algorithme

الخوارزمية

الخوارزمية algorithm هي: «مجموعة القواعد الدقيقة لمعالجة حاسوبية، تهدف إلى الحصول على نتائج محددة اعتباراَ من معطيات ابتدائية».

فعندما يُطلب من خبير في البرمجة أن يصنع برنامجاً، سواء لحل مسألة رياضية أو لاختراع لعبة أو لبناء برنامج تطبيقي يخدم أغراضاً محددة، فإن أول ما يفكر به المتخصص، بعد فهم المسألة ودراستها دراسة كافية، هو وضع استراتيجية للحل بطريقة تمكّن، فيما بعد، من ترجمة هذه الاستراتيجية إلى لغة يفهمها الحاسوب. تسمى هذه الاستراتيجية في أوساط المختصين بالبرمجة باسم «الخوارزمية». وقبل الخوض في التعريف الدقيق لمفهوم الخوارزمية، لابد من الإشارة إلى أصل التسمية الذي يعود إلى العالم المسلم محمد بن موسى الخوارزمي، وأصله كما يدل اسمه من خوارزم، وقد عاش في بغداد من سنة 780م إلى 847م في عهد الخليفة المأمون. وقد برع هذا العالم في الرياضيات والفلك، وترك بصمات في التراث الحضاري العالمي، فقد وضع الخوارزمي مبادئ علم الجبر وألف كتاب «الجبر والمقابلة»، وهو أول من سمّى علم الجبر بهذا الاسم، ثم انتشر هذا العلم وانتقل اسمه إلى جميع اللغات تقريباَ. ألف الخوارزمي كتاباً في الحساب، ترجم إلى اللاتينية بعد ثلاثة قرون تحت عنوان Algoritmi de nemero indriun، ثم أطلق على جداول الضرب والقسمة والحساب العشري اسم Algorisms. ظلت هذه الكلمة متداولة في أوربا حتى أصبحت مصطلحاَ يحمل مدلولاً جديداً مرتبطاً بالبرمجة Algorithm.

إن الصفات الأساسية التي تملكها الخوارزميات هي:

ـ أنها تتألف من مجموعة من القواعد الدقيقة التي يفهمها الجميع.

ـ تطبق على معطيات قابلة للتغيير.

ـ تسعى لبناء نتيجة نحصل عليها عندما يكون اختيار المعطيات ناجحاً.

إن التعريف الوارد في المقدمة غير كاف من وجهة نظر المعلوماتيين، إذ يعرِّف Knuth في كتابه «فن البرمجة» الخوارزمية، بأنها مجموعة من القواعد (أو التعليمات) التي تتميز بالصفات الآتية:

ـ يجب أن تكون هذه المجموعة منتهية، وتنتهي بعد عدد منته من العمليات.

ـ يجب أن تكون محددة ودقيقة، بمعنى أن كل تعليمة يجب أن توصف من دون لَبْس.

ـ يجب تحديد مجال تعريف المعطيات المُدخلة إن وجدت (أعداد صحيحة، حقيقية، أحرف،...).

ـ يجب أن يكون هنالك نتيجة (واحدة على الأقل).

ـ يجب أن تكون فعّالة، أي أن يتمكن شخص من تنفيذ العمليات كلها في وقت منته باستخدام الإمكانات اليدوية (دون حاسوب).

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

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

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

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

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

من الممكن كذلك الحصول على النتيجة ذاتها بتطبيق الطريقة الروسية في الضرب، حيث يكتب العددان على سطر واحد، ثم يقسم العدد الأول على 2، ويوضع ناتج القسمة تحته مع إهمال باقي القسمة، إن لم يكن صفراً، ويضرب العدد الثاني بـ2 ويوضع الجداء تحته، تكرر العملية حتى يصبح الرقم في نهاية عمود العدد الأول مساوياً 1، ولإيضاح هذه الطريقة سنستخدمها في إجراء عملية الضرب 45 × 19.

في نهاية العملية تحذف الأسطر التي تحتوي عدداً زوجياً في عمود العدد الأول، ثم تجمع العناصر الموجودة في عمود العدد الثاني. ففي مثالنا نحذف السطر الذي يحتوي 22 و2 ثم نجمع:

19 + 76 + 152 + 608 = 855

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

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

طرائق التعبير عن الخوارزمية

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

وهنا اقترحتُ عدة طرائق بعضها نصّية (عبارات) والأخرى بيانية (مخططات).

- الطرائق النصية

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

أ ـ اللغة الخوارزمية

تُعرّف في هذه اللغة الخوارزمية العناصر الآتية:

المتحول: وهو الغرض الذي تجري معالجته ضمن الخوارزمية، وتكون قيمته متحولة (قابلة للتغيير)، ويعرف باسم خاص متميز.

الثابت: وهو غرض قيمته غير متغيرة طوال البرنامج، ويعر ف باسم خاص.

الصيغة: وتتألف من متحولات وثوابت وعمليات حسابية أو منطقية.

يمكن التعبير عن مسار الحل لمسألة  أو توصيف خوارزمية بوساطة التعليمات أو الأوامر الأساسية الخمسة الآتية:

1ـ تعليمة القراءة: وهي قراءة قيمة من الدخل (من لوحة المفاتيح) لوضعها في خانة ذاكرة، وشكل التعليمة:

اقرأ < اسم المتحول >

2ـ تعليمة الكتابة: وهي كتابة قيمة معينة على وحدة الخرج (الشاشة)، وشكل التعليمة:

اكتب < صيغة >

3ـ تعليمة الإسناد: وهي إسناد قيمة محددة أو نتيجة صيغة لمتحول (خانة ذاكرة)، وشكل التعليمة:

< صيغة >   ¬  < اسم المتحول >

4ـ التعليمة الشرطية: وترد بأحد الشكلين الآتيين:

أ ـ التنفيذ بشرط: ونعبر عن ذلك كما يأتي:

ب ـ التعليمة الشرطية الاختيارية: وتسمح بالاختيار بين طريقتي تنفيذ وذلك وفق شرط.

5 ـ التعليمة التكرارية: وتستعمل لتكرار مجموعة من التعليمات مادام شرط محدد محققا، أي يتكرر تنفيذ مجموعة من العمليات ما دامت الصيغة المنطقية للشرط صحيحة.

ـ كيفية الوصول إلى الخوارزمية؟

للوصول إلى وضع الخوارزمية المناسبة لحل مسألة معينة، تُتَّبع الخطوات الآتية:

1- فهم المسألة وتحليلها بدقة، أي معرفة المدخلات (المعطيات) المطلوب معالجتها والمخرجات (النتائج) المطلوب الحصول عليها، وصياغة هذه المعلومات بوضوح ما أمكن، ويمكن استخدام العلاقات الرياضية التي توصف علاقة الدخل بالخرج (إن وجدت مثل هذه العلاقات).

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

3- عند الوصول إلى أدنى المستويات تنتج خوارزمية كاملة مكتوبة باللغة الخوارزمية، واعتماداً على هذه الخوارزمية يجري الترميز باللغة المناسبة (....,Java, C++, C, Pascal).

ـ الطرائق البيانية

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

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

مثال :

تستخدم في هذا المثال هذه الرموز للتعبير عن خوارزمية لقسمة عدد صحيح على عدد صحيح آخر. ليكن العدد المقسوم n والعدد القاسم d والناتج m والباقي r. هنا يجري طرح d من r طالما أن r أكبر من d وتكرر العملية حتى يغدو r أصغر من d فيكتب الناتج m والباقي r.

تعقيد الخوارزميات Algorithm Complexity

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

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

1- دراسة تعقيد الخوارزميات

في دراسة تعقيد الخوارزميات يكون الاهتمام بنوعين من التعقيد:

1ـ التعقيد الحجمي أو المكاني space complexity: ونقصد به تقدير حجم الذواكر اللازم  للخوارزمية.

2ـ التعقيد الزمني time complexity: ونقصد بذلك التقدير الزمني. وهنا، يجب البدء أولاً باختيار واحدة لقياس هذا التعقيد، وقد اقترح بعضهم اعتبار مدة تنفيذ البرنامج واحدة للقياس، لكن هذه الواحدة لا تصلح بسبب اختلاف الحواسيب وسرعة معالجاتها. كما اقترح البعض الآخر اعتبار عدد التعليمات واحدة للقياس، لكن هذه الواحدة لا تصلح أيضاً بسبب اختلاف عدد التعليمات التي نكتب بها البرنامج باختلاف لغة البرمجة المستخدمة وأسلوب المبرمج. وربما كان أفضل ما اقترح في هذا المضمار هو عدد العمليات الأساسية المستخدمة في الخوارزمية، لأنه يعطي فكرة جيدة عن أداء الخوارزمية، على وجه مستقل عن تفاصيـل التنفيذ، ولكن ما المقصود بالعمليات الأساسية؟

تختلف العمليات الأساسية باختلاف طبيعة الخوارزمية بحسب ما يبينه الجدول 1.

وبدهي أن عدد العمليات الأساسية يختلف باختلاف حجم معطيات الدخل.

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

يستخدم عادة تدوين لاندو Landau للدلالة على التعقيد، فإذا كان التعقيد من رتبة n³ يُقال أن التعقيد هو O (n³).

2- أهمية تعقيد الخوارزميات عملياً

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

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

3- مثال تحليل خوارزمية:

يقدر تعقيد البرامج تقديراً عملياً بحساب العدد الأعظمي للدوران في الحلقات التعليمات التكرارية بدلالة حجم معطيات الدخل.

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

لتكن لدينا مصفوفتان من الأعداد الحقيقية B,A و ، (A= (a_ij)  B = (b_ij)) بُعد كل منهما هو n * n.

وليكن المطلوب حساب  المصفوفة C = A * B.

يعطى ضرب مصفوفتين بالصيغة الرياضية الآتية:

 الخوارزمية

إن العملية الأساسية هنا هي الضرب، وهناك لكل عنصر من المصفوفة C، n عملية ضرب داخل حلقة k.

ولما كان هناك n² عنصراً في C فإن عدد عمليات الضرب هو n³.

ومن ثَمَّ فإن درجة تعقيد الخوارزمية هو O (n³).

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

أنواع الخوارزميات

يمكن تصنيف الخوارزميات بحسب الوظيفة التي تقوم بها، والمسألة الرئيسية التي تحلها، ومن ثم يمكن أن نتكلم مثلاً عن:

ـ خوارزميات البحث search  algorithm (هدفها البحث عن عنصر معطيات محدد في بنية معطيات)،

ـ خوارزميات الفرز sort  algorithm (هدفها ترتيب مجموعة من عناصر المعطيات ترتيباً متتالياً اعتماداً على أحد بنود العناصر أو على اجتماع عدة بنود محددة).

وغير ذلك.

كما يمكن اتباع أسلوب آخر في التصنيف يعتمد على التقنية المستخدمة في تشكيل التعليمات وتسلسلها، فنتكلم مثلاً عن:

ـ الخوارزميات التتابعية sequential algorithm (يجري تنفيذها لاحقاً وفق تتابع التعليمات وبترتيب معين)،

ـ الخوارزميات المتوازية parallel algorithm (يجري تنفيذ أكثر من جزء منها في آن واحد معاً، ويجري ذلك عادة على عدة معالجات)،

ـ الخوارزميات الرجوعية backtracking algorithm (وهي خوارزميات تستخدم لإيجاد حل ضمن مجموعة محاولات ممكنة، حيث تمثل المحاولات على شكل فروع في شجرة. يجري تجريب أحد الفروع، فإن لم نجد الحل نعود إلى الوراء لنختار مساراً آخر نجربه وهكذا، حتى نعثر على المسار المناسب)،

ـ الخوارزميات العَوْدية recursive algorithm (وهي خوارزميات تستخدم ضمن تعليماتها استدعاءً للخوارزمية نفسها)، وغير ذلك.

غيداء ربداوي 

- Thomas H.Cormen, Charles E.Leiserson, & Ronald L.Rivest, Introduction to Algorithms (McGraw Hill 1990).

- Ellis Horowitz, Sartaj Sahni, & Sanguthevar Rajasekaran, Computer Algorithms/C++ (Computer Science Press 1997).

التصنيف : الرياضيات و الفلك

النوع : علوم

المجلد: المجلد التاسع

رقم الصفحة ضمن المجلد : 38

آخر أخبار الهيئة :

معجم المصطلحات

الأطلس الجغرافي

البحوث الأكثر قراءة

اصدارات الموسوعة العربية

أسماء الباحثين

هل تعلم ؟؟

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

• - هل تعلم أن الإبل تستطيع البقاء على قيد الحياة حتى لو فقدت 40% من ماء جسمها ويعود ذلك لقدرتها على تغيير درجة حرارة جسمها تبعاً لتغير درجة حرارة الجو،

• - هل تعلم أن أبقراط كتب في الطب أربعة مؤلفات هي: الحكم، الأدلة، تنظيم التغذية، ورسالته في جروح الرأس. ويعود له الفضل بأنه حرر الطب من الدين والفلسفة.

• - هل تعلم أن المرجان إفراز حيواني يتكون في البحر ويتركب من مادة كربونات الكلسيوم، وهو أحمر أو شديد الحمرة وهو أجود أنواعه، ويمتاز بكبر الحجم ويسمى الش

• هل تعلم أن الأبسيد كلمة فرنسية اللفظ تم اعتمادها مصطلحاً أثرياً يستخدم في العمارة عموماً وفي العمارة الدينية الخاصة بالكنائس خصوصاً، وفي الإنكليزية أب

• - هل تعلم أن أبجر Abgar اسم معروف جيداً يعود إلى عدد من الملوك الذين حكموا مدينة إديسا (الرها) من أبجر الأول وحتى التاسع، وهم ينتسبون إلى أسرة أوسروين

• - هل تعلم أن الأبجدية الكنعانية تتألف من /22/ علامة كتابية sign تكتب منفصلة غير متصلة، وتعتمد المبدأ الأكوروفوني، حيث تقتصر القيمة الصوتية للعلامة الك

شراء النسخة الورقية