الخوارزميات

الخوارزميات (Algorithmique)

 

تعريف الخوارزمية

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

التسلسل  (Sequential) والاختيار (Selection) والتكرار( Repetition).

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

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

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

وهناك مثال نمطى لخوارزمية هو خوارزمية إقليدس لتحديد الحد الأقصى للقاسم المشترك لعددين.

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

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

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

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

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

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

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

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

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

وهناك مجموعة وعناصر من القيود والممانعات على نوع العمليات التي يمكن أن تتضمن وتحيط الخوارزمية وهي التالي:

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

إن أنظمة التشغيل في الكمبيوتر هي من التطبيقات المباشرة على الخوارزميات .

ونجد أن هذه النظم هي البرمجيات و الإجراءات الحسابية التي تتكون من مجموعة محدودة من الخطوات .

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

التركيبات المستخدمة في الخوارزميات هي:

• if-then-else
• for / end for
• while / end while
• repeat / until

ويمكننا خلط شبه الكود هذا مع مفردات الإنجليزية أو العربية عند الضرورة

ما المقصود بتحليل الخوارزميات؟

هو تحليل كفاءة الخوارزمية وتحسينها، و يوجد مقياسين لذلك هما :

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

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

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

الكُتاب الذين يؤكدون هذه الأطروحة يشملون منسكي  (1967)، سافاج (1987) وجورفيتش   (2000)

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

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

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

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

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

" أسفل"، وهي الفكرة التي توصف رسميا من قبل أكثر تدفق عناصر التحكم.

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

(Imperative Programming)  هذا هو المفهوم الأكثر شيوعا، ومحاولات وصف المهمة في وسائل منفصلة، "ميكانيكية". فريدة من نوعها لهذا المفهوم من الخوارزميات رسميا هو (Assignment Operation) ، وتحديد قيمة المتغير. أنه مستمد من الحدس من "الذاكرة" باعتبارها (Scratchpad)  .

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

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

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

• خرائط الانسياب: هو تمثيل مصور للخوارزمية يوضح خطوات حل المشكلة من البداية إلى النهاية مع إخفاء التفاصيل لإعطاء الصورة العامة للحل. و يمكن تصنيفها إلى أصناف أربعة هي:
  • مخططات سير العمليات التتابعية (Sequential Flowcharts).
  • مخططات سير العمليات ذات التفرع (Branched Flowcharts).
  • مخططات سير العمليات ذات التكرار والدوران (Loop Flowcharts).
  • مخططات سير العمليات ذات الاختيار (Selection Flowcharts).

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

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

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

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

• هناك أربعة طرق يستعان بها في الخوارزم البرمجي هي:
  • التكرار (Looping) :وتمكننا من حساب الأشياء المعقدة بطريقة سهلة عن طريق التكرار 
  • التفرع (Branching) :وتمكننا من ادخال معادلات معقدة للحاسوب ليقوم بمعالجتها بطريقة آلية.
  • الاختيار (Selection) :فائدة هذه الخاصية تظهر خاصة في ترتيب اعداد بطريقة تنازلية او العكس.
  • التتابع (Sequence) :تتابع الاوامر حيث ينفذها جهاز الحاسوب حسب الترتيب     

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

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

أشهر التطبيقات التي تدخل فيها الخوارزميات

تدخل الخوارزميات في تطبيقات كثيرة متنوعة وغاية في الأهمية، نسرد فيما يلي بعضها:

• الخارطة الجينية للإنسان (Human Genome Project) : يهدف هذا المشروع إلى تحديد أكثر من 100000 جين وراثي تُشكل الحمض النووي DNA، بالإضافة إلى تحديد ما يقارب 3 مليارات من الأزواج الكيميائية التي تكوِّن السلسلة الوراثية. إذاً، لدينا كم هائل من البيانات نحتاج لتخزينها ومعالجتها، وهنا يأتي دور الخوارزميات في تطوير تطبيقات وأدوات تحليل تُمكِّن العلماء من إجراء دراسات معمقة في زمن قصير نسبياً.
• تصفح الانترنت (Internet Surfing) : في وقتنا الحالي يوجد عدد كبير من مستخدمي شبكة الإنترنت، وهم يحصلون في كل لحظة على كم كبير جداً من المعلومات. فكيف يتم تأمين دخول هذا العدد الكبير من الزبائن وتأمين المعلومات لهم.. لهذا الغرض تمَّ تطوير ما يسمى بالخوارزميات الذكية، تلك المسؤولة عن عملية تخزين وتحصيل المعلومات بشكل سريع، وكمثال على هذه الخوارزميات: خوارزميات البحث المتوفرة ضمن محركات البحث وأشهرها محرك بحث Google.
• التجارة الإلكترونية  (Electronic Commerce) : تؤمِّن مجموعة من الخدمات الجيدة القابلة للتفاوض والتبادل بشكل إلكتروني، فرضت هذه الخدمات تأمين حماية بعض المعلومات الشخصية مثل: اسم المستخدم، كلمة المرور، رقم بطاقة الائتمان، الحسابات المصرفية وغيرها. مما أدى إلى تطوير خوارزميات التشفير والتوقيع الرقمي(Digital Signature)

بشكل عام، فإنّ أي مسألة حسابية ليس لها حل وحيد وحسب، وإنما عدد لا نهائي من الحلول، بمعنى أنّه يوجد لدينا عدد لا بأس به من الخوارزميات، فكيف نختار الخوارزمية المناسبة للتطبيق؟

يتم الاختيار بحيث نحقق استغلالاً أمثلياًّ لموارد الحاسوب، فما هي هذه الموارد؟

أهم هذه الموارد هي: زمن المعالجة وحجم الذاكرة اللازمة لتنفيذ الخوارزمية.

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

https://www.facebook.com/Algorithmique.Programation