رياضيات الأعمال، الصف الثاني عشر (حقل الأعمال) · الوحدة 2 · الوحدات والمواضيع
الخوارزميات ونظرية المخططات
الدروس باختصار
الخوارزميات وجداول التتبّع
الخوارزمية مجموعة من الخطوات المرتبة التي تحلّ مسألة معيّنة، ويمكن كتابتها بالكلمات أو بطريقة شبه رمزية أو بمخطط سير العمليات. نستعملها في الحساب والبرمجة، ويساعدنا جدول التتبّع على تنفيذها خطوة خطوة من دون خطأ.
اقرأ تلخيص الدرس كامل · أسئلة على الدرس
- تطبيق خوارزمية مكتوبة بالكلمات: نتّبع الخطوات واحدة بعد الأخرى على المُدخَلة. مثلًا الفرق المطلق يعني طرح الأصغر من الأكبر، فهو .
- بناء جدول التتبّع: نضع عمودًا لرقم الخطوة، وعمودًا لكل متغيّر، وعمودًا لنواتج Print. والتعليمة ليست معادلة، بل تعني زيادة قيمة بمقدار 1، وتعني نسخ القيمة الحالية لـ في .
- أشكال مخطط سير العمليات: مستطيل للتعليمات، ومعيّن للقرار (جوابه نعم أو لا)، ومستطيل بزوايا مستديرة للبداية والنهاية، ومتوازي أضلاع للإدخال والإخراج.
- خوارزمية المعادلة التربيعية: لإيجاد جذور نحسب المميّز . إذا كان فلا حلول حقيقية، وإذا كان فالحل ، وإذا كان فالحلّان .
خوارزميات تعبئة الصناديق
مسألة تعبئة الصندوق تسأل: كيف نضع عناصر مختلفة المقاسات في أقل عدد ممكن من الصناديق ذات السعة الواحدة؟ نستعملها في تحميل البضائع في الشاحنات، وترتيب الأغراض على الرفوف، وتخزين الملفات على الأقراص، وقصّ القماش من لفّات كبيرة.
اقرأ تلخيص الدرس كامل · أسئلة على الدرس
- الحدّ الأدنى لعدد الصناديق: نجمع مقاسات العناصر ونقسم على سعة الصندوق ثم نقرّب إلى الأعلى: . إن ساوى عدد صناديق حلّنا هذا العدد فالحلّ أمثل.
- المُلاءَمة الأولى والمُتناقِصة: في الأولى نلتزم الترتيب المعطى، وفي الثانية نرتّب تنازليًا قبل التعبئة. تضع كل منهما العنصر في أول صندوق يتّسع له، وتضيف صندوقًا جديدًا إذا لم يتّسع أي صندوق. الثانية أفضل عادةً لكنها لا تضمن الحلّ الأمثل.
- خوارزمية الصندوق الكامل: نملأ أولًا صناديق كاملة من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالمُلاءَمة الأولى. تعطي حلًّا جيدًا عادةً لكنها صعبة إذا كثرت العناصر أو كانت أعدادًا عشرية.
- حساب المهدور: المهدور = (عدد الصناديق المستعملة × سعة الصندوق) − مجموع المقاسات.
قاعدة القسمة على 11
للتحقّق من قابلية عدد للقسمة على نستعمل خوارزمية قصيرة تعتمد على أرقام العدد، دون إجراء القسمة. نتعلّم هنا خطواتها، وكيف نطبّقها على أعداد ذات أرقام كثيرة، وكيف نستعملها لإيجاد رقم مجهول.
اقرأ تلخيص الدرس كامل · أسئلة على الدرس
- خطوات الخوارزمية: (1) نجمع الأرقام الواقعة في المواضع الفردية. (2) نجمع الأرقام الواقعة في المواضع الزوجية. (3) نجد الفرق المطلق بين المجموعين. (4) إذا كان الفرق أو من مضاعفات فالعدد يقبل القسمة على ، وإلا فلا.
- مثال على الترقيم: في العدد الأرقام في المواضع الفردية (من اليمين) هي ومجموعها ، وفي الزوجية ومجموعها ، والفرق فهو يقبل القسمة. أمّا فالفرد والزوج والفرق فلا يقبل. لا يتغيّر الحكم إذا بدأنا الترقيم من اليسار لأن الفرق مطلق.
- استعمال الخوارزمية لرقم ناقص: إذا كان في العدد رقم مجهول كتبنا مجموعي المواضع الفردية والزوجية بدلالة ، ثم طلبنا أن يكون الفرق المطلق أو ، ونحسب بين و (تطبيق للقاعدة نفسها، معلومة مضافة).
مخططات أويلر
مُخطَّط أويلر هو مُخطَّط نستطيع فيه المرور بكل حافة مرَّة واحدة فقط. يُستعمَل هذا في تخطيط مسارات سيّارات البريد وتنظيف الأنابيب وجمع النفايات، حيث نريد المرور بكل شارع أو أنبوب بأقل كلفة ممكنة.
اقرأ تلخيص الدرس كامل · أسئلة على الدرس
- تصنيف المُخطَّط بدرجات الرؤوس: إذا كان المُخطَّط متصلًا وكل درجات رؤوسه زوجية فهو أويلري. وإذا كان متصلًا وفيه رأسان فقط درجتاهما فرديتان فهو شبه أويلري. وإذا زاد عدد الرؤوس الفردية على اثنين، أو كان المُخطَّط غير متصل، فليس أويلريًّا ولا شبه أويلري.
- أقصر مسار أويلري: المُخطَّط الأويلري: الطول يساوي الوزن الكلي للمُخطَّط: .
- أقصر مسار أويلري: المُخطَّط شبه الأويلري: نكرِّر حافات أقصر طريق بين الرأسين الفرديين، فيكون الطول: .
- أقصر مسار أويلري: أكثر من رأسين فرديين: نحدِّد الرؤوس الفردية، ونجرِّب كل طرائق ازدواجها (إضافة حافات تجمع كل رأسين معًا)، ونختار الطريقة ذات مجموع الأوزان المضافة الأقل، ثم نجمع الوزن الكلي بعد الإضافة.
المخططات
المُخطَّط (graph) طريقة بصرية لتمثيل الروابط بين أشياء مختلفة: مدن تصل بينها طرق، أو محطات باص، أو أجهزة حاسوب متصلة بشبكة. نتعلّم هنا مكوّنات المُخطَّط وكيف نحسب درجات رؤوسه ونصنّف المسارات داخله.
اقرأ تلخيص الدرس كامل · أسئلة على الدرس
- مجموعة الرؤوس والحافات والدرجات: نكتب رؤوس المُخطَّط في مجموعة وحافاته في مجموعة أخرى (الحافة بين A وB نكتبها AB أو BA). درجات الرؤوس تُجمع في مجموعة الدرجات ، والدرجة زوجية أو فردية بحسب عددها.
- مجموع الدرجات: كل حافة تمسّ رأسين، فمجموع درجات الرؤوس يساوي ضعف عدد الحافات: . ومنه يكون عدد الرؤوس ذات الدرجة الفردية زوجيًّا أو صفرًا.
- طول المسار في المُخطَّط الموزون: طول المسار هو مجموع أوزان حافاته. لإيجاد أقصر مسار نعدّد المسارات الممكنة بلا حافات مكرّرة ونحسب طول كل منها ثم نختار الأصغر.
- شرط وجود دارة أويلر: إذا كانت درجة كل رأس زوجية ويوجد ممر بين أي رأسين فإنّ المُخطَّط يحتوي على دارة أويلر.
المخططات الخاصة والأشجار
المُخطَّط مجموعة رؤوس تصل بينها حافات، ويُستعمل لتمثيل شبكات مثل الطرق وأسلاك الكهرباء وأنابيب المياه. في هذا الدرس نتعرّف أنواعًا خاصة منه (البسيط، والمتصل، والكامل، والشجرة)، ثم نبحث عن أقل كلفة لربط كل الرؤوس، ونمثّل المُخطَّط بمصفوفة.
اقرأ تلخيص الدرس كامل · أسئلة على الدرس
- الشجرة الشاملة: الشجرة متصلة وبلا دارات. وتحوي الشجرة الشاملة لمُخطَّط من رأسًا كل رؤوسه، ويمكن أن يكون للمُخطَّط الواحد عدة أشجار شاملة.
- خوارزمية برايم: لإيجاد أصغر شجرة شاملة لمُخطَّط موزون متصل: ابدأ من أي رأس، ثم أضف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها، ولا تُضِف حافة تكوّن دارة. كرّر حتى تدخل كل الرؤوس. الوزن الكلي هو مجموع أوزان الحافات المضافة.
- المُكمِّل: لرسم ارسم ثم احذف منه حافات G. وإذا جمعنا حافات G وحافات نحصل على .
- المصفوفات: رتبة المصفوفة حيث عدد الرؤوس، ولكل رأس صف وعمود. في مصفوفة الجوار يدل 0 على عدم وجود حافة. في مصفوفة الوزن يُكتب الوزن، ويُكتب – عند عدم الاتصال.
المخططات الجزئية
المخطط الجزئي مخطط نبنيه من بعض رؤوس مخطط آخر وبعض حافاته. نتعلّم هنا تعريفه بدقّة، وكيف نرسم مخططين جزئيين من أي مخطط معطى، وكيف نتحقّق أن مخططًا ما جزئي أو لا، وأن المخطط الجزئي لا يشترط أن يكون متصلًا.
اقرأ تلخيص الدرس كامل · أسئلة على الدرس
- تعريف المخطط الجزئي: المخطط الجزئي من المخطط هو مخطط كل رؤوسه من رؤوس وكل حافاته من حافات . لا نضيف رأسًا جديدًا ولا حافة غير موجودة في ، ولا نغيّر الرأسين اللذين تصل بينهما الحافة.
- طريقة رسم مخطط جزئي: نختار أولًا مجموعة من الرؤوس (كلها أو بعضها)، ثم نختار حافات من بين الحافات الموجودة فعلًا في المخطط الأصلي بين هذه الرؤوس، ويجوز أن نحذف بعض الحافات حتى بين الرؤوس المختارة. يوجد عادةً كثير من المخططات الجزئية لمخطط واحد، فنأخذ أي اثنين منها.
- لا يشترط الاتصال: قد يكون المخطط الجزئي غير متصل، مثل أن نأخذ رأسًا لا نصله بحافة أو نأخذ حافتين متباعدتين. وإذا كان المخطط الأصلي بسيطًا فكل مخطط جزئي منه بسيط.
- اختبار المخطط الجزئي: نمرّ على كل رأس في المخطط المقترَح فنتأكد أنه في الأصل، ثم على كل حافة فنتأكد أنها حافة بين الرأسين نفسيهما في الأصل. إذا وُجد رأس جديد، أو عدد رؤوس أكبر من الأصل، أو حافة غير موجودة، فهو ليس مخططًا جزئيًا.
ورقة القوانين
- جدول التتبع
- نضع عمودًا لرقم الخطوة وعمودًا لكل متغير وعمودًا للمطبوع؛ والتعليمة تعني استبدال قيمة بالقيمة الجديدة وليست معادلة.
- أشكال مخطط سير العمليات
- المستطيل للتعليمات، والمعيّن للقرار (نعم أو لا)، والمستطيل بزوايا مستديرة للبداية والنهاية، ومتوازي الأضلاع للإدخال والإخراج.
- خوارزمية حل المعادلة التربيعية
- إذا كان فلا حلول حقيقية، وإذا كان فالحل ، وإذا كان فللمعادلة حلان.
- الحد الأدنى لعدد الصناديق
- نقرّب الناتج إلى الأعلى دائمًا، فإن ساوى عدد صناديق حلّنا هذا العدد فالحل أمثل.
- خوارزمية الملاءمة الأولى
- نلتزم ترتيب العناصر المعطى، ونضع كل عنصر في أول صندوق يتسع له، ونفتح صندوقًا جديدًا إذا لم يتسع أي صندوق.
- خوارزمية الملاءمة المتناقصة
- نرتّب العناصر تنازليًّا أولًا ثم نطبّق الملاءمة الأولى؛ وهي أفضل عادة لكنها لا تضمن الحل الأمثل.
- خوارزمية الصندوق الكامل
- نملأ أولًا صناديق من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالملاءمة الأولى.
- حساب المهدور
- المهدور هو المساحة الفارغة الكلية في الصناديق المستعملة.
- تصنيف المخطط بدرجات الرؤوس
- المخطط المتصل الذي درجات رؤوسه كلها زوجية أويلري، وإن كان فيه رأسان فرديان فقط فهو شبه أويلري، وغير ذلك لا يكون أيًّا منهما.
- أقصر مسار أويلري في مخطط أويلري
- نمرّ على كل حافة مرة واحدة فقط فلا نكرر شيئًا.
- أقصر مسار أويلري في مخطط شبه أويلري
- نكرّر حافات أقصر طريق بين الرأسين الفرديين.
- مخطط فيه أكثر من رأسين فرديين
أمثلة محلولة
مثال 1
الخوارزمية: (1) أجمع أرقام العدد. (2) إذا كان المجموع يقبل القسمة على 9 فالعدد يقبل القسمة على 9، وإلا فلا. طبّقها على العدد 5832 ثم على العدد 4715. ما مجموع أرقام العدد 5832؟
اعرض الحل
- العدد 5832: نجمع أرقامه .
- المجموع يساوي 18.
- فالمجموع يقبل القسمة على 9، إذن 5832 يقبل القسمة على 9.
- العدد 4715: ، و17 لا يقبل القسمة على 9، إذن 4715 لا يقبل القسمة على 9.
الجواب: مجموع أرقام 5832 هو ، فالعدد يقبل القسمة على 9، أما 4715 فلا يقبلها.
مثال 2
يراد تعبئة عناصر مقاساتها 6, 9, 4, 7, 5, 8, 3, 2, 7 في صناديق سعة كلٍّ منها 12 وحدة. جد الحدّ الأدنى لعدد الصناديق اللازمة.
اعرض الحل
- نجمع المقاسات: .
- نقسم على سعة الصندوق: .
- نقرّب إلى الأعلى لأن الجزء العشري يحتاج صندوقًا إضافيًا كاملًا، فنحصل على 5.
الجواب: الحدّ الأدنى هو صناديق.
مثال 3
أطبّق الخوارزمية على .
اعرض الحل
- المواضع الفردية (الأول والثالث من اليمين): و، ومجموعها .
- المواضع الزوجية (الثاني والرابع): و، ومجموعها .
- الفرق المطلق وهو من مضاعفات ، فالعدد يقبل القسمة على ().
الجواب: نعم يقبل القسمة
جاهز تتدرّب؟
285 سؤال على هالوحدة، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 285 سؤال من هالوحدة مجانًا