تحميل كتاب رياضيات الحاسب باللغة العربية علي اكثر من سيرفر

الخوارزميات هي أسا البرمجة في الحاسب ، وسنتناول نبذة مختصرة عنها .

تعريف 1 : نسمي مسألة كل قائمة منتهية من المعطيات وسؤال متعلق بها ، وحل المسالة هو إعطاء جواب لسؤالها مهما تغيرت قيم المعطيات .
مثال 1 : نريد أن نحسب قيمة كثير الحدود التالي من أجل x = 5 :

فالمعطيات هنا هي : كثير الحدود f(x) والقيمة المعينة للمتغير x = 5 والسؤال هو : أوجد قيمة f(5) ، وحل هذه المسألة هو : f(5) = 800 .
تعريف 2 : نسمي حجم معطيات المسألة حجم الحيز الذي تشغله المعطيات في الذاكرة .
مثال 2 : نعتبر المسألة السابقة المعطيات هنا ثابتة فلا نحتاج إلى تخزينها في الذاكرة .
ولكن لو اعتبرنا مسألة أعم منها وهي حساب قيمة كثير الحدود نفسه من أجل أية قيمة ما للمتغير فنحتاج إلى إدخال قيمة المتغير كمتغير حقيقي ، وسيكون الحيز الذي يخصص في الذاكرة لتخزين هذا المتغير الحقيقي هو حجم المعطيات .
مثال 3 : كثير حدود f(x) من الدرجة الثالثة وقيمة معينة للمتغير x = a .
السؤال : أوجد قيمة f(a) .
فيجب إدخال معاملات كثير الدود من أصغر درجة إلى أكبرها وهذا يحتاج إلى مصفوفة 1 × 4 (مثلا) كما أننا نحتاج إلى متغير حقيقي لإدخال قيمة المتغير ، فحجم المعطيات سيكون بهذا الترميز هو الحيز الذي تشغله المصفوفة والمتغير الحقيقي .
تعريف 3 : نسمي خوارزمية كل قائمة منتهية من الخطوات لحل مسالة ما أي إيجاد جواب للمسالة .
يمكن أن نتصور الخوارزمية كبرنامج حاسب لحل مسألة ما .
مثال 4 : نعتبر مسألة المثال 1 : يمكن حلها بطريقة التعويض التالية :

= 250 – 175 + 20 – 15 = 75 + 20 15 = 95 – 15 = 80
احتجنا في هذه الخوارزمية إلى أداء 3+2+1 = 6 عمليات ضرب و 3 عمليات جمع .
كما يمكن حلها بطريقة هورنير التالية:-

ومنه فيكون :

= (15+4) × 5-15 = 19 × 5 – 15 = 95 – 15 = 80
احتجنا في هذه الخوارزمية إلى أداء 3 عمليات ضرب و 3 عمليات جمع .
إذن خوارزمية هورنير أسرع من خوارزمية التعويض من حيث الوقت المستغرق لإعطاء الجواب .
تجدر الإشارة إلى أن التحليل المعطى لكثير الحدود في طريقة هورنير ليس جزءا من الجواب وإنما يوضح صحة الطريقة فقط إذ يمكن تطبيقها مباشرة كالتالي:-
الخطوة الأولى : ضرب معامل x3  في قيمة المتغير .
الخطوة الثانية : إضافة الناتج السابق إلى معامل x2 .
الخطوة الثالثة : ضرب الناتج السابق في قيمة المتغير .
الخطوة الرابعة : إضافة الناتج السابق إلى معامل x .
الخطوة الخامسة : ضرب الناتج السابق في قيمة المتغير .
الخطوة السادسة : إضافة الناتج السابق إلى المعامل الثابت .
الجواب : الناتج الأخير هو قيمة كثير الحدود عند قيمة المتغير .
فواضح من خطوات الخوارزمية بأننا نحتاج إلى أداء 3 عمليات ضرب و 3 عمليات جمع فقط ، وهذه الخوارزمية يمكن تطبيقها لحل مسألة المثال 3 .
مثال 5 : نعتبر المسألة التالية :-
المعطيات : عددا طبيعيان a و b بحيث a > b .
السؤال : ما هو القاسم المشترك الأكبر للعددين a و b .
يمكن أن نحل هذه المسألة بطريقين مختلفتين :
1) الطريقة المباشرة : نطبق الخوارزمية التالية :-
الخطوة الأولى : إيجاد قواسم كل من العددين .
الخطوة الثانية : إيجاد القاسم المشترك الأكبر .
مثلا لو كان a = 258  و b = 60  فيكون :
الخطوة الأولى : قواسم a = 258  هي : 1 , 2 , 3 , 6 , 86 , 129 , 258  .
وقواسم b = 60 هي : 1 , 2 , 3 , 5 , 6 , 10 , 12 , 15 , 20 , 30 , 60 .
الخطوة الثانية : القاسم المشترك الأكبر للعددين a = 258  و b = 60  هو : 6 .
2) الطريقة الثانية : نطبق خوارزمية إقليدس التالية :-
الخطوة الأولى : نقسم a على b فنحصل على باقي r1 .
الخطوة الثانية : إذا كان الباقي يساوي الصفر فان القاسم المشترك الأكبر هو المقسوم عليه .
الخطوة الثالثة : إذا لم يكن الباقي يساوي الصفر فنقسم المقسوم عليه على الباقي فنحصل على باقي جديد .
الخطوة الرابعة : نكرر الخطوتين الثانية والثالثة إلى أن نجد القاسم المشترك الأكبر .
مثلا لو كان ن a = 258  و b = 60  فيكون :
الخطوة الأولى : نقسم ن a = 258  على b = 60  فنتحصل على الباقي : r1 = 18 .
الخطوة الثالثة : نقسم b = 60 على r1 = 18 فنتحصل على الباقي : r2 = 6 .
الخطوة الرابعة : نقسم r2 = 18  على r2 = 6 فنتحصل على الباقي : r3 = 0 .
الخطوة الثانية : الباقي يساوي الصفر إذن القاسم المشترك الكبر هو المقسوم عليه الأخير : r2 = 6  .
هذه الخوارزمية منتهية لأن الباقي يتناقص إلى أن يصبح صفرا :
a = 258 > b = 60 > r1 = 18 > r2 = 6 > r3 = 0

إن تحليل الخوارزميات مهمة رئيسية في علوم الحاسب ولمقارنة الخوارزميات يمكن اعتبار عاملين مهمين هما : الفضاء والزمن .
نعني بالفضاء الحيز الذي تشغله الخوارزمية في الذاكرة فكلما كان صغيرا كلما كان أحسن ، رغم أن هذا العامل ليس هو الأهم .
ونعني بالزمن الوقت الذي تستغرقه الخوارزمية لحل المسألة المطروحة فكلما كان الوقت اقصر كلما كانت الخوارزمية أكثر فاعلية ، وهذا العامل يكاد أن يكون هو الأساسي .
تعريف 4 : نسمي تعقد خوارزمية ما عدد العمليات الأساسية التي نؤديها في تنفيذ الخوارزمية وفي أسوأ حالة ، وذلك بدلالة حجم المعطيات ومن العمليات الأساسية : المقارنة والمساواة والجمع والطرح والضرب والقسمة .
مثال 6 : نعتبر مسألة المثال 3 ونعتبر خوارزمية التعويض لحلها والموضحة في المثال 4 ، ما هو تعقد هذه الخوارزمية ؟
الحل :-
نحل هذه لخوارزمية إلى أداء 3 + 2 + 1 = 6 عمليات ضرب و 3 عمليات جمع ، أي أن تعقد الخوارزمية هو : 9 عمليات أساسية .
بينما تعقد خوارزمية هورنير هو : 6 عمليات أساسية .
مثال 7 : نعتبر السألة التالية :
المعطيات : كثير حدود f(x) من الدرجة n وعدد حقيقي a .
السؤال : احسب f(a) .
ما هو تعقد خوارزمية التعويض لحل هذه المسألة ؟ وما هو تعقد خوارزمية هورنير ؟
الحل :
1) في خوارزمية التعويض نحتاج إلى أداء      عملية ضرب و n عملية جمع .
أي أن التعقد هو :          عملية أساسية .
2) في خوارزمية هورنير نحتاج إلى أداء n عملية ضرب و n عملية جمع أي أن التعقد
هو : n + n = 2n عملية أساسية ، ومنه فيمكن أن نقول بأن خوارزمية هورنير أحسن من خوارزمية التعويض .

لما نقوم بحساب تعقد خوارزمية معينة فإننا لا نحتاج إلى كل التفاصيل ولكن يكفي أن نعرف الحد المهيمن في هذا التعقد ، وذلك لأننا نريد أن نعرف نسبة التزايد لما يزيد حجم المعطيات ، وهذه قيم تقريبية لنسب تزايد بعض الدوال المشهورة .
2n    n3    n2    n log2 n    n    log2 n    n
32    125    25    15    5    3    5
10 3    10 3     100    40    10    4    10
10 30    10 6    10 4    700    100    7    100
10 300    10 9    10 6    10 4    10 3    10    1000
وللتعبير عن الحد المهيمن في التعقد نستخدم الرمز O .
مثال 8 : تعقد خوارزمية التعويض هو : O(n2) ، بينما خوارزمية هورنير تعقدها هو : O(n)
أي أن نسبة تزايد التعقد بدلالة حجم المعطيات هي من جنس تزايد الدالة المشار إليها .
وبهذه الطريقة سنعرف مسبقا الخورزميات التي ستستغرق وقتا معقولا والتي ستستغرق وقتا طويلا جدا وبالتالي فلا فائدة عملية من تنفيذها .