الفصل 2: أساسيات الخوارزميات

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

أنواع البيانات والبنى البيانية

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

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

عند تصميم الخوارزميات، من الضروري اختيار أنواع البيانات والبنى البيانية المناسبة التي تدعم العمليات المطلوبة بكفاءة. يمكن أن يؤدي اختيار البنية البيانية إلى اختلاف كبير في أداء الخوارزمية.

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

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

الأكياس

الكيس هو مجموعة غير مرتبة من العناصر التي تسمح بالنسخ المتكررة. العمليات الرئيسية التي يدعمها الكيس هي:

• add(item): إضافة عنصر إلى الكيسهنا هو الترجمة العربية لملف Markdown هذا:

• isEmpty(): تحقق من كون الحقيبة فارغة.

• size(): إرجاع عدد العناصر في الحقيبة.

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

الطوابير

الطابور هو مجموعة من العناصر تتبع مبدأ الدخول الأول والخروج الأول (FIFO). العمليات الرئيسية التي يدعمها الطابور هي:

• enqueue(item): إضافة عنصر إلى نهاية الطابور.
• dequeue(): إزالة وإرجاع العنصر من أمام الطابور.
• isEmpty(): التحقق من كون الطابور فارغًا.
• size(): إرجاع عدد العناصر في الطابور.

يتم استخدام الطوابير غالبًا في السيناريوهات التي تتطلب معالجة العناصر بترتيب وصولها، مثل جدولة المهام أو البحث بالعرض أولاً.

الأكوام

الكومة هي مجموعة من العناصر تتبع مبدأ آخر من يدخل أول من يخرج (LIFO). العمليات الرئيسية التي يدعمها الكومة هي:

• push(item): إضافة عنصر إلى أعلى الكومة.
• pop(): إزالة وإرجاع العنصر من أعلى الكومة.
• isEmpty(): التحقق من كون الكومة فارغة.
• size(): إرجاع عدد العناصر في الكومة.

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

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

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

إن تحليل كفاءة الخوارزميات أمر حاسم لفهم خصائص أدائها واتخاذ قرارات مستنيرة عند اختيار الخوارزميات للمشكلات المحددة. يتضمن تحليل الخوارزميات دراسة تعقيد الوقت والتعقيد المكاني للخوارزمية.

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

خوارزمية بتعقيد زمني من O(n) تعني أن وقت تشغيلها ينمو بشكل خطي مع حجم الإدخال.

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

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

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

دراسة حالة: اتحاد-إيجاد

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

• union(p, q): دمج المجموعات التي تحتوي على العناصر p و q.
• find(p): العثور على المجموعة التي تحتوي على العنصر p.

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

هناك العديد من الخوارزميات لتنفيذ هيكل البيانات اتحاد-إيجاد، لكل منها مقايضات مختلفة بين تعقيد الوقت لعمليتي union و find. بعض التنفيذات الشائعة تشمل:

• Quick-find: عملية find ثابتة الوقت، ولكن عملية union تأخذ وقتًا خطيًا.
• Quick-unioهنا الترجمة العربية للملف:

الملخص: عملية union أسرع من quick-find، ولكن عملية find قد تستغرق وقتًا خطيًا في أسوأ الحالات.

• weighted quick-union: تحسين على quick-union يوازن الأشجار حسب الحجم، مما يجعل كل من عمليتي union و find لوغاريتمية في أسوأ الحالات.
• weighted quick-union مع ضغط المسار: تحسين إضافي يسطح بنية الشجرة أثناء عمليات find، مما ينتج عنه تعقيد زمني تقريبًا ثابت لكل من union و find.

دراسة الحالة لاتحاد-البحث تسلط الضوء على أهمية اختيار هياكل البيانات والخوارزميات المناسبة بناءً على متطلبات المشكلة واعتبارات الأداء.

الخاتمة

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

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