الجلسة التطبيقية 10 (Recitation 10)

المصادر والنسبة والترخيص

المادة الأصلية: آنا بيل (Ana Bell)، MIT OpenCourseWare (MIT OCW)، معهد ماساتشوستس للتكنولوجيا، مقرر 6.100L: مقدمة في علوم الحاسوب والبرمجة باستخدام Python، خريف 2022 (Fall 2022).

• صفحة الجلسة الرسمية على OCW.

هذه ترجمة وتكييف عربي غير رسمي وفق رخصة CC BY-NC-SA 4.0: النسبة–غير التجاري–المشاركة بالمثل، ولا تعني اعتمادًا أو تأييدًا من MIT أو MIT OCW. شروط الاستخدام والاستشهاد.

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

ملاحظة المترجم: المصدر ملف PDF. في الملف الأصلي مخطّط «Big-O Complexity Chart» لم يُضمَّنا لأنّ الصفحة نصّية، ووُصف محتواهما في موضعيهما. وعوّضت علامات التنصيص المنحنية « “ ” » و« ‘ ’ » وشرطة الطرح « – » بعلامات ASCII حتى تعمل الشيفرة كما كُتبت.

المحاضرة المرتبطة

تُرافق هذه الجلسة التطبيقية المحاضرة 23: أمثلة أصناف التعقيد (Complexity Classes Examples). ويعرض ملخّصها مراجعةً لكتابة البرامج الكفؤة (Writing Efficient Programs) والتعقيد (Complexity) ورتبة النموّ (Order of Growth).

تذكيرات (Reminders)

6.100L، الجلسة التطبيقية 10 — 2 ديسمبر.

• مسابقة MQ10 يوم الاثنين 12/5.
• مجموعة المسائل PSET 5 مستحقّة الأربعاء 12/7 الساعة 9 مساءً.

مراجعة المحاضرة: كتابة البرامج الكفؤة والتعقيد

كتابة البرامج الكفؤة (Writing Efficient Programs)

• حتى الآن تكلّمنا غالبًا عن السلامة (correctness)، لكنّنا نحتاج أيضًا إلى التفكير في الكفاءة (efficiency) عند كتابة البرامج.
• حين نتكلّم عن تحسين الكفاءة، فإنّنا نعني عادةً كتابة البرنامج بطريقة مختلفة بحيث يُنفَّذ أسرع.

بعض طرق تقييم كفاءة البرامج

1. بمؤقّت (timer) وباستعمال وحدة time

مثال:

import time # import time module
tstart = time.time() # "start" timer
count = 0
for i in range(1000):
    count += 1
tend = time.time() # "end" timer
dt = tend - tstart
print(dt) # print time to run program

2. بعدد العمليات (Counting number of operations)

تأخذ الخطوات التالية زمنًا ثابتًا (constant time):

• العمليات الرياضية (Mathematical operations).
• المقارنات (Comparisons).
• الإسنادات (Assignments).
• الوصول إلى الكائنات في الذاكرة (Accessing objects in memory).

3. تجريد رتبة النموّ (Abstraction of order of growth) — انظر القسم التالي.

التعقيد ورتبة النموّ (Complexity/Order of Growth)

• الترميز «Big-O».

• يعطينا فكرة عن المدّة التي ستستغرقها خوارزمية ما لتعمل، بحسب حجم مدخلاتها (معاملاتها)، مهما كانت الآلة التي تعمل عليها.

• يعطيني الحالة الأسوأ (worst case).

• لا نهمّنا الحدود الأدنى رتبة والثوابت. نحن مهتمّون بالاتجاهات مع نموّ المدخلات كثيرًا جدًّا، ولذلك تهيمن الحدود الأعلى رتبة.

  • الجمع:

    $$O(n^2) + O(n) + O(1) \to O(n^2 + n + 1) \to O(n^2)$$

  • الثوابت المضروبة أو المضافة لا تهمّ:

    $$O(10*n) \to O(n)$$ $$O(n) * O(n) \to O(n^2)$$ $$O(\log_2(n)) \to O(\log(n)/\log(2)) \to O(\log(n))$$ $$O(n + 1) \to O(n)$$

• نريد أضيق حدّ ممكن. من الناحية الفنية، خوارزمية $O(n)$ هي أيضًا $O(n^2)$ و$O(2^n)$ إلخ، لأنّ $O$ تعني «أصغر من أو يساوي» فحسب، لكنّنا نريد أقرب حدّ أعلى ممكن.

• حدّ $\Theta$ الكبير (Big Θ bound) هو حدّ أدنى وحدّ أعلى لنموّ دالة ما — وهو حدّ أضيق:

  $$f(x) = \Theta(x^2) \ne \Theta(n^3) \ne \Theta(2^x)$$ $$n^2 + 2n + 6 \to \Theta(n^2)$$

رتب النموّ الشائعة مرتّبة حسب ازدياد التعقيد. والمثاليّ أن نصمّم خوارزميات أقرب ما يمكن إلى أعلى الجدول.

التعقيد (Complexity)	الزمن (Time)	أمثلة (Examples)
$O(1)$	ثابت (Constant)	جمع عددين معًا، والإلحاق بقائمة — مستقلّ عن حجم المدخلات!
$O(\log(n))$	لوغاريتمي (Logarithmic)	البحث الثنائي (Binary search)
$O(n)$	خطّي (Linear)	list.copy()، أو المرور على القائمة كاملةً بحثًا عن قيمة
$O(n \log(n))$	شبه خطّي (Log-linear)	الدمج والترتيب (Merge-sort)
$O(n^2)$ و$O(n^3)$ إلخ…	متعدّد الحدود (Polynomial)	حلقتا for متداخلتان
$O(2^n)$ و$O(3^n)$ إلخ…	أُسّي (exponential)	محاولة تخمين كلمة مرور من $n$ حرفًا

تعقيد دوال بايثون وكائناتها (Complexity of Python methods/objects)

• عمليات ذات زمن ثابت (Constant-time operations):
  • إسناد متغيّر (x = 1).
  • إجراء عمليات أساسيّة (+ و- و/ و** و< و> و== إلخ).
  • بعض طرائق بايثون المدمجة لبنى البيانات هي أيضًا ذات زمن ثابت، لكنّ كثيرًا منها ليس كذلك. وبرغم أنّنا لا ننظر إلى الآلية الداخلية لكثير من هذه الطرق المدمجة، فإنّ تعقيد تنفيذها يؤثّر في تحليل التعقيد لدوالنا هي.
• القواميس (Dictionaries) — تعتمد على دالة التجزئة (hash function):
  • $O(1)$: البحث (lookup)، وفحص إن كان المفتاح في القاموس، والطول، والإدراج، والحذف.
  • $O(n)$: d.keys() أو d.values() — إذ يجب توليد قائمة طولها $n$.
• القوائم (Lists):
  • $O(1)$: الإلحاق (append)، والطول.
  • $O(n)$: الإدراج، والحذف (تحريك العناصر)، والنسخ، وفحص إن كان العنصر موجودًا في قائمة غير مرتّبة.
  • $O(n \log(n))$: الترتيب (sort).

استراتيجيات تحليل رتبة النموّ (Strategies for Order-of-Growth Analysis)

• الحلقات: عدد التكرارات مضروبًا في تكلفة كلّ تكرار.
• الدوال ذات الاستدعاء الذاتي (Recursive functions):
  • كم عدد الاستدعاءات الذاتيّة التي تُجرى؟
  • كم من العمل يأخذه كلّ استدعاء ذاتي؟
  • ارسم شجرة تصل المسائل الفرعية ببعضها.

مخطط تعقيد Big-O المفيد (Helpful Big-O Complexity Chart)

ملاحظة المترجم: في المستند الأصلي مخطط «Big-O Complexity Chart» محوره الأفقي عدد العناصر (Elements) ومحوره العمودي عدد العمليات (Operations)، وعليه المنحنيات $O(1)$ و$O(\log n)$ و$O(n)$ و$O(n \log n)$ و$O(n^2)$ و$O(2^n)$، ويتوزّع خلفه على أشرطة لونية متدرّجة من «فظيع» (Horrible) إلى «ممتاز» (Excellent)، ويذكر أسفله أنّه من محاضرة 6.s061 رقم 20.