رياضيات الأعمال، الصف الثاني عشر (حقل الأعمال) · الخوارزميات ونظرية المخططات
ورقة مراجعة: خوارزميات تعبئة الصناديق
أهم أفكار الدرس ومصطلحاته وقوانين الوحدة بمكان واحد. اطبعها وراجع منها قبل الامتحان.
أهم الأفكار
- الحدّ الأدنى لعدد الصناديق نجمع مقاسات العناصر ونقسم على سعة الصندوق ثم نقرّب إلى الأعلى: . إن ساوى عدد صناديق حلّنا هذا العدد فالحلّ أمثل.
- المُلاءَمة الأولى والمُتناقِصة في الأولى نلتزم الترتيب المعطى، وفي الثانية نرتّب تنازليًا قبل التعبئة. تضع كل منهما العنصر في أول صندوق يتّسع له، وتضيف صندوقًا جديدًا إذا لم يتّسع أي صندوق. الثانية أفضل عادةً لكنها لا تضمن الحلّ الأمثل.
- خوارزمية الصندوق الكامل نملأ أولًا صناديق كاملة من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالمُلاءَمة الأولى. تعطي حلًّا جيدًا عادةً لكنها صعبة إذا كثرت العناصر أو كانت أعدادًا عشرية.
- حساب المهدور المهدور = (عدد الصناديق المستعملة × سعة الصندوق) − مجموع المقاسات.
مصطلحات الدرس
- خوارزميات تعبئة الصناديق
- طرائق منظّمة بخطوات محدّدة لتوزيع العناصر على الصناديق بأقل عدد ممكن منها.
- الحدّ الأدنى لعدد الصناديق
- أصغر عدد صحيح من الصناديق يمكن أن يتّسع لمجموع مقاسات العناصر؛ نحصل عليه بقسمة المجموع على سعة الصندوق ثم التقريب إلى الأعلى.
- خوارزمية المُلاءَمة الأولى
- نأخذ العناصر بالترتيب المعطى، ونضع كل عنصر في أول صندوق يتّسع له.
- خوارزمية المُلاءَمة الأولى المُتناقِصة
- نرتّب المقاسات من الأكبر إلى الأصغر أولًا، ثم نطبّق المُلاءَمة الأولى.
- خوارزمية الصندوق الكامل
- نبحث أولًا عن عناصر مجموعها يملأ صندوقًا تمامًا ونعبّئها معًا، ثم نطبّق المُلاءَمة الأولى على الباقي.
- الحلّ الأمثل
- حلّ عدد صناديقه يساوي الحدّ الأدنى لعدد الصناديق.
- المهدور
- المساحة الفارغة المتبقية في الصناديق المستعملة.
قوانين الخوارزميات ونظرية المخططات
- جدول التتبع
- نضع عمودًا لرقم الخطوة وعمودًا لكل متغير وعمودًا للمطبوع؛ والتعليمة تعني استبدال قيمة بالقيمة الجديدة وليست معادلة.
- أشكال مخطط سير العمليات
- المستطيل للتعليمات، والمعيّن للقرار (نعم أو لا)، والمستطيل بزوايا مستديرة للبداية والنهاية، ومتوازي الأضلاع للإدخال والإخراج.
- خوارزمية حل المعادلة التربيعية
- إذا كان فلا حلول حقيقية، وإذا كان فالحل ، وإذا كان فللمعادلة حلان.
- الحد الأدنى لعدد الصناديق
- نقرّب الناتج إلى الأعلى دائمًا، فإن ساوى عدد صناديق حلّنا هذا العدد فالحل أمثل.
- خوارزمية الملاءمة الأولى
- نلتزم ترتيب العناصر المعطى، ونضع كل عنصر في أول صندوق يتسع له، ونفتح صندوقًا جديدًا إذا لم يتسع أي صندوق.
- خوارزمية الملاءمة المتناقصة
- نرتّب العناصر تنازليًّا أولًا ثم نطبّق الملاءمة الأولى؛ وهي أفضل عادة لكنها لا تضمن الحل الأمثل.
- خوارزمية الصندوق الكامل
- نملأ أولًا صناديق من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالملاءمة الأولى.
- حساب المهدور
- المهدور هو المساحة الفارغة الكلية في الصناديق المستعملة.
- تصنيف المخطط بدرجات الرؤوس
- المخطط المتصل الذي درجات رؤوسه كلها زوجية أويلري، وإن كان فيه رأسان فرديان فقط فهو شبه أويلري، وغير ذلك لا يكون أيًّا منهما.
- أقصر مسار أويلري في مخطط أويلري
- نمرّ على كل حافة مرة واحدة فقط فلا نكرر شيئًا.
- أقصر مسار أويلري في مخطط شبه أويلري
- نكرّر حافات أقصر طريق بين الرأسين الفرديين.
- مخطط فيه أكثر من رأسين فرديين
- نجرّب كل طرائق ازدواج الرؤوس الفردية ونختار الطريقة التي مجموع أوزان طرقها أقل، ثم نضيفه إلى الوزن الكلي.
- مجموع درجات الرؤوس
- كل حافة تمس رأسين فمجموع الدرجات ضعف عدد الحافات.
- عدد الرؤوس الفردية
- عدد الرؤوس ذات الدرجة الفردية في أي مخطط زوجي أو صفر.
- طول المسار في مخطط موزون
- طول المسار هو مجموع أوزان حافاته.
- شرط وجود دارة أويلر
- إذا كانت درجة كل رأس زوجية ويوجد ممر بين أي رأسين فللمخطط دارة أويلر.
- الشجرة الشاملة
- الشجرة متصلة وبلا دارات، والشجرة الشاملة لمخطط من رأسًا تحوي كل رؤوسه و حافة.
- خوارزمية برايم لأصغر شجرة شاملة
- نبدأ من رأس، ونضيف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها دون تكوين دارة.
- مكمل المخطط
- المخطط التام فيه حافة، وحافات مع حافات مكمله تعطي .
- مصفوفة الجوار
- رتبتها حيث عدد الرؤوس، والعنصر إذا وُجدت حافة بين الرأسين و إذا لم توجد.
- مصفوفة الوزن
- نكتب وزن الحافة في الموضع المناظر ونكتب حيث لا يوجد اتصال.
من اُدرُس: odrosai.com/ar/subjects/JO-MATH-BUS/units/2/bus-bin_packing
بدك تتأكد إنك فاهم؟
سجّل مجاناً وحلّ أسئلة على هالدرس، بتتصحّح خطوة خطوة ومعها تلميحات لما تعلق.
سجّل مجاناً وراجع مع فهيم اقرأ تلخيص الدرس · راجعها ببطاقات · كل مصطلحات الدرس بصفحة وحدة