منتديات طموح الجزائر :: ˆ~¤®§][©][ العلوم و المعارف و الثقافة العامة ][©][§®¤~ˆ :: العلوم الهندسية

الخوارزمية Algorithm |

كاتب الموضوع

رسالة

المعلومات
الكاتب:	المدير{ع~المعز}العام
اللقب:	المدير العام
الرتبه:
الصورة الرمزية

البيانات
الجنسية :
الجنس :
الـبـلــــد :
المزاج :
نوع المتصفح :
المهنة :
الهواية :
تاريخ الميلاد :	07/04/1987
العمـر :	37
العمل/الترفيه :	المدير المميز في المنتدى
المزاج :	في منتهى الروعة و الإطمئنان فرح بما حوله
تاريخ التسجيل :	08/03/2009
النقاط :	77538
تقييم الأعضاء :	0
إحترام القوانين :
توقيع المنتدى :

التوقيت

الإتصالات
الحالة:
وسائل الإتصال:

موضوع: الخوارزمية Algorithm |

الثلاثاء فبراير 15, 2011 2:43 pm

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

الخوارزمية

الخوارزمية algorithm هي: «مجموعة القواعد الدقيقة لمعالجة حاسوبية، تهدف إلى الحصول على نتائج محددة اعتباراَ من معطيات ابتدائية».

فعندما
يُطلب من خبير في البرمجة أن يصنع برنامجاً، سواء لحل مسألة رياضية أو
لاختراع لعبة أو لبناء برنامج تطبيقي يخدم أغراضاً محددة، فإن أول ما يفكر
به المتخصص، بعد فهم المسألة ودراستها دراسة كافية، هو وضع استراتيجية للحل
بطريقة تمكّن، فيما بعد، من ترجمة هذه الاستراتيجية إلى لغة يفهمها
الحاسوب. تسمى هذه الاستراتيجية في أوساط المختصين بالبرمجة باسم
«الخوارزمية». وقبل الخوض في التعريف الدقيق لمفهوم الخوارزمية، لابد من
الإشارة إلى أصل التسمية الذي يعود إلى العالم المسلم محمد بن موسى
الخوارزمي، وأصله كما يدل اسمه من خوارزم، وقد عاش في بغداد من سنة 780م
إلى 847م في عهد الخليفة المأمون. وقد برع هذا العالم في الرياضيات والفلك،
وترك بصمات في التراث الحضاري العالمي، فقد وضع الخوارزمي مبادئ علم الجبر
وألف كتاب «الجبر والمقابلة»، وهو أول من سمّى
علم الجبر بهذا الاسم، ثم انتشر هذا العلم وانتقل اسمه إلى جميع اللغات
تقريباَ. ألف الخوارزمي كتاباً في الحساب، ترجم إلى اللاتينية بعد ثلاثة
قرون تحت عنوان Algoritmi de nemero indriun، ثم أطلق على جداول الضرب والقسمة والحساب العشري اسم Algorisms. ظلت هذه الكلمة متداولة في أوربا حتى أصبحت مصطلحاَ يحمل مدلولاً جديداً مرتبطاً بالبرمجة Algorithm.

إن الصفات الأساسية التي تملكها الخوارزميات هي:

ـ أنها تتألف من مجموعة من القواعد الدقيقة التي يفهمها الجميع.

ـ تطبق على معطيات قابلة للتغيير.

ـ تسعى لبناء نتيجة نحصل عليها عندما يكون اختيار المعطيات ناجحاً.

إن التعريف الوارد في المقدمة غير كاف من وجهة نظر المعلوماتيين، إذ يعرِّف Knuth في كتابه «فن البرمجة» الخوارزمية، بأنها مجموعة من القواعد (أو التعليمات) التي تتميز بالصفات الآتية:

ـ يجب أن تكون هذه المجموعة منتهية، وتنتهي بعد عدد منته من العمليات.

ـ يجب أن تكون محددة ودقيقة، بمعنى أن كل تعليمة يجب أن توصف من دون لَبْس.

ـ يجب تحديد مجال تعريف المعطيات المُدخلة إن وجدت (أعداد صحيحة، حقيقية، أحرف،...).

ـ يجب أن يكون هنالك نتيجة (واحدة على الأقل).

ـ يجب أن تكون فعّالة، أي أن يتمكن شخص من تنفيذ العمليات كلها في وقت منته باستخدام الإمكانات اليدوية (دون حاسوب).

تعبِّر
الخوارزمية وفق هذا التعريف عن طريقة منهجية لحل مسألة معينة، على وجه
قابل للتنفيذ الآلي. وإذا كان وضع الخوارزمية يحتاج إلى مزيج من المنهجية
والعلم والإبداع، فإن تنفيذها لا يترك مجالاً للتأويل والحدس.

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

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

ولكن
هل توجد خوارزمية واحدة لحل مسألة ؟ بالطبع لا؛ فمهما تكن المسألة بسيطة،
قد توجد طرائق عدة لحلها. وإن اختيار الخوارزمية المناسبة لحل مسألة معينة،
يتعلق بعدة عوامل: منها حجم المسألة والشكل الذي تطرح به، ونمط الأجهزة
المستخدمة للحل وإمكاناتها.

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

من
الممكن كذلك الحصول على النتيجة ذاتها بتطبيق الطريقة الروسية في الضرب،
حيث يكتب العددان على سطر واحد، ثم يقسم العدد الأول على 2، ويوضع ناتج
القسمة تحته مع إهمال باقي القسمة، إن لم يكن صفراً، ويضرب العدد الثاني
بـ2 ويوضع الجداء تحته، تكرر العملية حتى يصبح الرقم في نهاية عمود العدد
الأول مساوياً 1، ولإيضاح هذه الطريقة سنستخدمها في إجراء عملية الضرب 45 ×
19.

19	45
38	22
76	11
152	5
304	2
608	1

في
نهاية العملية تحذف الأسطر التي تحتوي عدداً زوجياً في عمود العدد الأول،
ثم تجمع العناصر الموجودة في عمود العدد الثاني. ففي مثالنا نحذف السطر
الذي يحتوي 22 و2 ثم نجمع:

19 + 76 + 152 + 608 = 855

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

توجد خوارزميات أخرى لضرب الأعداد الصحيحة الكبيرة جداً، ولكنها أكثر تعقيداً، ومن ثم أكثر بطئاً عندما تكون الأعداد صغيرة.

طرائق التعبير عن الخوارزمية

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

وهنا اقترحتُ عدة طرائق بعضها نصّية (عبارات) والأخرى بيانية (مخططات).

- الطرائق النصية

إن
أفضل طريقة لتجنب الالتباس المحتمل وروده عند التعبير باللغة المتداولة،
هي استخدام إحدى لغات البرمجة التي تتميز بصيغ قواعدية تحدّ من إمكانات
الالتباس هذه، وهذا يعني التعبير عن الخوارزمية بالبرنامج. ولكن الكتابة
بلغة برمجة ما يعني التقيد بلغة خاصة، في حين أن المطلوب وسيلة تعبير
مستقلة عن أية لغة. إن استخدام طريقة منتظمة للتعبير عن الخوارزمية يوفر
حرية التعبير عن الحل مع الاحتفاظ بسهولة نقل الحل إلى لغة برمجة يفهمها
الحاسوب، يمكن أن تسمى هذه الطريقة في التعبير عن الخوارزمية تجاوزاً لغة
خوارزمية pseudo-code وترجمتها الحرفية «شبه الترميز» إذ تشكل حلاً وسطاً بين لغتنا الطبيعية ولغات البرمجة.

أ ـ اللغة الخوارزمية

تُعرّف في هذه اللغة الخوارزمية العناصر الآتية:

المتحول: وهو الغرض الذي تجري معالجته ضمن الخوارزمية، وتكون قيمته متحولة (قابلة للتغيير)، ويعرف باسم خاص متميز.

الثابت: وهو غرض قيمته غير متغيرة طوال البرنامج، ويعر ف باسم خاص.

الصيغة: وتتألف من متحولات وثوابت وعمليات حسابية أو منطقية.

يمكن التعبير عن مسار الحل لمسألة أو توصيف خوارزمية بوساطة التعليمات أو الأوامر الأساسية الخمسة الآتية:

1ـ تعليمة القراءة: وهي قراءة قيمة من الدخل (من لوحة المفاتيح) لوضعها في خانة ذاكرة، وشكل التعليمة:

اقرأ < اسم المتحول >

2ـ تعليمة الكتابة: وهي كتابة قيمة معينة على وحدة الخرج (الشاشة)، وشكل التعليمة:

اكتب < صيغة >

3ـ تعليمة الإسناد: وهي إسناد قيمة محددة أو نتيجة صيغة لمتحول (خانة ذاكرة)، وشكل التعليمة:

< صيغة > ¬ < اسم المتحول >

4ـ التعليمة الشرطية: وترد بأحد الشكلين الآتيين:

أ ـ التنفيذ بشرط: ونعبر عن ذلك كما يأتي:

إذا < شرط > نفّذ

ب ـ التعليمة الشرطية الاختيارية: وتسمح بالاختيار بين طريقتي تنفيذ وذلك وفق شرط.

إذا < شرط > نفّذ

وإلا

5
ـ التعليمة التكرارية: وتستعمل لتكرار مجموعة من التعليمات مادام شرط محدد
محققا، أي يتكرر تنفيذ مجموعة من العمليات ما دامت الصيغة المنطقية للشرط
صحيحة.

مادام < شرط > كرر

ـ كيفية الوصول إلى الخوارزمية؟

للوصول إلى وضع الخوارزمية المناسبة لحل مسألة معينة، تُتَّبع الخطوات الآتية:

1-
فهم المسألة وتحليلها بدقة، أي معرفة المدخلات (المعطيات) المطلوب
معالجتها والمخرجات (النتائج) المطلوب الحصول عليها، وصياغة هذه المعلومات
بوضوح ما أمكن، ويمكن استخدام العلاقات الرياضية التي توصف علاقة الدخل
بالخرج (إن وجدت مثل هذه العلاقات).

2-
تصور شامل لحل المسألة، ومن ثم تجزئة هذا الحل إلى خطوط عريضة تمثل
الوظائف الأساسية، ثم يعاد النظر في كل وظيفة أساسية معقدة، وكأنها مسألة
جديدة تتطلب حلاً، وتتألف بدورها من عدة خطوات جزئية، وهكذا....، ويُحرص
دوماً على استخدام هياكل التعليمات الأساسية حين الحاجة (التكرار والتفرع
الشرطي). تكرر هذه الآلية إلى حين الوصول إلى عمليات يمكن التعبير عنها
مباشرة بالتعليمات البسيطة (قراءة، كتابة، إسناد، حساب)، وتسمى هذه العملية
التبسيط المتتالي أو الطريقة النزولية.

3-
عند الوصول إلى أدنى المستويات تنتج خوارزمية كاملة مكتوبة باللغة
الخوارزمية، واعتماداً على هذه الخوارزمية يجري الترميز باللغة المناسبة (....,Java, C++, C, Pascal).

ـ الطرائق البيانية

تعتمد
الطريقة البيانية لصياغة الخوارزميات على توضيح خطوات تنفيذ الخوارزمية
باستخدام أشكال هندسية خاصة وأسهم تصل بينها، إضافة إلى عبارات باللغة
الطبيعية، وتعابير رياضية أو منطقية، وبذلك ينتج ما يسمى بالمخطط التدفقي (flowchart diagram). ونلاحظ هنا أن الأسهم تفصّل العمليات اللازمة لإنجاز العمل، وتبيّن تسلسلها.

يستخدم
المخطط التدفقي أشكالا ًهندسية متفقاً عليها، خصّص كل منها لنوع من
العمليات. فقد استخدمت الشكل البيضوي لتحديد بداية الخوارزمية ونهايتها،
كما استخدم المستطيل للعمليات التنفيذية العادية، أما العمليات التي ترتبط
باختيار تحقق شرط وتتطلب قراراً منطقياً، فقد استخدم لها شكل المعيّن.

مثال :

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

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]

تعقيد الخوارزميات Algorithm Complexity

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

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

1- دراسة تعقيد الخوارزميات

في دراسة تعقيد الخوارزميات يكون الاهتمام بنوعين من التعقيد:

1ـ التعقيد الحجمي أو المكاني space complexity: ونقصد به تقدير حجم الذواكر اللازم للخوارزمية.

2ـ التعقيد الزمني time complexity:
ونقصد بذلك التقدير الزمني. وهنا، يجب البدء أولاً باختيار واحدة لقياس
هذا التعقيد، وقد اقترح بعضهم اعتبار مدة تنفيذ البرنامج واحدة للقياس، لكن
هذه الواحدة لا تصلح بسبب اختلاف الحواسيب وسرعة معالجاتها. كما اقترح
البعض الآخر اعتبار عدد التعليمات واحدة للقياس، لكن هذه الواحدة لا تصلح
أيضاً بسبب اختلاف عدد التعليمات التي نكتب بها البرنامج باختلاف لغة
البرمجة المستخدمة وأسلوب المبرمج. وربما كان أفضل ما اقترح في هذا المضمار
هو عدد العمليات الأساسية المستخدمة في الخوارزمية، لأنه يعطي فكرة جيدة
عن أداء الخوارزمية، على وجه مستقل عن تفاصيـل التنفيذ، ولكن ما المقصود
بالعمليات الأساسية؟

تختلف العمليات الأساسية باختلاف طبيعة الخوارزمية بحسب ما يبينه الجدول 1.

الخوارزمية	العمليات الأساسية
البحث عن اسم شخص ما X في قائمة أسماء	البحث عن اسم شخص ما X في قائمة أسماء
ضرب مصفوفتين	ضرب عددين
فرز مصفوفتين	مقارنة عنصرين
الجدول (1)

وبدهي أن عدد العمليات الأساسية يختلف باختلاف حجم معطيات الدخل.

يفترض في الحالة العامة أن حجم معطيات الدخل (وهو عدد عناصر هذه القائمة) هو n، فيكون هناك في أسوأ الحالات n عملية مقارنة، وبذلك يمكن تعريف التعقيد الزمني لخوارزمية بأنه مرتبة كبر أسوأ الحالات.

يستخدم عادة تدوين لاندو Landau للدلالة على التعقيد، فإذا كان التعقيد من رتبة n3 يُقال أن التعقيد هو O (n3).

2- أهمية تعقيد الخوارزميات عملياً

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

يبين الجدول 2 كيف تنعكس رتبة تعقيد خوارزمية على زمن التنفيذ، من أجل قيم مختلفة لحجم معطيات الدخل.

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

يقدر تعقيد البرامج تقديراً عملياً بحساب العدد الأعظمي للدوران في الحلقات التعليمات التكرارية بدلالة حجم معطيات الدخل.

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

لتكن لدينا مصفوفتان من الأعداد الحقيقية B,A و ، (A= (aij) B = (bij)) بُعد كل منهما هو n * n.

وليكن المطلوب حساب المصفوفة C = A * B.

يعطى ضرب مصفوفتين بالصيغة الرياضية الآتية:

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]

تعقيد الخوارزمية	n	n log2n	n2	n2	n n3	nn
حجم معطيات الدخل	n	n log2n	n2	n2	n n3	nn
10	10	33	100	1000	1024	1010
100	100	660	410	610	1010	20010
1000	1000	410	610	910	33010	300010
الجدول (2)

الخوارزمية

	من		أجل 1		¬	i وحتى n كرّر
من			أجل 1		¬	j وحتى n كرّر
			Cij ¬ 0
		من	أجل 1		¬	k وحتى n كرّر
				Cij = C ij + aik * bkj

إن العملية الأساسية هنا هي الضرب، وهناك لكل عنصر من المصفوفة C، n عملية ضرب داخل حلقة k.

ولما كان هناك n2 عنصراً في C فإن عدد عمليات الضرب هو n3.

ومن ثَمَّ فإن درجة تعقيد الخوارزمية هو O (n3).

إن
إيجاد الخوارزمية الفُضْلى من حيث التعقيد الزمني والحجمي ليس بالأمر
السهل، فغالباً ما يكون اختيار البنية التي تحقق وفراً أكبر في حجوم
التخزين مدعاة إلى عمليات أكثر، ومن ثَمَّ إلى تعقيد زمني أكبر، وبالعكس
فإن الخوارزمية ذات التعقيد الزمني الأقل تكون غالباً مرتبطة ببنية أقل
توفيراً في حجوم التخزين، ومن هنا لا يزال الباب مفتوحاً أمام الباحثين للبحث عن خوارزميات ذات توفير مزدوج في الحجم والذاكرة.

أنواع الخوارزميات

يمكن تصنيف الخوارزميات بحسب الوظيفة التي تقوم بها، والمسألة الرئيسية التي تحلها، ومن ثم يمكن أن نتكلم مثلاً عن:

ـ خوارزميات البحث search algorithm (هدفها البحث عن عنصر معطيات محدد في بنية معطيات)،

ـ خوارزميات الفرز sort algorithm (هدفها ترتيب مجموعة من عناصر المعطيات ترتيباً متتالياً اعتماداً على أحد بنود العناصر أو على اجتماع عدة بنود محددة).

وغير ذلك.

كما يمكن اتباع أسلوب آخر في التصنيف يعتمد على التقنية المستخدمة في تشكيل التعليمات وتسلسلها، فنتكلم مثلاً عن:

ـ الخوارزميات التتابعية sequential algorithm (يجري تنفيذها لاحقاً وفق تتابع التعليمات وبترتيب معين)،

ـ الخوارزميات المتوازية parallel algorithm (يجري تنفيذ أكثر من جزء منها في آن واحد معاً، ويجري ذلك عادة على عدة معالجات)،

ـ الخوارزميات الرجوعية backtracking algorithm
(وهي خوارزميات تستخدم لإيجاد حل ضمن مجموعة محاولات ممكنة، حيث تمثل
المحاولات على شكل فروع في شجرة. يجري تجريب أحد الفروع، فإن لم نجد الحل
نعود إلى الوراء لنختار مساراً آخر نجربه وهكذا، حتى نعثر على المسار
المناسب)،

ـ الخوارزميات العَوْدية recursive algorithm (وهي خوارزميات تستخدم ضمن تعليماتها استدعاءً للخوارزمية نفسها)، وغير ذلك.

سلآم ..

الموضوع الأصلي : الخوارزمية Algorithm | الكاتب : المدير{ع~المعز}العامالمصدر : منتديات طموح الجزائر

المدير{ع~المعز}العام : توقيع العضو

الخوارزمية Algorithm |

صفحة 1 من اصل 1

الكلمات الدلالية	الخوارزمية Algorithm \| حصرياا , الخوارزمية Algorithm \| بانفراد , الخوارزمية Algorithm \| منتديات اوديسا , الخوارزمية Algorithm \| حمل , الخوارزمية Algorithm \| download , الخوارزمية Algorithm \| تحميل حصري
رابط الموضوع
BBCode
HTML كود الموضوع

صلاحيات هذا المنتدى:

لاتستطيع الرد على المواضيع في هذا المنتدى