الخوارزميات – تعريفها وتصميمها وتحليلها وتصنيفاتها

ملخص المحتوى

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

المحتويات

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

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

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

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

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

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

كلمة الخوارزمية نفسها مشتقة من عالم الرياضيات في القرن التاسع محمد بن موسى الخوارزمي.

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

تضمنت هذه الإجراءات الرسمية الوظائف التكرارية وحساب لامدا وآلات تورينج.

أصول المصطلح

الخوارزمية كلمة لها جذورها المأخوذة عن اسم عالم الرياضيات محمد بن موسى الخوارزمي في خطواته الأولى في ابتكار الخوارزميات. وكان الخوارزمي (780-850م) عالم رياضيات وكذلك الفلك والجغرافيا، وكان باحثًا في بيت الحكمة في بغداد بالعراق، واسمه الخوارزمي يعني أنه من مواطني “خوارزم”، وهي المنطقة التي كانت جزءًا من إيران الكبرى وهي الآن في أوزبكستان.

في عام 825، كتب الخوارزمي أطروحة باللغة العربية حول نظام الأرقام الهندوسية العربية، والتي تُرجمت إلى اللاتينية خلال القرن الثاني عشر تحت عنوان (Algoritmi de numero Indorum). هذا العنوان يعني “الخوريتمي على أعداد الهنود”، حيث كان “الخوريتمي” هو الترجمة اللاتينية لاسم الخوارزمي. وكانت كتب الخوارزمي أكثر كتب علماء الرياضيات قراءة على نطاق واسع في أوروبا في أواخر العصور الوسطى، وفي المقام الأول من خلال كتابه “الجبر”. في اللغة اللاتينية المتأخرة في العصور الوسطى، تحول مصطلح الخوارزمية باللاتينية والإنجليزية ليصبح معناه ببساطة “نظام الأرقام العشري”، ولم يعد يُعبر عن اسم الخوارزمي. وفي القرن الخامس عشر، تحت تأثير الكلمة اليونانية ἀριθμός أو بالعربية رقم، تم تغيير الكلمة اللاتينية إلى خوارزمية. كما شهد المصطلح الإنجليزي المقابل (Algorithm) “الخوارزمية” لأول مرة في القرن السابع عشر؛ وأخيرًا تم تقديم المعنى الحديث في القرن التاسع عشر.

في اللغة الإنجليزية، تم استخدام مصطلح “خوارزمية” لأول مرة في حوالي 1230م، ثم من قبل تشوسر في عام 1391. اعتمدت اللغة الإنجليزية المصطلح الفرنسي، ولكن حتى أواخر القرن التاسع عشر، اكتسبت “الخوارزمية” المعنى الذي لها الآن في اللغة الإنجليزية الحديثة.

تعريف الخوارزمية

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

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

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

الخوارزميات في علوم الحاسب

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

وفي الممارسة العملية، يتم تخزين الخوارزمية في واحدة أو أكثر من بنية بيانات البرنامج.

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

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

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

التراكيب الأساسية في الخوارزميات

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

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

وفيما يلي وصفًا موجزًا لهذه التراكيب الثلاثة:

1. التسلسل

تكون الخوارزمية عبارة عن مجموعة من التعليمات المتسلسلة، وهذه التعليمات إما أن تكون بسيطة أو من النوعين الآخرين (2، 3).

2. الاختيار

بعض المشاكل لا يمكن حلها بتسلسل بسيط للتعليمات، وقد تحتاج إلى اختبار بعض الشروط وتنظر إلى نتيجة الاختبار.

فإذا كانت النتيجة صحيحة تتبع مسار يحتوي تعليمات متسلسلة.

وإذا كانت النتيجة خاطئة تتبع مسار آخر مختلف من التعليمات.

وهذه الطريقة تسمى اتخاذ القرار أو الاختيار.

3. التكرار

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

وهذا ما يُطلق عليه التكرار.

شرح طريقة عمل الخوارزميات

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

والأعداد كما يلي:

1، 2، 3، 4، 5، 6، 7، 8، 9، 10، 11، 12، 13، 14، 15، 16، 17، 18، 19، 20

ونفرض أن المطلوب معرفة العدد الذي يمثل إجابة على سؤال معين.

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

وفي حالة التخمين الخطأ يحدد له موقع العدد الصحيح وما إذا كان:

  • أكبر من التخمين أو
  • أصغر من التخمين

الحل الاعتيادي

الأصل في هذه المسألة هو أن الشخص الثاني قد يقوم بعملية التخمين بشكل عشوائي لمعرفة العدد الذي اختاراه الشخص الأول في ذهنه، وقد يستمر في تكرار المحاولات حتى يخمن الرقم الصحيح. وأقصى عدد للمحاولات في هذه الحالة هو (20) محاولة إذا لم يحالفه الحظ في (19) محاولة وكان التخمين الصحيح هو في المحاولة الأخيرة. أو إذا بدأ بالتخمين بشكل تصاعدي متسلسل بدءًا من العدد (1) وكانت الإجابة الصحيحة هي العدد (20).

الحل بأسلوب الخوارزميات

أما في حالة تحديد موقع العدد الصحيح بعد كل تخمين، من حيث أنه أكبر من أو أصغر من التخمين المذكور، فيكون بالإمكان التوصل إلى الحل الصحيح بعد (5) محاولات على الأكثر.

ويمكن إجراء هذه التجربة عمليًا للتحقق من ذلك.

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

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

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

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

هناك مجموعة متنوعة من التمثيلات الممكنة ويمكن للمرء أن يعبر عن برنامج آلة تورينج معين كتسلسل من جداول الآلة، مثل المخططات الانسيابية ومخططات دراكون، أو كشكل من رموز الآلة البدائية.

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

وتشتهر بعض لغات البرمجة بتوفير البيئة النموذجية لكتابة شفرة الخوارزميات، ومن أهم هذه اللغات لغة برمجة بايثون.

فيما يلي شرحًا مفصلا لبعض هذه الطرق:

1. الخرائط الانسيابية

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

مثال توضيحي على الخرائط الانسيابية

من أشهر الأمثلة على الخوارزميات التي يتم التعبير عنها باستخدام خريطة انسيابية هي خوارزمية إقليدس لحساب القاسم المشترك الأكبر بين عددين A, B.

ويتم تنفيذ هذه الخوارزمية عبر سلسلة من عمليات الطرح المتتالية في حلقتين (بالإنجليزية: Loops) كما يلي:

  1. إذا كان الفحص B ≤ A ينتج عنه “نعم” تعين الخوارزمية قيمة الناتج: B ← B – A.
  2. بالمثل، إذا كان A > B فإن الخوارزمية تقوم بتعيين قيمة الناتج A ← A – B.

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

أصناف خرائط الانسياب

إن خرائط الانسياب هي تمثيل مصور للخوارزمية يوضح خطوات حل المشكلة من البداية إلى النهاية مع إخفاء التفاصيل لإعطاء الصورة العامة للحل.

ويمكن تصنيفا خرائط الانسياب إلى أصناف أربعة هي:

  • مخططات سير العمليات التتابعية أو (بالإنجليزية: Sequential Flowcharts).
  • مخططات سير العمليات ذات التفرع أو (بالإنجليزية: Branched Flowcharts).
  • ومخططات سير العمليات ذات التكرار والدوران أو (بالإنجليزية: Loop Flowcharts).
  • مخططات سير العمليات ذات الاختيار أو (بالإنجليزية: Selection Flowcharts).

2. الشفرة الوصفية أو الشفرة الكاذبة

الشفرة الوصفية أو الشفرة الكاذبة (بالإنجليزية: Pseudo Code) هي وسيلة للتعبير عن أو تمثيل الخوارزمية.

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

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

وبشكل عام لا توجد قاعدة محددة لكتابة هذا النوع من الشفرات.

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

3. الشفرة البرمجية

الشفرة البرمجية أو (بالإنجليزية: Code) هي شيفرة مكتوبة باستخدام لغة برمجة يفهمها الحاسوب.

وكل لغة لها قواعدها الخاصة، وتُستخدم للتعبير عن الخوارزمية.

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

5 REM Euclid’s algorithm for greatest common divisor

6 PRINT “Type two integers greater than 0”

10 INPUT A, B

20 IF B=0 THEN GOTO 80

30 IF A > B THEN GOTO 60

40 LET B=B-A

50 GOTO 20

60 LET A=A-B

70 GOTO 20

80 PRINT A

90 END

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

يُشير تصميم الخوارزميات إلى طريقة أو عملية رياضية لحل المشكلات.

يُعد تصميم الخوارزميات جزءًا من العديد من نظريات الحلول لأبحاث التشغيل، مثل البرمجة الديناميكية.

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

يكمن أحد أهم جوانب تصميم الخوارزمية في إنشاء خوارزمية تتمتع بوقت تشغيل فعّال.

خطوات نموذجية في تصميم الخوارزميات

يمكن تلخيص الخطوات النموذجية التي يتم اتباعها من أجل تصميم الخوارزميات كما يلي:

  1. تعريف المشكلة
  2. تطوير النموذج
  3. تحديد المواصفات
  4. كتابة الخوارزمية
  5. التحقق من صحة الخوارزمية
  6. تحليل الخوارزمية
  7. تنفيذ الخوارزمية
  8. اختبار الخوارزمية
  9. إعداد التوثيق

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

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

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

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

المعايير الأخرى هي قدرة الخوارزمية على التكيف مع أجهزة الكمبيوتر.

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

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

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

هذا يعني أن المبرمج يجب أن يعرف “لغة” فعّالة بالنسبة لعامل الحوسبة المستهدفة بالكمبيوتر.

خوارزمية إيجاد العدد الأكبر

تتمثل إحدى أبسط الخوارزميات في العثور على أكبر عدد في قائمة من الأعداد المرتبة عشوائيًا.

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

وصف الخوارزمية باستخدام لغة رفيعة المستوى

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

If there are no numbers in the set then there is no highest number.

Assume the first number in the set is the largest number in the set.

For each remaining number in the set: if this number is larger than the current largest number, consider this number to be the largest number in the set.

When there are no numbers left in the set to iterate over, consider the current largest number to be the largest number of the set.

ترجمة الوصف:

  1. إذا لم تكن هناك أعداد في المجموعة، فلن يكون هناك أعلى رقم.
  2. افترض أن العدد الأول في المجموعة هو أكبر عدد في المجموعة.
  3. لكل عدد متبقٍ في المجموعة: إذا كان هذا العدد أكبر من أكبر عدد حالي، فضع في اعتبارك أن هذا العدد هو أكبر عدد في المجموعة.
  4. عند عدم تبقي أعداد في المجموعة للتكرار، ضع في اعتبارك أن أكبر عدد حالي هو أكبر عدد في المجموعة.

الوصف شبه الرسمي للخوارزمية

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

فيما يلي الترميز الأكثر رسمية للخوارزمية في الشفرة الزائفة أو شفرة الجسر:

Algorithm LargestNumber

  Input: A list of numbers L.

  Output: The largest number in the list L.

  if L.size = 0 return null

  largest ← L[0]

  for each item in L, do

    if item > largest, then

      largest ← item

  return largest

يشير الرمز “←” إلى عملية التعيين.

على سبيل المثال، “item ← largest” تعني تغيير قيمة largest وإعطاءها قيمة item.

” return ” تُنهي الخوارزمية وتُعطي القيمة النهائية.

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

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

تم تطوير طرق لتحليل الخوارزميات للحصول على هذه الإجابات الكمية (أو التقديرات الكمية).

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

قد تُكمل خوارزميات المختلفة نفس المهمة بمجموعة مختلفة من التعليمات في وقت أو مساحة أو “جهد” أقل أو أكثر من غيرها. على سبيل المثال، تتفوق خوارزمية البحث الثنائي (ذات التكلفة O-log n) على البحث المتسلسل (ذات التكلفة On) عند استخدامها لعمليات بحث في القوائم في الجدول أو في المصفوفات التي يتم فرزها.

وتفسير ذلك في المثال التالي:

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

التحليل التجريدي والتحليل التجريبي للخوارزميات

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

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

الاختبار التجريبي مفيد لأنه قد يكشف عن تفاعلات غير متوقعة تؤثر على الأداء.

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

كفاءة تنفيذ الخوارزمية

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

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

كل مجال من مجالات العلوم لديه مشاكله الخاصة ويحتاج إلى خوارزميات فعّالة من أجل حل تلك المشاكل.

كما أنه غالبًا ما تتم دراسة المشكلات ذات الصلة في مجال واحد معًا.

ومن أشهر أمثلة الخوارزميات:

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

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

وهناك طرق مختلفة لتصنيف الخوارزميات، لكل منها مزاياها الخاصة.

فيما يلي أهم هذه التصنيفات:

تصنيف الخوارزميات حسب طريقة التنفيذ

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

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

تستخدم الخوارزمية التكرارية تركيبات متكررة مثل الحلقات (بالإنجليزية: Loops) وأحيانًا هياكل بيانات إضافية مثل Stacks لحل المشكلات المُعطاة.

تتناسب بعض المشاكل بشكل طبيعي مع تنفيذ واحد أو آخر.

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

كل نسخة تكرارية لها نسخة تكرارية مكافئة (ولكن ربما أكثر أو أقل تعقيدًا)، والعكس بالعكس.

الخوارزمية المنطقية

يمكن اعتبار الخوارزمية على أنها خصم منطقي خاضع للرقابة. يمكن التعبير عن هذه الفكرة على النحو التالي:

خوارزمية = تحكم + منطق

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

الخوارزميات التسلسلية والمتوازية والموزعة

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

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

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

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

يمكن موازاة بعض خوارزميات الفرز بكفاءة، ولكن تكلفة الاتصال الخاصة بهم مكلفة. والخوارزميات التكرارية متوازية بشكل عام. لا تحتوي بعض المشكلات على خوارزميات متوازية وتسمى في هذه الحالة مشكلات تسلسلية أصلية أو خالصة.

الخوارزميات الحتمية وغير الحتمية

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

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

بينما تصل العديد من الخوارزميات إلى حل دقيق، تبحث خوارزميات التقريب عن تقريب أقرب إلى الحل الحقيقي.

يمكن الوصول إلى التقريب إما باستخدام استراتيجية حتمية أو عشوائية.

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

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

تعمل الخوارزمية الكمية على نموذج واقعي للحساب الكمي.

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

تصنيف الخوارزميات حسب نموذج التصميم

طريقة أخرى لتصنيف الخوارزميات هي بحسب نموذج التصميم أو المنهيجة.

هناك عدد معين من النماذج، يختلف كل منها عن الآخر.

علاوة على ذلك، تتضمن كل فئة من هذه الفئات العديد من أنواع الخوارزميات المختلفة.

بعض النماذج الشائعة هي كما يلي:

خوارزمية البحث الشامل

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

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

خوارزميات فرق تسدد

تقوم خوارزمية فرق تسد (بالإنجليزية: Divide and Conquer) بشكل متكرر بتقليص المشكلة إلى مشكلة واحدة أو أكثر من المشكلات المثيلة للمشكلة الأصلية ولكنها أصغر منها، وتقوم بذلك عادة بشكل متكرر حتى تكون المشكلات صغيرة بما يكفي لحلها بسهولة.

أحد الأمثلة على خوارزمية فرق تسد خوارزمية دمج الفرز.

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

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

من أمثلة خوارزمية الاختزال هي خوارزمية البحث الثنائية.

خوارزميات البحث والتعداد

يمكن تصميم العديد من المشكلات (مثل لعب الشطرنج) على أنها مشكلات في الرسوم البيانية.

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

تشمل هذه الفئة أيضًا خوارزميات البحث والتعداد الفردي وخوارزميات الترابط والتراجع.

الخوارزمية العشوائية

هذه الخوارزميات تجعل بعض الخيارات عشوائية (أو عشوائية زائفة).

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

هناك فئتان رئيسيتان أو أساسيتان من هذه النوع وهي:

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

خوارزمية مونتي كارلو أو (بالإنجليزية: Monte Carlo) تعطي إجابة صحيحة ذات احتمالية عالية.

خوارزميات لاس فيغاس

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

خوارزميات الحد من التعقيد

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

خوارزميات التتبع العكسي

في هذا النهج، يتم إنشاء حلول متعددة بشكل متزايد ويتم التخلي عنها عندما يتم تحديد أنها لا يمكن أن تؤدي إلى حل كامل صالح.

تصنيف الخوارزميات حسب أسلوب التحسين

يوجد تصنيف أكثر تحديدًا للخوارزميات بحسب أسلوب التحسين المستخدم في مشكلات التحسين أو (بالإنجليزية: Optimization).

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

خوارزميات البرمجة الخطية

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

خوارزميات البرمجة الديناميكية

عندما تُظهر المشكلة الهياكل الفرعية المثلى – بمعنى أنه يمكن بناء الحل الأمثل للمشكلة من الحلول المثلى للمشكلات الفرعية – والمشكلات الفرعية المتداخلة، مما يعني أن المشاكل الفرعية نفسها تُستخدم لحل العديد من حالات المشكلة المختلفة، فإن نهجًا أسرع يسمى البرمجة الديناميكية (بالإنجليزية: Dynamic Programming) يتجنب حلول إعادة الحوسبة التي تم حسابها بالفعل.

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

يكمن الاختلاف بين البرمجة الديناميكية وخوارزميات التكرار المباشرة في التخزين المؤقت أو التذكر للطلبات التكرارية.

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

الخوارزميات الجشعة

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

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

الطريقة الإرشادية

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

تتضمن هذه الخوارزمية:

  • البحث المحلي أو (بالإنجليزية: Local Search)،
  • والبحث المحظور أو (بالإنجليزية: Tabu Search)،
  • التلدين المحاكي أو (بالإنجليزية: Simulated Annealing)،
  • والخوارزمية الجينية أو (بالإنجليزية: Genetec Algorithm).

البعض من هذه الخوارزميات، مثل التلدين المحاكي، هي خوارزميات غير حتمية بينما البعض الآخر، مثل البحث المحظور، حتمية.

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

تصنيف الخوارزميات حسب مجال الدراسة

لكل مجال من مجالات العلوم مشاكله الخاصة ويحتاج إلى خوارزميات فعّالة.

غالبًا ما يتم دراسة المشكلات ذات الصلة في مجال واحد معًا.

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

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

تصنيف الخوارزميات حسب درجة التعقيد

يمكن تصنيف الخوارزميات حسب مقدار الزمن أو الوقت الذي تحتاجه لإكمال المهمة مقارنةً بحجم المدخلات:

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

الوقت اللوغاريتمي: إذا كان الوقت دالة لوغاريتمية لحجم الإدخال. على سبيل المثال خوارزمية البحث الثنائي.

الوقت الخطي: إذا كان الوقت متناسبًا طرديًا مع حجم الإدخال. على سبيل المثال اجتياز قائمة.

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

الوقت الأسي: إذا كان الوقت دالة أسية لحجم الإدخال.

على سبيل المثال خوارزمية البحث الشامل أو المعروفة باسم التوليد والاختبار.

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

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

يمكن أن تعني الصفة “مستمر” عند تطبيقها على كلمة “خوارزمية”:

  1. خوارزمية تعمل على بيانات تمثل كميات مستمرة، على الرغم من أن هذه البيانات ممثلة بتقديرات منفصلة – يتم دراسة هذه الخوارزميات في التحليل العددي؛ أو
  2. خوارزمية على شكل معادلة تفاضلية تعمل بشكل مستمر على البيانات، تعمل على كمبيوتر تمثيلي.

يمكن الاطلاع على بعض نماذج خوارزميات تنقيب البيانات المنشورة في كتاب تنقيب البيانات، ومنها:

خوارزميات التصنيف والتنبؤ وطريقة عملها وأنواعها

موسوعة تنقيب البيانات – مركز البحوث والدراسات متعدد التخصصات

أسئلة شائعة

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

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

ما هي التراكيب الأساسية في الخوارزميات؟

يوجد ثلاث تراكيب أساسية في الخوارزميات وهي كما يلي:
1. التسلسل
2. الاختيار
3. التكرار

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

أشهر أنواع الخوارزميات هي:
1. خوارزميات البحث والفرز والترتيب والدمج
2. الخوارزمية الرقمية
3. خوارزميات الرسم البياني
4. خوارزمية السلسلة
5. الخوارزمية الهندسية الحاسوبية
6. الخوارزمية التوافقية
7. خوارزميات الذكاء الاصطناعي
8. خوارزمية التشفير

وغيرها من الخوارزميات الأخرى.

المراجع

  • Leeuwen, Jan (1990). Handbook of Theoretical Computer Science: Algorithms and complexity. Volume A. Elsevier. p. 85. ISBN 978-0-444-88071-0.
  • Van Heijenoort, Jean (2001). From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931 ((1967) ed.). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7, 3rd edition 1976[?], ISBN 0-674-32449-8 (pbk.)
  • أساسيات الخوارزميات، ترجمة وإعداد: د. م. مصطفى عبيد، مركز البحوث والدراسات متعدد التخصصات، 2020.
الخوارزميات - تعريفها وتصميمها وتحليلها وتصنيفاتها
الخوارزميات – تعريفها وتصميمها وتحليلها وتصنيفاتها
error:
Scroll to Top