الخوارزميات 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 مره, إذاً نستخلص من هذا التحليل البسيط ان الوقت يزيد بنسبة 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 وليس العكس.

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

[ابو صالح]

الخوارزمي

لم يصلنا سوى القليل عن أخبار الخوارزمي، وما نعرفه عن آثاره أكثر وأهم مما نعرفه عن حياته الخاصة. هو محمد بن موسى الخوارزمي، أصله من خوارزم. ونجهل تاريخ مولده، غير أنه عاصر المأمون، أقام في بغداد حيث ذاع اسمه وانتشر صيته بعدما برز في الفلك والرياضيات. اتصل بالخليفة المأمون الذي أكرمه، وانتمى إلى (بيت الحكمة) وأصبح من العلماء الموثوق بهم. وقد توفي بعد عام 232 هـ
ترك الخوارزمي عدداً من المؤلفات أهمها: الزيج الأول، الزيج الثاني المعروف بالسند هند، كتاب الرخامة، كتاب العمل بالإسطرلاب، كتاب الجبر والمقابلة الذي ألَّفه لما يلزم الناس من الحاجة إليه في مواريثهم ووصاياهم، وفي مقاسمتهم وأحكامهم وتجارتهم، وفي جميع ما يتعاملون به بينهم من مساحة الأرضين وكرى الأنهار والهندسة، وغير ذلك من وجوهه وفنونه. ويعالج كتاب الجبر والمقابلة المعاملات التي تجري بين الناس كالبيع والشراء، وصرافة الدراهم، والتأجير، كما يبحث في أعمال مسح الأرض فيعين وحدة القياس، ويقوم بأعمال تطبيقية تتناول مساحة بعض السطوح، ومساحة الدائرة، ومساحة قطعة الدائرة، وقد عين لذلك قيمة النسبة التقريبية ط فكانت 7/1 3 أو 7/22، وتوصل أيضاً إلى حساب بعض الأجسام، كالهرم الثلاثي، والهرم الرباعي والمخروط.
ومما يمتاز به الخوارزمي أنه أول من فصل بين علمي الحساب والجبر، كما أنه أول من عالج الجبر بأسلوب منطقي علمي
لا يعتبر الخوارزمي أحد أبرز العلماء العرب فحسب، وإنما أحد مشاهير العلم في العالم، إذ تعدد جوانب نبوغه. ففضلاً عن أنه واضع أسس الجبر الحديث، ترك آثاراً مهمة في علم الفلك وغدا (زيجه) مرجعاً لأرباب هذا العلم. كما اطلع الناس على الأرقام الهندسية، ومهر علم الحساب بطابع علمي لم يتوافر للهنود الذين أخذ عنهم هذه الأرقام. وأن نهضة أوروبا في العلوم الرياضية انطلقت ممّا أخذه عنه رياضيوها، ولولاه لكانت تأخرت هذه النهضة وتأخرت المدنية زمناً ليس باليسير

www.alnoor-world.com/Scientists/83.asp