مستخدم:Rashaibrahim/خوارزمية

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


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


جزء من إضفاء الطابع الرسمي على هذا المفهوم بدأت مع محاولات حل Entscheidungsproblem ( "مشكلة القرار" التي طرحها ديفيد هيلبرت في عام 1928. بعد ذلك تم في إطار اضفاء الطابع الرسمي محاولات تحديد "الإحصائية الفعالة" ( كلين 1943:274) أو "الطريقة الفعالة" (روسر 1939:225) ؛ وشملت هذه التشكيلات الأعمال المتكررة لجودل- هربراند- كليين في اعوام 1930 ، 1934 و 1935 ، وكنيسة الونزو معامل لامبدا في التفاضل والتكامل لعام 1936 ، اميل بوست "صياغة 1" لسنة 1936 ، وآلان تورينج / آلات تورنج لل1936-7 و1939.


أصل الكلمة

الخوارزمي عالم فلك ورياضيات فارسي ، وكتب مقالة في 825 ميلادي ، عن الحساب مع الأرقام العربية. (انظر نظام العد العربي). ترجمت الي اللاتينية في القرن 12th بعنوان "Algoritmi de numero Indorum " (الدااف 1977) ، التي من المرجح أن القصد من العنوان يعني "Algoritmi عن أعداد الهنود" ، حيث "Algoritmi" كان المترجم تسليم اسم المؤلف ولكن سوء فهم الناس عنوان Algoritmi يعامل بوصفه اللاتينية بصيغة الجمع ، وهذا أدى إلى كلمة "خوارزمية" (اللاتينية algorismus) المقبل يعني "طريقة حساب". التدخلي "ال" على الأرجح بسبب وجود كاذبة المشابهة مع اليونانية ἀριθμός (arithmos) تعني "عددا".


لماذا الخوارزميات ضرورية : تعريف غير رسمي

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

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


مثال نموذجي لـ "الخوارزمية" خوارزمية إقليديس لتحديد الحد الأقصى للقاسم المشترك لاثنين من الأعداد الصحيحة (سين وصاد) التي هي أكبر من واحد :نتبع مجموعة من الخطوات : في الخطوة i ، نقسم س ص ونوجد البقية التي نسميها آر 1. ثم ننتقل إلى خطوة i+ 1 يتم تقسيم ص علي آر 1 ، ونوجد المتبقى ، والتي نسميها آر 2. إذا آر 2 = 0 ، نتوقف ونقول إن آر 1 هو أكبر قاسم مشترك ل س و صي وإذا لم يكن ، نكمل حتى ر ن. = 0س ن -1 هو أكبر قاسم مشترك ل س و صي . وهذا الإجراءلابد ان يتوقف دائما والعدد المطروح دائما أصغر من أكبر الرقمين.


يمكننا استخلاص دلائل على القضايا المننطوي عليها ، والمعني الغير رسمي للكلمة من الاقتباس التالي Boolos & Jeffrey (1974, 1999) (أضيفت حروف بارزة) :


فلا يمكن لأي إنسان أن يكتب بسرعة كافية أو طويلة بما فيه الكفاية أو صغيرة بما يكفي لجميع أعضاء قائمة من مجموعة احصائيا لا حصر لها من خلال كتابة أسمائهم ، واحدا تلو الآخر ، في التدوين. ولكن يمكن للانسان ان يفعل شيئا مفيدا أيضا ، في حالة بعض المجموعات احصائيا لا حصر لها : ويمكن أن تعطي تعليمات صريحة لتحديد أقصى عضو من المجموعة (ن) للالتعسفي المحدودة هذه التعليمات التي يجب أن تمنح صراحة ، في الشكل الذي يمكن أن يتبعه جهاز الكمبيوتر ، أو من قبل الذين البشرية قادرة على تنفيذ عمليات بسيطة جدا فقط على الرموز (Boolos, Jeffrey & 1974, 1999, p. 19)


عبارة "الإحصاء اللانهائي" وتعني "ربما تمتد الأعداد الصحيحة القابلة للعد إلى ما لا نهاية". ولهذايقول بولوس وجيفري أن الخوارزمية تنطوي على تعليمات "لخلق" أعداد صحيحة من مدخلات اعداد صحيحة اعتبارية ، من الناحية النظرية ، يمكن إختياره من 0 إلى ما لا نهاية. ولهذا نتوقعأن تكون الخوارزمية معادلة جبرية مثل م + ن = واي --م - ن وهما " مدخلات اعتبارية متغيرة "والتي تنتج واي كما نرى في خواص الخوارزمية-- كلمة خوارزمية تعني أكثر من ذلك بكثير ، (على سبيل المثال الإضافي) :

التعليمات الدقيقة (في لغة يفهمها "الكمبيوتر" للعملية "سريعة وفعالة وجيدة" التي تحدد "تحركات" "الكمبيوتر" (آلة أو انسان مجهزة داخليابالمعلومات والإمكانات الضرورية) للعثور ,وفك رموز ، ثم التعامل مع مدخلات الاعداد الصحيحية الإعتبارية\الرموز ن م والرموز = +... (موثوق بها ، على الوجه الصحيح "، على نحو فعال")تنتج , في وقت معقول، العدد الصحيح -واي- في مكان محدد وشكل معين.


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


إضفاء الطابع الرسمي

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


...حجج تورينج غير الرسمية المؤيدة لاطروحته تبرر أقوى أطروحة : يمكن محاكاة كل خوارزمية بواسطة آلة تورينج ( جورفيتش 2000:1)... وفقا لسافاج [1987] ، الخوارزمية هي عملية كمبيوترية محددة من قبل آلة تورينج. ( جورفيتش 2000:3)


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


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


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


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


لبعض المفاهيم البديلة لما يشكل خوارزمية انظر البرمجة الوظيفية والبرمجة المنطقية.


الخاتمة

حصر بعض الكتاب تعريف الخوارزمية علي الاجراءات التي تنتهى .في هذه الفئة , وضع كليين "إجراء القرار أو طريقة القرار أو خوارزمية للمسألة" ( كليين 1952:136). والآخرين ، بما فيهم كليين ، وضعوا إجراءات يمكن أن تدار الي مالانهاية دون توقف ؛ إجراء مثل هذا تم وصفه بـ "الطريقة الحسابية" (نث 1997:5) أو الإجراء الحسابي أو الخوارزمي" (كليين 1952:137) ، ومع ذلك ، لاحظ كليين أن مثل هذا الأسلوب يجب أن يظهر هدفا في نهاية المطاف (كليين 1952:137).


جعل مينسكاي المراقبة ذات الصلة ، فيما يتعلق بتحديد ما إذا كانت الخوارزمية ستنتهي في نهاية المطاف (من نقطة بداية محددة) :

ولكن إذا كان طول هذه العملية ليست معروفة مسبقا ، فان "المحاولة" قد لا تكون حاسمة ، لأنه إذا كانت العملية لن تستمر إلى الأبد -- فلهذا في اقل وقت سوف نكون على ثقة من الإجابة( مينسكاي 1967:105) .


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


انظر لأمثلة (im -) الطرح "المناسب" في المهمة الجزئية للمزيد من المعلومات حول ما يمكن أن يحدث عندما تفشل الخوارزمية في مدخلاتها العددية -- على سبيل المثال ، (i) عدم إنهاء (ii)'إنتاج" معدوم "( الناتج في شكل خاطئ يعتبر عدد )أو لا رقم (أرقام) على الإطلاق (تعلق النهاية بلا ناتج ) ، (iii) رقم (أرقام) خطأ ، أو (iv) مجموعة من هذه. اقترح كليين أن إنتاج "معدوم" أو الفشل في إصدار عدد تحل عن طريق الحصول على خوارزمية تكشف عن هذه الحالات وتنتج على سبيل المثال ، رسالة خطأ (واقترح "0") ، أو من الأفضل ، ادخال الخوارزمية في حلقة لا نهاية لها) ( كليين 1952:322). وطبق ديفيس هذة الفكرة خوارزمية الطرح -- حيث ضبط خوارزميته في المثال الثاني بحيث jكون الطرح الصحيح (ديفيس 1958:12-15). جنبا إلى جنب مع النتائج المنطقية "صح" و "خطأ" إقترح كليين استخدام رمز ثالث منطقي "u" -- متردد (كليين 1952:326) -- ومن ثم تنتج دائما الخوارزمية شيئا عندما تواجه "مسالة". يجب أن تحل مشكلة الاجابات الخاطئة بواسطة "دليل" مستقل عن الخوارزمية, على سبيل المثال استخدام المقدمة الإستهلالية :

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


التعبير عن الخوارزميات

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


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


ومن المفيد في بعض الأحيان في وصف الخوارزمية تكملة "الخرائط" الصغيرة (حالةالمخطط البياني) باللغة الطبيعية و / أو عبارات مكتوبة داخل الحساب "رسم بياني " لتلخيص ما تنجزه "المخططات" .


تصنف عادة تمثيل الخوارزميات إلى ثلاثة مستويات مقبولة طبقا لآلة تورينج (سيبسر 2006:157) :

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


مثال علي الخوارزمية البسيطة "أضف م + ن" تم وصفها في جميع المستويات الثلاثة انظر أمثلة الخوارزمات.


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

في انظمة الحاسوب ، الخوارزمية أساسا مثال منطقي مكتوب في البرنامج من قبل مطوري البرامج لتكون فعالة "لهدف" الحاسوب ، لكي يتسنى للبرمجيات على ماكينات الهدف لعمل شيء. على سبيل المثال ، إذاكتب الشخص برنامجا من المفترض ان يطبع وثيقة PDF تقع في مجلد نظام التشغيل "D/ المستندات"" في كل يوم الجمعة في 10PM ، سوف نكتب خوارزمية تحدد الإجراءات التالية : "اذا كان تاريخ اليوم (وقت الكمبيوتر)' الجمعة 'افتح وثيقة' D : / مستنداتي واستدعي "وظيفة "الطابعة . علي الرغم من ان هذة الخوارزمية البسيطة لا تهتم ما اذا كانت الطابعة لديها ما يكفي من ورق أو أن الوثيقة ما إذا كانت قد انتقلت الى مكان آخر ، من الممكن جعل هذة خوارزمية أكثر قوة وأن تتوقع هذه المشاكل على أنها إعادة صياغة رسمية لعبارة الترجمة، أو تسلسل عبارة إذا- ثم -أو. على سبيل المثال ،من الممكن ان تظهر عبارة الترجمة علي النحو التالي (توجد احتمالات أخرى) :

الحالة رقم 1 : إذا لم يكن تاريخ اليوم هو يوم الجمعة فاخرج من تعليمات البرنامج والإ.
الحالة رقم 2 : إذا كان تاريخ اليوم هو يوم الجمعة وهذه الوثيقة موجودة في "D \ مستنداتي' ، وهناك ورق في الطابعة ثم اطبع الوثيقة ثم اخرج من تعليمات البرنامج .
الحالة رقم 3 : إذا كان تاريخ اليوم هو يوم الجمعة والوثيقة لا توجد في 'D : / مستنداتي ثم اعرض لم يتم العثور على المستند' رسالة خطأ ثم اخرج من تعليمات البرنامج .
الحالة رقم 4 : إذا كان تاريخ اليوم هو يوم الجمعة وهذه الوثيقة موجودة في 'D :\ مستنداتي' وليس هناك ورقة في الطابعة ثم (i) اعرض 'لايوجد ورق في الطابعة' رسالة خطأ (ii) اخرج.


علما بأن الحالة 3 تشمل احتمالين : (i) الوثيقة غير موجودة في 'D : / مستنداتي وهنالك ورقة في الطابعة أو (ii) الوثيقة غير موجودة في'D : / مستنداتي' وهناك ورقة في الطابعة.


تسلسل اختبارات اذا- ثم - أو قد تبدو كالتالي :

اختبار 1 : إذا لم يكن تاريخ اليوم هو يوم الجمعة ثم تفعل آخر اختبار 2 :
اختبار 2 : إذا كانت الوثيقة موجودة في 'D :مستنداتي' ثم اعرض لم يتم العثور على الوثيقة' رسالة خطأ آخر اختبار 3 :
اختبار 3 : إذا لم يكن هناك أي ورق في الطابعة ثم اعرض 'خالية من الورق' رسالة خطأ أو اطبع الوثيقة.


هذه الأمثلة تمنح منطقيا الأسبقية ل" لا توجد وثيقة في 'D :\مستنداتي'. كما نلاحظ أيضا أنه في حالة الإعداد الجيد للبيان التسلسلي ل إذا- ثم-أو لعدد من الأعمال المتميزة --رقم 4 في هذه الأمثلة : لا تفعل شيئا ، طباعة الوثيقة ، واعرض الوثيقة لم يتم العثور علىها 'اعرض 'خالية من ورقة '-- يساوي عدد الحالات.


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


التنفيذ

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


مثال

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


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


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

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


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


قالب:Algorithm-begin 

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

اكبر  ← لام  0
بالنسبة لكل  بند من بنود  في  القائمة ل ≥ 1  ، هل
إذا كان  البند> أكبر  ،
اكبر  ← البند 
العودة  اكبر

قالب:Algorithm-end


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


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

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


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


الموجز مقابل التجريبية

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


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


التصنيف

هناك عدة طرق لتصنيف الخوارزميات ، ولكل منها مزايا.


عن طريق التنفيذ

إحدى الطرق لتصنيف الخوارزميات هي وسائل التنفيذ.


  • استدعاء ذاتي أو تكرار  : تكرر الخوارزمية المتكررة نفسها مرارا وتكرارا إلى أن تتطابق احدي الحالات ، وهي وسيلة عامة للبرمجة الوظيفية. تكرار استخدام الخوارزميات المتكررة ببناء متكرر وفي بعض الأحيان بيانات إضافية متراكمة لحل مشاكل معينة. وبطبيعة الحال بعض المشاكل تتلاءم مع تنفيذ واحد أو آخر. على سبيل المثال ، أبراج هانوي تفهم جيدا عن طريق التنفيذ المتكرر. كل نسخة متكررة(تستدعي ذاتيا ) لديها ما يعادلها (ربما أكثر أو أقل تعقيدا) من النسخ المتكررة ، والعكس بالعكس.
  • منطقيا  : الخوارزمية يمكن اعتبارها خصم منطقي مسيطر . هذه الفكرة يعبر عنها بـ : الخوارزمي = منطق + السيطرة (كوالسكي 1979). تعبر عنصر المنطق عن البديهيات التي يمكن استخدامها في الحساب وعنصر السيطرة الذي يحدد الطريقة التي يطبق فيها الخصم على البديهيات. وهذا هو الأساس في نموذج البرمجة المنطقية . في لغات البرمجة المنطقية الخالصة , العنصرالمسيطر يضبط و تحدد الخوارزميات فقط من خلال تقديم عنصر المنطق . مظهر هذا النهج هو اناقة معاني الكلمات : تغيير في البديهيات له تأثير التغيير في الخوارزمية.
  • المسلسل أو موازية أو توزيعها  : هي خوارزميات عادة تناقش مع افتراض أن أجهزة كمبيوتر تنفذ تعليمات من خوارزمية واحدة في وقت واحد. هذه الحواسيب هي التي تسمى أحيانا المسلسل الكمبيوتر. الخوارزمية المصممة لمثل هذه البيئة تسمى خوارزمية مسلسلة، على عكس خوارزمية موازية أو الخوارزميات الموزعة. وتستفيد الخوارزمات المتوازية من هندسة الكومبيوتر حيث يمكن العمل على اي مشكلة في الوقت نفسه ، في حين الخوارزميات الموزعة تستخدم آلات متعددة ترتبط مع الشبكة. الخوارزميات المتوازية أوالموزعة تقسم المشكلة الي مشاكل اصغر مماثلة او غير مماثلة وتجمع النتائج معا مرة أخرى. فإن استهلاك الموارد في هذه الخوارزميات ليست فقط في كل دورات المعالج لكل معالج بل أيضا الاتصال بين المعالجات. خوارزميات الفرز يمكن ان تكون متوازية بكفاءة ، ولكن الاتصالات العامة مكلفة. الخوارزميات المتكررة عموما متوازية. بعض المشاكل ليس لها خوارزميات متناظرة ، ويطلق عليها اصلا المشاكل المتسلسة .
  • القطعية أو عدم القطعية  : تحل الخوارزمية القطعية المشكلة على وجه الدقة في كل خطوة في حين ان الخوارزمية الغير قطعية تحل المشاكل عن طريق التخمين على الرغم من التكهنات هي أكثر دقة من خلال استخدام الاستدلال.
  • الدقيق أو التقريبي  : على الرغم من توصل العديد من الخوارزميات الى الحل على وجه الدقة ، حيث تبحث الخوارزمية التقريبية عن المستندات التي تقرب الى الحل الحقيقي. التقريبية قد تستخدم إما قطعية أو عشوائية استراتيجية. هذه الخوارزميات لها قيمة عملية بالنسبة لكثير من المشاكل الصعبة.


من خلال تصميم النموذج

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

  • فرق تسد. وهناك خوارزمية فرق تسد التي تقلل من حالة المشكلة الي واحدة أو أكثر من الحالات الأقل من نفس المشكلة (عادة تكرار) حتى تصل الي الحالات الصغيرة بما يكفي لحلها بسهولة. أحد الأمثلة لفرق تسد هو دمج الفرز. و يتم الفرز على كل جزء من البيانات بعد تقسيم البيانات إلى شرائح وويتم فرز كل البيانات في مرحلة تسد من خلال دمج أجزاء. وثمة بديل أكثر بساطة من فرق تسد تسمى خوارزمية النقصان والقهر ، التي تحل المشكل الثانوية المتطابقة ، وتستخدم حلول المشاكل الثانوية في حل مشكلة أكبر. تقسم فرق تسد المشكلة الي مشاكل ثانوية متعددة. وبالتالي مرحلة تسد ستكون أكثر تعقيدا من خوارزميات النقصان والقهر. مثال على خوارزمية النقصان والقهر هي خوارزمية البحث الثنائي.
  • البرمجة الديناميكية. عندما تظهر مشكلة في المكونات الثانوية ، هذا يعني ان الحل الأمثل للمشكلة لا يمكن بناؤها من الحلول المثلى للمشاكل الثانوية ، والمشاكل الثانوية المتداخلة ، بمعنى ان المشاكل الثانوية نفسها تستخدم في حل مشكلة العديد من الحالات ، ويدعى هذا النهج السريع بالبرمجة الديناميكية والتي تتجنب إعادة إستعمال حاسبات الحلول التي قد تم حسابها. على سبيل المثال ، أقصر الطرق إلى الهدف من قمة الرأس في رسم ضخم عن طريق استخدام أقصر الطرق إلى الهدف من كل القمم المجاورة. البرمجة الديناميكية والحفظية يسيران جنبا إلى جنب. والفرق الرئيسي بين البرمجة الديناميكية وفرق تسد هو أن المشاكل الثانوية تكون أكثر أو أقل استقلالا في فرق تسد ، في حين ان المشاكل الثانوية تتداخل في البرمجة الديناميكية. الفرق بين البرمجة الديناميكية ومباشرة استدعاء ذاتي في التخزين المؤقت أو التحفيظ للدعوات المتكررة. عندما تكون المشاكل الثانوية مستقلة ، وليس هناك تكرار ،فان التحفيظ لا يساعد بالتالي البرمجة الديناميكية ليست حلا لجميع المشاكل المعقدة. باستخدام التحفيظ أو الحفاظ على الجدول من المشاكل الثانوية التي سبق حلها ، يقلل البرمجة الديناميكية طابع الأسي لمشاكل متعددة لمشاكل كثيرة التعقيد.
  • الطريقة الجشعة. خوارزمية الجشع مشابهة لخوارزمية البرمجة الديناميكية ، ولكن الفرق هو أن حلول المشاكل الثانوية لا يجب أن تكون معروفة في كل مرحلة من المراحل , بدلا من ذلك ,يتكون الاختيار "الجشع" مما يبدو أفضل لهذة اللحظة. تزود طريقة الجشع الحل بأفضل قرار ممكن (ليست كلها قابلة للقرارات) في مرحلة الحساب على أساس القرار المحلي على الوجه الأمثل والأفضل (وليس كل ما يمكن من قرارات) تم عمله في المرحلة السابقة. انها ليست شاملة ، ودقيقة ولا تعطي إجابة على الكثير من المشاكل. ولكن عندما تعمل ، ستكون أسرع وسيلة. الأكثر شعبية لخوارزمية الجشع هي إيجاد الحد الأدنى لشجرة تمتد على النحو الذي قدمه كروسكال.
  • البرمجة الخطية. عند حل المشكلة باستخدام البرمجة الخطية ، عدم المساواة الموجودة بالمدخلات يتم عمل محاولات لتحقيق الحد الأقصى (أو الأدني ) لبعض المهام الخطية في المدخلات. كثير من المشاكل (مثل الحد الأقصى لتدفق توجيه الرسوم البيانية) ويمكن وضعها في البرمجة الخطية ، وبعد ذلك تحل بواسطة خوارزمية شاملة مثل الخوارزمية البسيطة. وهنالك بديل أكثر تعقيدا من البرمجة الخطية يسمى برمجة الإنتجر ، حيث فراغ الحل مقصور على الإنتجر
  • الحد. وينطوي هذا الأسلوب علي حل المشكلة الصعبة وتحويلها الى مشكلة معروفة جيدا والتي لدينا (نأمل)لها خوارزميات مقاربة مثالية. الهدف هو العثور على خوارزمية الحد والتي لا يهيمن عليها التعقيد ناتجا عن خوارزمية الحد. على سبيل المثال ، لاختيار خوارزمية واحدة لإيجاد الوسيط في قائمة غير مفرزة يشمل الفرز في القائمة اولا (الجزء الباهظ ) ، ثم تحديد عنصر الوسطي في قائمة التصنيف (الجزء الرخيص). هذه التقنية تعرف أيضا باسم تحويل وقهر.
  • البحث والسرد. كثير من المشاكل (مثل لعب الشطرنج) كما يمكن أن تكون على غرار المشاكل على الرسوم البيانية. تحدد خوارزمية الرسم البياني الاستكشافي قواعد للتحرك نحو رسم بياني ومفيد لهذه المشاكل. وتشمل هذه الفئة أيضا خوارزمية البحث في فرع والالتزام بالسرد والتراجع.
  • الاحتمالية ونموذج الكشف عن مجريات الأمور. الخوارزميات التي تنتمي إلى هذه الفئة تناسب تعريف الخوارزمية بكل سهولة.
  1. خوارزمية الاحتمال هي تلك التي تجعل بعض الخيارات عشوائيا (أو عشوائية زائفة) ، للاطلاع على بعض المشاكل ، يمكن في الواقع إثبات أن أسرع الحلول يجب أن تشمل بعض عشوائية.
  2. تحاول الخوارزمية الجينية إيجاد حلول للمشاكل عن طريق محاكاة عملية التطور البيولوجي ، مع حلقة من الطفرات العشوائية تثمر عن أجيال متعاقبة من "الحلول". وهكذا ، وتحاكي التكاثر و "البقاء للأصلح". في البرمجة الجينية ، فإن هذا النهج يشمل الخوارزميات ، باعتبار الخوارزمية نفسها "حل" للمشكلة.
  3. خوارزميات الكشف عن مجريات الأمور التي من أغراضها العامة ليس إيجاد الحل الأمثل ، ولكن تقريب الحل حيث الوقت أو الموارد محدودة. فهي ليست عملية لإيجاد حلول مثالية. ومثالا على ذلك سيكون البحث المحلي ، لبحث تابو ، أو خوارزميات محاكاة الصلب ، وفئة من خوارزميات الكشف عن مجريات الأمور التي تختلف في حل مشكلة عشوائية . اسم "محاكاة الصلب" يشير إلى معنى مصطلح متعلق بعلوم التعدين تسخين وتبريد المعدن لتحقيق التحرر من العيوب. والغرض من هذه الفرق العشوائي هو التوصل الى الحلول المثلى على الصعيد العالمي وليس فقط المحلي منها ، والفكرة هي انخفاض عنصر العشوائية حينما تستقر الخوارزمية على الحل.


حسب مجال الدراسة

انظر أيضاً: List of algorithms

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


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


من جانب التعقيد

انظر أيضاً: Complexity class and Parameterized complexity

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


من خلال الحواسيب

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


يستخدم بورجين (2005 ، ص 24) تعريف الخوارزميات العام الذي يريح الشرط المشترك ان ناتج الخوارزمية التي يحسب وظيفة يجب أن يتحدد بعد عدد معين من الخطوات. يعرف بورجين الخوارزميات فوق المتكررة "فئة من الخوارزميات التي يمكن حساب الوظائف لايمكن حسابها من جانب أي آلة تورينج" (بورجين 2005 ، p. 107). هذا يرتبط ارتباطا وثيقا لدراسة أساليب الحساب فوق العادة


المسائل القانونية

وانظر أيضا : براءات اختراع البرمجيات في لمحة عامة عن براءات الاختراع للبرمجيات ، بما في تنفيذ خوارزميات الحاسوب.


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


وبالإضافة إلى ذلك ، تصدير بعض خوارزميات الترميز (انظر التصدير الترميز).


التاريخ : تطوير مفهوم "الخوارزمية"

أصل الكلمة

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


رموز منفصلة ومميزة

ويمثل هذا العدد  : لتتبع أغنامهم ، وأكياس الحبوب وأموالهم , استخدم الأولين دمة : تراكم الحجارة أو علامات خدوش على العصي ، أو جعل رموز منفصلة في الطين. الطريقة البابلية والمصرية في استخدام العلامات والرموز ، وفي نهاية المطاف الأرقام الرومانية وأباكس تطورت (Dilson ، p.16 - 41). الحصيلة تبدو علامات بارزة في نظام حسابي أحادي العدد مستخدم في آلة تورينج وبعد آلة تورينج الحسابية.


التلاعب بالرموز "أصحاب المكان" للأرقام : الجبر

عمل علماء هندسة اليونانية القديمة ، وعالم الرياضيات الفارسي آل Khwarizmi (وغالبا ما تعتبر "والد الجبر" ،ويستمد من اسمه "نظام العد العربي" و "الخوارزمية" ) ، وتوجت ودول أوروبا الغربية الرياضيات Leibniz / وفكرة حساب التفاضل والتكامل ratiocination (كاليفورنيا (1680) :

"قرن ونصف قبل وقته ، واقترح Leibniz الجبر المنطقي ، الجبر التي من شأنه أن يحدد القواعد المنطقية لتلاعبه في المفاهيم بطريقة الجبر العادية و التي تحدد قواعد التحكم في الأعداد" (ديفيز 2000:1)


الإختراعات الميكانيكية مع حالات منفصلة

الساعة  : ائتمن بولتر اختراع ساعة يحركها وزن "مفتاح الاختراع [من أوروبا في العصور الوسطى]" ، ولا سيما وشك ميزان (بولتر 1984:24) أن يقدم لنا تيك وتوك عقارب الساعة الميكانيكية . أدىت "الآلة التلقائية الدقيقة" (بولتر 1984:26) على الفور إلى "الميكانيكية الباردون" في بداية القرن الثالث عشر ، وأخيرا إلى "آلات الحسابية" -- الفرق في المحرك والمحرك التحليلي لل تشارلز Babbage الكونتيسة وأدا لافليس (ص بولتر 33-34 ، p.204 - 206).


الجاكار قماش تلوح في الأفق ، لكمة هولليريث البطاقات الهاتفية والبرق -- التتابع الكهربائي  : بيل ونيويل (1971) تشير إلى أن تلوح الجاكار قماش (1801) ، مقدمة لهولليريث بطاقات (كمة بطاقات ، 1887) ، و "تكنولوجيات التحويل الهاتفي" جذور من الشجرة مما يؤدي إلى وضع أول الكمبيوتر (بيل ونويل الرسم ص 39 ، انظر ديفيس عام 2000). وبحلول منتصف 1800s فإن البرق ، بداية الهاتف ، وكانت تستخدم في جميع أنحاء العالم ، منفصلة ومميزة لترميز الرسائل "النقط وشرطات" لصوت طبيعي. وبحلول أواخر 1800s فإن استخدام شريط التسجيل (كاليفورنيا 1870s) ، وكذلك استخدام بطاقات هولليريث بالولايات المتحدة في 1890. ثم جاءت كتابة البرق (حوالي 1910) مع استخدام لكمة الورقة بشفرة بودو على الشريط.


الهاتف تحويل شبكات التتابع الكهروميكانيكي (اخترع 1835) كان وراء أعمال جورج ستبتز (1937) ، مخترع جهاز الإضافة الرقمي . حيث عمل في مختبرات بيل ، لاحظ "عبئ استخدام الآلات الحاسبة الميكانيكية مع التروس. وتوجه الى منزله في احدي اليالي في عام 1937 عليعازما اختبار فكرته... عندما انته الترقيع ، كان ستيبز شيدت جهاز اضافه ثنائي ". (وادي الأخبار ، p. 13).


ديفيز (2000) لاحظ أهمية خاصة للالكهروميكانيكية التتابعية) مع احالته الثنائية مفتوحة ومغلقة)  :

إلا أنه مع تنمية ، وتبدأ في 1930s ، الكهروميكانيكية والكهربائية ببعضها البعض واستخدام الآلات الحاسبة ، والآلات التي تم بناؤها بعد أن كان نطاق باباج متوخاة ". فان هيجنوورت"(ديفيز ، ص. 14,


الرياضيات خلال 1800s حتى منتصف 1900s

رموز و قواعد : في تتابع سريع في الرياضيات من جورج بوول (1847 ، 1854),جوتلوب فريج ( 1879 )وجوزيبي بيانو (1888-1889) و خفض الحساب و سلسلة من رموز بواسطة التعامل مع القواعد مبادئ الحساب لبيانو ، والتي قدمها بأسلوب جديد (1888) كانت أول محاولة تبسيط الحقائق في الرياضيات في لغة رمزية "(فان هيجنوورت : 81ff).


ولكن هيجنووت اعطي فرينج (1879) هذا مجد : فرينج قال "ربما يكون أهم من أي وقت مضى العمل المكتوب في المنطق.... التي نرى فيها" صيغة اللغة '، التي هي مميزات اللغة ، وهي لغة مكتوبة خاصة مع رموز "الفكر المحض" ، أي خالية من الزينة الخطابي... شيدت من الرموز التي هي محددة وفقا للتعامل مع القواعد (1). عمل فريج كذلك تم تبسيطه وتقويتة بواسطة ألفريد نورث وايتهيد وبرتراند رسل في مباديء الرياضيات (1910-1913).


مفارقات  : في الوقت نفسه عددا من المفارقات المثيرة للقلق ظهرت في الأدب ، ولا سيما مفارقة بورالي فورتي (1897) ، والمفارقة راسل (1902-03) ، وريتشارد بارادوكس (ديكسون 1906 ، انظر Kleene 1952:36-40). أدت نتائج الاعتبارات إلى كورت جودل / ورقة (1931) -- على وجه التحديد ويذكر انه من المفارقة كاذب -- قلل تماما من قواعد الاستدعاء الذاتي الى الأرقام.


الفاعلية الحسابية} : في محاولة لحل Entscheidungsproblem هيلبرت حددها بدقة من قبل في عام 1928 ، أول مجموعة من علماء الرياضيات حول تعريف ما هو المقصود "طريقة فعالة" أو "فعالة لحساب" أو "calculability فعالة" (أي حساب من شأنها أن تنجح . في تتابع سريع فيما يبدو التالية : الونزو الكنيسة ، كليين ستيفن وJB Rosser / λ - حساب التفاضل والتكامل ، (انظر الحاشية في كنيسة الونزو 1936a : 90 ، 1936b : 110) تعريف رائع "استدعاء ذاتي عام" من عمل Gödel بناء على اقتراحات من جاك هيربراند (راجع قال برينستون Gödel المحاضرات لعام 1934) وما تلاه من التبسيط من قبل Kleene (1935-6:237 وما بعدها ، وما يليها 1943:255). إثبات الكنيسة (1936:88 وو) أن Entscheidungsproblem كان غير قابل للحل ، اميل بوست / تعريف المحاسبية الفعالة على النحو التالي العامل بغفلة عن طريق قائمة تعليمات للتحرك لليسار أو اليمين من خلال سلسلة من الغرف ، وعلى الرغم من وجود أي علامة أو محو أو ورقة مراقبة وتقديم ورقة بنعم او لا قرار حول التعليمات التالية (راجع "صياغة I" بوست 1936:289-290). آلان تورنج / دليل على أن Entscheidungsproblem كان غير قابل للحل عن طريق استخدام "أ [تلقائيا] آلة" تورينج 1936-7:116 وو) -- في واقع الأمر مطابقة تقريبا للبوست "الصيغة" ، J. باركلي Rosser / تعريف "طريقة فعالة" من حيث "ماكينة" (Rosser 1939:226). المحكمة العليا Kleene / اقتراح مقدمة ل"أطروحة الكنيسة" التي وصفها بانها "الأطروحة لي" (Kleene 1943:273-274) ، وبعد سنوات قليلة إعاد كليين تسمية اطروحته" أطروحة الكنيسة"(Kleene 1952:300 ، 317) ويقترح "أطروحة تورينج " (Kleene 1952:376).


اميل الوظائف (1936) وآلن تورينج (1936-7 ، 1939)

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


اميل بوست (1936) ووصف الإجراءات التي يتخذها "الحاسوب" (إنسان) على النحو التالي :

"... المفهومين هما : أن من رمز الفضائية التي تعمل من المشكلة التي تؤدي إلى الإجابة التي يتعين الاضطلاع بها ، ومجموعة من الاتجاهات ثابتة غير قابلة للتغيير


رمز الفضاء سيكون

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


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


"مجموعة من التوجهات التي تنطبق على مشكلة عامة ينشئ عملية القطعية عند تطبيقه على كل مشكلة محددة. هذه العملية ستنتهي فقط عندما يتعلق الأمر بتوجيه من نوع (ج) [أي توقف. " (يو ص. 289-290) انظر في ما بعد آلة تورينج


عمل آلان تورنج / (1936 ، 1939:160) وسبق ستبيتز (1937) ، ومن غير المعروف ما اذا كان يعرف ستبيز عن عمل تورينج. كاتب سيرة تورينج عبر عن اعتقاده بأن تورينج استخدام آلة كاتبة على غرار نموذج مستمد من اهتمام الشباب : "آلان كان يحلم باختراع الآلات الكاتبة كماكان صبي السيدة تورينج لديه آلة كاتبة ، وانه قد بدأ بطرح نفسه ، ما هو المقصود من خلال تسمية آلة كاتبة 'الميكانيكية" (هودجز ، p. 96). ونظرا لانتشار مورس والبرق ،و شريط آلة التسجيل ، وكتابة البرق يمكن الظن أن تؤثر على الجميع.


تورينج -- له نموذج حسابي الآن يسمى آلة تورينج -- تبدأ ، كما فعل بوست ، مع تحليل الحاسوب لبشري انه ينجر الى مجرد مجموعة من الاقتراحات والأساسية "وحالات العقل ". لكنه اكمل خطوة أخرى وصنع الآلة بوصفها نموذجا لحساب الأعداد (تورينج 1936-7:116).


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


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


"فلنتخيل أن العمليات التي يقوم بها جهاز الكمبيوتر المقرر تقسيم' العمليات بسيطة التي هي الابتدائية حتى أنه ليس من السهل تصور المزيد من تقسيمها "(تورينج 1936-7:136).


تخفيض تورينج ما يلي :

واضاف "ولذلك يجب أن العمليات البسيطة وتشمل :
"(أ) التغيرات من رمز واحد من لاحظ الساحات
"(ب) التغيرات التي طرأت على واحدة من الساحات لاحظ آخر مربع داخل ساحات لتر واحد من قبل ولاحظ الساحات.

"وقد يكون بعض هذه بالضرورة تغيير في الاحتجاج على تغيير الحالة الذهنية. عموما أكثر عملية واحدة ولذلك يجب اتخاذها لتكون واحدة من ما يلي :

"(أ) من الممكن تغيير (أ) من الرمز مع احتمال تغيير الحالة الذهنية.
"(ب) من الممكن تغيير (ب) من ساحات لاحظ ، مع احتمال تغيير الحالة الذهنية"


وتابع "ربما كنا الآن في بناء جهاز للقيام بهذا العمل من هذا الكمبيوتر." (تورينج 1936-7:136)


وبعد سنوات قليلة ، والتوسع في تحليل تورينج (أطروحة ، وتعريف) مع هذا بتعبيرات منه :

"وظيفة ويقال إنه" يمكن حسابه بشكل فعال "في حال قيمته ويمكن الاطلاع على بعض لعملية ميكانيكية بحتة. وإن كان من السهل الحصول على بديهية فهم هذه الفكرة ، إلا أنه من المستحسن أن يكون أكثر تحديدا بعض الرياضيات للتعبير عن التعريف. . . [يناقش تاريخ تعريف حد كبير كما هو وارد أعلاه فيما يتعلق Gödel ، Herbrand ، Kleene ، والكنيسة ، وتورينج بوست]. . . قد يستغرق هذا البيان حرفيا ، فهم عملية ميكانيكية بحتة واحدة الذي يمكن أن يقوم بها الجهاز. ومن الممكن إعطاء وصف رياضي ، في شكل طبيعي معين ، من هياكل هذه الآلات. تطوير هذه الأفكار الى صاحب البلاغ وهو محسوب على تعريف وظيفة ، وتحديد المحاسبة † الفعالية الحسابية. . . .
"† ننتقل لتعبير" وظيفة حسابية "، على أنها تعني وظيفة يمكن حسابها من قبل الآلة ، وتركنا" بفعالية حسابه "إلى فكرة بديهية ولا سيما من دون تحديد أي واحد من هذه التعريفات.")تورينج 1939:160)


JB Rosser (1939) واتفاقية استكهولم Kleene (1943)

J. باركلي روسر بجرأة حدد الفعالة [الرياضية] على النحو التالي (بحروف بارزة وأضاف :

"طريقة فعالة' تستخدم هنا في شعور خاص وليس طريقة كل خطوة منها على وجه التحديد ، والتي هي مصممة لانتاج بعض الجواب في وجود عدد محدود من الخطوات. هذا معنى خاص ، ثلاثة تعريفات دقيقة وقد منحت حتى الآن. [# 5 حاشية له انظر فورا دون مناقشة. أبسط من هذه الحالة (بسبب تورينج و بوست) التي تقول في جوهرها وسيلة فعالة لمجموعات من حل بعض المشاكل في حال وجود احد يستطيع بناء الآلة التي سوف تحل اي مشكلة من مجموعة بدون تدخل بشري وراء إدراج هذه المسألة و (لاحقا) قراءة الجواب. جميع التعاريف تعادل ثلاثة ، لذلك لا يهم من هو المستخدم. وعلاوة على ذلك ، حقيقة أن كل ما يعادل ثلاثة هي حجة قوية على صحة أي واحد ". (Rosser 1939:225-6)


حاشية روسر رقم 5 إشارات عمل (1) ، والكنيسة وكليين تعريف الوضوح λ - ، ولا سيما الكنيسة واستخدام ذلك في مشكلة لا يمكن حلها من نظرية الابتدائية رقم (1936) ، (2) وهيربراند واستخدامها جودل استدعاء ذاتي ولا سيما للاستخدام في جودل الشهيرة وعلى ورقة المقترحات من الناحية الرسمية الرياضيات والمباديء ذات الأنظمة الأول (1931) ، و (3) من الوظائف (1936) وتورينج (1936-7) في آلية بين النماذج الحسابية.غ


ستيفن كليين المحدد له الآن "أطروحة لي" الشهيرة المعروفة باسم أطروحة كنيسة تورينج . لكنه فعل ذلك في السياق التالي (بحروف بارزة في النص الأصلي) :

"12. النظريات الحسابية ... في وضع نظرية كاملة حسابية ما نقوم به هو لوصف الإجراء ، لكل مجموعة من القيم من المتغيرات المستقلة ، والتي تنتهي بالضرورة الي إجراء وبهذه الطريقة من أن النتائج يمكننا قراءة اجابة محددة ، "نعم" أو "لا" على سؤال "أصلية هي القيمة الحقيقية"؟ " (كليين 1943:273)


التاريخ بعد عام 1950

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


انظر أيضا

 هناك كتاب ، Algorithms، في معرفة الكتب.


At Wikiversity, you can learn more and teach others about Rashaibrahim/خوارزمية at the Department of Rashaibrahim/خوارزمية

! (انظر تحليل الأداء أعلاه


وتلاحظ


المراجع

  • Axt ، P. (1959) على التسلسل الهرمي تكرار ثانوي تكراري البدائي والدرجات ، والمعاملات الاميركية جمعية رياضية 92 ، ص. 85-105
  • ويشمل ممتازة 56 ببليوغرافيا المراجع.
  • Boolos, George; Jeffrey, Richard (1974, 1980, 1989, 1999). Computability and Logic (4th ed.). Cambridge University Press, London. ISBN 0-521-20402-X. {{cite book}}: Check date values in: |year= and |date= (help)CS1 maint: date and year (link) : انظر الفصل 3 آلات تورنج حيث بحث "مجموعات معينة للاحصاء غير فعال (ميكانيكية) للاحصاء".
  • بيرجين ، M. سوبر متكررة الخوارزميات ، دراسات في علم الحاسوب ، وسبرينغر ، 2005. ردمك 0387955690
  • كومباجنو، وحركة التحرير ، مور ، C. ، وكوستا ، ج. ف.)2000) التناظرية توصيف للوظائف subrecursive. في إجراءات. 4th للمؤتمر ، والأعداد الحقيقية للكمبيوتر ، جامعة أودنسي ، ص. 91-109
  • Church, Alonzo (1936a). "An Unsolvable Problem of Elementary Number Theory". The American Journal of Mathematics. 58: 345–363. doi:10.2307/2371045. أعيدت طباعته في غير مقررة ، p. 89ff. أول تعبير "اطروحة الكنيسة ء". انظر على وجه الخصوص في الصفحة 100 (إن Undecidable) حيث يحدد مفهوم "الحساب فعالة" من حيث "خوارزمية" ، وأنه يستخدم كلمة "تنهي" ، الخ.
  • Church, Alonzo (1936b). "A Note on the Entscheidungsproblem". Journal of Symbolic Logic. 1 no. 1 and volume 1 no. 3. أعيدت طباعته في غير مققررة ، p. 110ff. الكنيسة أن Entscheidungsproblem هو غير قابل للحل في حوالي 3 صفحة من النصوص و 3 صفحة من الحواشي.
  • Daffa', Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 0-85664-464-1.
  • Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. ديفيس قبل التعليق يعطي كل مادة. ورقات من جوبل ، الونزو الكنيسة ، تورينج ، روسر، كليين ، واميل بوست أدرجت تلك المذكورة في المادة المذكورة هنا اسم المؤلف.
  • Davis, Martin (2000). Engines of Logic: Mathematicians and the Origin of the Computer. New York: W. W. Nortion. ديفيس عروض موجزة سير Leibniz ، بوول ، فرج ، قائد الفرقة الموسيقية في الكنيسة ، هيلبرت ، جودل وتورينج مع فون نيومان كما تبين سرقة الشرير. موجز جدا من السير جوزيف ماري الجاكار قماش ، باباج ، افليس آدا ، كلود شانون ، هوارد ايكن ، الخ.
  • قالب:DADS
  • Dennett, Daniel (1995). Darwin's Dangerous Idea. New York: Touchstone/Simon & Schuster.
  • يوري جيرفيتش، الدولة المتعاقبة الموجز آلات التقاط المتعاقبة الخوارزميات ، إيه سي إم معاملات الحوسبة المنطق ، المجلد 1 ، رقم 1 (يوليو 2000) ، الصفحات 77-111. وتتضمن ببليوغرافيا 33.
  • Kleene C., Stephen (1936). "General Recursive Functions of Natural Numbers". Mathematische Annalen. Band 112, Heft 5: 727–742. doi:10.1007/BF01565439+. مقدم إلى جمعية رياضية الأمريكية ، سبتمبر 1935. أعيد طبعه في غير مقررة ، p. 237ff. كليين تعريف "استدعاء ذاتي عام" (والمعروفة الآن باسم مو - استدعاء ذاتي) الذي استخدمته الكنيسة في 1935 ورقة للمشكلة لا يمكن حلها عدد الأولية أثبتت أن نظرية "المشكلة بقرار" الى "غير مقرر" (أي نتيجة سلبية).
  • Kleene C., Stephen (1943). "Recursive Predicates and Quantifiers". American Mathematical Society Transactions. Volume 54, No. 1: 41–73. doi:10.2307/1990131. {{cite journal}}: |volume= has extra text (help) أعيدت طباعته في Undecidable ، p. 255ff. كليين المكرر له تعريف "استدعاء ذاتي عام" ، وشرع في الفصل "(12). حسابي النظريات "إلى افتراض و" الأطروحة لي "(ص 274) وأنه سوف يكرر هذه الرسالة في وقت لاحق (في كليين 1952:300) ، واسم" الكنيسة في الرسالة "كليينne 1952:317) (أي ، أطروحة الكنيسة ).
  • Kleene, Stephen C. (First Edition 1952). Introduction to Metamathematics (Tenth Edition 1991 ed.). North-Holland Publishing Company. {{cite book}}: Check date values in: |year= (help) ممتاز -- يمكن الوصول إليها ، وقراءتها -- مرجعا الرياضية "الأسس".
  • Knuth, Donald (1997). Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison-Wesley. ISBN 0201896834.
  • كوسوفوفسكي، ناغورني كاراباخ أركان الحسابي وتطبيق لنظرية متكررات ثانوية خوارزميات ، LSU Publ ، ليننغراد ، 1981
  • Kowalski, Robert (1979). "Algorithm=Logic+Control". Communications of the ACM. ACM Press. 22 (7): 424–436. doi:10.1145/359131.359136. ISSN 0001-0782.
  • ألف ألف ماركوف (1954) نظرية الخوارزميات. [ترجمة جاك J. Schorr - غون والموظفين الباسيفيكي] لمحة مختصرة عن موسكو ، وأكاديمية العلوم في اتحاد الجمهوريات الاشتراكية السوفياتية ، 1954] ، أي القدس ، إسرائيل البرنامج العلمي للترجمة ، 1961 ؛ المتاحة من مكتب الخدمات الفنية ، قسم التجارة الامريكية ، واشنطن] الوصف 444 ص. 28 سم. وأضاف أ ن في الترجمة الروسية الاشغال الرياضية من معهد أكاديمية العلوم في اتحاد الجمهوريات الاشتراكية السوفياتية ، v. 42. العنوان الأصلي : تيوريا الجيمو الجريموفيتش .M2943 مكتبة كلية دارتموث. قسم التجارة الامريكية ، مكتب للخدمات التقنية ، وعدد OTS 60-51085.]
  • Minsky, Marvin (1967). Computation: Finite and Infinite Machines (First ed.). Prentice-Hall, Englewood Cliffs, NJ. مينسكاي توسع "... فكرة خوارزمية -- إجراء فعال..." في الفصل 5.1 الكمبيوترية، إجراءات فعالة والخوارزميات. آلة بلا حدود ".
  • Post, Emil (1936). "Finite Combinatory Processes, Formulation I". The Journal of Symbolic Logic. 1: pp.103–105. doi:10.2307/2269031. {{cite journal}}: |pages= has extra text (help) أعيدت طباعته في Undecidable ، p. 289ff. وتحدد وظيفة بسيطة حسابي يشبه عملية الكتابة رجل محو علامات أو علامات ، والانتقال من مربع إلى مربع ووقفها في نهاية الأمر ، كما يلي قائمة من التعليمات البسيطة. هذا ونقلت وKleene حسب مصدر واحد "الأطروحة الأولى" ، أو ما يسمى الكنيسة تورينج أطروحة.
  • Rosser, J.B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". Journal of Symbolic Logic. 4. أعيدت طباعته في غير مقررة ، p. 223ff. هنا روسرالشهيرة تعريف "طريقة فعالة" : "... وسيلة كل خطوة من خطوات محددة سلفا والذي هو على وجه التحديد ، والتي من المؤكد أن الجواب في انتاج وجود عدد محدود من الخطوات التي... آلة ثم تحل اي مشكلة مجموعة من دون تدخل بشري وراء إدراج هذه المسألة و(لاحقا) ريدينج الرد "(ص. 225-226 ، غير مقررة)
  • Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing Company.
  • Stone, Harold S. Introduction to Computer Organization and Data Structures (1972 ed.). McGraw-Hill, New York. راجع. ولا سيما في الفصل الأول تحت عنوان : الخوارزميات ، وآلات تورنج ، والبرامج. تعريف غير رسمية مقتضبة له : "... أي سلسلة من التعليمات التي يمكن أن إطاعة روبوت يسمى خوارزمية" (ص. 4
  • تصويبات ، المرجع نفسه ، المجلد 43 (1937) pp.544 - 546. أعيد طبعه في غير مقررة ، p. 116ff. تورينج الشهيرة رقة المنتهية أطروحة الماجستير بينما في كلية كينغ كامبردج في المملكة المتحدة.
  • Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. series 2, volume 45: 161–228. doi:10.1112/plms/s2-45.1.161. أعيدت طباعته في غير مقررة ، p. 155ff. تورينج رقة تحدد "أوراكل" وأعرب عن أطروحة الدكتوراه في جامعة برنستون في حين أن الولايات المتحدة الأمريكية.
  • الولايات المتحدة مكتب البراءات والعلامات التجارية (2006) ، 2106.02 **> خوارزميات رياضية <-- 2100 قابلية الحصول على براءات الاختراع ، ودليل إجراءات فحص البراءات (MPEP). آخر تنقيح أغسطس 2006


المراجع الثانوية

  • Bolter, David J. Turing's Man: Western Culture in the Computer Age (1984 ed.). The University of North Carolina Press, Chapel Hill NC. ، ردمك 0-8078-4108-0 pbk.
  • Dilson, Jesse. The Abacus ((1968,1994) ed.). St. Martin's Press, NY. ، ردمك 0 - 312 - 10409 - العاشر (pbk.)
  • van Heijenoort, Jean. From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931 ((1967) ed.). Harvard University Press, Cambridge, MA. ، 3rd طبعة 1976 [؟] ، ردمك 0-674-32449-8 (pbk.)
  • Hodges, Andrew. Alan Turing: The Enigma ((1983) ed.). Simon and Schuster, New York. ، ردمك 0-671-49207-1. قارن فصل "روح الحقيقة" للتاريخ مما أدى إلى ومناقشة ، دليل على ذلك.


روابط إضافية


تمّ الاسترجاع من "https://www.marefa.org/w/index.php?title=مستخدم:Rashaibrahim/خوارزمية&oldid=816211"