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

السلام عليكم ورحمة الله وبركاته


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




فى عام 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 مره, إذاً نستخلص من هذا التحليل البسيط ان الوقت يزيدبنسبة x^3 (العدد مرفوع إلى أس 3), ويرمز لها بمصطلح Big O هكذا CODE O(x^3)


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

خوارزميه رقم 1: سرعة الأداء x, معطيات 10, الوقت 0.001 , معطيات 100, الوقت 0.01

خوارزميهرقم 2: سرعة الأداء 2^x, معطيات 10, الوقت 0.001 , معطيات 100, الوقت 0.1

خوارزميه رقم 3: سرعة الأداء 3^x, معطيات 10, الوقت 0.001 , معطيات 100, الوقت 1

خوارزميه رقم 4: سرعة الأداء x^ـ2, معطيات 10, الوقت 0.001 , معطيات 100, الوقت 40000000000000000 عام

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

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

منقولـ للاهمية