خوارزمية

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Image-Al-Kitāb al-muḫtaṣar fī ḥisāb al-ğabr wa-l-muqābala.jpg

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

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

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

تعريف رسمي[عدل]

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

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

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

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

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

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

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

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

<-! إذا قمت بتغيير عنوان هذا البند، برنامج الكمبيوتر وصلات هنا. ->

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

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

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

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

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

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

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

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

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

ويمكن التعبير عن الخوارزميات في العديد من أنواع التدوينات، بما في ذلك اللغة الطبيعية و أشباه الكود، [[المخططات الانسيابية، دراكون-الرسم البياني و لغات البرمجة أو جداول التحكم (التي تتم معالجتها بواسطة المترجمين الفوريين). Natural language expressions of algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical algorithms. Pseudocode, flowcharts, drakon-charts and control tables are structured ways to express algorithms that avoid many of the ambiguities common in natural language statements. Programming languages are primarily intended for expressing algorithms in a form that can be executed by a computer, but are often used as a way to define or document algorithms.

There is a wide variety of representations possible and one can express a given Turing machine program as a sequence of machine tables (see more at finite state machine, state transition table and control table), as flowcharts and drakon-charts (see more at state diagram), or as a form of rudimentary machine code or assembly code called "sets of quadruples" (see more at Turing machine).

Representations of algorithms can be classed into three accepted levels of Turing machine description:[11]

1 High-level description
"...prose to describe an algorithm, ignoring the implementation details. At this level we do not need to mention how the machine manages its tape or head."
2 Implementation description
"...prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level we do not give details of states or transition function."
3 Formal description
Most detailed, "lowest level", gives the Turing machine's "state table".

For an example of the simple algorithm "Add m+n" described in all three levels, see Algorithm examples.

تمثيلها[عدل]

خريطة انسيابية تمثل خوارزم إقليدس لحساب القاسم الأكبر المشترك (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

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

أمثلة[عدل]

مثال الترتيب[عدل]

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

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

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

خوارزم إقليدس[عدل]

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

برنامج بسيط لمحاكاة خوارزم إقليدس[عدل]

المثال التالي بلغة بيسك يمثل برنامجاً بسيطاً على خوارزم اقليدس.

   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 مرة. أثر هذا التسريع إلى تمكين الأجهزة الحاسوبية المحمولة (فضلا عن غيرها من الأجهزة) من استهلاك طاقة أقل[15].

مصادر[عدل]

  1. ^ Stone 1973:4
  2. ^ Stone يتطلب ببساطة أنه "يجب أن تنتهي في عدد محدود من الخطوات" (Stone 1973:7–8).
  3. ^ Boolos and Jeffrey 1974,1999:19
  4. ^ cf Stone 1972:5
  5. ^ Knuth 1973:7 states: "في الواقع نحن لا نريد فقط الخوارزميات، بل نحن نريد خوارزميات جيدة... معيار واحد من الخير هو طول الوقت الذي يستغرقه أداء الخوارزمية... other criteria are the adaptability of the algorithm to computers, its simplicity and elegance, etc."
  6. ^ cf Stone 1973:6
  7. ^ Stone 1973:7–8 تنص على أنه يجب أن يكون هناك، حالات فعالة "...إجراء من شأنه أن الروبوت [أي كمبيوتر] يمكنع اتباعها من أجل تحديد بدقة كيفية الانصياع لتعليمات. "Stone يضيف محدودية العملية, والوضوح (عدم وجود غموض في التعليمات) لهذا التعريف.
  8. ^ Knuth, loc. cit
  9. ^ Minsky 1967:105
  10. ^ Gurevich 2000:1, 3
  11. ^ Sipser 2006:157
  12. ^ Heath 1908:300; Hawking’s Dover 2005 edition derives from Heath.
  13. ^ " '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
  14. ^ 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).
  15. ^ 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