د.أحــمــد
المدير العام
الهواية : 
المزاج : 
المهنة : 
البلــد : 
عدد المساهمات : 49
تاريخ التسجيل : 08/11/2009
 |  موضوع: الخوارزميات - Algorithm الأحد مارس 21, 2010 7:10 am | |
|  الخوارزميات - Algorithm | رغم أن الحاسب الالكتروني يتميز بقدرته على إنجاز العمليات الحسابية حسب الأوامر و التعليمات المعطاة له بسرعة فائقة و بدقة متناهية و كذلك بإمكانياته الكبيرة في حفظ المعلومات الواسعة و المختلفة التي يعجز الإنسان عن حفظها و استعادتها باستعمال ذاكرته العادية. فهو يعجز عن أن يقوم بشكل ذاتي بحل أي مسألة مهما كانت بسيطة، أي أن عمله ينحصر في إنجاز الحلول للمسائل التي تبرمج له بشكل صحيح يتوافق مع الأسس العلمية الصحيحة التي تعتد عليها هذه الحلول.
لذا سوف نستعرض في هذا الفصل الخطوات الضرورية اللازمة لحل المسائل باستخدام الحاسب الالكتروني وكذلك توضيحاً مفصلاً لمفهوم الخوارزميات و خرائط سير العمليات التي تشكل العنصر الأساسي لكيفية البرمجة. |
12-2 خطوات حل مسألة باستخدام الحاسب: | عند حل أي مسألة باستعمال الحاسب الالكتروني تتم المعالجة بإتباع خطوات نبينها بإيجاز فيما يلي:
•تعريف وتحليل المسألة:
إن تعريف المسألة هو عبارة عن دقة التعبير في تطبيق المسألة بحيث يجعلها معروفة ومفهومة بصورة واضحة وبدون أي غموض لجميع الأشخاص العاملين ضمن مجال الاختصاص الذي تخضع له المسألة.
أما تحليل المسألة ووضع طريقة الحل فهو أصعب المصاعب و أشق الخطوات، و من أجل الوصول إلى حل صحيح فإن كثير من القوانين والطرق الرياضية المناسبة لحل المسألة يجب أن تستعمل و لربما تحتاج أيضاً إلى تطوير هذه القوانين والطرق لنجعلها تناسب الحل في كثير من الأحيان ففي هذه الخطوة يجب تحديد:
• طبيعة المخرجات(النتائج) و تنظيم كتابتها.
• المدخلات (البيانات أو المعلومات) و تحديد نوعها و تنظيم إدخالها إلى الحاسب الالكتروني.
• طرق الحل المناسبة و تقييمها بما يتلاءم مع كيفية تنفيذها بالحاسب الالكتروني و في ضوء ذلك يتم اختيار الحل الأفضل.
• برمجة الحل خطياً:
بعد اختيار طريقة الحل المثالية و تحديد كل ما تشمله من علاقات رياضية، يتم التعبير عنها على شكل خطوات متسلسلة ومترابطة منطقياً، دقيقة الوصف تؤدي إلى الوصول إلى حل المسألة.و هذه الخطوات المتسلسلة تعرف بخوارزمية المسألة Algorithm of the Problem و يمكن تمثيل هذه الخوارزمية بعد إيضاح جميع التعليمات والأوامر المتسلسلة التي يراد تنفيذها في كل خطوة بمخطط وصفي تسلسلي يدعى بمخطط سير العمليات Flowchart وذلك باستخدام مجموعة من الأشكال الاصطلاحية الرمزية. إن كلمة Algorithm مشتقة نسبة إلى العالم العربي المشهور الخوارزمي الذي قام بوضع أسس حل المسائل بشكل تتابعي.
•برمجة الحل باستخدام إحدى لغات البرمجة:
إن مخطط سير العمليات هو عبارة عن تخطيط تصوري مساعد سهل
الملاحظة بالنسبة للمبرمج و لكنه غير مفهوم عند الحاسب الالكتروني، لذلك فإن طريقة الحل الممثلة بمخطط سير العمليات يجب أن تكتب بإحدى لغات الحاسب التي يفهمها و التي تتلاءم مع حل المسألة.
و يلي ذلك كتابة البرنامج على الوسط الخارجي المناسب و إدخال البرنامج
إلى الحاسب و البرنامج الناتج من هذه الخطوة و المكتوبة بإحدى اللغات الرمزية أو الراقية يسمى بالبرنامج المصدري source program.
• ترجمة البرنامج المصدري:
بعد الانتهاء من كتابة البرنامج المصدري يتعين إدخاله إلى الحاسب للتأكد من صحة كتابته من جهة، ثم لترجمته إلى لغة الآلة بواسطة برنامج الترجمة الخاص في حالة عدم وجود أخطاء في البرنامج المصدري. و تمر عملية الترجمة في المراحل الآتية:
1. مرحلة التحليل المعجمي Lexical analysis:
في هذه المرحلة يتم مطابقة مفردات برنامج المصدر والعلاقات و الأسماء
مع تلك المسموح بها في اللغة و اكتشاف أي أخطاء فيها.
2. مرحلة التحليل اللغوي والنحوي Syntax analysis:
في هذه المرحلة تجري عملية مطابقة تعليمات البرنامج المصدري مع
القواعد اللغوية المستخدمة، و اكتشاف أي أخطاء فيها، بالإضافة إلى عملية تحويل البرنامج المصدري إلى تعليمات و أوامر رمزية بلغة التجميع.
3.مرحلة ترجمة البرنامج إلى لغة الآلة:
في هذه المرحلة نحصل على البرنامج الهدفي object program و الذي بموجبه يمكن البدء في عملية التنفيذ.
• تجربة البرنامج و تنفيذه:
بعد الحصول على البرنامج الهدفي، تتم تجربته للتأكد من صحته منطقياً
وذلك باستخدام عينة من المعطيات الاختبارية Test Data فإذا ثبت صحة طريقة الحل بمطابقة النتائج الخارجة من الحاسب مع النتائج التي تم الحصول عليها يدوياً على سبيل المثال، يمكن تنفيذ البرنامج على المعطيات الحقيقية. |
12-3 مفهوم خرائط سير العمليات: | الخوارزمية هي عبارة عن مجموعة من الخطوات المتسلسلة التي تصف بصورة مضبوطة وبدون أي غموض جميع الخطوات الرياضية والمنطقية اللازمة لحل مسألة ما. ولكن هذا الوصف في كثير من الأحيان يكون معقداَ وصعب الملاحظة والتتبع لذلك فإن خريطة سير العمليات التي تمثل وصفاً تصويرياً لخطوات الخوارزمية تكون أكثر وضوحاً. وخريطة سير العمليات تقوم مقام الخوارزمية ويمكن بواسطتها ملاحظة تتبع التسلسل المنطقي لحل المسألة بكل سهولة، وغالباً ما تكون استخراج الخوارزمية من خريطة سير العمليات أسهل بكثير من كتابة الخوارزمية مباشرة.
و عند رسم خريطة سير العمليات لمسألة معينة فإننا نستخدم مجموعة من الأشكال الرمزية الاصطلاحية المبينة في الجدول التالي:
من أهم فوائد استخدام خرائط سير العمليات قبل كتابة البرنامج لمسألة ما، ما يأتي:
1. تمكن المبرمج من الإلمام الكامل بالمسألة المراد حلها و السيطرة على كل أجزائها بحيث تساعده على اكتشاف الأخطاء المنطقية (Logic Error) و التي تعتبر من أهم الأخطاء التي تجهد المبرمج.
2. تساعد بيسر و سهولة على تعديل البرامج الموضوعة بمجرد النظر.
3. يعتبر الاحتفاظ برسوم خرائط سير العمليات لحلول مسائل معينة أمراً مهماً إذ يكون مرجعاً عند إجراء تعديلات عليها أو استخدامها لحل مسائل أخرى مشابهة دون الحاجة إلى الرجوع إلى المبرمج الأول باعتبار أن الحلول الأولى قد صيغت في خطوات واضحة بسيطة و مفهومة.
4. توفير وسيلة مناسبة ومساعدة في كتابة البرامج ذات التفرعات الكثيرة.
هذا و يمكن تصنيف خرائط سير العمليات بما يلي:
•خرائط التتابع البسيط (Simple sequential Flowchart).
•خرائط التفرع (Branched Flowchart).
•خرائط الدوران البسيط (Loop Flowchart).
•خرائط الدورانات المتداخلة (Nested).
و يمكن للبرنامج الواحد أن يشتمل على أكثر من نوع واحد من هذه الأنواع. و سنتناول فيما يأتي شرح هذه الأنواع بشيء من التفصيل.
|
12-4 خرائط التتابع البسيط: |
يخلو هذا النوع من التفرعات Branches و الدورانات loops، و يكون الشكل العام لهذا النوع كما هو مبين في الشكل 12-1:
|
الشكل 12-1خرائط التتابع البسيط |
و كلمة Event الواردة في شكل 12-1 تعني الحدث أو العملية المطلوب تنفيذها.
مثال : أرسم خريطة سير العمليات لإيجاد مساحة و محيط دائرة نصف قطرها معلوم R.
وقيمتها العددية ثابتة و تساوي 3.14 بينما R متغير.
وتكون خطوات الحل المبينة في الشكل 12-2 كما يلي:
1.ابدأ.
2.اقرأ قيمة R.
3. ضع قيمة 3.14=PIE
4. احسب المساحة(A) من المعادلة A =(PIE)*R*R.
5. احسب المحيط (C) من المعادلة C =2*(PIE)*R .
6. اطبع قيم كل من C, A, R.
7. توقف.
|
|
|
الشكل 12-2 |
مثال:ارسم خريطة سير العمليات لحساب قيمة كل من المتغيرات C, B, A في المعادلة الآتية:
إذا علمت أن قيم كل من Y, X معطاة (معلومة)، ثم اطبع قيم كل من C, B, A, Y, X.
الحل: من الواضح أنه يمكننا من حساب قيمة المتغير A في المعادلة(1) لمعرفتنا بقيم المعطيات الأولية Y, X، ويمكننا من حساب قيمة المتغير B في المعادلة (2) بالاعتماد على قيمة X المعلومة لدينا وقيمة المتغير Aالمحسوبة في الخطوة السابقة، أما قيمة المتغير C في المعادلة (3) بالاعتماد على قيم كل من المتغيرات B, A, X وكلها معلومة.
وتكون خطوات حل المسألة كما هو مبين في الشكل 12-3 كما يلي:
1.ابدأ.
2.اقرأ قيمة كل من Y, X.
3.احسب قيمة A من المعادلة (1).
4.احسب قيمة B من المعادلة (2).
5.احسب قيمةC من المعادلة (3).
6.اطبع قيمة كل من C, B, A, Y, X.
7.توقف.
|
|
الشكل 12-3 |
|
12-5 خرائط التفرع: |
ويحدث التفرع في البرامج بسبب الحاجة لاتخاذ قرار أو مفاضلة بين اختيارين أو أكثر، وهناك أسلوبان في تنفيذ القرار(انظر شكل 12-4).
|
|
قرار ذو تفرعين |
قرار ذو ثلاثة تفرعات |
الشكل 12-4 |
وبشكل عام فإن خرائط التفرع يمكن أن تأخذ إحدى الصورتين الآتيتين (انظر شكل 12-5 و الشكل 12-6 ).
 |
 |
الشكل 12-5 |
الشكل 12-6 |
يمكننا ملاحظة أن شكل 12-5 يبين أنه إذا كان جواب الشرط YSE (Condition) فإن الحدث التالي في التنفيذ يكون الحدث (a) أما إذا كان الجواب NO فإن الحدث التالي يكون الحدث(b) كما يمكننا أن نلاحظ في الشكل 12-6 أنه إذا كان جواب الشرط YSE فإن الحدث التالي في التنفيذ يكون الحدث (a) ثم يتبعه الحدث (b) أما إذا كان جواب الشرط NO فإن الحدث التالي يكون الحدث (b) مباشرة.
مثال:ارسم خريطة سير العمليات لإيجاد قيمة الاقتران F(x) المعرف حسب القاعدة التالية:
X if X>=0 |
F(X) = ׀X׀ |
-X if X<0 |
حيث كلمة (if) هنا تعني عندما.
خطوات الحل المبينة في الشكل 12-7 تكون:
1. ابدأ
2. اقرأ قيمة المتغير X .
3. إذا كانت X أكبر أو تساوي صفرًا اذهب إلى خطوة(4) وإلا فأذهب إلى الخطوة(5).
4.احسب قيمة الاقتران منF(X)=X ثم اذهب إلى الخطوة(6).
5.احسب قيمة الاقتران من F(x)= -X.
6. اطبع قيمة كل من X ,F(x).
7. توقف.
|
|
الشكل 12-7 |
مثال:ارسم خريطة سير العمليات لحساب قيمة Wطبقًا للمعادلات الآتية علمًا بأن قيمة المتغير X معطاة معلومة:
خطوات الحل كما هي مبينة في الشكل 12-8 :
1. ابدأ.
2. اقرأ قيمة المتغيرX .
3. إذا كانت X أكبر من صفر فاذهب إلى الخطوة 4 أما إذا كانت ليست أكبر من فاذهب إلى خطوة 5.
4. احسب W من المعادلة (1) ثم اذهب إلى الخطوة 8.
5. إذا كانت X تساوي صفر فاذهب إلى الخطوة 6 وإلا فاذهب إلى الخطوة 7.
6. احسب W من المعادلة (2) ثم اذهب إلى الخطوة 8.
7. احسب W من المعادلة (3) ثم اذهب إلى الخطوة 9.
8. اطبع قيمة W.
9. توقف.
|
 |
|
الشكل 12-8 |
|
12-6 خرائط الدوران (التكرار) البسيط: |
وهذه الخرائط نحتاج إليها لإعادة عملية أو مجموعة من العمليات في البرنامج عددًا محدودًا أو غير محدود من المرات، ويكون الشكل العام لمثل هذه الخرائط كما يلي (انظر الشكل12-9 ).
|
|
الحدث (a) يتكرر تنفيذه في كل دوره حتى يصبح جواب الشرط YES. |
الحدث (a) يتكرر تنفيذه في كل دورة طالما كان جواب الشرط YES. |
الشكل 12-9 |
مثال: ارسم خريطة سير العمليات لإيجاد مساحة مجموعة من الدوائر أنصاف أقطارها معلومة:
تكون خطوات الحل المبينة في الشكل 12-10 كما يلي:
- ابدأ.
- اقرأ نصف قطر الدائرة (R).
- أوجد مساحة الدائرة (A).
- اطبع قيم كل من A, R.
- هل هناك مزيد من الدوائر؟
فإن كان نعم فعد إلى الخطوة(2) وإن كان لا فعد إلى الخطوة (6).
|
|
|
الشكل 12-10 |
|
12-7 العداد Counter: |
في كثير من الأحيان نحتاج في برامج الحاسب الالكتروني إلى العد
Counting، فقد نريد مثلاً أن نعد عدد كل من الطلاب والطالبات ضمن
الشعبة, وقد تكون هذه العملية سهلة للإنسان لأنها أصبحت ضمن قدراته
العقلية التي يكتسبها من الطفولة، إلا أن الحاسب يحتاج إلى تصميم
خوارزمية للعد Counting Algorithm تتضمن خطوات معينة إذا اتبعتها
استطاع أن يعد.
ويمكن تحديد الخطوات التي يتبعها الحاسب حتى يتمكن من العد في
الخطوات الأساسية:
1.اجعل العداد مساويًا للصفر.
2.اجعل القيمة الجديدة للعداد تساوي القيمة القديمة لها زائد واحد, أي أن:
قيمة العداد (الجديدة)= قيمة العداد (القديمة)+1
3.كرر الخطوات ابتداء من الخطوة 2.
مثال: ارسم خريطة سير العمليات التي يتبعها الحاسب لطباعة الأعداد الطبيعية من 1 إلى 100 ومربعاتها.
الحل: خطوات الحل مبينة في الشكل 12-11هي:
- ابدأ.
- اجعل I=0.
- اجعل I=I+1.
- اجعل
 .
- اطبع J, I.
- إذا كانت I=100 اذهب إلى الخطوة 7 وإلا اذهب إلى الخطوة 3.
- توقف.
|
|
|
الشكل 12-11 |
|
12-8 المجاميع الإجمالية: |
في كثير من الأحيان نحتاج في برامج الحاسب الإلكتروني إلى جمع مجموعة كبيرة من الأعداد التي تمثل معطيات ظاهرة معينة، فمثلاً قد نرغب في إيجاد الوسط الحسابي لأعمار طلاب الجامعة، ولتحقيق هذا أولاً يجب أن نحسب مجموع أعمار الطلاب، وطبعًا ليس عمليًا إعطاء رمز أبجدي لكل عمر طالب فقد تحتاج لأكثر من عشرة الآلاف رمز، في مثل هذه الحالات نصمم خوارزمية معينة للتجميع تسمى خوارزمية التجميع summers Algorithm تتضمن خطوات محددة إذا اتبعها الحاسب استطاع أن يجمع أي كمية من البيانات باستخدام متغيرين اثنين إحداهما هو المتغير الذي نجمعه والآخر هو الجمع الإجمالي (المجمع)، ويمكن تحديد الخطوات التي يجب أن يتبعها الحاسب لتحقيق ذلك في أربع خطوات هي:
1. اجعل المجمع مساويًا الصفر.
2. ادخل قيمة واحدة للمتغير.
3. اجعل القيمة الجديدة للمجمع تساوي القيمة القديمة له زائد القيمة المدخلة للمتغير، أي أن:
قيمة المجمع الجديدة=قيمة المجمع القديمة + آخر قيمة مدخلة للمتغير.
4. كرر ابتداءًا من الخطوة الثانية.
مثال:ارسم خريطة سير العمليات لإيجاد الوسط الحسابي لأعمار طلاب شعبتك.
الحل: نفترض أن إجمالي عدد الطلاب =N ونستخدم عددًا لرقم كل طالب ونرمز له بالرمز I ونرمز لعمر الطالب بX ونستخدم مجمعًا لأعمار الطلبة ونرمز له بالرمزS ونستخدم الرمز A ليدل على معدل أعمار الطلبة.
وتكون خطوات الحل كما هو مبين في الشكل 12-12هي:
- ابدأ.
- ادخل إجمالي عدد الطلاب (N).
- اجعل I=0.
- اجعل S=0.
- اجعل I=I+1.
- ادخل X.
- اجعل S=S+X.
- إذا كانت I=N اذهب إلى الخطوة 9 وإلا اذهب إلى الخطوة 5.
- اجعل A=S/N.
- توقف.
|
|
|
الشكل 12-12 |
|
12-9 خرائط الدورانات المتدخلة: |
في هذه الحالة تكون الدورانات داخل بعضها البعض بحيث لا تتقاطع فإذا كان لدينا مثلاً دورانان من هذا النوع (انظر شكل 12-13 فيسمى الدوران قم (1) دورانًا داخليًا (Inner Loop) بينما الدوران رقم (2) دورانًا خارجيًا (Outer Loop ويتم التناسق في عملي مثل هذين الدورانين بحيث:
تكون أولوية التنفيذ للدوران الداخلي.
مثال: يرغب نجار في تقطيع مجموعة من القطع الخشبية طول كل منها يزيد عن3 متر إلى قطع صغيرة طول الواحدة منها يساوي 3 متر.
ارسم خريطة سير العمليات.
خطوات الحل المبينة في شكل 12-14هي:
- ابدأ.
- خذ قطعة.
- اقطع منها قطعة طولها 3 متر.
- هل المتبقي يزيد عن 3 متر؟
إذا كان الجواب نعم فاذهب إلى الخطوة(3). وإذا كان الجواب لا فاذهب إلى الخطوة (5).
- هل هناك مزيد من القطع المراد تقطيعها ؟ إن كان الجواب نعم فاذهب إلى الخطوة(2) وإن كان لا فاذهب إلى الخطوة(6).
- توقف.
ملحوظة: يلاحظ من الشكل 12-14 أن الدوران الداخلي يتضمن تقطيع القطعة الواحدة إلى قطع متعددة طول كل منها 3 متر بينما يمثل الدوران الخارجي تناول قطعة واحدة جديدة لتنفذ عليها إجراءات الدوران الداخلي.
|
|
|
الشكل 12-14 |
|
12-10 صيغة الدوران باستعمال الشكل الاصطلاحي:
لقد عرفنا في الفقرتين السابقتين مفهوم الدوران البسيط والدورانات الضمنية ويمكننا الآن استخدم الشكل الاصطلاحي للدوران والوارد على النحو التالي: |  | الشكل 12-15 |
نلاحظ في الشكل 12-15 أننا نحتاج إلى العناصر الآتية:
•القيمة الأولية للعداد I (هنا(I=1 .
•القيمة النهائية للعداد I (هنا I=1).
• القيمة النهائية للعداد I (هنا n).
• قيمة الزيادة عند نهاية كل دورة  .
نلاحظ في الشكل 12-15 إن إجراءات الدوران كانت تتم طبقاً للخطوات الآتية والمفصلة من قبل المبرمج:
1. أعط I قيمة أولية.
2. أتم الإجراءات المطلوب إعادتها.
3. (تقرير) إذا كانت قيمة العداد 1 وصلت إلى القيمة النهائية n اخرج إلى الخطوة التالية في البرنامج وإلا فاذهب إلى الخطوة (4).
4. زد I بمقدار الزيادة .
5. عد إلى الخطوة (2).
يمكننا استبدال الخطوات المفصلة  في الشكل12-15 بخطوة مجملة واحدة مبينة في الشكل الاصطلاحي للدوران شكل12-15حيث تنفذ هذه الخطوات بصورة أوتوماتيكية من قبل الحاسب، وهذا من شأنه تسهيل عملية البرمجة واختصار عدد التعليمات في البرنامج وتجنب بعض الأخطاء.
ملحوظة: تعتبر قيمة تساوي 1 دائمًا إذا لم تعط قيمة أخرى بخلاف ذلك، وفي حالة عدم ذكر قيمة يصبح الشكل الاصطلاحي الوارد في الشكل 12-15 كما يلي حيث تكون قيمة تساوي 1وبصورة أوتوماتيكية.
مثال: أعد حل مثال الموضح في الشكل 12-11 لإيجاد مساحة n من الدوائر باستخدام الشكل الاصطلاحي للدوران.
خطوات الحل كما هي مبينة في الشكل 12-17. | | الشكل 12-17 |
ارسم خريطة سير العمليات لإيجادN!.
الحل: N!=N (N-1) (N-2) …3*2*1.
فخطوات الحل كما يلي هي مبينة في الشكل 12-18 : | | الشكل 12-18 |
 | |
|
