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

الخوارزمية: هي مجموعة محددة من التعليمات ( خطوات الحل ) التي تؤدي إلى انجاز مهمة معينة والتي تتوافق فيها الشروط التالية:
1. المدخلات (inputs ) :- صفر أو أكثر من المدخلات.
2. المخرجات (outputs ) :- قيمة واحدة على الأقل.
3. الوضوح (definiteness ) :- كل خطوة فيها واضحة المعاني وغير غامضة ( يجب أن تفهم من قبل الناس ).
4. المحدودية (finiteness ) :- كل خطوات الخوارزمية يمكن حلها في فترة زمنية محددة ( أي توجد دوارات غير منتهية ), مثال: تقسيم 10 على 3 قسمة حقيقية بدقة كاملة فسوف تستمر إلى مالا نهاية.
5. المحلولية (effective ) : كل خطوة لها حل.

الفرق بين الخوارزمية والبرنامج :-

كل خوارزمية يجب توفر فيها الشروط الخمسة والخوارزمية يمكن وصفها بطرق عديدة ( على أن تكتب باللغة الطبيعية أو ما تسمى باللغة الشبيهة بالايعازات pseudo code ) مع التأكيد على شرط الوضوح, بينما في البرنامج يمكن إن لايتحقق الشرط الرابع مثل نظام التشغيل, حيث إن نظام التشغيل يصمم للتحكم في تنفيذ المهمات ( jobs ) بحيث عند عدم توفر مهمة معينة فأنه لا ينتهي بل يستمر ويدخل في حالة الانتظار لحين إدخال مهمة جديدة. علما إن البرنامج يوصف بلغة الحاسبة ( لغة البرمجة ) .
ملاحظة :- البرنامج = خوارزمية + هيكل بياني ( طريقة لتنظيم البيانات ).

مثال:
Algorithm ArrayMax (A, n)
Input: An array A storing n integers;
Outputs: The maximum element in A;









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

يقصد بالتحليل هنا تحليل كفاءة الخوارزمية ومن ثم تحسينها, حيث يوجد مقياسين مرتبطان مباشرة بانجازية الخوارزمية هما :

أ- تعقيدات الخزن (Space Complexity ) :- هي كمية الذاكرة التي يتطلبها تشغيل البرنامج (run ) حتى اكتمالها.










شكل (1 ) صورة الخزن في الذاكرة

يعتمد الخزن الذي يتطلبه البرنامج على جزئيين :

1. جزء ثابت مستقل عن خصائص المدخلات والمخرجات:
حيث يتضمن هذا الجزء فراغ التعليمات أو الايعازات Code Space , والجزء المخصص لخزن المتغيرات البسيطة أو المركبة ذات الحجم الثابت, إضافة إلى خزن الثوابت.
2. جزء متغير :
يتألف من الفراغ أو الخزن الذي يتطلبه البرنامج للمتغيرات المركبة والتي يعتمد حجمها على مثال المسألة المراد حله, إضافة إلى فراغ المكدس المستخدم للتداخل (recursion ) وعليه يمكن صياغة تعقيدات الخزن s(p) للبرنامج p كالأتي:








ب- تعقيدات الوقت (Time Complexity ):-

هو كمية الوقت التي يتطلبها تشغيل البرنامج (run ) حتى اكتمالها ويتألف من حاصل جمع وقتي التأليف (الترجمة ) وتشغيل البرنامج ويمكن صياغته كالتالي:

(خصائص المثال)tp + const. = T(p)









مثال (1 (: ابني دالة تحسب المجموع الأتي sum= ثم احسب لهذه الدالة تعقيدات الخزن والوقت؟
الحل:
Function sum(byval n ) as integer
S=0 1
For k=1 to n n+1
S=s+k n
Next
Sum=s 1
End function 2n+3
أ‌- تعقيدات الخزن:
الدالة sum تتطلب خمس خلايا خزنية لخزن قيم n, k, s, sum بالإضافة الى عنوان العودة return address وهي كمية ثابتة لا تعتمد على خصائص المثال وكذلك لا تعتمد على n .
ب‌- تعقيدات الوقت:
تستخدم صيغة عد التعليمات (step count ) مقياس لتقدير الوقت:
وقت تقديري (ليس فعلي) مثال (2 ):
اكتب دالة تقوم بحساب المعادلة حيث ان ai هي عبارة عن مصفوفة ثم احسب تعقيدات الوقت والخزن؟
Function sum (byval a,byval n) as single
S=0 1
For i=1 to n n+1
s=s+a(i) n
next
sum=s 1
End function 2n+3
أ‌- تعقيدات الخزن :
تتطلب الدالة sum خلايا خزنية للمصفوفة أي حجمها وحجمها يتغيير تبعاً لـ n , وخلايا ثابتة تخزن فيها قيم n, i, s, sum وعنوان العودة


ب‌- تعقيدات الوقت:

ملاحظة: إذا غيرنا طريقة تمرير المعامل a للدالة sum من معامل قيمة ByVal إلى معامل مرجع ByRef (معامل قيمة إذا كان قبله ByVal ومعامل مرجع إذا كان قبله ByRef علما إن الفيجوال بيسك تضع ByVal إذا لم تحدد أنت طريقة التمرير) فأننا لن نحتاج الى تخصيص خزن جديد للمصفوفة a وبدلا من ذلك سوف نحتاج الى خلية واحدة لخزن عنوان a فقط, لذلك تعقيدات الخزن سوف تصبح كالاتي: