خوارزمية

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

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

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

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

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

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

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

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

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

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

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

مصادر[عدل]

  1. ^ Heath 1908:300; Hawking’s Dover 2005 edition derives from Heath.
  2. ^ " '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
  3. ^ 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).
  4. ^ 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