مرجع
آخر الزيارات

خوارزمية فرق تسد

520 كلمة•0 مشاهدة•🗒️ منذ 10 أيام
باختصار: في علم الحاسوب، خوارزمية فرق تسد هي بارادايم تصميم خوارزميات مهم مبني على استدعاء ذاتي متعدد الفروع. في هذه المقالة 6 أقسام: «حل مسائل صعبة»، «الوصول للذاكرة» و«كفاءة الخوارزمية» وغيرها.
المحتويات
  1. حل مسائل صعبة
  2. الوصول للذاكرة
  3. كفاءة الخوارزمية
  4. حوسبة متوازية
  5. التحكم في التقريب
  6. أمثلة تاريخية مبكرة
خوارزمية فرق تسد

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

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

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

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

حل مسائل صعبة

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

الوصول للذاكرة

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

كفاءة الخوارزمية

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

من جهة ثانية، في كل الأمثلة، أدى نهج فرق تسد إلى تطوير تكلفة الحل. مثلا، إذا كان لحالات الأساس حجم ثابت محدود، تقسيم المسألة ودمج الحلول الجزئية هو نسبي لحجم المسألة n، وهنالك عدد محدود من المسائل الجزئية p بحجم ~ n/p في كل مرحلة، ولذلك تكلفة خوارزمية فرق تسد تكون (O(n log n.

حوسبة متوازية

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

التحكم في التقريب

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

  • انظر كذلك
  • استقراء رياضي
  • خوارزمية بحث ثنائي
  • ترتيب دمجي
  • ترتيب سريع

أمثلة تاريخية مبكرة

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

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

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

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

ايجابيات

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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