الفصل 9: نماذج تصميم الخوارزميات

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

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

تقسيم والاستيلاء

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

تتكون خوارزمية تقسيم والاستيلاء النموذجية من ثلاث خطوات:

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

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

ترتيب الدمج: خوارزمية تقسيم والاستيلاء كلاسيكية

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

فيما يلي وصف عام لخوارزمية ترتيب الدمج:هنا الترجمة العربية للملف:

خوارزمية الفرز بالدمج:

function mergesort(array):
    # إذا كان طول المصفوفة أقل من أو يساوي 1، فأرجع المصفوفة كما هي
    if array.length <= 1:
        return array
    else:
        # قسم المصفوفة إلى نصفين
        mid = array.length / 2
        left = mergesort(array[0:mid])
        right = mergesort(array[mid:])
        # دمج النصفين المفروزين
        return merge(left, right)

الدالة merge تقوم بدمج مصفوفتين مفروزتين إلى مصفوفة واحدة مفروزة:

function merge(left, right):
    # إنشاء مصفوفة النتيجة
    result = []
    # دمج العناصر من المصفوفتين اليسرى واليمنى
    while left is not empty and right is not empty:
        if left[0] <= right[0]:
            # إضافة العنصر الأول من المصفوفة اليسرى إلى النتيجة
            append left[0] to result
            # إزالة العنصر الأول من المصفوفة اليسرى
            remove left[0] from left
        else:
            # إضافة العنصر الأول من المصفوفة اليمنى إلى النتيجة
            append right[0] to result
            # إزالة العنصر الأول من المصفوفة اليمنى
            remove right[0] from right
    # إضافة العناصر المتبقية من المصفوفة اليسرى إلى النتيجة
    append remaining elements of left to result
    # إضافة العناصر المتبقية من المصفوفة اليمنى إلى النتيجة
    append remaining elements of right to result
    # إرجاع مصفوفة النتيجة
    return result

استراتيجية التقسيم والاستيلاء تسمح لخوارزمية الفرز بالدمج بتحقيق زمن تشغيل سوء الحال بمعدل O(n log n)، مما يجعلها واحدة من أكثر خوارزميات الفرز العامة كفاءة.

نظرية السيد

يمكن تحليل زمن تشغيل العديد من خوارزميات التقسيم والاستيلاء باستخدام نظرية السيد، والتي توفر صيغة عامة للتكرارات من الشكل:

T(n) = aT(n/b) + f(n)

هنا، a هو عدد المكالمات المتكررة، n/b هو حجم كل مشكلة فرعية، و f(n) هي تكلفة تقسيم المشكلة ودمج النتائج.

تنص نظرية السيد على أن الحل لهذا التكرار هو:

1. إذا كان f(n) = O(n^(log_b(a) - ε)) لبعض الثابت ε > 0، فإن T(n) = Θ(n^log_b(a)).
2. إذا كان f(n) = Θ(n^log_b(a))، فإن T(n) = Θ(n^log_b(a) * log n).
3. إذا كان f(n) = Ω(n^(log_b(a) + ε)) لبعض الثابت ε > 0، وإذا كان af(n/b) ≤ cf(n) لبعض الثابت c < 1 وجميع n الكافية، فإن T(n) = Θ(f(n)).

بالنسبة لخوارزمية الفرز بالدمج، لدينا a = 2 (مكالمتان متكررتان)، b = 2 (كل مشكلة فرعية نصف الحجم)، و f(n) = Θ(n) (خطوة الدمج تستغرق وقتًا خطيًا). بما أن log_2(2) = 1، فنحن في الحالة 2 من نظرية السيد، وزمن التشغيل هو Θ(n log n).

خوارزميات التقسيم والاستيلاء الأخرى

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

الخوارزميات باستخدام نموذج "قسم وانتصر"

يمكن تصميم الخوارزميات باستخدام نموذج "قسم وانتصر". بعض الأمثلة البارزة تشمل:

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

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

• ضرب كاراتسوبا: هذه هي خوارزمية "قسم وانتصر" لضرب رقمين ذوي n رقم في O(n^log_2(3)) ≈ O(n^1.585) وقت، وهو أسرع من الخوارزمية التقليدية O(n^2).

• ضرب مصفوفات ستراسن: تضرب خوارزمية ستراسن مصفوفتين n × n في O(n^log_2(7)) ≈ O(n^2.807) وقت، مما يحسن من الخوارزمية البسيطة O(n^3).

توضح هذه الأمثلة مرونة وقوة نموذج "قسم وانتصر" في تصميم خوارزميات فعالة.

الخوارزميات الجشعة

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

السمات الرئيسية للخوارزميات الجشعة هي:

1. إنها تتخذ خيارًا أمثل محليًا في كل خطوة، دون القلق بشأن العواقب المستقبلية.
2. إنها تفترض أن الخيار الأمثل محليًا سيؤدي إلى حل أمثل عالميًا.
3. إنها لا تعيد النظر في الخيارات السابقة.

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

ترميز هافمان: خوارزمية جشعة لضغط البيانات

ترميز هافمانهذا هو الترجمة العربية للملف:

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

فيما يلي وصف عام لخوارزمية ترميز هوفمان:

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

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

فيما يلي مثال على ترميز هوفمان في العمل:

لنفترض أننا لدينا تردد الأحرف التالي:

d: 1
e: 1

فيما يلي شجرة هوفمان لهذا المثال:

      (15)
     /    \
   (7)    (8)
   / \    / \
 (4) (3) (3) (5)
 /\  /\  /\  /\
A B  C D E

رموز هوفمان الناتجة هي:

A: 00
B: 01
C: 10
D: 110
E: 111

لذلك ستكون السلسلة الأصلية "AAAABBBCCCDDDEEE" مرمزة كما يلي:

00000000010101101010110110110111111111

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

ضغط LZW

ضغط Lempel-Ziv-Welch (LZW) هو خوارزمية ضغط قائمة على القاموس تبني قاموسًا (أو كتاب رموز) من السلاسل أثناء ضغط المدخل. يُستخدم LZW على نطاق واسع في أدوات ضغط الملفات وتم استخدامه في تنسيق صور GIF.

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

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

فيما يلي وصف خطوة بخطوة لكيفية عمل ضغط LZW:

1. قم بتهيئة القاموس ليحتوي على جميع السلاسل ذات الحرف الواحد.
2. ابحث عن أطول سلسلة W في القاموس التي تطابق الإدخال الحالي.
3. أرسل فهرس القاموس لـ W إلى الإخراج وأزله من الإدخال.
4. أضف W متبوعًا بالرمز التالي في الإدخال إلى القاموس.
5. انتقل إلى الخطوة 2.

لنأخذ مثالاً. لنفترض أننا نريد ضغط السلسلة "ABABABABA" باستخدام LZW.

1. قم بتهيئة القاموس ليحتوي على "A" و "B".
2. أطول تطابق هو "A". أرسل فهرسه (0) وأزله من الإدخال. الآن يحتوي القاموس على "A"، "B"، و "AB".
3. أطول تطابق هو "B". أرسل فهرسه (1) وأزله من الإدخال. الآن يحتوي القاموس على "A"، "B"، "AB"، و "BA".
4. أطول تطابق هو "AB". أرسل فهرسه (2) وأزله من الإدخال. الآن يحتوي القاموس على "A"، "B"، "AB"، "BA"، و "ABA".
5. أطول تطابق هو "ABA". أرسل فهرسه (4) وأزله من الإدخال. الآن يحتوي القاموس على "A"، "B"، "AB"، "BA"، "ABA"، و "ABAB".
6. أطول تطابق هو "BA". أرسل فهرسه (3). الإدخال الآن فارغ.

التمثيل المضغوط لـ "ABABABABA" هو تسلسل الفهارس [1]، والذي يتطلب عددًا أقل من البتات لتمثيله مقارنة بالتمثيل ASCII الأصلي.

يعمل فك الضغط بطريقة مماثلة، ولكن بالعكس:

1. قم بتهيئة القاموس ليحتوي على جميع السلاسل ذات الحرف الواحد.
2. اقرأ رمزًا X من الإدخال.
3. أخرج السلسلة لـ X من القاموس.
4. إذا كان الرمز السابق موجودًا، أضف السلسلة السابقة مع الحرف الأول من السلسلة لـ X إلى القاموس.
5. انتقل إلى الخطوة 2.

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

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

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

الخاتمة

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

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

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

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

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

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

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

العمل مع البيانات النصية

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

# هذا هو تعليق باللغة العربية
# يقوم هذا الكود بتنفيذ عملية معينة
def example_function(input_string):
    # هذا هو تعليق آخر باللغة العربية
    # يقوم هذا الكود بتنفيذ عملية أخرى
    processed_string = input_string.upper()
    return processed_string