Arabic:هياكل البيانات والخوارزميات

مقدمة

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

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

ستستخدم أمثلة بلغة Python لتثبيت الأفكار، لكن الهدف ليس حفظ بناء جملة لغة بعينها، بل اكتساب نمط تفكير يمكن نقله إلى Java أو C++ أو غيرهما. وعند قراءة أي خوارزمية اسأل دائماً: ما حجم المدخلات؟ ما العمليات المسيطرة؟ كيف يتغير استهلاك الزمن والذاكرة عندما يكبر الحجم؟ وما البنية التي تجعل هذه العمليات أرخص؟

مخطط عربي للمكدس بوصفه بنية تعمل وفق مبدأ الداخل أخيراً يخرج أولاً.

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

أهداف التعلم

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

ستتدرب كذلك على تتبع التنفيذ يدوياً، وبناء اختبارات حدّية، واكتشاف الافتراضات الخفية، وكتابة حلول صغيرة قابلة للقياس والمقارنة.

التفكير الخوارزمي واختيار بنية البيانات

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

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

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

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

المصفوفات والقوائم

المصفوفة تخزن العناصر في مواقع متجاورة منطقياً، وتسمح بالوصول إلى عنصر بواسطة فهرسه في زمن ثابت تقريباً O(1). لكن إدراج عنصر في وسط مصفوفة مرتبة قد يتطلب إزاحة عدد من العناصر، فتكون الكلفة O(n) في أسوأ حالة. في Python تمثل البنية list مصفوفة ديناميكية؛ فهي توسع سعتها تلقائياً عند الحاجة، ولذلك تكون الإضافة في النهاية O(1) في المتوسط المُهلك، مع وجود عمليات توسعة نادرة تكلف O(n).

بيانات = [12, 5, 9, 20]
بيانات[2] = 11
print(بيانات[1])
بيانات.append(31)

أما القائمة المرتبطة فتتكون من عقد، وتحمل كل عقدة قيمة وإشارة إلى العقدة التالية، وقد تحمل أيضاً إشارة إلى السابقة في القائمة المزدوجة. لا توفر القائمة المرتبطة وصولاً مباشراً بالفهرس؛ للوصول إلى العنصر رقم k يجب المرور بالعقد السابقة، لذلك يكون الوصول O(n). لكنها تسمح بإدراج أو حذف عقدة في O(1) إذا كان موضع العقدة أو مرجعها معروفاً ولم نحتج إلى البحث عنها أولاً.

قائمة مرتبطة أحادية: كل عقدة تقود إلى العقدة التالية حتى نهاية القائمة.

class عقدة:
    def __init__(self, قيمة, التالي=None):
        self.قيمة = قيمة
        self.التالي = التالي

أولى = عقدة(7)
ثانية = عقدة(12)
أولى.التالي = ثانية

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

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

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

المكدسات والطوابير

المكدس يتبع مبدأ الداخل أخيراً يخرج أولاً. تظهر هذه الفكرة في مكدس الاستدعاءات، والتراجع عن العمليات، وتحليل الأقواس، وتنفيذ البحث بعمق البيان. العمليات الجوهرية هي الإضافة إلى القمة والإزالة منها والاطلاع على القمة، ويمكن تنفيذها في O(1) عند استخدام بنية مناسبة.

مكدس = []
مكدس.append("أ")
مكدس.append("ب")
عنصر = مكدس.pop()
print(عنصر)

تتغير قمة المكدس فقط أثناء الإضافة والإزالة.

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

أما الطابور فيتبع مبدأ الداخل أولاً يخرج أولاً. يدخل العنصر من الخلف ويخرج من الأمام. تُستخدم الطوابير في جدولة الأعمال، والمحاكاة، ومعالجة الطلبات، والبحث بعرض البيان. في Python لا يُفضّل حذف العنصر الأول من list بصورة متكررة لأن الإزاحة تكلف O(n)؛ بل يُفضّل استعمال deque التي تدعم الإضافة والحذف من الطرفين بكفاءة.

الطابور يحافظ على ترتيب الدخول عند المعالجة.

from collections import deque
طابور = deque()
طابور.append("مهمة أولى")
طابور.append("مهمة ثانية")
منفذة = طابور.popleft()
print(منفذة)

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

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

الأشجار وأشجار البحث الثنائية

الشجرة بنية هرمية من عقد وروابط. للعقدة الجذرية مستوى أعلى، وقد تكون لكل عقدة عقد أبناء. في الشجرة الثنائية لا يزيد عدد الأبناء عن اثنين. من المصطلحات المهمة: الجذر، والأب، والابن، والورقة، والعمق، والارتفاع، والشجرة الفرعية.

شجرة البحث الثنائية تضيف شرط ترتيب: القيم الأصغر من قيمة عقدة ما تكون في الفرع الأيسر، والقيم الأكبر في الفرع الأيمن وفق سياسة المقارنة المختارة. يتيح هذا الشرط بحثاً وإدراجاً وحذفاً بكلفة متناسبة مع ارتفاع الشجرة. إذا كانت الشجرة متوازنة يكون الارتفاع من رتبة log n، فتكون العمليات الأساسية O(log n). وإذا انحرفت الشجرة وصارت شبيهة بقائمة طويلة فقد تهبط الكفاءة إلى O(n).

مثال على شجرة بحث ثنائية يُقارن فيها الهدف بعقد متتابعة على مسار واحد.

توضح الحركة كيف يتحدد موضع الإدراج عبر المقارنات المتتالية.

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

def بحث_في_شجرة(عقدة, هدف):
    while عقدة is not None:
        if هدف == عقدة.قيمة:
            return True
        if هدف < عقدة.قيمة:
            عقدة = عقدة.يسار
        else:
            عقدة = عقدة.يمين
    return False

تحدٍ برمجي: نفّذ دالة تحسب ارتفاع شجرة ثنائية ودالة تعيد عدد الأوراق. ثم أنشئ شجرتين لهما العدد نفسه من العقد لكن شكلان مختلفان، وقارن عدد المستويات التي تزورها عملية البحث.

البيانات وتمثيل العلاقات

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

مثال على بيان يوضح الرؤوس والحواف والعلاقات بين العقد.

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

البحث بعرض البيان يوسّع الجبهة بحسب المسافة بعدد الحواف من نقطة البدء.

البحث بعمق البيان يتقدم على مسار قبل أن يعود إلى نقاط التفرع.

from collections import deque

def بحث_بالعرض(بيان, بداية):
    طابور = deque([بداية])
    مزارة = {بداية}
    ترتيب = []
    while طابور:
        رأس = طابور.popleft()
        ترتيب.append(رأس)
        for جار in بيان[رأس]:
            if جار not in مزارة:
                مزارة.add(جار)
                طابور.append(جار)
    return ترتيب

إذا كان لدينا V من الرؤوس وE من الحواف وتمثيل بقوائم المجاورة، فإن البحثين بعرض البيان وعمقه يعملان في O(V + E) لأن كل رأس وكل حافة تُعالج عدداً محدوداً من المرات.

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

البحث الخطي والبحث الثنائي

البحث الخطي يفحص العناصر تباعاً حتى يجد الهدف أو تنتهي البيانات. لا يحتاج إلى ترتيب مسبق، وتكلفته O(n) في أسوأ حالة. وهو خيار معقول للمدخلات الصغيرة أو غير المرتبة أو عندما يحدث البحث مرة واحدة فقط.

البحث الثنائي يستغل ترتيب البيانات. يقارن الهدف بالعنصر الأوسط، ثم يستبعد نصف المجال في كل خطوة. لذلك يحتاج تقريباً إلى عدد خطوات لوغاريتمي O(log n). لكنه يتطلب بيانات مرتبة وبنية تسمح بالوصول الفعال إلى العنصر الأوسط؛ ولهذا يكون مناسباً للمصفوفات أكثر من القوائم المرتبطة التقليدية.

يوضح الرسم لماذا ينمو عدد خطوات البحث الثنائي لوغاريتمياً مع حجم المدخلات.

في كل مقارنة يستبعد البحث الثنائي جزءاً كبيراً من المجال المتبقي.

def بحث_ثنائي(بيانات, هدف):
    يسار = 0
    يمين = len(بيانات) - 1
    while يسار <= يمين:
        وسط = (يسار + يمين) // 2
        if بيانات[وسط] == هدف:
            return وسط
        if بيانات[وسط] < هدف:
            يسار = وسط + 1
        else:
            يمين = وسط - 1
    return -1

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

تحدٍ برمجي: عدّل البحث الثنائي ليعيد أول موضع لقيمة مكررة في قائمة مرتبة بدلاً من التوقف عند أي نسخة منها. اختبر قائمتك بقيم مكررة في البداية والوسط والنهاية.

خوارزميات الفرز

الفرز يعيد ترتيب العناصر وفق مفتاح مقارنة. من المفيد التمييز بين خوارزميات بسيطة سهلة الفهم وخوارزميات أكثر كفاءة للمدخلات الكبيرة. فرز الاختيار يبحث في كل دورة عن أصغر عنصر متبقٍ ويضعه في موضعه؛ تكلفته الزمنية O(n²) حتى لو كانت القائمة شبه مرتبة. فرز الإدراج يبني جزءاً مرتباً ويُدرج كل عنصر في موقعه، وهو أيضاً O(n²) في أسوأ حالة لكنه قد يكون عملياً جيداً للمدخلات الصغيرة أو شبه المرتبة.

فرز الاختيار يثبت عنصراً في موضعه النهائي في كل دورة.

def فرز_بالإدراج(بيانات):
    for موضع in range(1, len(بيانات)):
        قيمة = بيانات[موضع]
        سابق = موضع - 1
        while سابق >= 0 and بيانات[سابق] > قيمة:
            بيانات[سابق + 1] = بيانات[سابق]
            سابق -= 1
        بيانات[سابق + 1] = قيمة
    return بيانات

فرز الدمج يقسم البيانات إلى أجزاء، يفرزها استدعائياً، ثم يدمج الأجزاء المرتبة. زمنه O(n log n) في جميع الحالات القياسية، لكنه يحتاج عادة إلى ذاكرة إضافية للدمج. الفرز السريع يختار محوراً ويقسم العناصر إلى مجموعات بحسب علاقتها بالمحور، ثم يكرر العملية على الأجزاء. يكون متوسط زمنه O(n log n)، بينما قد يصل أسوأ زمن إلى O(n²) إذا كانت عمليات التقسيم سيئة بصورة متكررة، ويمكن تقليل هذا الخطر باختيار محور مناسب أو عشوائي.

الفرز السريع يقسم العناصر حول محور ثم يعالج الأجزاء الناتجة.

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

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

تحدٍ برمجي: قِس زمن فرز الإدراج وفرز الدمج على قوائم عشوائية بأحجام متزايدة، ثم كرر القياس على قوائم شبه مرتبة. لا تستنتج من تجربة واحدة؛ أعد القياس عدة مرات وفسّر النتائج مع التعقيد النظري.

تصميم الخوارزميات والتعقيد الحسابي

التعقيد الحسابي يصف معدل نمو الموارد مع حجم المدخلات، لا الزمن بالثواني على جهاز محدد. يعبّر الرمز O عادة عن حد علوي تقاربي، وOmega عن حد سفلي، وTheta عن حد محكم من الجهتين. في الممارسة التعليمية كثيراً ما نستخدم O لوصف رتبة النمو المهيمنة عند تحليل خوارزمية.

ترتيب معدلات النمو الشائع من الأفضل إلى الأسوأ عند كبر n هو تقريباً: O(1)، ثم O(log n)، ثم O(n)، ثم O(n log n)، ثم O(n²)، ثم O(n³)، ثم معدلات أسية مثل O(2^n). الفروق الصغيرة في الثوابت قد تهم للمدخلات الصغيرة، لكن معدل النمو يهيمن غالباً عندما تكبر المدخلات.

من قواعد التحليل: نتجاهل الثوابت في الرتبة التقاربية، ونحتفظ بالحد المسيطر. فإذا كانت الكلفة 3n² + 8n + 20 فإن الرتبة O(n²). وإذا كانت حلقتان متداخلتان كل منهما تمر تقريباً على n عنصر فالكلفة الشائعة O(n²)، أما حلقتان متتاليتان فالكلفة O(n) + O(n) التي تبقى O(n).

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

تحميل الفيديو

يوتيوب

قد يقوم يوتيوب بجمع البيانات الشخصية. سياسة الخصوصية

استمرار تجاهل

البنية أو الخوارزمية	عملية نموذجية	الرتبة الزمنية الشائعة	ملاحظة
مصفوفة	وصول بالفهرس	O(1)	الوصول المباشر هو نقطة القوة الأساسية
قائمة مرتبطة	وصول إلى العنصر رقم k	O(n)	يلزم اجتياز العقد السابقة
مكدس	إضافة أو إزالة من القمة	O(1)	عند التنفيذ ببنية مناسبة
طابور	إضافة من الخلف وإزالة من الأمام	O(1)	عند التنفيذ ببنية مناسبة مثل deque
شجرة بحث ثنائية متوازنة	بحث أو إدراج	O(log n)	يعتمد الضمان على بقاء الشجرة متوازنة
بحث خطي	العثور على هدف	O(n)	لا يحتاج ترتيباً مسبقاً
بحث ثنائي	العثور على هدف	O(log n)	يحتاج بيانات مرتبة ووصولاً فعالاً للوسط
فرز الدمج	فرز n عناصر	O(n log n)	يحتاج عادة إلى ذاكرة إضافية للدمج

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

تحدٍ برمجي: لديك قائمتان مرتبتان. صمّم خوارزمية لدمجهما في قائمة مرتبة واحدة في O(n + m)، ثم اشرح لماذا سيكون جمع القائمتين ثم استخدام فرز عام أقل مباشرة من الاستفادة من خاصية الترتيب الموجودة مسبقاً.

أخطاء شائعة وحدود النماذج

من الأخطاء الشائعة الاعتقاد أن O الكبير يعطي زمناً دقيقاً؛ هو يصف النمو التقاربي ولا يتنبأ وحده بالثوابت أو سلوك الذاكرة المخبئية أو كلفة المترجم. ومن الأخطاء كذلك تطبيق البحث الثنائي على بيانات غير مرتبة، أو افتراض أن شجرة البحث الثنائية متوازنة تلقائياً، أو استخدام قائمة Python كطابور مع حذف متكرر من البداية، أو نسيان تعليم الرؤوس المزارة في اجتياز بيان يحوي دورات.

كذلك لا يعني أن خوارزمية O(n log n) أسرع دائماً من خوارزمية O(n²) لكل قيمة صغيرة من n؛ لكنه مؤشر قوي عند التوسع. والقياس التجريبي لا يحل محل التحليل النظري، كما أن التحليل النظري لا يغني عن القياس عندما تهم تفاصيل المنصة والبيانات الفعلية.

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

مهام تفاعلية

اختبار: اختبر معرفتك

أي بنية توفر عادة وصولاً مباشراً إلى عنصر بواسطة فهرسه؟ (المصفوفة) (!القائمة المرتبطة) (!المكدس) (!الطابور)

ما المبدأ الذي يصف سلوك المكدس؟ (الداخل أخيراً يخرج أولاً) (!الداخل أولاً يخرج أولاً) (!الأصغر يخرج أولاً دائماً) (!العناصر تخرج عشوائياً)

ما البنية التي يعتمد عليها البحث بعرض البيان عادة؟ (الطابور) (!المكدس فقط) (!المصفوفة المرتبة فقط) (!شجرة البحث الثنائية فقط)

ما الشرط الأساسي لاستخدام البحث الثنائي بصورة صحيحة؟ (أن تكون البيانات مرتبة وفق معيار البحث) (!أن تكون البيانات في قائمة مرتبطة) (!أن تكون جميع القيم مختلفة) (!أن يكون عدد العناصر زوجياً)

ما التعقيد الزمني للبحث الخطي في أسوأ حالة؟ (زمن خطي) (!زمن ثابت) (!زمن لوغاريتمي) (!زمن تربيعي دائماً)

ماذا يحدث عادة لكفاءة شجرة بحث ثنائية غير متوازنة بشدة؟ (قد تصبح بعض العمليات خطية) (!تصبح جميع العمليات ثابتة) (!تتحول تلقائياً إلى طابور) (!يصبح البحث مستحيلاً دائماً)

أي خوارزمية فرز لها زمن من رتبة n log n في الحالات القياسية كلها؟ (فرز الدمج) (!فرز الاختيار) (!فرز الإدراج) (!البحث الخطي)

ما معنى أن البحث بعرض البيان يجد أقصر مسار في بيان غير موزون؟ (يجد أقل عدد من الحواف من نقطة البدء) (!يجد دائماً أقل وزن عددي للحواف) (!يزور كل رأس مرة بلا حاجة إلى طابور) (!يعمل فقط على الأشجار الثنائية)

أي عبارة أدق عن ترميز O الكبير؟ (يصف معدل نمو حد علوي تقاربي) (!يعطي زمن التنفيذ بالثواني) (!يعطي مقدار الذاكرة فقط) (!يثبت أن خوارزمية ما هي الأفضل عملياً دائماً)

لماذا قد نفضل قوائم المجاورة لبيان قليل الحواف؟ (لأنها غالباً تستهلك ذاكرة تتناسب مع الرؤوس والحواف الموجودة) (!لأنها تجعل كل خوارزمية بزمن ثابت) (!لأنها تمنع وجود الدورات) (!لأنها ترتب الرؤوس تلقائياً)

لعبة الذاكرة

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

السحب والإفلات

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

كلمات متقاطعة

مصفوفة	بنية تسمح بالوصول إلى عنصر بواسطة فهرس
مكدس	بنية يخرج منها آخر عنصر دخل
طابور	بنية يخرج منها أول عنصر دخل
شجرة	بنية هرمية لها جذر وفروع
بيان	بنية تتكون من رؤوس وحواف
تعقيد	مفهوم يصف نمو كلفة الخوارزمية مع حجم المدخلات

مهام مفتوحة

سهل

1. مقارنة المصفوفة والقائمة: أنشئ جدولاً عربياً يقارن بين الوصول والإدراج والحذف واستهلاك الذاكرة في المصفوفة والقائمة المرتبطة، ثم اذكر مثالاً مناسباً لكل بنية.
2. تتبع المكدس: ارسم على ورقة تغير محتوى مكدس أثناء إدخال خمسة عناصر ثم إزالة ثلاثة، وصوّر الرسم أو حوّله إلى مخطط رقمي مع تفسير قصير.
3. محاكاة طابور: اكتب برنامجاً قصيراً يحاكي وصول طلبات إلى طابور وخدمتها بالترتيب، ثم اختبر حالة الطابور الفارغ.
4. تتبع البحث الثنائي: اختر قائمة مرتبة من خمسة عشر عدداً وسجّل حدود مجال البحث والوسط في كل خطوة عند البحث عن قيمة موجودة وأخرى غير موجودة.

متوسط

1. مختبر القوائم المرتبطة: نفّذ قائمة مرتبطة أحادية تدعم الإضافة في البداية والبحث والحذف، ثم اكتب مجموعة اختبارات تشمل قائمة فارغة وعنصراً واحداً وقيمة مكررة.
2. مقارنة البحث: نفّذ البحث الخطي والثنائي وقِس عدد المقارنات على بيانات بأحجام مختلفة، ثم اكتب تفسيراً يربط النتائج بالتعقيد النظري.
3. استكشاف الأشجار: أنشئ شجرة بحث ثنائية من مجموعة قيم، وارسم شكلها بعد كل إدراج، ثم قارن ارتفاعها عند إدخال القيم بترتيب عشوائي وبترتيب تصاعدي.
4. فيديو اجتياز البيان: أنشئ فيديو قصيراً أو عرضاً متحركاً يوضح الفرق بين البحث بالعرض والبحث بالعمق على البيان نفسه، مع تسمية ترتيب زيارة الرؤوس بالعربية.

متقدم

1. تجربة خوارزميات الفرز: نفّذ فرز الإدراج وفرز الدمج والفرز السريع، ثم نفّذ تجربة منهجية على بيانات عشوائية وشبه مرتبة ومعكوسة، واعرض النتائج في رسوم بيانية وفسرها.
2. مصمم مسارات جامعية: مثّل متطلبات مجموعة من المقررات الجامعية ببيان موجه، ثم صمّم خوارزمية تكشف الدورات وتقترح ترتيباً صالحاً للدراسة عندما يكون ذلك ممكناً.
3. تحليل الذاكرة والزمن: اختر مسألة يمكن حلها بطريقتين تختلفان في استهلاك الذاكرة والزمن، ونفّذ الطريقتين ثم اكتب تقريراً يبرر متى تفضل كل واحدة.
4. مشروع محرك توصية مصغر: صمّم نموذجاً تعليمياً يستخدم بياناً لتمثيل المستخدمين أو العناصر والعلاقات بينهم، وحدد بنية البيانات وخوارزمية الاجتياز ومقاييس التعقيد، ثم قدّم الشيفرة والاختبارات والقيود الأخلاقية المتعلقة بالبيانات.

مجالات تعلم مرتبطة

هياكل البيانات والخوارزميات البرمجة الرياضيات المتقطعة تحليل الخوارزميات نظرية البيان قواعد البيانات نظم التشغيل

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

مسرد

بنية البيانات: طريقة منظمة لتمثيل البيانات وتخزينها بحيث تدعم مجموعة من العمليات بكفاءة محددة.

الخوارزمية: تسلسل محدود وواضح من الخطوات يحول مدخلات إلى مخرجات لحل مشكلة محددة.

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

القائمة المرتبطة: سلسلة من العقد تحمل قيماً وروابط إلى عقد أخرى، ولا تعتمد على الفهرسة المباشرة.

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

الطابور: نوع مجرد للبيانات يعالج العناصر عادة وفق مبدأ الداخل أولاً يخرج أولاً.

الشجرة: بنية هرمية من عقد وعلاقات أبوة وفروع، تبدأ عادة بجذر.

شجرة البحث الثنائية: شجرة ثنائية تنظم المفاتيح بحيث تقود المقارنات إلى فرع أيسر أو أيمن وفق ترتيب محدد.

البيان: نموذج يتكون من رؤوس وحواف لتمثيل العلاقات العامة بين الكيانات.

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

الفرز: إعادة ترتيب مجموعة عناصر وفق مفتاح أو علاقة مقارنة محددة.

التعقيد الزمني: وصف تقاربي لكيفية نمو عدد العمليات مع زيادة حجم المدخلات.

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

الثبات المنطقي: خاصية تبقى صحيحة قبل تكرارات محددة وأثناءها وبعدها، وتساعد في تفسير صحة الخوارزمية.