خوارزمية

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

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

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

تعريف رسمي

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

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

Boolos & Jeffrey (1974, 1999) تقدم معنى رسميا للحدثة في الاقتباس التالي:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

تمثيلها

خريطة انسيابية تمثل خوارزم إقليدس لحساب القاسم الأكبر المشهجر (g.c.d.) بين عددين a وb في موضعين يدعيان A وB. يتم الخوارزم عبر سلسلة من عمليات الطرح المتتالية في حلقتين: إذا كان الفحص B ≤ A ينتج عنه "نعم" (أوقضية صائبة) فإن العدد b في الموضع B أقل من أويساوي العدد a في الموضع A)ثم يعين الخوارزم B ← B - A (بمعنى حتى العدد b - a يبدل القيمة السابقة b). بالمثل، إذا كان A > B فإن A ← A - B.حينما تصبح (محتويات) B مساوية لـ 0، وينجم عن ذلك قاسم مشهجر أكبر في A.

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

مخططات سير العمليات التتابعية (Sequential Flowcharts).
مخططات سير العمليات ذات التفرع (Branched Flowcharts).
مخططات سير العمليات ذات التكرار والدوران (Loop Flowcharts).
مخططات سير العمليات ذات الاختيار (Selection Flowcharts).

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

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

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

قواعد البرمجة

هناك أربعة طرق يستعان بها في الخوارزم البرمجي هي:

التكرار Looping

مثال لحساب 2 أس 50.

التفرع Branching

وتمكننا من ادخال معادلات معقدة للحاسوب ليقوم بمعالجتها بطريقة آلية.

الاختيار Selection

فائدة هذة الخاصية تظهر خاصة في ترتيب اعداد بكيفية تنازلية أوالعكس.

التتابع Sequence

تتابع الاوامر حيث ينفذها جهاز الحاسوب حسب الترتيب.

أمثلة

مثال الترتيب

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

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

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

خوارزمية إقليدس

تظهر خوارزمية إقليدس في المسألة الثانية من كتابه ("نظرية الأعداد الأساسية"). يعرض إقليدس المسألة: "إذا كان لدينا عددان أوليان فيما بينهما، لإيجاد قياسهما المشهجر الأكبر". يقوم بتعريف "العدد [بأنه] متعدد مؤلف من وحدات":، عدد حسابي، عدد موجب لا يتضمن الصفر. ومن أجل "القياس" فيعني حتى نضع بترة قياس طولية s بشكل متعاقب (q من المرات) على طول البترة الأطول l حتى يتبقى الجزء r أقل من البترة الأقصر s. في العبارات الحديثة نقول، الباقي r = l - q*s، q هي حاصل القسمة, r "باقي القسمة", الجزء الكسري المتبقي بعد إجراء القسمة.

برنامج سهل لمحاكاة خوارزمية إقليدس

المثال التالي بلغة بيسك يمثل برنامجاً بسيطاً ينفذ خوارزمية إقليدس:

   5  REM Euclid's algorithm for greatest common divisor
   6  PRINT "Type two integers greater than 0"
   10 INPUT A,B
   20 IF B=0 THEN GOTO 80
   30 IF A > B THEN GOTO 60
   40 LET B=B-A
   50 GOTO 20
   60 LET A=A-B
   70 GOTO 20
   80 PRINT A
   90 END

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

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

تسريع الإف إف تي

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

مصادر

^ Stone 1973:4
^ Stone يحتاج ببساطة أنه "يجب حتى تنتهي في عدد محدود من المراحل" (Stone 1973:7–8).
^ Boolos and Jeffrey 1974,1999:19
^ cf Stone 1972:5
^ Knuth 1973:7 states: "في الواقع نحن لا نريد فقط الخوارزميات، بل نحن نريد خوارزميات جيدة... معيار واحد من الخير هوطول الوقت الذي يستغرقه أداء الخوارزمية... other criteria are the adaptability of the algorithm to computers, its simplicity and elegance, etc."
^ cf Stone 1973:6
^ Stone 1973:7–8 تنص على أنه يجب حتىقد يكون هناك، حالات فعالة "...إجراء من شأنه حتى الروبوت [أي كمبيوتر] يمكنع اتباعها من أجل تحديد بدقة كيفية الانصياع لتعليمات. "Stone يضيف محدودية العملية, والوضوح (عدم وجود غموض في التعليمات) لهذا التعريف.
^ Knuth, loc. cit
^ Minsky 1967:105
^ Gurevich 2000:1, 3
^ Heath 1908:300; Hawking’s Dover 2005 edition derives from Heath.
^ " 'Let CD, measuring BF, leave FA less than itself.' This is a neat abbreviation for saying, measure along BA successive lengths equal to CD until a point F is reached such that the length FA remaining is less than CD; in other words, let BF be the largest exact multiple of CD contained in BA" (Heath 1908:297
^ For modern treatments using division in the algorithm see Hardy and Wright 1979:180, Knuth 1973:2 (Volume 1), plus more discussion of Euclid's algorithm in Knuth 1969:293-297 (Volume 2).
^ Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price http://siam.omnibooksonline.com/2012SODA/data/papers/500.pdf Kyoto, January 2012. See also the sFFT Web Page