خوارزمية ، إجراء منهجي ينتج - في عدد محدود من الخطوات - إجابة سؤال أو حل مشكلة. يُشتق الاسم من الترجمة اللاتينية ، Algoritmi de numero Indorum ، من رسالة الحساب الرياضي الإسلامية الخوارزمي في القرن التاسع "الخوارزمي بخصوص الفن الهندوسي للحساب."
علوم الكمبيوتر: الخوارزميات والتعقيد
الخوارزمية هي إجراء محدد لحل مشكلة حسابية محددة جيدًا. تطوير وتحليل الخوارزميات أمر أساسي
بالنسبة للأسئلة أو المشكلات المتعلقة بمجموعة محدودة من الحالات أو القيم ، توجد دائمًا خوارزمية (على الأقل من حيث المبدأ) ؛ يتكون من جدول قيم الإجابات. بشكل عام ، ليس من مثل هذا الإجراء التافه الإجابة على الأسئلة أو المشكلات التي لها عدد لا حصر له من الحالات أو القيم التي يجب مراعاتها ، مثل "هل الرقم الطبيعي (1 ، 2 ، 3 ،..). أولي؟" أو "ما هو أكبر القاسم المشترك بين الأعداد الطبيعية أ و ب؟" الأول من هذه الأسئلة ينتمي إلى فئة تسمى decidable؛ الخوارزمية التي تنتج إجابة بنعم أو لا تسمى إجراء اتخاذ القرار. السؤال الثاني ينتمي إلى فئة تسمى محسوبة. تسمى الخوارزمية التي تؤدي إلى إجابة رقم معين إجراء حساب.
توجد خوارزميات للعديد من فئات الأسئلة اللانهائية. تحتوي عناصر إقليدس ، المنشورة حوالي 300 قبل الميلاد ، على واحد للعثور على أكبر قاسم مشترك بين رقمين طبيعيين. يتم حفر كل طالب في مدرسة ابتدائية بتقسيم طويل ، وهو خوارزمية للسؤال "عند قسمة رقم طبيعي أ على رقم طبيعي آخر ب ، ما هو القسمة والباقي؟" يؤدي استخدام هذا الإجراء الحسابي إلى إجابة السؤال المحدد "هل يقسم b؟" (الجواب نعم إذا كان الباقي صفر). يؤدي التطبيق المتكرر لهذه الخوارزميات في النهاية إلى الإجابة على السؤال الذي يمكن تحديده "هل أساسي؟" (الجواب لا إذا كان العدد قابلاً للقسمة على أي رقم طبيعي أصغر بجانب 1).
في بعض الأحيان لا يمكن أن توجد خوارزمية لحل فئة لا حصر لها من المشاكل ، خاصة عندما يتم إجراء المزيد من القيود على الطريقة المقبولة. على سبيل المثال ، تمت متابعة مشكلتين من وقت إقليدس تتطلب استخدام بوصلة فقط وحافة مستقيمة (مسطرة غير مميزة) - تقطير زاوية وإنشاء مربع بمساحة تساوي دائرة معينة - لقرون قبل أن يثبت أنه مستحيل. في مطلع القرن العشرين ، اقترح عالم الرياضيات الألماني المؤثر ديفيد هيلبرت 23 مشكلة للرياضيين لحلها في القرن المقبل. طلبت المشكلة الثانية في قائمته تحقيقًا في اتساق البديهيات الحسابية. لم يكن لدى معظم علماء الرياضيات شك كبير في تحقيق هذا الهدف في نهاية المطاف حتى عام 1931 ، عندما أظهر المنطق النمساوي المولد كيرت جودل النتيجة المدهشة بأنه يجب أن تكون هناك مقترحات حسابية (أو أسئلة) لا يمكن إثباتها أو دحضها. بشكل أساسي ، يؤدي أي اقتراح من هذا القبيل إلى إجراء تحديد لا ينتهي أبدًا (حالة تعرف باسم مشكلة التوقف). في محاولة فاشلة للتأكد على الأقل من المقترحات التي لا يمكن حلها ، قام عالم الرياضيات الإنجليزي والباحث آلان تورينج بتعريف المفهوم الخوارزمي المفهوم بشكل فضفاض. على الرغم من أن Turing قد انتهى إلى إثبات أنه يجب أن تكون هناك مقترحات غير قابلة للتحديد ، فإن وصفه للميزات الأساسية لأي آلة خوارزمية للأغراض العامة ، أو آلة Turing ، أصبح أساس علوم الكمبيوتر. واليوم تعتبر قضايا قابلية الفصل والحوسبة أساسية لتصميم برنامج الكمبيوتر - وهو نوع خاص من الخوارزميات.
