الخوارزميات
Introduced| English | العربية |
|---|---|
| algorithm/ˈælɡərɪθəm/ | خوارزمية |
| flowchart/ˈfləʊtʃɑːt/ | مخطط انسيابي |
| pseudocode/ˈsuːdəʊkəʊd/ | الكود الوهمي |
| tracing/ˈtreɪsɪŋ/ | التتبع |
| binary search/ˈbaɪnəri sɜːtʃ/ | البحث الثنائي |
| linear search/ˈlɪnɪə sɜːtʃ/ | البحث الخطي |
| efficiency/ɪˈfɪʃənsi/ | الكفاءة |
حدد المدخلات التي يجب أن تعالجها الإجراء
- الخوارزمية تصف خطوات واضحة ومحددة لمهمة ما. يجب أن ينتهي إجراء يحل مهمة محدودة وواضحة ويعطي النتيجة الصحيحة لكل مدخل مسموح به.
- تتبع ناجح على مدخل واحد يظهر تلك الحالة، وليس دليلاً على جميع المدخلات. يمكن أن تكشف حالات الحدود والمدخلات الفارغة عن أخطاء قد تفوتها الأمثلة النموذجية.
ما الذي يجب توفره في سلسلة خطوات لتُعد خوارزمية؟ اختر كل ما ينطبق.
الإجراء الذي يحل المهمة المحدودة finite stated يحتاج خطوات غير غامضة، ونتائج صحيحة وانتهاء على المدخلات المسموحة. الكود الوهمي والمخططات الانسيابية هي تمثيلات، وليست متطلبات لاستخدام لغة برمجة معينة.
مثّل الخيارات والتحديثات بوضوح
- المخطط الانسيابي يستخدم معين القرار، مستطيل العملية، متوازي الأضلاع للإدخال/الإخراج، ومحطات البداية/النهاية، المتصلة بأسهم تدفق موجهة.
- الكود الوهمي يصف الخطوات دون الحاجة إلى لغة برمجة واحدة. حدد معنى التعيين، ونقطة بداية المؤشر، وحدود الحلقة، وشروط التفرع قبل التتبع.
طابق كل شكل في المخطط الانسيابي مع معناه.
استخدم مستطيلات العمليات، ومعالم القرار وبداية/نهاية كما هو معطى؛ الإدخال/الإخراج يُعرض عادةً بموازٍ. عيّن فروع قرار واتجاهات التدفق.
سجّل القيم الفعلية للمتغيرات
- التتبع يتبع التحديثات المعلنة بالترتيب. قد تحافظ متغير مؤقت على قيمة كانت ستُستبدل بخلاف ذلك.
- أظهر low، high، middle، والقيمة المقارنة للبحث الثنائي؛ وأظهر كل متغير تم تغييره لحلقة حسابية. احكم على ما يفعله الإجراء، وليس غرضه المقصود فقط.
اتفاقية محددة للبحث الثنائي. استخدم حدوداً شاملة تبدأ من الصفر والأخذ بالسفل لمتوسطهما للمنتصف. عند البحث عن 7 في [1,3,5,7,9,11] تتم مقارنة الفهرس 2/القيمة 5، ثم الفهرس 4/القيمة 9، ثم الفهرس 3/القيمة 7. عدد المقارنات هو ثلاثة تحت هذه الاتفاقية.
البحث الخطي مقابل البحث الثنائي
التقسيم للنصف يفوق الفحص واحداً تلو الآخر، وتزداد الفجوة مع طول القائمة.
باستخدام حدود شاملة قائمة على الصفر وقاعدة floor((low+high)/2)، كم عدد المقارنات التي تستخدم البحث الثنائي لإيجاد 7 في [1,3,5,7,9,11]؟
الفهارس الوسطى هي 2، 4، ثم 3، مع القيم 5، 9 و7. ثلاث مقارنات تحت الاتفاقية المحددة.
قارن الجهد تحت افتراضاته
- البحث الخطي يمكن أن يتوقف مبكراً لكنه قد يفحص جميع العناصر n. البحث الثنائي يقلص نطاق البحث المرتب مرتين ويحتاج إلى تحديثات متسقة للحدود.
- الكفاءة تصف كيف يتوسع العمل المطلوب مع حجم المدخلات ضمن نموذج محدد.Sorting له تكليفه الخاص؛ لا يمكن لمدخل غير مرتب أن يعتمد على ضمان الترتيب في البحث الثنائي.
لقائمة مرتبة مسبقاً من مليون عنصر، كم عدد مقارنات القيمة الوسطى التي يمكن أن يحتاجها البحث الثنائي في أسوأ حالة تقريباً؟
كل مقارنة تُضعف نطاق البحث المتبقي؛ حوالي 20 مقارنة تكفي لمليون عنصر مرتب. هذا excludes أي تكلفة للتصنيف مسبقاً.
يعمل البحث الثنائي على قائمة غير مرتبة، لكن ببطء أكثر.
بدون الترتيب المطلوب، استبعاد نصف يمكن أن يفوت عنصراً موجوداً. بعض الحالات قد تنجح بالصدفة، لكن الصحة غير مضمونة.
تحقق من الصفر وآخر فهرس مسموح به. ورقة العمل 4.4 تفتش حلقة مجموع تستخدم i أصغر من n، مما يفوّت الحد الأخير. كما يفسر تتبع إقليد stopping: يتم استبدال كل قاسم موجب بقسمة غير سالبة أصغر حتى الوصول إلى الصفر.