رياضيات الأعمال، الصف الثاني عشر (حقل الأعمال) · الخوارزميات ونظرية المخططات
ورقة مراجعة: الخوارزميات وجداول التتبّع
أهم أفكار الدرس ومصطلحاته وقوانين الوحدة بمكان واحد. اطبعها وراجع منها قبل الامتحان.
أهم الأفكار
- تطبيق خوارزمية مكتوبة بالكلمات نتّبع الخطوات واحدة بعد الأخرى على المُدخَلة. مثلًا الفرق المطلق يعني طرح الأصغر من الأكبر، فهو .
- بناء جدول التتبّع نضع عمودًا لرقم الخطوة، وعمودًا لكل متغيّر، وعمودًا لنواتج Print. والتعليمة ليست معادلة، بل تعني زيادة قيمة بمقدار 1، وتعني نسخ القيمة الحالية لـ في .
- أشكال مخطط سير العمليات مستطيل للتعليمات، ومعيّن للقرار (جوابه نعم أو لا)، ومستطيل بزوايا مستديرة للبداية والنهاية، ومتوازي أضلاع للإدخال والإخراج.
- خوارزمية المعادلة التربيعية لإيجاد جذور نحسب المميّز . إذا كان فلا حلول حقيقية، وإذا كان فالحل ، وإذا كان فالحلّان .
مصطلحات الدرس
- الخوارزمية (algorithm)
- خطوات مرتبة ومحدّدة نتّبعها لحلّ مسألة ما.
- المُدخَلة
- القيمة التي نطبّق عليها الخوارزمية في بدايتها.
- الطريقة شبه الرمزية (pseudocode)
- كتابة الخوارزمية بخطوات مرقّمة تستعمل كلمات ورموزًا مثل Let وPrint وIf.
- جدول التتبّع (trace table)
- جدول نسجّل فيه قيمة كل متغيّر وكل ناتج بعد كل خطوة أثناء تطبيق الخوارزمية.
- مخطط سير العمليات (flow chart)
- رسم من أشكال هندسية وأسهم يبيّن ترتيب خطوات الخوارزمية.
- العدّاد
- متغيّر يزداد في كل دورة ويضمن أن تنتهي الخوارزمية.
- المُخرَجات
- القيم التي تطبعها الخوارزمية بالأمر Print.
قوانين الخوارزميات ونظرية المخططات
- جدول التتبع
- نضع عمودًا لرقم الخطوة وعمودًا لكل متغير وعمودًا للمطبوع؛ والتعليمة تعني استبدال قيمة بالقيمة الجديدة وليست معادلة.
- أشكال مخطط سير العمليات
- المستطيل للتعليمات، والمعيّن للقرار (نعم أو لا)، والمستطيل بزوايا مستديرة للبداية والنهاية، ومتوازي الأضلاع للإدخال والإخراج.
- خوارزمية حل المعادلة التربيعية
- إذا كان فلا حلول حقيقية، وإذا كان فالحل ، وإذا كان فللمعادلة حلان.
- الحد الأدنى لعدد الصناديق
- نقرّب الناتج إلى الأعلى دائمًا، فإن ساوى عدد صناديق حلّنا هذا العدد فالحل أمثل.
- خوارزمية الملاءمة الأولى
- نلتزم ترتيب العناصر المعطى، ونضع كل عنصر في أول صندوق يتسع له، ونفتح صندوقًا جديدًا إذا لم يتسع أي صندوق.
- خوارزمية الملاءمة المتناقصة
- نرتّب العناصر تنازليًّا أولًا ثم نطبّق الملاءمة الأولى؛ وهي أفضل عادة لكنها لا تضمن الحل الأمثل.
- خوارزمية الصندوق الكامل
- نملأ أولًا صناديق من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالملاءمة الأولى.
- حساب المهدور
- المهدور هو المساحة الفارغة الكلية في الصناديق المستعملة.
- تصنيف المخطط بدرجات الرؤوس
- المخطط المتصل الذي درجات رؤوسه كلها زوجية أويلري، وإن كان فيه رأسان فرديان فقط فهو شبه أويلري، وغير ذلك لا يكون أيًّا منهما.
- أقصر مسار أويلري في مخطط أويلري
- نمرّ على كل حافة مرة واحدة فقط فلا نكرر شيئًا.
- أقصر مسار أويلري في مخطط شبه أويلري
- نكرّر حافات أقصر طريق بين الرأسين الفرديين.
- مخطط فيه أكثر من رأسين فرديين
- نجرّب كل طرائق ازدواج الرؤوس الفردية ونختار الطريقة التي مجموع أوزان طرقها أقل، ثم نضيفه إلى الوزن الكلي.
- مجموع درجات الرؤوس
- كل حافة تمس رأسين فمجموع الدرجات ضعف عدد الحافات.
- عدد الرؤوس الفردية
- عدد الرؤوس ذات الدرجة الفردية في أي مخطط زوجي أو صفر.
- طول المسار في مخطط موزون
- طول المسار هو مجموع أوزان حافاته.
- شرط وجود دارة أويلر
- إذا كانت درجة كل رأس زوجية ويوجد ممر بين أي رأسين فللمخطط دارة أويلر.
- الشجرة الشاملة
- الشجرة متصلة وبلا دارات، والشجرة الشاملة لمخطط من رأسًا تحوي كل رؤوسه و حافة.
- خوارزمية برايم لأصغر شجرة شاملة
- نبدأ من رأس، ونضيف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها دون تكوين دارة.
- مكمل المخطط
- المخطط التام فيه حافة، وحافات مع حافات مكمله تعطي .
- مصفوفة الجوار
- رتبتها حيث عدد الرؤوس، والعنصر إذا وُجدت حافة بين الرأسين و إذا لم توجد.
- مصفوفة الوزن
- نكتب وزن الحافة في الموضع المناظر ونكتب حيث لا يوجد اتصال.
من اُدرُس: odrosai.com/ar/subjects/JO-MATH-BUS/units/2/bus-algorithms_trace
بدك تتأكد إنك فاهم؟
سجّل مجاناً وحلّ أسئلة على هالدرس، بتتصحّح خطوة خطوة ومعها تلميحات لما تعلق.
سجّل مجاناً وراجع مع فهيم اقرأ تلخيص الدرس · راجعها ببطاقات · كل مصطلحات الدرس بصفحة وحدة