خوارزمية

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

This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style. (April 2024) (Learn how and when to remove this message)

في الرياضيات وعلوم الكمبيوتر ، الخوارزمية ( / ˈælɡərɪðəm /​​​​​​​​ ^ⓘ ) عبارة عن تسلسل محدود منالدقيقة رياضيًا، تُستخدم عادةً لحل فئة منالمشكلاتأو لإجراءعملية حسابية.^[1]تُستخدم الخوارزميات كمواصفات لإجراءالعمليات الحسابيةومعالجةالبيانات. يمكن للخوارزميات الأكثر تقدمًا استخدامالشرطياتلتحويل تنفيذ التعليمات البرمجية عبر طرق مختلفة (يشار إليها باسماتخاذ القرار الآلي) واستنتاجاستنتاجات(يشار إليها باسمالاستدلال الآلي).

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

كطريقة فعّالة ، يمكن التعبير عن الخوارزمية ضمن مقدار محدود من المساحة والوقت ^[3] وفي لغة شكلية محددة جيدًا ^[4] لحساب دالة . ^[5] بدءًا من حالة أولية وإدخال أولي (ربما فارغ )، ^[6] تصف التعليمات عملية حسابية، عند تنفيذها ، تمر عبر عدد محدود ^[7] من الحالات المتعاقبة المحددة جيدًا، وتنتج في النهاية "إخراجًا" ^[8] وتنتهي في حالة نهاية نهائية. الانتقال من حالة إلى أخرى ليس بالضرورة حتميًا ؛ بعض الخوارزميات، المعروفة باسم الخوارزميات العشوائية ، تتضمن إدخالًا عشوائيًا. ^[9]

حوالي عام 825 م، كتب العالم الفارسي والموسوعي محمد بن موسى الخوارزمي كتاب الحساب الهندي وكتاب الجمع والطرح في الحساب الهندي . [ 1 ^] في أوائل القرن الثاني عشر، ظهرت ترجمات لاتينية لنصوص الخوارزمي المذكورة التي تتضمن نظام الأرقام الهندوسية العربية والحساب ، على سبيل المثال Liber Alghoarismi de practica arismetrice ، المنسوب إلى جون الإشبيلية ، و Liber Algorismi de numero Indorum ، المنسوب إلى أديلارد من باث . ^[10] وبالتالي، فإن alghoarismi أو algorismi هو لاتينية اسم الخوارزمي؛ يبدأ النص بعبارة Dixit Algorismi ، أو "هكذا تكلم الخوارزمي". ^[2] حوالي عام 1230، تم إثبات الكلمة الإنجليزية algorism ثم في عام 1391، تبنى الإنجليز المصطلح الفرنسي بواسطة تشوسر . ^{[3] [4] [ يحتاج إلى توضيح ]} في القرن الخامس عشر، وتحت تأثير الكلمة اليونانية ἀριθμός ( arithmos ، "عدد"؛ قارن "الحساب")، تم تغيير الكلمة اللاتينية إلى algorithmus . ^{[ بحاجة لمصدر ]}

أحد التعريفات غير الرسمية هو "مجموعة من القواعد التي تحدد بدقة تسلسل العمليات"، ^{[11] [ تحتاج إلى اقتباس للتحقق ]} والتي تشمل جميع برامج الكمبيوتر (بما في ذلك البرامج التي لا تقوم بإجراء حسابات رقمية)، وأي إجراء بيروقراطي محدد ^[12] أو وصفة كتاب طبخ . ^[13] بشكل عام، يكون البرنامج خوارزمية فقط إذا توقف في النهاية ^[14] - على الرغم من أن الحلقات اللانهائية قد تكون مرغوبة في بعض الأحيان. Boolos، Jeffrey & 1974، 1999 يعرّف الخوارزمية بأنها مجموعة صريحة من التعليمات لتحديد الناتج، والتي يمكن أن تتبعها آلة حاسوبية أو إنسان يمكنه فقط تنفيذ عمليات أولية محددة على الرموز . ^[15]

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

This section is missing information about 20th and 21st century development of computer algorithms. Please expand the section to include this information. Further details may exist on the talk page. (October 2023)

تم تسجيل إجراءات خطوة بخطوة لحل المشكلات الرياضية منذ العصور القديمة. ويشمل ذلك في الرياضيات البابلية (حوالي 2500 قبل الميلاد)، ^[16] والرياضيات المصرية (حوالي 1550 قبل الميلاد)، ^[16] والرياضيات الهندية (حوالي 800 قبل الميلاد وما بعده)، ^{[17] [18]} وعرافة إيفا (حوالي 500 قبل الميلاد)، ^[19] والرياضيات اليونانية (حوالي 240 قبل الميلاد)، ^[20] والرياضيات العربية (حوالي 800 بعد الميلاد). ^[21]

أقدم دليل على الخوارزميات موجود في الرياضيات في بلاد ما بين النهرين القديمة. يصف لوح طيني سومري عُثر عليه في شوروباك بالقرب من بغداد ويرجع تاريخه إلى حوالي  2500 قبل الميلاد أقدم خوارزمية للقسمة . ^[16] خلال عهد سلالة حمورابي حوالي  1800  - حوالي  1600 قبل الميلاد ، وصفت الألواح الطينية البابلية خوارزميات لحساب الصيغ. ^[22] كما استُخدمت الخوارزميات في علم الفلك البابلي . تصف الألواح الطينية البابلية وتستخدم إجراءات خوارزمية لحساب وقت ومكان الأحداث الفلكية المهمة. ^[23]

توجد أيضًا خوارزميات الحساب في الرياضيات المصرية القديمة ، ويعود تاريخها إلى بردية ريند الرياضية التي يعود تاريخها إلى حوالي  عام 1550 قبل الميلاد . ^[16] واستُخدمت الخوارزميات لاحقًا في الرياضيات الهلنستية القديمة . ومن الأمثلة على ذلك غربال إراتوستينس، الذي وُصف في مقدمة الحساب لنيقوماخوس ، [ 24 ] [ 20 ] ^{: الفصل 9.2} والخوارزمية الإقليدية ، التي وُصفت لأول مرة في عناصر إقليدس ( حوالي  300 قبل الميلاد ). ^{[20] : الفصل 9.1} وشملت أمثلة الرياضيات الهندية القديمة شولبا سوترا ومدرسة كيرالا وبراهماسفوتاسيدانتا . ^[17]

تم تطوير أول خوارزمية تشفير لفك رموز الشفرات المشفرة بواسطة الكندي ، وهو عالم رياضيات عربي من القرن التاسع، في مخطوطة فك رموز الرسائل المشفرة . وقد قدم أول وصف لتحليل الشفرات عن طريق تحليل التردد ، وهي أقدم خوارزمية لفك الشفرات. ^[21]

يعزو بولتر اختراع الساعة التي تعمل بالوزن إلى "الاختراع الرئيسي [ لأوروبا في العصور الوسطى ]"، وتحديدًا آلية الإفلات الحافة ^[25] التي تنتج دقات الساعة الميكانيكية. أدت "الآلة الأوتوماتيكية الدقيقة" ^{[26] على الفور إلى "} الأتمتة الميكانيكية " في القرن الثالث عشر و"الآلات الحسابية" - محركات الفرق والتحليل الخاصة بتشارلز باباج وأدا لوفليس في منتصف القرن التاسع عشر. ^[27] صمم لوفليس أول خوارزمية مخصصة للمعالجة على جهاز كمبيوتر، محرك باباج التحليلي، وهو أول جهاز يُعتبر كمبيوترًا كاملاً حقيقيًا لتورنج بدلاً من مجرد آلة حاسبة . وعلى الرغم من عدم تحقيق التنفيذ الكامل لجهاز باباج الثاني لعقود من الزمان بعد حياتها، فقد أُطلق على لوفليس لقب "أول مبرمجة في التاريخ".

كتب بيل ونيويل (1971) أن نول جاكار ، وهو سلف بطاقات هوليريث (البطاقات المثقبة)، و"تقنيات تبديل الهاتف" أدت إلى تطوير أول أجهزة الكمبيوتر. ^[28] وبحلول منتصف القرن التاسع عشر، كان التلغراف ، سلف الهاتف، قيد الاستخدام في جميع أنحاء العالم. وبحلول أواخر القرن التاسع عشر، كان شريط التيكر ( حوالي  سبعينيات القرن التاسع عشر ) قيد الاستخدام، وكذلك بطاقات هوليريث (حوالي عام 1890). ثم جاءت الطابعة عن بعد ( حوالي عام  1910 ) باستخدام ورق مثقب لرمز بودو على الشريط.

تم اختراع شبكات التبديل الهاتفي التي تعتمد على مرحلات كهروميكانيكية في عام 1835. وقد أدى هذا إلى اختراع جهاز الجمع الرقمي بواسطة جورج ستيبيتز في عام 1937. أثناء عمله في مختبرات بيل، لاحظ الاستخدام "المرهق" للآلات الحاسبة الميكانيكية ذات التروس. "عاد إلى منزله ذات مساء في عام 1937 عازمًا على اختبار فكرته... وعندما انتهى من العبث، كان ستيبيتز قد أنشأ جهاز جمع ثنائي". ^{[29] [30]}

في عام 1928، بدأ إضفاء طابع رسمي جزئي على المفهوم الحديث للخوارزميات بمحاولات لحل مشكلة القرار التي طرحها ديفيد هيلبرت . وتم صياغة التشكيلات الرسمية اللاحقة على أنها محاولات لتعريف " القدرة الحسابية الفعالة " ^[31] أو "الطريقة الفعالة". ^[32] وتضمنت هذه التشكيلات الرسمية الدوال المتكررة لغودل - هيربراند - كلين في أعوام 1930 و1934 و1935، وحساب لامدا لألونزو تشرش في عام 1936، وصيغة إميل بوست 1 في عام 1936، وآلات تورينج لألان تورينج في أعوام 1936-1937 و1939.

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

هناك العديد من التمثيلات الممكنة ويمكن التعبير عن برامج آلة تورينج كتسلسل من جداول الآلة (انظر آلة الحالة المحدودة وجدول انتقال الحالة وجدول التحكم لمزيد من المعلومات)، ومخططات انسيابية ومخططات دراكون (انظر مخطط الحالة لمزيد من المعلومات)، كشكل من أشكال التعليمات البرمجية الآلية الأولية أو تعليمات التجميع المسماة "مجموعات الرباعيات"، والمزيد. يمكن أيضًا تصنيف تمثيلات الخوارزمية إلى ثلاثة مستويات مقبولة لوصف آلة تورينج: الوصف عالي المستوى ووصف التنفيذ والوصف الرسمي. ^[33] يصف الوصف عالي المستوى صفات الخوارزمية نفسها، متجاهلاً كيفية تنفيذها على آلة تورينج. ^[33] يصف وصف التنفيذ الطريقة العامة التي تحرك بها الآلة رأسها وتخزن البيانات من أجل تنفيذ الخوارزمية، لكنها لا تعطي حالات دقيقة. ^[33] بأكبر قدر من التفصيل، يعطي الوصف الرسمي جدول الحالة الدقيق وقائمة انتقالات آلة تورينج. ^[33]

تقدم الأداة الرسومية المسماة مخطط التدفق طريقة لوصف وتوثيق خوارزمية (وبرنامج كمبيوتر يتوافق معها). وهي تحتوي على أربعة رموز أساسية: الأسهم التي توضح تدفق البرنامج، والمستطيلات (SEQUENCE، GOTO)، والمعينات (IF-THEN-ELSE)، والنقاط (OR-tie). يمكن أن "تتداخل" الهياكل الفرعية في المستطيلات، ولكن فقط إذا حدث خروج واحد من الهيكل العلوي.

غالبًا ما يكون من المهم معرفة مقدار الوقت أو التخزين أو التكلفة الأخرى التي قد تتطلبها الخوارزمية. تم تطوير طرق لتحليل الخوارزميات للحصول على مثل هذه الإجابات الكمية (التقديرات)؛ على سبيل المثال، فإن الخوارزمية التي تجمع عناصر قائمة من n رقم سيكون لها متطلب زمني قدره ⁠ ⁠${\displaystyle O(n)}$ ، باستخدام تدوين O الكبير . تحتاج الخوارزمية فقط إلى تذكر قيمتين: مجموع جميع العناصر حتى الآن وموضعها الحالي في قائمة الإدخال. إذا لم يتم احتساب المساحة المطلوبة لتخزين أرقام الإدخال، فسيكون لها متطلب مساحة قدره ⁠ ⁠${\displaystyle O(1)}$ ، وإلا فستكون ⁠ ⁠${\displaystyle O(n)}$ مطلوبة.

قد تنجز خوارزميات مختلفة نفس المهمة بمجموعة مختلفة من التعليمات في وقت أو مساحة أو " جهد " أقل أو أكثر من غيرها. على سبيل المثال، تتفوق خوارزمية البحث الثنائي (بتكلفة ) على البحث المتسلسل (تكلفة ) عند استخدامها للبحث في الجداول في القوائم أو المصفوفات المرتبة. ${\displaystyle O(\log n)}$${\displaystyle O(n)}$

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

يُعد الاختبار التجريبي مفيدًا في الكشف عن التفاعلات غير المتوقعة التي تؤثر على الأداء. ويمكن استخدام معايير المقارنة لمقارنة التحسينات المحتملة قبل/بعد الخوارزمية بعد تحسين البرنامج. ومع ذلك، لا يمكن للاختبارات التجريبية أن تحل محل التحليل الرسمي، كما أنها ليست سهلة الأداء بشكل عادل. ^[34]

لتوضيح التحسينات المحتملة الممكنة حتى في الخوارزميات الراسخة، يمكن لابتكار مهم حديث يتعلق بخوارزميات تحويل فورييه السريع (المستخدمة بكثافة في مجال معالجة الصور) أن يقلل من وقت المعالجة حتى 1000 مرة لتطبيقات مثل التصوير الطبي. ^[35] بشكل عام، تعتمد تحسينات السرعة على خصائص خاصة للمشكلة، وهي شائعة جدًا في التطبيقات العملية. ^[36] تمكن عمليات التسريع بهذا الحجم أجهزة الحوسبة التي تستخدم معالجة الصور على نطاق واسع (مثل الكاميرات الرقمية والمعدات الطبية) من استهلاك طاقة أقل.

تصميم الخوارزمية هو طريقة أو عملية رياضية لحل المشكلات وهندسة الخوارزميات. يعد تصميم الخوارزميات جزءًا من العديد من نظريات الحل، مثل فرق تسد أو البرمجة الديناميكية ضمن بحوث العمليات . تُسمى أيضًا تقنيات تصميم وتنفيذ تصاميم الخوارزمية بأنماط تصميم الخوارزمية، ^[37] مع أمثلة تشمل نمط طريقة القالب ونمط الديكور. أحد أهم جوانب تصميم الخوارزمية هو كفاءة الموارد (وقت التشغيل واستخدام الذاكرة)؛ يتم استخدام تدوين O الكبير لوصف، على سبيل المثال، نمو وقت تشغيل الخوارزمية مع زيادة حجم مدخلاتها. ^[38]

وفقًا لأطروحة تشيرش-تورنج ، يمكن حساب أي خوارزمية بواسطة أي نموذج تورنج كامل . يتطلب اكتمال تورنج أربعة أنواع فقط من التعليمات - GOTO الشرطية، GOTO غير الشرطية، التعيين، HALT. ومع ذلك، لاحظ كيميني وكورتز أنه في حين أن الاستخدام "غير المنضبط" لـ GOTOs غير الشرطية و IF-THEN GOTOs الشرطية يمكن أن يؤدي إلى " كود سباغيتي "، يمكن للمبرمج كتابة برامج منظمة باستخدام هذه التعليمات فقط؛ من ناحية أخرى "من الممكن أيضًا، وليس من الصعب جدًا، كتابة برامج سيئة البنية في لغة منظمة". ^[39] يكمل تاوسورث الهياكل الثلاثة القياسية لـ بوم-جاكوبيني : ^[40] SEQUENCE، IF-THEN-ELSE، و WHILE-DO، مع اثنين آخرين: DO-WHILE و CASE. ^[41] ميزة إضافية للبرنامج المنظم هي أنه يلائم إثباتات الصحة باستخدام الاستدلال الرياضي . ^[42]

في حد ذاتها، لا تكون الخوارزميات عادةً قابلة للحصول على براءة اختراع. في الولايات المتحدة، لا يشكل الادعاء الذي يتكون فقط من معالجات بسيطة للمفاهيم المجردة أو الأرقام أو الإشارات "عمليات" (USPTO 2006)، وبالتالي فإن الخوارزميات ليست قابلة للحصول على براءة اختراع (كما في قضية Gottschalk v. Benson ). ومع ذلك، فإن التطبيقات العملية للخوارزميات تكون قابلة للحصول على براءة اختراع في بعض الأحيان. على سبيل المثال، في قضية Diamond v. Diehr ، اعتُبر تطبيق خوارزمية ردود الفعل البسيطة للمساعدة في معالجة المطاط الصناعي قابلاً للحصول على براءة اختراع. إن براءات الاختراع للبرمجيات مثيرة للجدل، ^[43] وهناك انتقادات لبراءات الاختراع التي تنطوي على خوارزميات، وخاصة خوارزميات ضغط البيانات ، مثل براءة اختراع LZW لشركة Unisys . بالإضافة إلى ذلك، فإن بعض خوارزميات التشفير لها قيود تصدير (انظر تصدير التشفير ).

التكرار

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

متسلسل أو متوازي أو موزع

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

حتمية أو غير حتمية

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

دقيق أو تقريبي

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

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

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

هناك طريقة أخرى لتصنيف الخوارزميات وهي من خلال منهجية التصميم أو النموذج . ومن بين النماذج الشائعة:

البحث بالقوة الغاشمة أو البحث الشامل

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

فرق تسد

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

البحث والحصر

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

خوارزمية عشوائية

تتخذ مثل هذه الخوارزميات بعض الخيارات عشوائيًا (أو بشكل شبه عشوائي). وتجد حلولًا تقريبية عندما يكون إيجاد الحلول الدقيقة غير عملي (انظر الطريقة الاستدلالية أدناه). بالنسبة لبعض المشكلات، يجب أن تنطوي أسرع التقريبات على بعض العشوائية . ^[45] ما إذا كانت الخوارزميات العشوائية ذات التعقيد الزمني متعدد الحدود يمكن أن تكون أسرع خوارزمية لبعض المشكلات هو سؤال مفتوح يُعرف باسم مشكلة P مقابل NP . هناك فئتان كبيرتان من هذه الخوارزميات:

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

تقليل التعقيد

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

التتبع الخلفي

في هذا النهج، يتم بناء حلول متعددة بشكل تدريجي ويتم التخلي عنها عندما يتم تحديد أنها لا يمكن أن تؤدي إلى حل كامل صالح.

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

البرمجة الخطية

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

البرمجة الديناميكية

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

الطريقة الجشعة

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

الطريقة الاستدلالية

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

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

الوصف رفيع المستوى:

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

الوصف (شبه) الرسمي: مكتوب بالنثر ولكنه أقرب كثيرًا إلى لغة المستوى العالي لبرنامج الكمبيوتر، فيما يلي الترميز الأكثر رسمية للخوارزمية في الكود الزائف أو الكود العام :

خوارزمية أكبر عدد
الإدخال: قائمة بالأرقام L .
الإخراج: أكبر رقم في القائمة L .

إذا كان  L.size = 0 ، قم بإرجاع null
 larger ← L [0]
 لكل  عنصر  في  L ، فافعل ذلك 
    إذا كان  العنصر > larger ، ثم 
        larger ← item 
قم بإرجاع  larger

• زاسلافسكي، سي. (1970). رياضيات شعب اليوروبا وجيرانهم في جنوب نيجيريا. مجلة الرياضيات الجامعية لمدة عامين، 1(2)، 76-99. https://doi.org/10.2307/3027363

ابحث عن خوارزمية في ويكاموس، القاموس الحر.

يحتوي موقع ويكيبيديا على كتاب حول موضوع: الخوارزميات

في ويكي الجامعة ، يمكنك تعلم المزيد وتعليم الآخرين عن الخوارزمية في قسم الخوارزمية

تحتوي ويكيميديا ​​كومنز على وسائط متعلقة بـ الخوارزميات .

• "الخوارزمية". موسوعة الرياضيات . EMS Press . 2001 [1994].
• وايسشتاين، إريك دبليو. "الخوارزمية". MathWorld .
• قاموس الخوارزميات وهياكل البيانات – المعهد الوطني للمعايير والتكنولوجيا

مستودعات الخوارزميات

• مستودع خوارزميات ستوني بروك – جامعة ولاية نيويورك في ستوني بروك
• مجموعة من الخوارزميات الخاصة بجمعية ACM – جمعيات آلات الحوسبة
• تم أرشفة Stanford GraphBase في 6 ديسمبر 2015، على موقع Wayback Machine – جامعة ستانفورد

Original text

Rate this translation

Your feedback will be used to help improve Google Translate