D1 · Decision Mathematics 1

رياضيات القرار 1 (D1، ورقة WDM01/01، 1 ساعة 30 دقيقة، 75 علامات، أول تقييم يونيو 2019) هو الخيار المنفصل في IAL: تُفترض P1–P2، وكل طريقة هي خوارزمية — قائمة نهائية من التعليمات الدقيقة. لا توجد مدخلات في كتيب القوانين beyond الـ الأساسيات: العلامات منفذة لإجراءات بدقة وإرجاع النتائج بالصيغة المطلوبة. يشمل هذا المرجع خوارزميات الفرز والتعبئة، وأشجار التغطية الدنيا، أقصر المسارات، ومشكلة بريد الصين ومشكلة بائع التجوال، وتحليل المسار الحرج والبرمجة الخطية.

قواعد المنزل للإجابات الخوارزمية:

تقوم خوارزمية الترتيب الفقاعي بمقارنة العناصر المجاورة وتبديل الأزواج غير المرتبة، تمريرة واحدة في كل مرة؛ تنتهي أي تمريرة لا تحتوي على تبديلات. تختار خوارزمية الترتيب السريع العنصر الأوسط القائمة كمحور دوران، يقسم العناصر المتبقية إلى مجموعات "أقل من المحور" و"يساوي المحور" و"أكبر من المحور" (مع الاحتفاظ بكل نسخة)؛ يصنف المجموعات الأصغر والأكبر بشكل تكراري — يجب ذكر المحور دائمًا و تحدد المواصفات اختيار عنصر الوسطي وفق الطريقة المعرّفة في المصطلحات، لذا تحافظ قوائم التمارين هنا على عدد فردي من العناصر ويكون العنصر الوسطي هو الذي يقع عند الموقع $\tfrac{n+1}2$. تعبئة الصناديق: وضع أولي يوضع كل عنصر في أول صندوق يتسع له؛ وضع أولي تنازلي يرتب العناصر من الأكبر إلى الأصغر ثم يطبق الوضع الأولي؛ تعبئة الصندوق الكامل تبحث عن تركيبات تملأ صندوقًا تمامًا.

مثال محلل — الترتيب السريع (الأصلي). رتب 9، 2، 7، 5، 3، 4، 6. العنصر الأوسط (الموضع 4 من 7) هو 5: الأقل = 2، 3، 4؛ الأكبر = 9، 7، 6، مما يعطي 2، 3، 4، 5، 9، 7، 6. القائمة الفرعية 2، 3، 4 (محور 3): 2، 3، 4 — مرتبة. القائمة الفرعية 9، 7، 6 (محور 7): 6، 7، 9 — مرتبة. القائمة النهائية: 2، 3، 4، 5، 6، 7، 9.

مثال محلل — تعبئة الصناديق (الأصلي). صناديق سعتها 10؛ عناصر 7، 5، 4، 3، 6، 2 (إجمالي 27، إذن لا يقل عن 3 صندوق). الوضع الأولي: 7→صندوق1، 5→صندوق2 (7+5 > 10)، 4→صندوق2 (9)، 3→صندوق1 (10)، 6→صندوق3، 2→صندوق3 (8): الصناديق (7,3)، (5,4)، (6,2). الوضع الأولي التنازلي: 7، 6، 5، 4، 3، 2: 7→b1، 6→b2، 5→b3 (6+5 > 10)، 4→b2 (10)، 3→b1 (10)، 2→b3 (7): صناديق (7,3)، (6,4)، (5,2) — أيضًا صناديق 3.

شجرة التغطية الصغرى (MST) تربط كل رأس بأقل وزن إجمالي ممكن. خوارزمية كروسكال: رتّب الحواف حسب الوزن، وأضف أصغرها الذي لا يشكّل دورة (ارفضه وانتقل عند حدوث ذلك). خوارزمية بریم: نمّ شجرةً من أي رأس بداية، وأضف بشكل متكرر الحافة الأرخص من الشجرة إلى رأس جديد. رأس جديد. الصيغة المصفوفية لخوارزمية بریم: احذف صف البداية، وضع دائرة حول أصغر قيمة متبقية في عمود الرأس المختار، واستمر في ذلك. كروسكال تعتمد على الحواف (مناسبة للشبكات المرسومة)؛ بریم تعتمد على الرؤوس (مناسبة للمصفوفات). كلاهما يعطي نفس الإجمالي؛ قد تختلف الحواف فقط عندما تتساوى الأوزان. في عمود الرأس المختار، واستمر. كروسكال يعتمد على الحواف (جيد في حالة التعادل always list the edges in the order chosen and give the total. always list the edges in the order chosen and give the total.

مثال محلول (الأصلي). حواف AB 4، AC 2، BC 3، BD 5، CD 1: يأخذ كروسكال CD 1، AC 2، BC 3 (B تنضم — لا دورة)، ثم ترفض AB 4 و BD 5 (دورات): المجموع الكلي لـ MST هو 6. بریم من A: AC 2، CD 1 (أرخص حافة من {A,C} إلى رأس جديد)، CB 3: نفس الشجرة، و المجموع الكلي 6 ✓. اذكر دائماً الحواف بالترتيب الذي تم اختيارها به وأعطِ المجموع الكلي.

للوزن غير السالب للحواف، خوارزمية ديوكسترا تعطي الرؤوس أصغر مسافة كلية مُكتشفة حتى الآن: علامة رأس البداية 0؛ اختر بشكل متكرر الرأس غير المُعَيَّن ذو الأصغر تعيين مؤقت، اجعله دائمًا، وحلّل جيرانه (جديد = دائم + الوزن، فقط إذا كان أصغر). سجّل ترتيب التثبيت والنهاية التسميات؛ يتم استعادة المسار عن طريق التتبع العكسي عبر الرؤوس التي تساوي تسميتها التسمية النهائية ناقص وزن الوصلة.

مثال محلول (أصلي). الحواف AB 4، AC 2، BC 1، BD 5، CD 8. التسميات: A = 0 دائم; C = 2 دائم؛ B = min(4, 2+1) = 3 دائم؛ D = min(3+5, 2+8) = 8 دائم. المسار الأقصر من A إلى D طوله 8: A–C–B–D (التتبع العكسي: 8 = 3 + 5 عند B، 3 = 2 + 1 عند C).

مسألة فحص المسار (بريد الصين) تمر على كل حافة على الأقل مرة وتعود إلى نقطة البداية. الطول الكلي = مجموع جميع الحواف + أقصر طريقة لـ تكرار الحواف لتصبح كل الرؤوس زوجية. حدد الرؤوس الفردية (لا تزيد عن أربعة)، ودرج ازوجاتها، واختر الزوجية ذات أقل وزن إجمالي، وأعد تكرار تلك الحواف. صغّ الزوجية قبل المجموع الكلي.

مثال محلول (أصلي). الحواف AB 4، AC 2، BC 3، BD 5، CD 1 (المجموع 15). الدرجات: A 2, B 3، C 3، D 2 — الرؤوس الفردية هي B وC، لذا نعيد تكرار BC (الوزن 3): أقصر مسار مغلق يمر على كل حافة على الأقل طوله 15 + 3 = 18.

مسألة البائع المتجول الكلاسيكية تجوب كل رأس مرة واحدة بالضبط وتعود، على رسم بياني كامل مع عدم المساواة المثلثية. الحدود: الشجرة الممتدة الدنيا للشبكة المضاعفة هي مسار حد علوي (مشي كل حافة في الشجرة الممتدة الدنيا مرتين)؛ الاختصارات تعطي حدًا علويًا أفضل حد. الحدود السفلية تأتي من حجج مبنية على الشجرة الممتدة الدنيا (مثل الشجرة الممتدة الدنيا نفسها، أو حذف رأس وإضافة أضفأ حافتين رخيصتين له). خوارزمية الجار الأقرب تبني جولة: من الرأس البداية انتقل بشكل متكرر إلى أقرب رأس لم يتم زيارته بعد، ثم عود. حول أولاً إلى شبكة كاملة بأقصر المسافات. عندما لا تكون الشبكة كاملة (عن طريق خوارزمية ديكسترا أو الفحص البصري). عندما لا تكون الشبكة مكتملة (باستخدام خوارزمية ديكسترا أو الفحص).

مثال محلول (الأصلي). شبكة مكتملة: AB 4، AC 2، AD 7، BC 3، BD 5، CD 6 (الـ D–A (2): طول الجولة 3 — وهو حد علوي. شجرة التمدد الصغرى هي AC + BC + BD = 5، لذا مضاعفتها D–A (7): طول الجولة 17 — حد علوي. الـ MST هو AC + BC + BD = 10، لذا مضاعفته تعطي الحد العلوي الخشن 20، المحسن إلى 17 عن طريق الاختصارات؛ حد سفلي من حذف A (MST لـ B, C, D هو 3 + 5 = 8، زائد أرقى حافتين لـ A هما AC + AB = 2 + 4 = 6) هو 14. الـ الجولة الأمثل تقع بين 14 و17.

الروابط الوهمية (أقواس ذات وزن صفر) تحل الاعتماديات التي لا يمكن للتقاطعات المشتركة التعبير عنها. المسار الحرج هو أطول سلسلة تمر عبر الشبكة: وهي مدة المشروع. احسب أوقات الحدث الأولى (المرور الأمامي: القيمة القصوى لـ الوصولات) وأوقات الحدث الأخيرة (المرور الخلفي: القيمة الدنيا لـ المغادرات). المرونة الكلية للنشاط = وقت الانتهاء الأخير − وقت البدء الأول − المدة؛ الأنشطة الحرجة لها مرونة صفرية. مخططات غانت (الشلال) تمثل كل نشاط بعمود يبدأ من وقت بدايته الأولي مع ترك مساحة فارغة تالية مساوية لمرونته؛ وتخصيص الجدول يوزع العمال يومًا بيوم. الفجوة الكلية للنشاط = وقت الانتهاء الأحدث − وقت البدء المبكر − المدة؛ النشاطات الحرجة لها فجوة صفرية. مخططات جانيت (التسلسل) ترسم شريطاً لكل نشاط بدءاً من أول وقت بدء مع هامشها كفاصل خلفي؛ يخصص الجدول الزمني العمال يومًا بيوم.

مثال محلول (الأصلي). أنشطة A (3 أيام)، B (4)، C (4 بعد A)، D (1 بعد B)، E (5 بعد C و D). السلسلة A–C–E = 12 أيام؛ السلسلة B–D–E = 10 أيام: المسار الحرج هو A–C–E والمشروع يستغرق 12 أيام؛ الفاصلة الكلية لـ D = 12 − (4 + 1 + 5) = 2 أيام.

الصياغة: عرّف متغيرات القرار، واكتب الهدف (تعظيم/تقليل) وكل قيد كمتباينة، بما في ذلك $x, y \ge 0$. حل مسائل ذات متغيرين بيانياً: ظلل المنطقة الممكنة، ثم استخدم طريقة المسطرة (تحريك مسطرة على ميل دالة الهدف) أو طريقة الرؤوس (حساب قيمة دالة الهدف عند كل رأس من المنطقة الممكنة). الحلول الصحيحة: اختبر النقاط الصحيحة القريبة من الرأس الأمثل داخل المنطقة.

مثال محلول — البرمجة الخطية (الأصلي). تعظيم $P = 3x + 2y$ تخضع لـ $x + y \le 10$، $2x + y \le 14$، $x, y \ge 0$. رؤوس المنطقة الممكنة هي $(0,0)$، $(7,0)$، $(4,6)$، $(0,10)$؛ بحساب $P$: 0، 21، 24، 20 — القيمة العظمى هي $P = 24$ عند $(4,6)$، حيث كلا القيدتين محققان.

• نفذ خوارزميات الترتيب الفقاعي والمرتجف مُظهرة كل دورة ومحور؛ وتعبئة الصناديق بتقنية "أول ما يصل"، "أول ما يصل تنازلياً" و"صندوق ممتلئ" مع إظهار التوزيعات.
• أوجد الأشجار الممتدة الصغرى باستخدام Kruskal و Prim (أشكال العقد والمصفوفة)؛ وارسم شبكة من مصفوفة والعكس.
• طبق خوارزمية Dijkstra بوضع العلامات حسب الثبات؛ واستخرج المسار وليس الطول فقط.
• حل فحص المسار: العقد الفردية، جميع الأزواج بالأوزان، أقل تكرار، إجمالي طول المشي.
• حدود مشكلة البائع المتجول الكلاسيكية: مضاعفة الشجرة الممتدة الصغرى واختصارات للحدود العليا، وحذف الشجرة الممتدة الصغرى للحدود الدنيا؛ وطبق أقرب جار على الشبكة الكاملة لأقصر المسافات.
• بنِ شبكات النشاط مع العناصر الوهمية؛ والتمرير الأمامي والخلفي لأوقات الأحداث؛ والفاصل الكلية؛ وتحديد المسار الحرج؛ ورسم مخطط غانت والجداول الزمنية.
• صغ برامج خطية بالكامل؛ حل بيانياً باستخدام المسطرة أو طرق الرؤوس؛ أوجد أفضل حلول صحيحة.