الرياضيات: التطبيقات والتفسير HL

1. 1.

   لبيان بسيط رؤوس درجاتها 3، 2، 2، 3، 2. استخدم مصافحة اليد لإيجاد عدد أضلاع البيان.

   [2 درجة]

   نقاط التصحيح

   • تحديد مصافحة اليد: مجموع درجات جميع الرؤوس يساوي ضعف عدد الأضلاع.
   • حساب مجموع الدرجات بـ 3+2+2+3+2 = 12، والقسمة على 2 للحصول على 6 أضلاع.

   ملاحظة الفاحص: تخبرك مصافحة اليد أيضاً بأن مجموع الدرجات في أي بيان يجب أن يكون زوجياً دائماً — طريقة سريعة للتحقق مما إذا كان تسلسل الدرجات المقترح ممكناً أصلاً.

2. 2.

   تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لبيان بسيط رؤوس درجاتها 3، 2، 2، 3، 2. استخدم مصافحة اليد لإيجاد عدد أضلاع البيان.» وتعالج إجابته هذه النقطة فقط: «تحديد مصافحة اليد: مجموع درجات جميع الرؤوس يساوي ضعف عدد الأضلاع.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

   [2 درجة]

   نقاط التصحيح

   • يقر باستحقاق الدرجة للنقطة المذكورة: تحديد مصافحة اليد: مجموع درجات جميع الرؤوس يساوي ضعف عدد الأضلاع.
   • يحدد المتطلب الناقص: حساب مجموع الدرجات بـ 3+2+2+3+2 = 12، والقسمة على 2 للحصول على 6 أضلاع.

   ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

3. 3.

   اشرح لماذا لا يمكن لأي بيان بسيط أن يمتلك تسلسل الدرجات 3، 2، 2، 2.

   [2 درجة] · بدون آلة حاسبة

   نقاط التصحيح

   • حساب مجموع الدرجات المقترحة: 3 + 2 + 2 + 2 = 9.
   • تحديد أن هذا المجموع فردي، مما يناقض مصافحة اليد (يجب أن يكون مجموع الدرجات زوجياً)، لذا لا يوجد مثل هذا البيان.

   ملاحظة الفاحص: يُعدّ التحقق مما إذا كان مجموع تسلسل درجات مقترح زوجياً دائماً أسرع فحص أول لإمكانية التحقق — يستبعده المجموع الفردي فوراً، دون حاجة لمزيد من التحليل.

4. 4.

   تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «اشرح لماذا لا يمكن لأي بيان بسيط أن يمتلك تسلسل الدرجات 3، 2، 2، 2.» وتعالج إجابته هذه النقطة فقط: «حساب مجموع الدرجات المقترحة: 3 + 2 + 2 + 2 = 9.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

   [2 درجة] · بدون آلة حاسبة

   نقاط التصحيح

   • يقر باستحقاق الدرجة للنقطة المذكورة: حساب مجموع الدرجات المقترحة: 3 + 2 + 2 + 2 = 9.
   • يحدد المتطلب الناقص: تحديد أن هذا المجموع فردي، مما يناقض مصافحة اليد (يجب أن يكون مجموع الدرجات زوجياً)، لذا لا يوجد مثل هذا البيان.

   ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

5. 5.

   لبيان رؤوسه A، وB، وC، وD وأضلاعه AB، وAC، وBC، وBD. أنشئ مصفوفة التجاور لهذا البيان، وتحقق من أن مجموع كل صف يساوي درجة الرأس المقابل.

   [4 درجة]

   نقاط التصحيح

   • إنشاء مصفوفة التجاور 4×4 بترتيب الصفوف/الأعمدة A، وB، وC، وD: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].
   • جمع الصف A: 0+1+1+0 = 2، مطابقاً درجة A (متصل بـB وC).
   • جمع الصف B: 1+0+1+1 = 3، مطابقاً درجة B (متصل بـA وC وD).
   • جمع الصفين C وD بالمثل، مؤكداً الدرجتين 2 و1 على الترتيب.

   ملاحظة الفاحص: في مصفوفة التجاور لبيان غير موجه بسيط، تكون المصفوفة متناظرة دائماً وكل عنصر قطري يساوي صفراً، لأن الرأس لا يكون مجاوراً لنفسه أبداً.

6. 6.

   تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لبيان رؤوسه A، وB، وC، وD وأضلاعه AB، وAC، وBC، وBD. أنشئ مصفوفة التجاور لهذا البيان، وتحقق من أن مجموع كل صف يساوي درجة الرأس المقابل.» وتعالج إجابته هذه النقطة فقط: «إنشاء مصفوفة التجاور 4×4 بترتيب الصفوف/الأعمدة A، وB، وC، وD: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 4 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

   [4 درجة]

   نقاط التصحيح

   • يقر باستحقاق الدرجة للنقطة المذكورة: إنشاء مصفوفة التجاور 4×4 بترتيب الصفوف/الأعمدة A، وB، وC، وD: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].
   • يحدد المتطلب الناقص: جمع الصف A: 0+1+1+0 = 2، مطابقاً درجة A (متصل بـB وC).
   • يحدد المتطلب الناقص: جمع الصف B: 1+0+1+1 = 3، مطابقاً درجة B (متصل بـA وC وD).
   • يحدد المتطلب الناقص: جمع الصفين C وD بالمثل، مؤكداً الدرجتين 2 و1 على الترتيب.

   ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

7. 7.

   تربط شبكة ست بلدات A، وB، وC، وD، وE، وF بالطرق والمسافات التالية (كم): AB=4، AC=2، BC=1، BD=5، CD=8، CE=10، DE=2، DF=6، EF=3. استخدم خوارزمية كروسكال لإيجاد شجرة ممتدة صغرى لهذه الشبكة، مع إظهار ترتيب إضافة الأضلاع، وحدد وزنها الكلي.

   [6 درجة]

   نقاط التصحيح

   • ترتيب الأضلاع تصاعدياً حسب الوزن: BC(1)، AC(2)، DE(2)، EF(3)، AB(4)، BD(5)، DF(6)، CD(8)، CE(10).
   • إضافة BC(1): لا تتكون دورة.
   • إضافة AC(2): لا تتكون دورة.
   • إضافة DE(2): لا تتكون دورة.
   • إضافة EF(3): لا تتكون دورة؛ رفض AB(4) لأن A وB متصلان بالفعل عبر C؛ إضافة BD(5): لا تتكون دورة، فتتصل الرؤوس الستة بخمسة أضلاع.
   • تحديد أضلاع الشجرة الممتدة الصغرى {BC، AC، DE، EF، BD} بوزن كلي 1+2+2+3+5 = 13.

   ملاحظة الفاحص: تنظر خوارزمية كروسكال دائماً إلى الأضلاع بترتيب تصاعدي للوزن وترفض أي ضلع يُكوّن دورة — يسهّل تتبع الرؤوس المتصلة بالفعل (باستخدام رسم مثلاً) التحقق من ذلك.

8. 8.

   تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «تربط شبكة ست بلدات A، وB، وC، وD، وE، وF بالطرق والمسافات التالية (كم): AB=4، AC=2، BC=1، BD=5، CD=8، CE=10، DE=2، DF=6، EF=3. استخدم خوارزمية كروسكال لإيجاد شجرة ممتدة صغرى لهذه الشبكة، مع إظهار ترتيب إضافة الأضلاع، وحدد وزنها الكلي.» وتعالج إجابته هذه النقطة فقط: «ترتيب الأضلاع تصاعدياً حسب الوزن: BC(1)، AC(2)، DE(2)، EF(3)، AB(4)، BD(5)، DF(6)، CD(8)، CE(10).» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 6 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

   [6 درجة]

   نقاط التصحيح

   • يقر باستحقاق الدرجة للنقطة المذكورة: ترتيب الأضلاع تصاعدياً حسب الوزن: BC(1)، AC(2)، DE(2)، EF(3)، AB(4)، BD(5)، DF(6)، CD(8)، CE(10).
   • يحدد المتطلب الناقص: إضافة BC(1): لا تتكون دورة.
   • يحدد المتطلب الناقص: إضافة AC(2): لا تتكون دورة.
   • يحدد المتطلب الناقص: إضافة DE(2): لا تتكون دورة.
   • يحدد المتطلب الناقص: إضافة EF(3): لا تتكون دورة؛ رفض AB(4) لأن A وB متصلان بالفعل عبر C؛ إضافة BD(5): لا تتكون دورة، فتتصل الرؤوس الستة بخمسة أضلاع.
   • يحدد المتطلب الناقص: تحديد أضلاع الشجرة الممتدة الصغرى {BC، AC، DE، EF، BD} بوزن كلي 1+2+2+3+5 = 13.

   ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

9. 9.

   باستخدام الشبكة نفسها من السؤال السابق، طبّق خوارزمية بريم بدءاً من الرأس A لإيجاد شجرة ممتدة صغرى، مع إظهار ترتيب إضافة الرؤوس. تحقق من أن الوزن الكلي يطابق نتيجة خوارزمية كروسكال.

   [6 درجة]

   نقاط التصحيح

   • البدء بـA؛ أرخص ضلع من الشجرة {A} هو AC(2)، فتُضاف C.
   • أرخص ضلع من {A, C} إلى رأس خارجي هو BC(1)، فتُضاف B.
   • أرخص ضلع من {A, B, C} إلى رأس خارجي هو BD(5) (يُرفض AB(4) لأنه يصل رأسين موجودين بالفعل في الشجرة)؛ تُضاف D.
   • أرخص ضلع من الشجرة الحالية إلى رأس خارجي هو DE(2)، فتُضاف E، ثم EF(3)، فتُضاف F.
   • سرد الأضلاع المختارة بـ {AC، BC، BD، DE، EF}.
   • التأكيد على الوزن الكلي 2+1+5+2+3 = 13، مطابقاً نتيجة كروسكال.

   ملاحظة الفاحص: تُنمّي خوارزمية بريم شجرة متصلة واحدة بدءاً من الرأس المحدد، بخلاف خوارزمية كروسكال التي يمكنها إضافة أضلاع غير متصلة قبل أن تتصل في النهاية — تنتج كلتاهما دائماً شجرة ممتدة صغرى بالوزن الكلي نفسه.

10. 10.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «باستخدام الشبكة نفسها من السؤال السابق، طبّق خوارزمية بريم بدءاً من الرأس A لإيجاد شجرة ممتدة صغرى، مع إظهار ترتيب إضافة الرؤوس. تحقق من أن الوزن الكلي يطابق نتيجة خوارزمية كروسكال.» وتعالج إجابته هذه النقطة فقط: «البدء بـA؛ أرخص ضلع من الشجرة {A} هو AC(2)، فتُضاف C.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 6 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [6 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: البدء بـA؛ أرخص ضلع من الشجرة {A} هو AC(2)، فتُضاف C.
    • يحدد المتطلب الناقص: أرخص ضلع من {A, C} إلى رأس خارجي هو BC(1)، فتُضاف B.
    • يحدد المتطلب الناقص: أرخص ضلع من {A, B, C} إلى رأس خارجي هو BD(5) (يُرفض AB(4) لأنه يصل رأسين موجودين بالفعل في الشجرة)؛ تُضاف D.
    • يحدد المتطلب الناقص: أرخص ضلع من الشجرة الحالية إلى رأس خارجي هو DE(2)، فتُضاف E، ثم EF(3)، فتُضاف F.
    • يحدد المتطلب الناقص: سرد الأضلاع المختارة بـ {AC، BC، BD، DE، EF}.
    • يحدد المتطلب الناقص: التأكيد على الوزن الكلي 2+1+5+2+3 = 13، مطابقاً نتيجة كروسكال.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

11. 11.

    لشبكة رؤوسها P، وQ، وR، وS، وT، وU وأضلاع موزونة: PQ=7، PR=9، PU=14، QR=10، QS=15، RS=11، RU=2، ST=6، UT=9. استخدم خوارزمية ديكسترا لإيجاد أقصر مسار من P إلى T، مع تحديد المسار وطوله الكلي.

    [7 درجة]

    نقاط التصحيح

    • تعيين تسمية دائمة 0 لـP والنظر في جيرانه: تحصل Q على قيمة عاملة 7، وR على 9، وU على 14.
    • إعطاء Q التسمية الدائمة التالية (7)، أصغر قيمة عاملة.
    • إعطاء R التسمية الدائمة التالية (9)؛ تحديث قيمة U العاملة عبر R: 9+2=11، وهي أفضل من 14.
    • إعطاء U التسمية الدائمة التالية (11)؛ تحديث S عبر R (9+11=20) وعبر Q (7+15=22)، مع إبقاء القيمة الأصغر 20.
    • إعطاء S تسمية دائمة 20؛ تحديث T عبر U (11+9=20) وعبر S (20+6=26)، مع إبقاء القيمة الأصغر 20.
    • إعطاء T تسمية دائمة 20، والتراجع عبر الأسلاف لإيجاد المسار P → R → U → T.
    • تحديد أقصر مسار بـ P → R → U → T بطول كلي 20.

    ملاحظة الفاحص: تُعطي خوارزمية ديكسترا دائماً تسمية دائمة للرأس ذي أصغر قيمة عاملة في كل مرحلة — بمجرد إعطاء رأس تسمية دائمة، لا يمكن لأقصر مسافة له من البداية أن تتحسن أبداً بعد ذلك.

12. 12.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لشبكة رؤوسها P، وQ، وR، وS، وT، وU وأضلاع موزونة: PQ=7، PR=9، PU=14، QR=10، QS=15، RS=11، RU=2، ST=6، UT=9. استخدم خوارزمية ديكسترا لإيجاد أقصر مسار من P إلى T، مع تحديد المسار وطوله الكلي.» وتعالج إجابته هذه النقطة فقط: «تعيين تسمية دائمة 0 لـP والنظر في جيرانه: تحصل Q على قيمة عاملة 7، وR على 9، وU على 14.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 7 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [7 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: تعيين تسمية دائمة 0 لـP والنظر في جيرانه: تحصل Q على قيمة عاملة 7، وR على 9، وU على 14.
    • يحدد المتطلب الناقص: إعطاء Q التسمية الدائمة التالية (7)، أصغر قيمة عاملة.
    • يحدد المتطلب الناقص: إعطاء R التسمية الدائمة التالية (9)؛ تحديث قيمة U العاملة عبر R: 9+2=11، وهي أفضل من 14.
    • يحدد المتطلب الناقص: إعطاء U التسمية الدائمة التالية (11)؛ تحديث S عبر R (9+11=20) وعبر Q (7+15=22)، مع إبقاء القيمة الأصغر 20.
    • يحدد المتطلب الناقص: إعطاء S تسمية دائمة 20؛ تحديث T عبر U (11+9=20) وعبر S (20+6=26)، مع إبقاء القيمة الأصغر 20.
    • يحدد المتطلب الناقص: إعطاء T تسمية دائمة 20، والتراجع عبر الأسلاف لإيجاد المسار P → R → U → T.
    • يحدد المتطلب الناقص: تحديد أقصر مسار بـ P → R → U → T بطول كلي 20.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

13. 13.

    باستخدام جدول خوارزمية ديكسترا نفسه من السؤال السابق، حدد ترتيب حصول الرؤوس P، وQ، وR، وS، وT، وU على تسمياتها الدائمة.

    [2 درجة]

    نقاط التصحيح

    • تحديد ترتيب التسمية الدائمة بـ P، وQ، وR، وU، وS، وT.
    • ملاحظة أن كلاً من S وT يحصلان على تسمية دائمة نهائية 20، لكن S تُسمّى أولاً لأنها وُصل إليها بقيمة عاملة أصغر قبل أن تُحسم قيمة T.

    ملاحظة الفاحص: يمكن أن ينتهي رأسان بشكل صحيح بالمسافة النهائية الأقصر نفسها من المصدر — لا يشير ذلك إلى خطأ، بل يعني ببساطة أن مسارين مختلفين لهما طول كلي متساوٍ بالصدفة.

14. 14.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «باستخدام جدول خوارزمية ديكسترا نفسه من السؤال السابق، حدد ترتيب حصول الرؤوس P، وQ، وR، وS، وT، وU على تسمياتها الدائمة.» وتعالج إجابته هذه النقطة فقط: «تحديد ترتيب التسمية الدائمة بـ P، وQ، وR، وU، وS، وT.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [2 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: تحديد ترتيب التسمية الدائمة بـ P، وQ، وR، وU، وS، وT.
    • يحدد المتطلب الناقص: ملاحظة أن كلاً من S وT يحصلان على تسمية دائمة نهائية 20، لكن S تُسمّى أولاً لأنها وُصل إليها بقيمة عاملة أصغر قبل أن تُحسم قيمة T.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

15. 15.

    لخمس مدن W، وX، وY، وZ، وV المسافات المباشرة التالية (كم): WX=12، WY=10، WZ=19، WV=8، XY=3، XZ=7، XV=6، YZ=2، YV=20، ZV=4. بدءاً من W، استخدم خوارزمية أقرب جار لإيجاد حد أعلى لطول جولة البائع المتجول التي تزور كل مدينة مرة واحدة وتعود إلى W.

    [5 درجة]

    نقاط التصحيح

    • من W، أقرب مدينة لم تُزر هي V (8 كم).
    • من V، أقرب مدينة لم تُزر هي Z (4 كم).
    • من Z، أقرب مدينة لم تُزر هي Y (2 كم).
    • من Y، أقرب مدينة لم تُزر هي X (3 كم)؛ العودة إلى W من X (12 كم).
    • تحديد المسار W→V→Z→Y→X→W بحد أعلى كلي 8+4+2+3+12 = 29 كم.

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

16. 16.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لخمس مدن W، وX، وY، وZ، وV المسافات المباشرة التالية (كم): WX=12، WY=10، WZ=19، WV=8، XY=3، XZ=7، XV=6، YZ=2، YV=20، ZV=4. بدءاً من W، استخدم خوارزمية أقرب جار لإيجاد حد أعلى لطول جولة البائع المتجول التي تزور كل مدينة مرة واحدة وتعود إلى W.» وتعالج إجابته هذه النقطة فقط: «من W، أقرب مدينة لم تُزر هي V (8 كم).» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 5 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [5 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: من W، أقرب مدينة لم تُزر هي V (8 كم).
    • يحدد المتطلب الناقص: من V، أقرب مدينة لم تُزر هي Z (4 كم).
    • يحدد المتطلب الناقص: من Z، أقرب مدينة لم تُزر هي Y (2 كم).
    • يحدد المتطلب الناقص: من Y، أقرب مدينة لم تُزر هي X (3 كم)؛ العودة إلى W من X (12 كم).
    • يحدد المتطلب الناقص: تحديد المسار W→V→Z→Y→X→W بحد أعلى كلي 8+4+2+3+12 = 29 كم.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

17. 17.

    باستخدام المدن الخمس نفسها من السؤال السابق، أوجد حداً أدنى لجولة البائع المتجول بحذف المدينة W، وإيجاد الشجرة الممتدة الصغرى للمدن الأربع المتبقية، وإضافة أقصر ضلعين متصلين بـW.

    [6 درجة]

    نقاط التصحيح

    • حذف W وإيجاد الشجرة الممتدة الصغرى لـX، وY، وZ، وV باستخدام خوارزمية كروسكال أو بريم.
    • الحصول على أضلاع الشجرة الممتدة الصغرى {YZ(2), XY(3), ZV(4)} بوزن كلي 9.
    • تحديد أقصر ضلعين متصلين بـW بـWV(8) وWY(10).
    • إضافة هذين الضلعين إلى وزن الشجرة الممتدة الصغرى: 9 + 8 + 10 = 27.
    • تحديد الحد الأدنى بـ27 كم.
    • الاستنتاج بأن طول الجولة المثلى يقع بين الحد الأدنى 27 كم والحد الأعلى 29 كم الموجود سابقاً.

    ملاحظة الفاحص: يحصر الجمع بين الحد الأدنى بحذف رأس والحد الأعلى بأقرب جار طول الجولة المثلى الحقيقي بين قيمتين، حتى عندما يكون إيجاد الجولة المثلى بالضبط بالقوة الغاشمة غير عملي.

18. 18.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «باستخدام المدن الخمس نفسها من السؤال السابق، أوجد حداً أدنى لجولة البائع المتجول بحذف المدينة W، وإيجاد الشجرة الممتدة الصغرى للمدن الأربع المتبقية، وإضافة أقصر ضلعين متصلين بـW.» وتعالج إجابته هذه النقطة فقط: «حذف W وإيجاد الشجرة الممتدة الصغرى لـX، وY، وZ، وV باستخدام خوارزمية كروسكال أو بريم.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 6 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [6 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: حذف W وإيجاد الشجرة الممتدة الصغرى لـX، وY، وZ، وV باستخدام خوارزمية كروسكال أو بريم.
    • يحدد المتطلب الناقص: الحصول على أضلاع الشجرة الممتدة الصغرى {YZ(2), XY(3), ZV(4)} بوزن كلي 9.
    • يحدد المتطلب الناقص: تحديد أقصر ضلعين متصلين بـW بـWV(8) وWY(10).
    • يحدد المتطلب الناقص: إضافة هذين الضلعين إلى وزن الشجرة الممتدة الصغرى: 9 + 8 + 10 = 27.
    • يحدد المتطلب الناقص: تحديد الحد الأدنى بـ27 كم.
    • يحدد المتطلب الناقص: الاستنتاج بأن طول الجولة المثلى يقع بين الحد الأدنى 27 كم والحد الأعلى 29 كم الموجود سابقاً.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

19. 19.

    تُكوّن شبكة توصيل بياناً يجب فيه اجتياز كل ضلع مرة واحدة على الأقل، بدءاً من المستودع وانتهاءً به. الأضلاع والمسافات (كم) هي: AB=3، وBC=4، وCA=5، وCD=6، حيث A هو المستودع. رأسان بالضبط، C وD، لهما درجة فردية. أوجد طول أقصر مسار ممكن يجتاز كل ضلع مرة واحدة على الأقل ويعود إلى A.

    [5 درجة]

    نقاط التصحيح

    • حساب الوزن الكلي لجميع الأضلاع: 3 + 4 + 5 + 6 = 18.
    • تحديد الرأسين ذوي الدرجة الفردية بـC وD (هذه مسألة البائع الصيني).
    • إيجاد أقصر مسار بين الرأسين الفرديين C وD، وهو الضلع المباشر CD = 6.
    • إضافة وزن أقصر مسار هذا إلى الوزن الكلي للأضلاع بوصفه المسار المكرر: 18 + 6 = 24.
    • تحديد طول أقصر مسار بـ24 كم.

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

20. 20.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «تُكوّن شبكة توصيل بياناً يجب فيه اجتياز كل ضلع مرة واحدة على الأقل، بدءاً من المستودع وانتهاءً به. الأضلاع والمسافات (كم) هي: AB=3، وBC=4، وCA=5، وCD=6، حيث A هو المستودع. رأسان بالضبط، C وD، لهما درجة فردية. أوجد طول أقصر مسار ممكن يجتاز كل ضلع مرة واحدة على الأقل ويعود إلى A.» وتعالج إجابته هذه النقطة فقط: «حساب الوزن الكلي لجميع الأضلاع: 3 + 4 + 5 + 6 = 18.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 5 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [5 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: حساب الوزن الكلي لجميع الأضلاع: 3 + 4 + 5 + 6 = 18.
    • يحدد المتطلب الناقص: تحديد الرأسين ذوي الدرجة الفردية بـC وD (هذه مسألة البائع الصيني).
    • يحدد المتطلب الناقص: إيجاد أقصر مسار بين الرأسين الفرديين C وD، وهو الضلع المباشر CD = 6.
    • يحدد المتطلب الناقص: إضافة وزن أقصر مسار هذا إلى الوزن الكلي للأضلاع بوصفه المسار المكرر: 18 + 6 = 24.
    • يحدد المتطلب الناقص: تحديد طول أقصر مسار بـ24 كم.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

21. 21.

    لكل من تسلسلات الدرجات التالية، حدد ما إذا كان البيان المقابل يمتلك دورة أويلرية، أم مساراً أويلرياً (وليس دورة)، أم لا هذا ولا ذاك: (أ) 4، 4، 2، 2 (كلها زوجية). (ب) 3، 3، 2، 2 (فرديتان بالضبط). (ج) 3، 3، 3، 3 (أربع فرديات).

    [3 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • تحديد أن (أ)، بكل رؤوسها زوجية الدرجة، تمتلك دورة أويلرية.
    • تحديد أن (ب)، برأسين فرديي الدرجة بالضبط، تمتلك مساراً أويلرياً وليس دورة (يجب أن يبدأ وينتهي عند الرأسين الفرديين).
    • تحديد أن (ج)، بأربعة رؤوس فردية الدرجة، لا تمتلك دورة أويلرية ولا مساراً أويلرياً.

    ملاحظة الفاحص: عُدّ عدد الرؤوس فردية الدرجة: الصفر يعني وجود دورة أويلرية، والعدد اثنان بالضبط يعني وجود مسار أويلري فقط، وأي عدد آخر (زوجي دائماً، وفق مصافحة اليد) يعني عدم وجود أي منهما.

22. 22.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لكل من تسلسلات الدرجات التالية، حدد ما إذا كان البيان المقابل يمتلك دورة أويلرية، أم مساراً أويلرياً (وليس دورة)، أم لا هذا ولا ذاك: (أ) 4، 4، 2، 2 (كلها زوجية). (ب) 3، 3، 2، 2 (فرديتان بالضبط). (ج) 3، 3، 3، 3 (أربع فرديات).» وتعالج إجابته هذه النقطة فقط: «تحديد أن (أ)، بكل رؤوسها زوجية الدرجة، تمتلك دورة أويلرية.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [3 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: تحديد أن (أ)، بكل رؤوسها زوجية الدرجة، تمتلك دورة أويلرية.
    • يحدد المتطلب الناقص: تحديد أن (ب)، برأسين فرديي الدرجة بالضبط، تمتلك مساراً أويلرياً وليس دورة (يجب أن يبدأ وينتهي عند الرأسين الفرديين).
    • يحدد المتطلب الناقص: تحديد أن (ج)، بأربعة رؤوس فردية الدرجة، لا تمتلك دورة أويلرية ولا مساراً أويلرياً.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

23. 23.

    اشرح لماذا تمتلك الشجرة ذات n رأساً دائماً n − 1 ضلعاً بالضبط، وحدد عدد الأضلاع في شجرة ذات 6 رؤوس.

    [3 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • شرح أن الشجرة بيان متصل بلا دورات، وأن وصل n رأساً بأقل عدد ممكن من الأضلاع مع البقاء متصلاً يتطلب n − 1 ضلعاً بالضبط.
    • ملاحظة أن إضافة أي ضلع آخر إلى شجرة سيُكوّن دورة بالضرورة، بينما حذف أي ضلع سيفصلها.
    • تحديد أن الشجرة ذات 6 رؤوس لها 6 − 1 = 5 أضلاع.

    ملاحظة الفاحص: تمتلك الشجرة الممتدة الصغرى لبيان متصل ذي n رأساً دائماً n − 1 ضلعاً بالضبط — هذه طريقة سريعة للتحقق مما إذا كانت الشجرة الممتدة المقترحة مكتملة.

24. 24.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «اشرح لماذا تمتلك الشجرة ذات n رأساً دائماً n − 1 ضلعاً بالضبط، وحدد عدد الأضلاع في شجرة ذات 6 رؤوس.» وتعالج إجابته هذه النقطة فقط: «شرح أن الشجرة بيان متصل بلا دورات، وأن وصل n رأساً بأقل عدد ممكن من الأضلاع مع البقاء متصلاً يتطلب n − 1 ضلعاً بالضبط.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [3 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: شرح أن الشجرة بيان متصل بلا دورات، وأن وصل n رأساً بأقل عدد ممكن من الأضلاع مع البقاء متصلاً يتطلب n − 1 ضلعاً بالضبط.
    • يحدد المتطلب الناقص: ملاحظة أن إضافة أي ضلع آخر إلى شجرة سيُكوّن دورة بالضرورة، بينما حذف أي ضلع سيفصلها.
    • يحدد المتطلب الناقص: تحديد أن الشجرة ذات 6 رؤوس لها 6 − 1 = 5 أضلاع.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

25. 25.

    لبيان مثلث رؤوسه A، وB، وC، كل زوج منها موصول بضلع، ومصفوفة تجاوره M = [[0,1,1],[1,0,1],[1,1,0]]. احسب M²، واشرح ما تمثله عناصر M².

    [4 درجة]

    نقاط التصحيح

    • ضرب M في نفسها للحصول على M² = [[2,1,1],[1,2,1],[1,1,2]].
    • شرح أن كل عنصر خارج القطر (i, j) من M² يعطي عدد السير بطول 2 من الرأس i إلى الرأس j.
    • شرح أن كل عنصر قطري من M² يساوي درجة ذلك الرأس، لأنه يحصي السير التي تغادر وتعود عبر كل من أضلاعه.
    • التحقق من أن العناصر القطرية (كلها 2) تطابق درجة كل رأس في بيان المثلث هذا.

    ملاحظة الفاحص: تحصي قوى مصفوفة التجاور دائماً السير بذلك الطول بالضبط بين الرؤوس، بما في ذلك السير التي تكرر أضلاعاً أو رؤوساً — وهذا يختلف عن إحصاء المسارات البسيطة.

26. 26.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لبيان مثلث رؤوسه A، وB، وC، كل زوج منها موصول بضلع، ومصفوفة تجاوره M = [[0,1,1],[1,0,1],[1,1,0]]. احسب M²، واشرح ما تمثله عناصر M².» وتعالج إجابته هذه النقطة فقط: «ضرب M في نفسها للحصول على M² = [[2,1,1],[1,2,1],[1,1,2]].» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 4 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [4 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: ضرب M في نفسها للحصول على M² = [[2,1,1],[1,2,1],[1,1,2]].
    • يحدد المتطلب الناقص: شرح أن كل عنصر خارج القطر (i, j) من M² يعطي عدد السير بطول 2 من الرأس i إلى الرأس j.
    • يحدد المتطلب الناقص: شرح أن كل عنصر قطري من M² يساوي درجة ذلك الرأس، لأنه يحصي السير التي تغادر وتعود عبر كل من أضلاعه.
    • يحدد المتطلب الناقص: التحقق من أن العناصر القطرية (كلها 2) تطابق درجة كل رأس في بيان المثلث هذا.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

27. 27.

    عرّف المقصود بالدورة الهاملتونية، وأوجد دورة هاملتونية واحدة في شبكة المدن الخمس من سؤال سابق (W، وX، وY، وZ، وV، وجميع الأزواج متصلة)، مع تحديد طولها الكلي.

    [3 درجة]

    نقاط التصحيح

    • تعريف الدورة الهاملتونية بأنها مسار مغلق يزور كل رأس من رؤوس البيان مرة واحدة بالضبط قبل العودة إلى رأس البداية.
    • تحديد دورة هاملتونية صحيحة، مثل W→X→Y→Z→V→W.
    • حساب طولها الكلي بـ12 + 3 + 2 + 4 + 8 = 29 كم، مع ملاحظة أن أي دورة هاملتونية صحيحة مقبولة، وليس بالضرورة الأقصر.

    ملاحظة الفاحص: تحتاج الدورة الهاملتونية فقط إلى زيارة كل رأس مرة واحدة بالضبط — لا يلزم أن تكون أقصر دورة ممكنة من هذا النوع إلا إذا طلب السؤال تحديداً الجولة المثلى.

28. 28.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «عرّف المقصود بالدورة الهاملتونية، وأوجد دورة هاملتونية واحدة في شبكة المدن الخمس من سؤال سابق (W، وX، وY، وZ، وV، وجميع الأزواج متصلة)، مع تحديد طولها الكلي.» وتعالج إجابته هذه النقطة فقط: «تعريف الدورة الهاملتونية بأنها مسار مغلق يزور كل رأس من رؤوس البيان مرة واحدة بالضبط قبل العودة إلى رأس البداية.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [3 درجة]

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: تعريف الدورة الهاملتونية بأنها مسار مغلق يزور كل رأس من رؤوس البيان مرة واحدة بالضبط قبل العودة إلى رأس البداية.
    • يحدد المتطلب الناقص: تحديد دورة هاملتونية صحيحة، مثل W→X→Y→Z→V→W.
    • يحدد المتطلب الناقص: حساب طولها الكلي بـ12 + 3 + 2 + 4 + 8 = 29 كم، مع ملاحظة أن أي دورة هاملتونية صحيحة مقبولة، وليس بالضرورة الأقصر.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

29. 29.

    اشرح الفرق الرئيسي بين الشجرة والبيان المتصل العام، من حيث عدد الأضلاع بالنسبة لعدد الرؤوس، ومن حيث الدورات.

    [2 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • شرح أن الشجرة بيان متصل بـ n − 1 ضلعاً بالضبط وبلا دورات، بينما قد يمتلك البيان المتصل العام n − 1 ضلعاً أو أكثر ويمكن أن يحتوي دورة واحدة أو أكثر.
    • ملاحظة أن كل شجرة بيان متصل، لكن ليس كل بيان متصل شجرة.

    ملاحظة الفاحص: فكّر في الشجرة بوصفها الطريقة 'الصغرى' للحفاظ على اتصال بيان ما — أي ضلع إضافي يتجاوز n − 1 يُكوّن دورة بالضرورة.

30. 30.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «اشرح الفرق الرئيسي بين الشجرة والبيان المتصل العام، من حيث عدد الأضلاع بالنسبة لعدد الرؤوس، ومن حيث الدورات.» وتعالج إجابته هذه النقطة فقط: «شرح أن الشجرة بيان متصل بـ n − 1 ضلعاً بالضبط وبلا دورات، بينما قد يمتلك البيان المتصل العام n − 1 ضلعاً أو أكثر ويمكن أن يحتوي دورة واحدة أو أكثر.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [2 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: شرح أن الشجرة بيان متصل بـ n − 1 ضلعاً بالضبط وبلا دورات، بينما قد يمتلك البيان المتصل العام n − 1 ضلعاً أو أكثر ويمكن أن يحتوي دورة واحدة أو أكثر.
    • يحدد المتطلب الناقص: ملاحظة أن كل شجرة بيان متصل، لكن ليس كل بيان متصل شجرة.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

31. 31.

    تُشكّل خمسة مواقع A، وB، وC، وD، وE مربعاً ABCD طول ضلعه 1 كم (بأقطار AC = BD ≈ 1.41 كم)، إضافة إلى موقع خامس E يبعد 6.02 كم عن A وD، و5.02 كم عن B وC. بدءاً من A، تعطي خوارزمية أقرب جار الجولة A→B→C→D→E→A بطول 15.04 كم، لكن الجولة المثلى A→B→E→C→D→A طولها 13.04 كم. اشرح لماذا فشلت خوارزمية أقرب جار في إيجاد الجولة المثلى في هذه الحالة.

    [3 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • شرح أن خوارزمية أقرب جار تتخذ الخيار الأمثل محلياً في كل خطوة دون النظر في البنية الكلية لبقية المسار.
    • شرح أنه بزيارة C وD قبل النقطة البعيدة E، تُضطر الخوارزمية لإجراء رحلتين طويلتين من وإلى E (من D إلى E ومن E عودة إلى A)، بدلاً من زيارة E في التفافة واحدة فعالة من B.
    • الاستنتاج بأن الخيارات الجشعة المثلى محلياً لا تؤدي دائماً إلى حل أمثل عالمياً لمسألة البائع المتجول.

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

32. 32.

    تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «تُشكّل خمسة مواقع A، وB، وC، وD، وE مربعاً ABCD طول ضلعه 1 كم (بأقطار AC = BD ≈ 1.41 كم)، إضافة إلى موقع خامس E يبعد 6.02 كم عن A وD، و5.02 كم عن B وC. بدءاً من A، تعطي خوارزمية أقرب جار الجولة A→B→C→D→E→A بطول 15.04 كم، لكن الجولة المثلى A→B→E→C→D→A طولها 13.04 كم. اشرح لماذا فشلت خوارزمية أقرب جار في إيجاد الجولة المثلى في هذه الحالة.» وتعالج إجابته هذه النقطة فقط: «شرح أن خوارزمية أقرب جار تتخذ الخيار الأمثل محلياً في كل خطوة دون النظر في البنية الكلية لبقية المسار.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.

    [3 درجة] · بدون آلة حاسبة

    نقاط التصحيح

    • يقر باستحقاق الدرجة للنقطة المذكورة: شرح أن خوارزمية أقرب جار تتخذ الخيار الأمثل محلياً في كل خطوة دون النظر في البنية الكلية لبقية المسار.
    • يحدد المتطلب الناقص: شرح أنه بزيارة C وD قبل النقطة البعيدة E، تُضطر الخوارزمية لإجراء رحلتين طويلتين من وإلى E (من D إلى E ومن E عودة إلى A)، بدلاً من زيارة E في التفافة واحدة فعالة من B.
    • يحدد المتطلب الناقص: الاستنتاج بأن الخيارات الجشعة المثلى محلياً لا تؤدي دائماً إلى حل أمثل عالمياً لمسألة البائع المتجول.

    ملاحظة الفاحص: تعامل مع كل نقطة تصحيح كمتطلب مستقل. لا تمنح الفكرة نفسها درجتين ولا تفترض عملاً لم يُظهره المتعلم.

أسئلة تدريبية أصلية غير رسمية من SubjectScout، وليست أسئلة أوراق سابقة رسمية.