خوارزميات الفرز والتعبئة والشبكات
مُقدَّم| English | المعنى |
|---|---|
| algorithm/ˈælɡərɪθəm/ | الخوارزمية |
هل طريقة التغليف السريعة دائمًا مثلى؟
- طريقة تغليف سريعة تملأ الصناديق، لكن الترتيب الصحيح السريع قد لا يستخدم أقل عدد من الصناديق.
- تدرس هذه الدرس الخوارزمية: مجموعة محدودة من التعليمات المرتبة التي تحل فئة محددة من المشكلات.
اختر البنية الرياضية
- تتبع الخوارزمية المسمى بدقة، بما في ذلك قواعد التعادل. في تغليف "الأول المناسب"، ضع كل عنصر في أول صندوق متاح يمكن استيعابه. يقوم "الأول المناسب التنازلي" بالترتيب قبل تطبيق "الأول المناسب". قد تكون الوصفية صحيحة دون أن تكون مثلى.
- حدد المدخلات المسموحة والوحدات قبل الحساب. يجب أن يعبر المعادلة عن العلاقة، وليس فقط تسجيل إدخال الآلة الحاسبة.
استخدم خوارزمية first-fit 2 حاويات لـ 6,5,4,3,2 بسعة 10، مما يطابق الحد الأدنى. ماذا يمكن استنتاجه؟
Difficulty 1/5 · 100 coins + a small bonus on first completion today
تحقيق الحد الأدنى يثبت الأمثلية لهذه الحالة فقط. نجاح خوارزمية تقريبية على مثال واحد لا يقول شيئاً عن الحالات الأسوأ - قوائم عناصر أخرى قد تجعل first-fit يتجاوز الحد الأدنى.
اعمل على حالة تم فحصها
- تحقق من النتيجة مقابل الكميات الأولية. عوض في العلاقة الأصلية، أو قارن بين الرسم البياني والإجابة العددية عند الاستلزام.
بطاقة سعة 10 وعناصر 6,5,4,3,2 بنفس الترتيب، يضع أول ملاءم 6 و4 في بطاقة 1، ثم 5,3,2 في بطاقة 2. يستخدم 2 بطاقات. الحجم الكلي هو 20، لذا الحد الأدنى هو ceil(20/10)=2؛ هذه الترتيبة مثالية لهذه الحالة.
خوارزميات الفرز والتعبئة والشبكات
تتبع الخوارزمية المسماة بدقة، بما في ذلك قواعد التعادل
قارن النموذج بالحالة المحلولة واشرح تغييراً واحداً.
كم عدد الحاويات التي تستخدمها ترتيب الملاءمة الأولى المحلول؟
Difficulty 2/5 · 140 coins + a small bonus on first completion today
يملأ ترتيب الملاءمة الأولى حايتين، كل منهما بحجم إجمالي 10.
اختبر طريقة مختصرة مغرية
- مثال على النجاح لا يثبت أن الوصفية دائمًا مثلى. احتفظ بالقوائم الوسيطة في تتبع الترتيب؛ لا تقفز من المدخلات إلى القائمة النهائية المرتبة. يجب أن يحتفظ تحديث أقصر مسار بمعلومات السلف إذا طُلب طريق.
- عندما تفشل طريقة مختصرة، حدد الافتراض الذي تخالفه. احتفظ بالقيمة الدقيقة حتى التحويل النهائي المطلوب.
خوارزمية تجميعية تعمل بشكل جيد في مثال واحد يجب أن تكون دائمًا مثلى. هذا الادعاء غير صحيح. اشرح أي تعريف أو افتراض تخالفه.
أوجد الحد الأدنى لعدد الحاويات لحجم إجمالي 20 وطاقة 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
كل حاوية تحتوي على ما لا يزيد عن 10، لذا يلزم على الأقل ceiling(20/10)=2 حاوية.
لا يجب أن يكون مقياس تعبئة يعمل بشكل جيد في مثال واحد دائماً أمثلاً.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
مثال نجاح لا يثبت أن المقياس دائماً أمثل. احتفظ بقوائم وسيطة في تتبع الفرز؛ لا تقفز من المدخلات إلى القائمة النهائية المرتبة. يجب أن تحتفظ تحديث أقصر مسار بمعلومات السلف إذا طُلب مسار.
تفسير موقف جديد
- بالنسبة لخوارزمية دايكسترا، اختر أصغر علامة مؤقتة غير محسومة وحدّ جيرانها. أما في مسائل فحص المسار، فاميز بين المسار المغلق والمفتوح وحدد الرؤوس ذات الدرجة الفردية قبل مقابلتها.
- الحل الكامل يعطي النتيجة الرياضية ويشرح معناها. تحقق من إمكانية حدوثه في السياق المعلن.
أوجد المساحة المتبقية في حاوية تحتوي على عناصر 5,3,2 بطاقة 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
السعة غير المستخدمة = 10 - (5 + 3 + 2) = 0.
طابِق كل قاعدة لتعبئة بمهمتها.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
تتبع الخوارزمية تماماً كما هي معرَّفة؛ يحكم الحد الأدنى على مدى جودة التعبئة الممكنة.
استخدم هذا في مسارك الدراسي
- رياضيات edexcel IAL؛ الوحدة الرسمية D1. يتم تحديد إثراء الوحدات الأخرى في مراجعة النطاق؛ ولا يعتبر شرطًا إضافيًا للدفع.
- قدم الطريقة قبل الإجابة النهائية، واستخدم قواعد الآلة الحاسبة والصيغ الورقية. راجع إجابة خاطئة عن طريق تحديد الخطوة الأولى غير الصالحة.
مجموعة منتهية من التعليمات المرتبة التي تحل فئة محددة من المشكلات. حدد العلاقة، وعرض الطريقة، وتحقق من افتراضاتها وتفسير النتيجة.