لخوارزميات Algorithms

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

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

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

فى عالم البرمجيات تكتب الخوارزميه على النحو
التالى:

1. اعثر على أصغر رقم فى المتبقى من القائمة.
2. قم بعملية
تبديل مكان العدد الذى عثرت عليه مع أول عدد فى القائمة المتبقية.
3. عد
إلى الخطوة الأولى وكرر الخوارزمية إلى أن تنتهى القائمة.

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

تذكر أن إيجاد خوارزمية لمسأله معينه
أمر يسير للغاية, ولكن إيجاد خوارزمية فعالة وسريعة ليس من السهل فى كل
الحالات.

نفترض أنك تريد السفر من القاهره إلى الرياض, يمكنك فعل ذالك
باحدى هاتين الطريقتين:

القاهره-دمشق-الخرطوم-القاهره-الرياض

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

فى الواقع إن
مشكلة إيجاد أقصر طريق تسمى traveling salesperson problem وهى من المسائل
المعقدة, والتى تندرج تحت المسمى NP-complete Problems.

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

1. Insertion sort
2.
Maxsort
3. Bubble Sort
4. Quicksort
5. Heapsort
6.
Mergesort
7. Shellsort
8. Radix Sort

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

ومن هنا قد تتساءل: ما هى القواعد التى تحكم كفاءة
خوارزمية معينة لاداء المهمه؟

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

1.
صحة النتيجة:

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

2. كمية العمل
المطلوب:

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

3. الذاكرة
المستخدمة:

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

4. السهولة:

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

5. المثالية:

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

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

تحويل الخوارزمية إلى برنامج:

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

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

كيف يتم
الحساب؟!

هناك طريقة يستخدمها علماء الرياضيات لحساب سرعة النمو,
وبذالك نصعد سرعة نمو المعطيات والناتج أثناء عمل الحاسوب, هذه الطريقة تسمى
(Asymptotic Groowth Rate), كل function له سرعة نمو مقارنة بالمعطيات
الاولية للمعادلة, هذه السرعة يرمز لها ب Big O.

هناك العدد من الرموز
المستخدمة فى حساب سرعة النمو, ولكن نقتصر فى هذا الموضوع على ذكر Big O,
ماهى Big O؟ من الصعب أن تصبح خبير فى الخوارزميات دون التمكن من إستخدام هذا
المصطلح.

دعونا نأخذ بعض الأمثله لأن شرح هذا المصطلح صعب لكونه مصطلح
نظرى.

نفترض أن لديك برنامج معين يقوم بترتيب 10 أرقام فى 0.0034
ثانيه, ولكن إذا أدخلنا 100 رقم إستغرق الترتيب 3.4 ثانيه, قد يبدو الوقت
المستغرق بسيط ولكن هل تعلم كم سيستغرق برنامجك فى ترتيب 100000 رقم, سيستغرق
108 سنوات, والان تستطيع المقارنه لنعرف كيف نستخدم Big O للوصول إلى هذه
النتيجة!

نلاحظ أنه عندما زادت المعطيات بنسبه 10مرات زاد الوقت
المستغرق بنسبه 1000 مره, إذاً نستخلص من هذا التحليل البسيط أن الوقت يزيد
بنسبة x3 (العدد مرفوع إلى أس 3), ويرمز لها بمصطلح Big O
هكذا:

O(x3)

قارن الآن بين بعض سرعات النمو لتعرف
الفرق:

خوارزميه رقم 1:

سرعة الأداء x:

- معطيات 10،
الوقت 0.001
- معطيات 100, الوقت 0.01

خوارزميه رقم
2:

سرعة الأداء(x2):

- معطيات 10, الوقت 0.001
- معطيات
100, الوقت 0.1

خوارزميه رقم 3:

سرعة الأداء
(x3):

- معطيات 10, الوقت 0.001
- معطيات 100, الوقت
1

خوارزميه رقم 4:

سرعة الأداء (2x) :

- معطيات 10,
الوقت 0.001
- معطيات 100, الوقت 40000000000000000 عام

لاحظ
أن الأخيره هى خوارزمية بسرعة نمو 2 مرفوعة لأس x وليس العكس.

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