الدرس 22 · الوحدة 10: تحليل وفهم المشكلات التطبيقية

تحليل المشكلة قبل الحل

حجم البيانات وطبيعة الأسئلة يحددان الحل قبل أن تكتب سطرًا. ⏱ نحو 30 دقيقة.

بعد هذا الدرس ستستطيع أن:

تحلل المشكلة إلى مدخلات ومخرجات وعمليات متكررة وقيود.
تقدّر التعقيد المقبول من حجم البيانات.
تحوّل وصفًا واقعيًّا إلى قرارات تصميم: تركيب وخوارزمية.
تتعرف على المشكلات الصعبة بطبيعتها مثل البائع المتجول.

١أسئلة قبل أن تكتب سطرًا

المشكلات الحقيقية لا تأتي بصيغة «رتّب هذه القائمة». تأتي بصيغة: «التطبيق بطيء حين يبحث العميل عن منتج». أول عمل للمبرمج أن يحلل المشكلة:

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

٢حجم البيانات يحدد التعقيد المقبول

قاعدة تقريبية: بايثون تنفّذ نحو عشرة ملايين عملية بسيطة في الثانية. فإن طُلب جواب في ثانية تقريبًا:

حجم المدخل n	أقصى تعقيد مقبول تقريبًا	أمثلة
حتى 10	`O(n!)` أو `O(2ⁿ)`	تجربة كل الترتيبات
حتى 20 – 25	`O(2ⁿ)`	تجربة كل المجموعات الجزئية
حتى 500	`O(n³)`	ثلاث حلقات متداخلة
حتى 5,000	`O(n²)`	مقارنة كل زوج
حتى مليون	`O(n log n)`	الترتيب، ثم مرور واحد
عشرات الملايين	`O(n)`	مرور واحد بقاموس
أكبر من ذلك	`O(log n)` أو `O(1)`	بحث ثنائي، أو فهرس، أو جدول تجزئة

main.py

ops_per_sec = 10_000_000for n in [1_000, 100_000, 1_000_000]:    for name, ops in [("n²", n * n), ("n log n", n * (n.bit_length())), ("n", n)]:        secs = ops / ops_per_sec        print(f"n={n:>9,} {name:>8}: {secs:>12,.3f} ثانية تقريبًا")

Shell×

>>> %Run main.py

n= 1,000 n²: 0.100 ثانية تقريبًا

n= 1,000 n log n: 0.001 ثانية تقريبًا

n= 1,000 n: 0.000 ثانية تقريبًا

n= 100,000 n²: 1,000.000 ثانية تقريبًا

n= 100,000 n log n: 0.170 ثانية تقريبًا

n= 100,000 n: 0.010 ثانية تقريبًا

n=1,000,000 n²: 100,000.000 ثانية تقريبًا

n=1,000,000 n log n: 2.000 ثانية تقريبًا

n=1,000,000 n: 0.100 ثانية تقريبًا

>>>

٣مثال محلول: نظام حضور المتدربين

الوصف: بوابة الكلية تسجّل كل دخول: (الرقم التدريبي، الوقت). في نهاية اليوم نريد: من حضر؟ ومن تأخر بعد الساعة 7:30؟ ومن غاب من قائمة الشعبة؟

التحليل	القرار
المدخلات: سجل دخول فيه تكرار (المتدرب يدخل ويخرج)، وقائمة الشعبة.	نحفظ أول دخول لكل متدرب في قاموس: الرقم ← أول وقت.
الحجم: نحو 3000 متدرب و 10000 سجل يوميًّا.	`O(n)` أو `O(n log n)` يكفي جدًّا.
العملية المتكررة: «هل حضر فلان؟».	بحث في قاموس `O(1)`، لا في قائمة.
الغياب: من في الشعبة وليس في الحضور.	فرق مجموعتين: `O(n)`.
حالات خاصة: رقم غير موجود في الشعبة، أوقات غير مرتبة.	نتجاهل الغرباء، ونأخذ أصغر وقت.

main.py

log = [("441001", "07:12"), ("441005", "07:41"), ("441001", "09:30"),       ("441003", "07:28"), ("999999", "07:00"), ("441005", "07:35")]section = {"441001", "441002", "441003", "441004", "441005"} first = {}for sid, t in log:    if sid in section and (sid not in first or t < first[sid]):        first[sid] = t late = sorted(s for s, t in first.items() if t > "07:30")absent = sorted(section - first.keys())print("الحضور:", len(first))print("المتأخرون:", late)print("الغائبون:", absent)

Shell×

>>> %Run main.py

الحضور: 3

المتأخرون: ['441005']

الغائبون: ['441002', '441004']

>>>

٤قيّم صعوبة المشكلة

بعض المشكلات لا يوجد لها حل سريع معروف مهما ذكي المبرمج. مثال شهير: البائع المتجول TSP: أقصر جولة تزور كل المدن مرة وتعود. عدد الجولات الممكنة لـ n مدينة نحو (n−1)! ÷ 2:

main.py

import mathfor n in [5, 10, 15, 20]:    print(n, "مدن ←", f"{math.factorial(n - 1) // 2:,}", "جولة ممكنة")

Shell×

>>> %Run main.py

5 مدن ← 12 جولة ممكنة

10 مدن ← 181,440 جولة ممكنة

15 مدن ← 43,589,145,600 جولة ممكنة

20 مدن ← 60,822,550,204,416,000 جولة ممكنة

>>>

مع 20 مدينة تحتاج تجربة كل الجولات قرونًا. حين تواجه مشكلة كهذه نقبل حلًّا «جيدًا بما يكفي» بخوارزمية تقريبية أو جشعة (الدرس 24) بدل الحل الأمثل.

توقّع وتحقّق

مليون عنصر، والجواب مطلوب في ثانية. التعقيد المناسب:

10¹² عملية مستحيلة.

السؤال المتكرر «هل حضر فلان؟» يناسبه:

O(1).

15 مدينة وتجربة كل الجولات:

نمو مضروبي.

أول خطوة في تحليل المشكلة:

افهم أولًا.

الخلاصة

قبل الكود: المدخل، والمخرج، والحجم، والعملية المتكررة، والقيود، والحالات الخاصة.
نحو 10 ملايين عملية في الثانية في بايثون: الحجم يحدد التعقيد المقبول.
العملية المتكررة تحدد التركيب: بحث كثير ← قاموس.
بعض المشكلات بلا حل سريع معروف، فنقبل حلًّا تقريبيًّا.

تحدٍّ برمجي: حلّل ثم حل: الأكثر طلبًا

متوسط

سجل طلبات يومي فيه أسماء الأصناف. المطلوب أكثر 3 أصناف طلبًا مع عددها. الحجم المتوقع مليون طلب، فالحل يجب ألا يكون O(n²). اكتب في أول الكود تعليقات التحليل: المدخل، والمخرج، والتعقيد.

المطلوب:

ثلاثة أسطر تعليق: المدخل، المخرج، التعقيد.
عدّ بقاموس أو Counter.
اطبع كل صنف وعدده في سطر، من الأكثر.

ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:

main.py

orders = ["قهوة", "شاي", "قهوة", "كيك", "ماء", "قهوة", "شاي", "كيك", "قهوة", "عصير", "شاي"]

المطلوب×

قهوة 4

شاي 3

كيك 2

💡 تلميح 1

Counter(orders).most_common(3)

💡 تلميح 2

orders.count لكل صنف داخل حلقة يجعل الحل O(n²).

حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.

main.py

# المدخل: قائمة أسماء أصناف (قد تصل إلى مليون)# المخرج: أكثر 3 أصناف مع عددها# التعقيد: O(n) للعدّ، والأصناف المختلفة قليلةfrom collections import Counter orders = ["قهوة", "شاي", "قهوة", "كيك", "ماء", "قهوة", "شاي", "كيك", "قهوة", "عصير", "شاي"] for item, n in Counter(orders).most_common(3):    print(item, n)

انتقل إلى تقييم الدرساختيار من متعدد، وصح وخطأ، وأكمل الفراغ، وتتبّع الناتج.ابدأ التقييم ←

📝 معلم؟ أرسل ملاحظة للمؤلف عن هذا الدرس