تقرير حول كتاب كتاب رياضيات الحاسب باللغة العربية
كتاب الرياضيات الثاني المتخصص في رياضيات الحاسب كما وعدناكم يتبعه ان شاء الله كتيب صغير جدا في الرياضيات المتقطعه و بهذا ان شاء الله نكون لبينا طلب الاخ kingpro ثم نتبع هذا الكتيب (كتيب الرياضيات المتقطعه في المشاركه القادمه ان شاء الله ) بكتيب نظرية الحوسبة تلبية لطلب الاخ ahmed.magician و الله يعلم مدي سعادتنا بتلقي طلباتكم وسعدتنا اكثر اذا من الله علينا و لبينها
رياضيات الحاسب .
أنظمة العد .
الجدارة :
معرفة أنظمة العد الأساسية في الحاسب والعمليات الحسابية فيها والتحويل بينها .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدر على:-
• التحويل بين النظام العشري والنظام الثنائي .
• إجراء العمليات الحسابية في النظام الثنائي .
• تمثيل الأعداد السالبة باستخدام النظام الثنائي .
• التحويل بين النظام الستعشري والنظام العشري والثنائي .
معرفة أنظمة العد الأساسية في الحاسب والعمليات الحسابية فيها والتحويل بينها .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدر على:-
• التحويل بين النظام العشري والنظام الثنائي .
• إجراء العمليات الحسابية في النظام الثنائي .
• تمثيل الأعداد السالبة باستخدام النظام الثنائي .
• التحويل بين النظام الستعشري والنظام العشري والثنائي .
أنظمة العد .
1. النظام العشري .
2. النظام الثنائي .
قاعدة التحويل لعدد صحيح من النظام العشري إلى النظام الثنائي .
قاعدة التحويل لعدد كسري من النظام العشري إلى النظام الثنائي .
3. العمليات الحسابية في النظام الثنائي .
الجمع الثنائي .
الطرح الثنائي .
الضرب الثنائي .
القسمة الثنائية .
4. تمثيل الأعداد السالبة باستخدام النظام الثنائي .
النظام الثنائي إشارة - سعة .
النظام الثنائي متمم 1 .
النظام الثنائي متمم 2 .
5. النظام الستعشري .
قاعدة التحويل لعدد صحيح من النظام الثنائي إلى النظام الستعشري .
قاعدة التحويل لعدد صحيح من النظام الستعشري إلى النظام الثنائي .
2. النظام الثنائي .
قاعدة التحويل لعدد صحيح من النظام العشري إلى النظام الثنائي .
قاعدة التحويل لعدد كسري من النظام العشري إلى النظام الثنائي .
3. العمليات الحسابية في النظام الثنائي .
الجمع الثنائي .
الطرح الثنائي .
الضرب الثنائي .
القسمة الثنائية .
4. تمثيل الأعداد السالبة باستخدام النظام الثنائي .
النظام الثنائي إشارة - سعة .
النظام الثنائي متمم 1 .
النظام الثنائي متمم 2 .
5. النظام الستعشري .
قاعدة التحويل لعدد صحيح من النظام الثنائي إلى النظام الستعشري .
قاعدة التحويل لعدد صحيح من النظام الستعشري إلى النظام الثنائي .
تمارين .
التعبيرات المنطقية والعمليات عليها .
الجدارة :
معرفة مفهوم التعبيرات المنطقية والعمليات عليها والقدرة على تقييمها من حيث الصحة أو الخطأ .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدر على:-
• تكوين مفهم التعبيرات المنطقية البسيطة والمركبة .
• إجراء العلميات المنطقة الأساسية .
• تكوين جدول الحقائق وبعض أنواع التعبيرات الهامة .
• استخدام بعض القوانين المنطقية الهامة .
• تكوين العبارات المنطقية المشروطة .
معرفة مفهوم التعبيرات المنطقية والعمليات عليها والقدرة على تقييمها من حيث الصحة أو الخطأ .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدر على:-
• تكوين مفهم التعبيرات المنطقية البسيطة والمركبة .
• إجراء العلميات المنطقة الأساسية .
• تكوين جدول الحقائق وبعض أنواع التعبيرات الهامة .
• استخدام بعض القوانين المنطقية الهامة .
• تكوين العبارات المنطقية المشروطة .
التعبيرات المنطقية والعمليات عليها .
1. مقدمة .
2. التعبيرات والتعبيرات المركبة .
3. العلميات المنطقية الأساسية .
• رابطة العطف ( conjunction ) : " و " " and " ورمزه : ^
• رابط التخيير ( disjunction ) : " أو " " or " ورمزه : v
• رابط النفي ( negation ) :
1.3. العطف p ^ q .
2.3. التخيير p v q .
3.3. النفي
4.3. التعبيرات وجدول الحقائق .
ملاحظة .
5.3. التوافق والتناقض .
6.3. التكافؤ المنطقي .
7.3. جبر التعبيرات .
2. التعبيرات والتعبيرات المركبة .
3. العلميات المنطقية الأساسية .
• رابطة العطف ( conjunction ) : " و " " and " ورمزه : ^
• رابط التخيير ( disjunction ) : " أو " " or " ورمزه : v
• رابط النفي ( negation ) :
1.3. العطف p ^ q .
2.3. التخيير p v q .
3.3. النفي
4.3. التعبيرات وجدول الحقائق .
ملاحظة .
5.3. التوافق والتناقض .
6.3. التكافؤ المنطقي .
7.3. جبر التعبيرات .
1) قوانين الإبدال .
2) قوانين التجميع .
2) قوانين التجميع .
3) قوانين التوزيع .
4) قوانين اللانمو .
4) قوانين اللانمو .
5) قوانين المحايد .
6) قوانين المتمم
7) قانون متمم المتمم
8) قوانين دي مورجان .
8.3. التعبيرات المشروطة وثنائية الشروط .
a ) العبارة المشروطة .
b ) العبارة الثنائية الشروط .
9.3. القياس .
10.3. الحتمية المنطقية .
a ) العبارة المشروطة .
b ) العبارة الثنائية الشروط .
9.3. القياس .
10.3. الحتمية المنطقية .
تمارين .
البوابات المنطقية والدوائر .
الجدارة :
معرفة مفهوم البوابات المنطقية والقدرة على تصميم دوائر منطقية واختصارها .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدرة على :
• اختصار العبارات المنطقية باستخدام جبر بول .
• تصميم الدوائر المنطقية .
• اختصار الدوائر المنطقية .
• استخدام البوابات المنطقية الأساسية .
• تصميم الدوائر المنطقية وكيفية تصميمها باستخدام البوابة NAND .
البوابات المنطقية والدوائر .
1. جبر بول .
2. جدول الصدق .
3. تعريف البوابات المنطقية والدوائر .
4. البوابات المنطقية .
1.4. البوابة AND ( و ) .
2.4. البوابة OR ( أو ) .
3.4. البوابة NOT ( النفي ) .
4.4. البوابة NAND .
5.4. البوابة NOR .
6.4. تصميم الدوائر باستخدام البوابة NAND .
معرفة مفهوم البوابات المنطقية والقدرة على تصميم دوائر منطقية واختصارها .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدرة على :
• اختصار العبارات المنطقية باستخدام جبر بول .
• تصميم الدوائر المنطقية .
• اختصار الدوائر المنطقية .
• استخدام البوابات المنطقية الأساسية .
• تصميم الدوائر المنطقية وكيفية تصميمها باستخدام البوابة NAND .
البوابات المنطقية والدوائر .
1. جبر بول .
2. جدول الصدق .
3. تعريف البوابات المنطقية والدوائر .
4. البوابات المنطقية .
1.4. البوابة AND ( و ) .
2.4. البوابة OR ( أو ) .
3.4. البوابة NOT ( النفي ) .
4.4. البوابة NAND .
5.4. البوابة NOR .
6.4. تصميم الدوائر باستخدام البوابة NAND .
تمارين .
مبادئ الرياضة الرقمية .
الجدارة :
معرفة مفهوم المجموعات والعمليات عليها والمجموعات العددية المشهورة ، ومعرفة مفهوم الدالة وأنواعها وبعض الدوال العددية المشهورة والقدرة على تمثيل منحنياتها ومعرفة مفهوم الخوارزمية والقدرة على حساب تعقدها وبعض الخوارزميات المشهورة .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدرة على:
• تعريف المجموعات وتحديد خصائصها .
• إجراء العمليات عليها ومقارنتها بالعمليات المنطقية .
• تصنيف الأعداد حسب مجموعاتها العددية .
• تحديد مجال الدوال ومداها وأنواعها وتركيبها .
• تصنيف الدوال العددية المشهورة .
• حساب الدوال العددية الهامة في الحاسب .
• تحويل المسائل إلى خوارزميات .
• حساب تعقد خوارزمية ما .
• تحليل الخوارزميات المشهورة للبحث والترتيب .
معرفة مفهوم المجموعات والعمليات عليها والمجموعات العددية المشهورة ، ومعرفة مفهوم الدالة وأنواعها وبعض الدوال العددية المشهورة والقدرة على تمثيل منحنياتها ومعرفة مفهوم الخوارزمية والقدرة على حساب تعقدها وبعض الخوارزميات المشهورة .
الأهداف :
بعد دراسة هذه الوحدة يكون للمتدرب القدرة على:
• تعريف المجموعات وتحديد خصائصها .
• إجراء العمليات عليها ومقارنتها بالعمليات المنطقية .
• تصنيف الأعداد حسب مجموعاتها العددية .
• تحديد مجال الدوال ومداها وأنواعها وتركيبها .
• تصنيف الدوال العددية المشهورة .
• حساب الدوال العددية الهامة في الحاسب .
• تحويل المسائل إلى خوارزميات .
• حساب تعقد خوارزمية ما .
• تحليل الخوارزميات المشهورة للبحث والترتيب .
الفصل الأول : المجموعات .
1. تعريف المجموعة .
رموز المجموعات وعناصرها .
طرق تعريف المجموعات .
المجموعة الجزئية .
خصائص المجموعة الجزئية .
تساوي مجموعتين .
المجموعة الشاملة والمجموعة الخالية .
تمارين .
طرق تعريف المجموعات .
المجموعة الجزئية .
خصائص المجموعة الجزئية .
تساوي مجموعتين .
المجموعة الشاملة والمجموعة الخالية .
تمارين .
2. العلميات على المجموعات .
اتحاد مجموعتين .
خصائص الاتحاد .
تقاطع مجموعتين .
خصائص التقاطع .
العلاقة ببين الاتحاد والتقاطع ( قانون التوزيع ) .
الفرق بين مجموعتين .
خصائص الطرح .
متممة المجموعة .
خصائص المتممة .
قانون ديمورغان .
الفرق التناظري بين مجموعتين .
خصائص الفرق التناظري .
تمارين .
خصائص الاتحاد .
تقاطع مجموعتين .
خصائص التقاطع .
العلاقة ببين الاتحاد والتقاطع ( قانون التوزيع ) .
الفرق بين مجموعتين .
خصائص الطرح .
متممة المجموعة .
خصائص المتممة .
قانون ديمورغان .
الفرق التناظري بين مجموعتين .
خصائص الفرق التناظري .
تمارين .
3. التقابل بين العمليات على المجموعات والعمليات المنطقية .
4. مجموعات الأعداد .
مجموعة الأعداد الطبيعية .
مجموعة الأعداد الكلية .
مجموعة الأعداد الصحيحة .
مجموعة الأعداد النسبية أو الكسرية .
مجموعة الأعداد الحقيقة .
مجموعة الأعداد الكلية .
مجموعة الأعداد الصحيحة .
مجموعة الأعداد النسبية أو الكسرية .
مجموعة الأعداد الحقيقة .
تمارين .
الفصل الثاني : الدوال .
1. مراجعة .
منحنى الدالة .
الدوال الجبرية .
الدوال غير الجبرية .
تمارين .
الدوال الجبرية .
الدوال غير الجبرية .
تمارين .
2. بعض الدوال العددية الهامة في الحاسب .
دالة الجزء الصحيح الأصغر .
دالة الجزء الصحيح الأكبر .
دالة الجزء الصحيح .
دالة القيمة المطلقة .
دالة باقي القسمة .
تمارين .
دالة الجزء الصحيح الأكبر .
دالة الجزء الصحيح .
دالة القيمة المطلقة .
دالة باقي القسمة .
تمارين .
الفصل الثالث : الخوارزميات .
الخوارزميات هي أسا البرمجة في الحاسب ، وسنتناول نبذة مختصرة عنها .
تعريف 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)
أي أن نسبة تزايد التعقد بدلالة حجم المعطيات هي من جنس تزايد الدالة المشار إليها .
وبهذه الطريقة سنعرف مسبقا الخورزميات التي ستستغرق وقتا معقولا والتي ستستغرق وقتا طويلا جدا وبالتالي فلا فائدة عملية من تنفيذها .
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
2. تعقد الخوارزمية :
نعني بالفضاء الحيز الذي تشغله الخوارزمية في الذاكرة فكلما كان صغيرا كلما كان أحسن ، رغم أن هذا العامل ليس هو الأهم .
ونعني بالزمن الوقت الذي تستغرقه الخوارزمية لحل المسألة المطروحة فكلما كان الوقت اقصر كلما كانت الخوارزمية أكثر فاعلية ، وهذا العامل يكاد أن يكون هو الأساسي .
تعريف 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 عملية أساسية ، ومنه فيمكن أن نقول بأن خوارزمية هورنير أحسن من خوارزمية التعويض .
نسبة التزايد والرمز O الكبير :
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)
أي أن نسبة تزايد التعقد بدلالة حجم المعطيات هي من جنس تزايد الدالة المشار إليها .
وبهذه الطريقة سنعرف مسبقا الخورزميات التي ستستغرق وقتا معقولا والتي ستستغرق وقتا طويلا جدا وبالتالي فلا فائدة عملية من تنفيذها .
3. بعض الخوارزميات المشهورة .
البحث الخطي :
المعطيات : DATA : مصفوفة من n عنصر و ITEM : قيمة معينة .
السؤال : هل ITEM موجود في DATA وإذا كان نعم فما هو موقعه ؟
الخوارزمية : سنجد LOC موقع ITEM في DATA أو نرسل رسالة عدم وجوده .
الخطوة الأولى : نقارن عناصر DATA مع ITEM واحدا واحد فإن وجدنا عنصرا مساويا سجلنا موقعه في LOC .
الخطوة الثانية : نرسل رسالة عدم وجود القيمة المطلوبة إذا لم ننجح في الخطوة الأولى .
تعقد الخوارزمية : في أسوأ حالة ، نحتاج في هذه الخوارزمية إلى أداء n مقارنة ومساواة واحدة إذن تعقد الخوارزمية هو : O(n) .
مثال 9 : طبق البحث الطي على المعطيات التالية:-
DATA = ( 0,-2.3.15.-7) ITEM = 15
الحل :
الخطوة الأولى : نعطي قيمة ابتدائية للمتغير loc = 1 ونقوم بالمقارنات التالية :-
15 مع 0 : غير متساويين فننتقل إلى العنصر الموالي : LOC = 2 ؛
15 مع -2 : غير متساويين فننتقل إلى العنصر الموالي : LOC = 3 ؛
15 مع 3 : مع متساويين فننتقل إلى العنصر الموالي : LOC = 4 ؛
15 مع 15 : متساويين إذن العنصر موجود وموقعه هو : LOC = 4 .
السؤال : هل ITEM موجود في DATA وإذا كان نعم فما هو موقعه ؟
الخوارزمية : سنجد LOC موقع ITEM في DATA أو نرسل رسالة عدم وجوده .
الخطوة الأولى : نقارن عناصر DATA مع ITEM واحدا واحد فإن وجدنا عنصرا مساويا سجلنا موقعه في LOC .
الخطوة الثانية : نرسل رسالة عدم وجود القيمة المطلوبة إذا لم ننجح في الخطوة الأولى .
تعقد الخوارزمية : في أسوأ حالة ، نحتاج في هذه الخوارزمية إلى أداء n مقارنة ومساواة واحدة إذن تعقد الخوارزمية هو : O(n) .
مثال 9 : طبق البحث الطي على المعطيات التالية:-
DATA = ( 0,-2.3.15.-7) ITEM = 15
الحل :
الخطوة الأولى : نعطي قيمة ابتدائية للمتغير loc = 1 ونقوم بالمقارنات التالية :-
15 مع 0 : غير متساويين فننتقل إلى العنصر الموالي : LOC = 2 ؛
15 مع -2 : غير متساويين فننتقل إلى العنصر الموالي : LOC = 3 ؛
15 مع 3 : مع متساويين فننتقل إلى العنصر الموالي : LOC = 4 ؛
15 مع 15 : متساويين إذن العنصر موجود وموقعه هو : LOC = 4 .
البحث الثنائي :
المعطيات : DATA : مصفوفة من n عنصر مرتبة من أصغرها إلى أكبرها و ITEM : قيمة معينة .
السؤال : هل ITEM موجود في DATA وإذا كان نعم فما هو موقعه ؟
الخوارزمية : تعتمد الخوارزمية على مبدأ " فرق تسد " كالتالي:-
الخطوة الأولى : نقارن العنصر ذا الموقع الوسط ( إذا كان n فرديا ) أو ( إذا كان n زوجيا ) مع ITEM .
إذا كان ITEM يساويه فنتوقف .
إذا كان ITEM أكبر منه فنبحث عن ITEM في النصف العلوي المتبقي .
إذا كان ITEM أصغر منه فنبحث عن ITEM في النصف السفلي المتبقي .
الخطوة الثانية : نكرر الخطوة الأولى بتطبيقها على النصف المتبقي من المصفوفة أي أننا نقارن ITEM مع العنصر ذي الموقع ( بحسب المجموع فريد أم زوجي ) وحيث : high هو موقع أكبر عنصر في المتبقي ، و low هو موقع أصغر عنصر في المتبقي .
الخطوة الثالثة : إذا لم نجد ITEM فنرسل رسالة عدم وجوده .
تعقد الخوارزمية : O(log2 n) .
مثال 10 : طبق البحث الثنائي على المعطيات التالية :-
DATA = ( -3,-1,0,4.5,5,10,16) ITEM = 15
الحل :-
الخطوة الأولى : نعطي قيمة ابتدائية للمتغيرات ونقوم بالمقارنة التالية:-
15 مع 15 > 4.5 : 4.5 فننتقل إلى النصف العلوي المتبقي : LOC = 6 , high = 7 , low = 5 ؛
15 مع 15 > 16 : 16 فنتوقف لأنه لم يتبقى شيء غير مفحوص .
الخطوة الثالثة : 15 غير موجود في DATA .
الترتيب البالوني :
المعطيات : DATA : مصفوفة من n عدد .
السؤال : رتب عناصر DATA من اصغر عنصر إلى أكبرها .
الخوارزمية : نبحث عن اصغر عنصر ونبادله بأول عنصر ، ثم نبحث عن العنصر الذي يليه ونبادله بثنائي عنصر وهكذا إلى أكبر عنصر .
تعقد الخوارزمية : في أسوأ حالة نحتاج لتثبيت أصغر عنصر إلى n-1 مقارنة و 3 ( n - 1 ) مساواة ، أي 4 ( n - 1 ) عملية أساسية .
ولتثبيت العنصر الذي يليه نحتاج إلى 4 ( n - 2 ) عملية أساسية ، وهكذا سنحتاج في الإجمال إلى :-
مثال 11 : طبق الترتيب البالوني على المعطيات التالية :-
DATA = ( 16,12,21,-5,-3,11,8 )
الحل : -
الخطوة الأولى : نعطي قيم ابتدائية للمتغيرات :
currentMinimum = 16 , currentMinLocation = 1, currentLevel = 1
ونبحث عن أصغر عنصر :
currentMinLocation currentMinimum DATA
2 12 12
2 12 21
4 - 5 - 5
5 - 3 - 3
5 - 3 11
5 - 3 8
إذن أصغر عنصر في هذا المستوى هو : - 3 وموقعه هو : 5
نبادل هذا العنصر بالعنصر الأول من هذا المستوى فتصبح المصفوفة كما يلي:-
DATA = ( -3,12,21,-5,16,11,8 )
الخطوة الثانية : نعطي قيم ابتدائية للمتغيرات :
currentMinimum = 12 , currentMinLocation = 2, currentLevel = 2
ونبحث عن أصغر عنصر في هذا المستوى :
DATA currentMinimum currentMinLocation
21 12 2
- 5 - 5 4
16 - 5 4
11 - 5 4
8 - 5 4
إذن أصغر عنصر في هذا المستوى هو : - 5 وموقعه هو : 4
نبادل هذا العنصر بالعنصر الأول من هذا المستوى وهو العنصر الثاني فتصبح المصفوفة كما يلي:-
DATA = ( -3,5,21,12,16,11,8 )
وهكذا إلى أن تصبح المصفوفة كما يلي:-
DATA = ( -3,-5,8,11,12,16,21 )
السؤال : هل ITEM موجود في DATA وإذا كان نعم فما هو موقعه ؟
الخوارزمية : تعتمد الخوارزمية على مبدأ " فرق تسد " كالتالي:-
الخطوة الأولى : نقارن العنصر ذا الموقع الوسط ( إذا كان n فرديا ) أو ( إذا كان n زوجيا ) مع ITEM .
إذا كان ITEM يساويه فنتوقف .
إذا كان ITEM أكبر منه فنبحث عن ITEM في النصف العلوي المتبقي .
إذا كان ITEM أصغر منه فنبحث عن ITEM في النصف السفلي المتبقي .
الخطوة الثانية : نكرر الخطوة الأولى بتطبيقها على النصف المتبقي من المصفوفة أي أننا نقارن ITEM مع العنصر ذي الموقع ( بحسب المجموع فريد أم زوجي ) وحيث : high هو موقع أكبر عنصر في المتبقي ، و low هو موقع أصغر عنصر في المتبقي .
الخطوة الثالثة : إذا لم نجد ITEM فنرسل رسالة عدم وجوده .
تعقد الخوارزمية : O(log2 n) .
مثال 10 : طبق البحث الثنائي على المعطيات التالية :-
DATA = ( -3,-1,0,4.5,5,10,16) ITEM = 15
الحل :-
الخطوة الأولى : نعطي قيمة ابتدائية للمتغيرات ونقوم بالمقارنة التالية:-
15 مع 15 > 4.5 : 4.5 فننتقل إلى النصف العلوي المتبقي : LOC = 6 , high = 7 , low = 5 ؛
15 مع 15 > 16 : 16 فنتوقف لأنه لم يتبقى شيء غير مفحوص .
الخطوة الثالثة : 15 غير موجود في DATA .
الترتيب البالوني :
المعطيات : DATA : مصفوفة من n عدد .
السؤال : رتب عناصر DATA من اصغر عنصر إلى أكبرها .
الخوارزمية : نبحث عن اصغر عنصر ونبادله بأول عنصر ، ثم نبحث عن العنصر الذي يليه ونبادله بثنائي عنصر وهكذا إلى أكبر عنصر .
تعقد الخوارزمية : في أسوأ حالة نحتاج لتثبيت أصغر عنصر إلى n-1 مقارنة و 3 ( n - 1 ) مساواة ، أي 4 ( n - 1 ) عملية أساسية .
ولتثبيت العنصر الذي يليه نحتاج إلى 4 ( n - 2 ) عملية أساسية ، وهكذا سنحتاج في الإجمال إلى :-
مثال 11 : طبق الترتيب البالوني على المعطيات التالية :-
DATA = ( 16,12,21,-5,-3,11,8 )
الحل : -
الخطوة الأولى : نعطي قيم ابتدائية للمتغيرات :
currentMinimum = 16 , currentMinLocation = 1, currentLevel = 1
ونبحث عن أصغر عنصر :
currentMinLocation currentMinimum DATA
2 12 12
2 12 21
4 - 5 - 5
5 - 3 - 3
5 - 3 11
5 - 3 8
إذن أصغر عنصر في هذا المستوى هو : - 3 وموقعه هو : 5
نبادل هذا العنصر بالعنصر الأول من هذا المستوى فتصبح المصفوفة كما يلي:-
DATA = ( -3,12,21,-5,16,11,8 )
الخطوة الثانية : نعطي قيم ابتدائية للمتغيرات :
currentMinimum = 12 , currentMinLocation = 2, currentLevel = 2
ونبحث عن أصغر عنصر في هذا المستوى :
DATA currentMinimum currentMinLocation
21 12 2
- 5 - 5 4
16 - 5 4
11 - 5 4
8 - 5 4
إذن أصغر عنصر في هذا المستوى هو : - 5 وموقعه هو : 4
نبادل هذا العنصر بالعنصر الأول من هذا المستوى وهو العنصر الثاني فتصبح المصفوفة كما يلي:-
DATA = ( -3,5,21,12,16,11,8 )
وهكذا إلى أن تصبح المصفوفة كما يلي:-
DATA = ( -3,-5,8,11,12,16,21 )
تمارين .
المراجع .
1) صلاح أحمد وإلهام حمصى وموفق دعبول ، معجم الرياضيات المعاصرة ، مؤسسة الرسالة ، بيروت 1403 هـ - 1983 م .
2) Alfred Aho, John Hopcroft and Jeffrey Ullman, Design and Analysis of Computer Algorithms, Addison Wesley, Reading, England, 1974.
3) Gwyn Davies and Gordon Hick, Mathematics for scientific and technical students, Addison Wesley Longman, Harlow, England, 1998.
4) Micheal Garey and David Johnson, Computer and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
5) C. L. Lui, Elements of Discrete Mathematics, McGraw-Hill, New York, 1977.
6) Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, England, 1986.
7) Seymour Lipschutz and Marc Lipson, Discrete Mathematics, McGraw-Hill, New York, 1997.
8) Peter Tebbutt, Basic Mathematics, John Wiley & Sons, Chichester, England, 1998.
3) Gwyn Davies and Gordon Hick, Mathematics for scientific and technical students, Addison Wesley Longman, Harlow, England, 1998.
4) Micheal Garey and David Johnson, Computer and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
5) C. L. Lui, Elements of Discrete Mathematics, McGraw-Hill, New York, 1977.
6) Alexander Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, England, 1986.
7) Seymour Lipschutz and Marc Lipson, Discrete Mathematics, McGraw-Hill, New York, 1997.
8) Peter Tebbutt, Basic Mathematics, John Wiley & Sons, Chichester, England, 1998.
merci
ردحذف