تحليل وتصميم الخوارزميات
تعريف الخوارزمية
سُمِّيت جداول الضرب والقسمة قديماً بالخوارزميات، وبعد أن تقدمت الحضارات واختُرِعت الحواسيب ارتبطت الخوارزميات بها ارتباطاً تاماً، وقد عُرِّفت بعدها الخوارزمية بأنّها مجموعة من الخطوات التي يستطيع الشخص الوصول عن طريقها إلى حلٍّ محدد؛ حيث تعالج الخوارزمية المعطيات والبيانات، وتجدر الإشارة هنا إلى أنّ هذه البيانات لا تقتصر على الأرقام والأعداد، بل تفوق ذلك لتشمل الرسومات، والنصوص، والأصوات، والصور،[١] وبصورة أخرى فإنّ الخوارزميّة هي قائمة من القواعد والتعليمات التي يجب اتباعها لحل مشكلة معينة، وممّا يجدر ذكره أن الترتيب والتنسيق فيها مهم جداً؛ إذ لا يُمكن الوصول إلى الحلّ المنشود إلّا باتّباع الخطوات والتعليمات بالترتيب الذي وردت عليه،[٢] كما لا يجوز تكرار أي خطوة، أو حتّى تجاهل إحداها.[١]
وأول من ابتكر مفهوم الخوارزميات هو العالم الرياضي المسلم الشهير محمد بن موسى الخوارزمي. عاش الخوارزمي في مدينة بغداد بين عامي 780-847م، وكان ذلك في عهد الخليفة المأمون، وقد برز في الرياضيات والفلك، ومن أهمّ إنجازاته الرياضية وضعه لمبادئ علم الجبر، وتأليف كتابه الشهير الجبر والمقابلة، ومنه أُخِذت كلمة الجبر لتُتَرجَم إلى جميع لغات العالم، كما قدّم كتاباً آخر في الحساب، نُقِل إلى اللغة اللاتينية بعنوان (Algoritmi de nemero lndriun).[١]
شروط الخوارزمية
يجب أن تتوفر في الخوارزمية مجموعة من الشروط، هي:[٣]
- المدخلات (Input ): يجب أن تكون المدخلات صفراً، أو أكثر من ذلك.
- المخرجات ( Output): يجب أن تكون المخرجات قيمةً على الأقل.
- الوضوح (Definiteness): يجب أن تكون الخطوات واضحة وغير مبهمة، حتى تُفهَم بصورة سلسة لدى الناس، فمثلاً هذه العبارة: (Add 6 or 7 to x) غير واضحةK وبهذا فهي لا تستوفي شروط الخوارزمية.
- المحدودية (Finiteness): تُحلّ كل خطوة من خطوات الخوارزمية بوقت وزمن معين، فمثلاً العبارة التالية: (قسمة الرقم 10 على الرقم3 بدقة عالية)، تعد غير محدودة ، وبهذا فهي لا تستوفي شروط الخوارزمية ولا يسمح وجودها في البرنامج.
- المحلولية (Effectiveness): يجب أن تكون كل خطوة ممكنة الحل، فعلى سبيل المثال تعد العبارة التالية: (3/0)عبارة مستحيلة الحل، لأنها قيمة غير معرفة.
كيفية تحليل الخوارزمية
يعرف تحليل الخوارزمية (بالإنجليزية: Algorithm Analysis) على أنه تحديد كفاءة الخوارزمية وجودتها، ومن ثم تطويرها بشكل أفضل، ويقاس مدى إنجازية وجودة الخوارزمية بمقياسين، هما:[٣]
- مقياس تعقيدات الفراغ (Space Complexity): هو عبارة عن كمية الذاكرة التي يحتاجها البرنامج (من تشغيله إلى حين إكماله)، ويُينى هذا النوع على قسمين، هما:
- القسم الثابت: هو القسم المستقل المخصص للمتغيرات البسيطة والمركبة، والثوابت والتعليمات.
- القسم المتغير: يتكون هذا القسم من الفراغ الذي يحتاجه البرنامج من المتغيرات المركبة التي يعتمد حجمها على المسألة التي يُراد حلها.
- تعقيدات الوقت (Time complexity): هي عبارة عن كمية الزمن اللازم لتكوين وتشكيل برنامج لحين انتهائه، ويتكون من: (T(P)= Const tp)
- حيث إنّ الرمز (tp): يمثل وقت تشغيل البرنامج، والرمز (Const): ثابت يوقت التأليف.
تصميم الخوارزمية
المخططات
يُعرَّف المخطط (بالإنجليزيّة: Graph) بأنه مجموعة من العناصر التي تعبر عن الرؤوس (بالإنجليزيّة: Vertices)؛ بحيث ترتبط هذه العناصر مع بعضها البعض بعلاقات تسمى بالحواف (بالإنجليزيّة: Edges)، وتُقسَم المخططات إلى ثلاثة أنواع، هي:[٣]
- المخطط غير المتجه: هو عبارة عن المخطط الذي ترتبط عناصره مع بعضها البعض بطريقة غير مرتبة، وبهذا فإن الاتجاهات مهمشة.
- المخطط المتجه: هو عبارة عن المخطط الذي ترتبط عناصره مع بعضها البعض ضمن نمط وترتيب معين، وبهاذ فإن الاتجاهات (الأسهم) ضرورية ومهمة جداً.
- المخطط المشترك: هو عبارة عن المخطط الذي يتضمن كلا النوعين السابقين، فمن العناصر ما يربطها علاقة متجهة ومنها ما يربطها علاقة غير متجهة.
المسار
المسار هو عبارة عن مجموعة من الخطوط المستقيمة الواصلة بين نقطتين في المخطط، مع التنبيه إلى أن المسار لا يُكتَب ضمن أقواس المجموعة، أما طول المسار فهو عدد الخطوط الواصلة بين كل نقطتين في المخطط، ويُحسَب طول المسار عن طريق حساب عدد الأزواج أو عدد المستقيمات في المخطط، مع مراعاة وجود أكثر من مسار بين النقاط في المخططات المتجهة.[٣]
المخطط المتصل وغير المتصل
المخطط المتصل هو عبارة عن المخطط الذي يحتوي على مسارات بين كل نقطتين في المخطط، أما المخطط غير المتصل فهو المخطط الذي يحتوي على بعض العناصر غير المتصلة (المنفصلة).[٣]
طريقة الجموح
تعمل هذه الطريقة على حل مسائل الأمثلة التي غالباً ما تقوم بتكبيرها لشيء معين أو تصغيرها لنفس الشيء، كما هو الحال في الفوز والخسارة، وتحتوي هذه المسائل على العناصر الآتية، وهي:[٣]
- دالة الهدف (بالإنجليزيّة: Objective Function)؛ بحيث يكون الحل ضمن شروط وقيود معينة للمسألة، وأفضل الحلول المقترحة والممكنة يُسمّى الحل الأفضل.
- تُسمّى مجموعة القيود بالإنجليزيّة بـ (Constraints)، ويُسمّى الحل الذي يوصل إلى أحسن دالة هدف بالحل الأمثل.
طرق كتابة الخوارزمية
تصاغ الخوارزمية بعدة طرق، بحيث تختلف هذه الطرق في بساطة الفهم والدقة، ومن أهمّ هذه الطرق ما يأتي:[١]
- صياغة الخوارزمية باللغة الطبيعية المستخدمة يومياً: يتم من خلال هذه الطريقة ترتيب خطوات الحل باللغة المستخدمة يومياً؛ سواءً كانت هذه اللغة هي العربية أو الإنجليزية، ومن الأمثلة البسيطة على هذه الطريقة المثال الآتي:
مثال: خوارزمية الاستيقاظ التي تبين الخطوات من لحظة الاستيقاظ من النوم إلى حين الذهاب إلى العمل:[١]
الحل:
- البداية.
- النهوض من الفراش.
- خلع ملابس النوم.
- الاستحمام.
- تجفيف الجسم من الماء.
- ارتداء ملابس نظيفة.
- تناول وجبة الفطور.
- الذهاب إلى العمل.
- النهاية.
يُلاحَظ في هذا المثال أنّ ترتيب الخطوات وعدم الاستغناء عن أي خطوة أمر مهمّ لتنفيذ الخوارزمية وإتمامها.
- صياغة الخوارزمية بلغة رمزية خاصة: تُبنى هذه الطريقة على أسس ومفاهيم رياضية، ومن أهم الطرق الرمزية التي تمثّل الخوارزميات هي لغات البرمجة سي (بالإنجليزيّة: C)، والترميز الرياضي للمفاهيم بعدة أساليب كالأسلوب البياني.
- صياغة الخوارزمية بطريقة بيانية: تُبنى هذه الطريقة على أسس هندسية، بحيث يتم تنفيذها عن طريق الأشكال الهندسية، وتعد المخططات الانسيابية من أكثر المخططات استخداماً في تنفيذ الخوارزميات.
الفرق بين الخوارزمية والبرنامج
هناك فرق بين البرنامج والخوارزمية؛ من حيث النظرية الاحتسابية، فالخوارزمية تحقق جميع الشروط التي تم ذكرها سابقاً (الشروط الخمسة)، ويمكن وصف الخوارزمية بعدة عبارات كلغة الخوارزمية، والمخططات الانسيابية، أما البرنامج فلا يحقق الشرط الثالث، ويوصَف البرنامج بلغة الحاسوب، ومن هنا فإن:[٣]
- البرنامج=خوارزمية هيكل بياني يبين أسلوب لتنظيم البيانات.
ويتطور البرنامج بعدة خطوات ومراحل، هي:[٣]
- توصيف المتطلبات: وذلك عن طريق تحديد المدخلات والمخرجات.
- التصميم: هو عبارة عن تحديد العمليات الرئيسية التي تنطبق على كل هيكل بياني، مع افتراض وجود أجهزة تعالج العمليات.
- التحليل: هو مقارنة الخوارزميات التي توصل للحل نفسه، تبعاً لمقاييس معينة لاختيار الأفضل والأجود من بين هذه الخوارزميات، وما يجب التنبيه إليه هو أن التحليل يصلح الأخطاء بناءً على تعقيدات الخزن، أما بالنسبة للتحسين فهو يعالج المشاكل ويصلح الأخطاء بناءً على النتائج التي تظهر في آخر البرنامج.
- التشفير: في هذه الخطوة يتمّ تحديد التمثيل البياني، ثمّ تحديد الإجراءات، ومن ثمّ كتابتها لكل عملية، ثمّ تكوين نسخة كاملة متكاملة للبرنامج.
- التأكد من الصلاحية: تتضمن هذه الخطوة ثلاثة أمور، هي:
- البرهنة على الصحة: قبل استخدام البرنامج يجب إثبات صحّته.
- الاختبار: هو عملية يتم عن طريقها توليد نماذج بيانية، وفي حال وجود خطأ ما، فلا بد من وجود إشارة تنبّه لذلك.
- تشخيص الأخطاء: هو عملية يتم عن طريقها تعيين مواقع الأخطاء البرمجية، وتصحيحها بالطرق المناسبة.