مقدمة في علم الخوارزميات
كل واحد منا ، بغض النظر عما إذا كان تخصصًا في علوم الكمبيوتر أم لا ، قد صادفنا مصطلح ALGORITHM. إذن الآن ، ماذا تعني هذه الكلمة بالضبط؟ اسمحوا لي أن أناقشها معك بطريقة مراوغة للغاية. سأبدأ في شرحه بمستوى الصفر ، ثم سأنتقل إلى مستوى المخضرم. نظرًا لكوني من خلفية أساسية في علوم الكمبيوتر ، فقد أتيحت لي هذه الفرصة لإعطائك لمحة عن عالم الخوارزميات وهياكل البيانات. لذا ، فلنبدأ بدون أي مقدمة رسمية أخرى.
عندما لم يكن هناك أجهزة كمبيوتر ، كان هناك Algos (اختصار للخوارزمية) ، وعندما يكون هناك أجهزة كمبيوتر ، يكون هناك المزيد من الخوارزميات.
الخوارزميات ليست سوى ترتيب مناسب للإرشادات التي تساعد إطار عمل أو فردًا على كسر المشكلات وفحصها جزءًا تلو الآخر ثم بناء العديد من الاتجاهات العددية لمعالجة هذه المشكلات. عند هذه النقطة ، افهم هذه الحقيقة القائلة بأن الخوارزميات وبناء الأساس المنطقي هي أم كل الرياضيات الحالية. مع بداية أسلوب معين لتسوية قضية ما ، ظهرت أسباب منطقية ، ومع بداية المبررات ، ظهرت الخوارزميات. عندما ظهرت الخوارزميات ، ظهرت لهجات رسمية لرعاية مثل هذه القضايا بمساعدة مشاريع تسمى لهجات البرمجة في هذا اليوم وهذا العصر. شيء واحد يمكنك التفكير فيه هو أن الخوارزميات هي حجر الأساس لأي لغة برمجة. عندما تطبخ الخبز من الوصفة ، فأنت تتبع عملية حسابية. عندما تنسج سترة من مثال ، فأنت تتبع عملية حسابية. عندما تضع حدًا حادًا على قطعة صخرة عن طريق تنفيذ سلسلة متوالية من الضربات بنهاية الشق - وهو تقدم حاسم في صناعة الأجهزة الحجرية الجميلة - فأنت تتبع عملية حسابية. كانت الخوارزميات جزءًا من الابتكار البشري منذ عصر العصر الحجري.
بالنظر إلى نطاق واسع من خلال عدسة علوم الكمبيوتر ، يمكن للخوارزميات أن تعلمنا عن طبيعة العقل البشري ، ومعنى العقلانية ، وأقدم سؤال على الإطلاق: كيف نعيش. إن فحص الإدراك لحل المشكلات الحسابية الأساسية التي تطرحها بيئتنا يمكن أن يغير تمامًا طريقة تفكيرنا في العقلانية البشرية.
إن الفكرة القائلة بأن دراسة الأعمال الداخلية لأجهزة الكمبيوتر قد تكشف عن كيفية التفكير واتخاذ القرار ، وما يجب تصديقه وكيفية التصرف ، قد تصيب الكثير من الناس على أنها ليست مختزلة بشكل كبير فحسب ، بل مضللة في الواقع. حتى لو كان لعلوم الكمبيوتر أشياء تقولها حول كيفية التفكير والتصرف ، فهل نريد الاستماع؟ نحن ننظر إلى الذكاء الاصطناعي وروبوتات الخيال العلمي ، ويبدو أن حياتهم ليست حياة يرغب أي منا في أن يعيشها. قام آلان تورينج (أحد أعظم علوم الكمبيوتر ، والذي غالبًا ما يُطلق عليه بشكل غير رسمي باسم نيوتن في علوم الكمبيوتر) بتعريف فكرة الحساب من خلال تشبيه لعالم رياضيات بشري يعمل بعناية من خلال خطوات عملية حسابية مطولة ، مما ينتج عنه إجابة صحيحة لا لبس فيها. يقول الكثير من الناس أن دراسة الخوارزميات تشبه إلى حد ما تعلم البرمجة ، وغالبًا ما يشيرون إلى الخوارزمية على أنها كود زائف. نعم ، هذا صحيح إلى حد ما ، لكن دراسة الخوارزميات ليست مثل تعلم كتابة الكود. تعلم كتابة خوارزمية يعني أنك وضعت أساس الكود ، والآن ناطحة السحاب (الكود الخاص بنا) جاهزة للتنفيذ. أيضًا ، هناك أسطورة شائعة بين معظم الشباب الذين يدرسون علوم الكمبيوتر في الوقت الحاضر. إنهم يميلون إلى الاعتقاد بأن "التشفير هو علم الكمبيوتر". إذا حاول شخص ما أن يقول إن علوم الكمبيوتر تدور حول البرمجة ، من فضلك لا تصدقه / تصدقها. إنها أسطورة. يهتم جزء من علوم الكمبيوتر بالبرمجة ، لكن علوم الكمبيوتر لها علاقة بالرياضيات والمنطق أكثر من البرمجة.
شراء عنصر واجهة المستخدم من المتجر تحكمه الديناميكيات التي يصفها علم الاقتصاد. يمكننا استخدام علم الاقتصاد للإجابة على أسئلة مثل "لماذا تم تسعير الأداة كما هي؟" أو "لماذا يخزن هذا المتجر عناصر واجهة المستخدم في المقام الأول؟" لكن من المبالغة القول إن المشاركة في الاقتصاد تؤدي إلى الاقتصاد. وبالمثل ، عندما تقوم بإدخال رمز في جهاز الكمبيوتر الخاص بك ، فإن الطريقة التي يأخذ بها المترجم أو المترجم الشفوي الشفرة التي كتبتها ويقوم بالأشياء باستخدامها هي علوم الكمبيوتر. في بعض الأحيان يتم تخزين المتغيرات الرقمية في التعليمات البرمجية الخاصة بك كنقاط عائمة ، وفي بعض الأحيان تلك النقاط العائمة التي يجب أن تكون مكافئة ظاهريًا لا تكون مكافئة ؛ يتم شرح السبب من خلال علوم الكمبيوتر. لكن هذا لا يعني أن البرمجة هي علوم الكمبيوتر. الآن ، دعونا نستكشف المزيد في عالم الخوارزميات.
إعداد بيئة العمل
والآن بعد أن أصبح من الواضح أن الخوارزميات مهمة جدًا في حياتنا لحل المشكلات عمليًا ، سأقدم لك بعض الأمثلة العملية لمساعدتك على فهم أهمية الخوارزميات أكثر. إذا كنت تعتقد أن تعلم الخوارزميات لن يساعدك إلا في اجتياز امتحانات الجامعة ، ففكر مرة أخرى. الخوارزميات هي مثل هذه الأشياء التي تشارك في حياتنا اليومية بطريقة أخرى. لتوضيح الأمر بشكل أكبر ، ضع في اعتبارك الحالات التالية.
1. إذا افترضنا أنك بحاجة إلى استئجار منزل ، وبالتالي ، تبدأ في التحقيق في منزلين للتحقق مما إذا كان ذلك مناسبًا لك. بعد التحقق من عدد قليل من المنازل ، تجد أن أيا منها ليس مناسبًا لك. الآن يظهر الاستفسار ، هل من المستحسن أن تفكر في حجز منزل من المنازل التي قمت بالتحقيق فيها للتو ، أم أنك ستستغرق بعض الوقت الإضافي وتحقق من المزيد من المنازل؟ هذه مشكلة شديدة قد ينظر إليها أي فرد عادي في مرحلة ما من حياته. قد يتم النظر في هذه المشكلة بطريقة أخرى أيضًا ، لنفترض أنك تبحث عن تطابق معقول مع حفل زفاف. في الوقت الحالي ، هل سيكون من الجيد بالنسبة لك أن تقضي كل وقتك على الأرض في البحث عن التطابق المثالي؟
أو من ناحية أخرى ، هناك إنهاء للتحقيق. إذا كانت هناك نهاية ، في هذه المرحلة ، ما هي هذه النهاية؟ كيف يمكنك أن تدرك أن فرصتها الآن للتخلي عن البحث والتسوية مع أي من التطابقات المعقولة التي قمت بالتحقيق فيها حتى الآن؟ وهكذا ، ها هو الرد على هذا الاستفسار. هذا ، فيما يتعلق بهندسة البرمجيات ، يسمى EXPLORE EXPLOIT DILEMMA. بهذه الطريقة ، تعتمد حياتنا كلها على التحقيق في إساءة استخدام الترتيبات المعقدة. تذهب إلى أي متجر وتحاول شراء بعض السراويل. هل ستكون فكرة جيدة أن تستقر في أعقاب محاولة مجموعتين ، والحصول على واحدة على المدى الطويل ، أم أنها فكرة جيدة بالنسبة لك للتحقيق في المزيد من الخيارات لتحسين واحدة؟
الإجابة بسيطة ، يجب أن تستكشف بدقة ما يصل إلى 37٪ من إجمالي الاحتمالات ، وبعد ذلك يجب أن تفكر في تسوية (استغلال تقنيًا) مع الخيارات التي تم استكشافها بالفعل دون إضاعة المزيد من الوقت على أمل الحصول على خيار أفضل. (جاء هذا 37٪ من قيمة 1 / e ، وأنا لا أدخل في اشتقاق هذا الحل لأنه تقني للغاية ، وقد يكون خارج نطاق القارئ العادي). لذلك ، في المرة القادمة التي تشعر فيها بالحيرة فيما إذا كان عليك البحث عن المزيد من التطابقات للزواج أو محاولة استغلال الخيارات التي تم تحديدها بالفعل ، تأكد من أنه إذا كان لديك عشرة خاطبين محتملين ، فجرّب أربعة من الخاطبين بالضبط (حوالي 37٪ من 10 ، تقريبًا) إلى أقرب عدد صحيح) المواعدة ، ثم تسوية مع شخص ما بينهم. وهذا ينطبق على جميع مجالات الحياة ، وقد ثبت بالبحث أنه يعطي أفضل النتائج.
2. عندما يكون لديك مساحة محدودة داخل الحقيبة ، فأنت داخل مجمع تسوق حيث يكلف كل عنصر نفس المبلغ. يُطلب منك اختيار حقيبة مليئة بالعناصر. حتى الآن ، كيف يجب أن تختار العناصر؟ كيف يجب أن تقرر أيهما تختار وكميته ، بحيث يمكنك الحصول على أقصى فائدة من العرض؟
تم شرح هذه المشكلة بشكل جميل من قبل Cryptographers Ralph Merkle و Martin Hellman في عام 1978. وهذا ما يسمى بمشكلة KNAPSACK. يخبرك أنه عندما يكون لديك حقيبة أو حاوية ثابتة و n كائنات مختلفة ذات قيم مختلفة ، كيف يجب أن تخطط لأخذ هذه العناصر ومقدار الكمية بحيث يكون ربحك الحد الأقصى.
3. النظر في الحالة التالية. تريد زيارة عمك الذي يبقى بعيدًا قليلاً عن مدينتك. تحتاج إلى شراء بعض الحليب لكلبك. أنت بحاجة لزيارة المعبد أثناء العودة. لديك قائمة بقالة لأخذ بعض السلع لمنزلك. إذن ، سؤالي هو ، كيف تخطط لزيارتك لكل مكان والعودة إلى منزلك ، وعند القيام بذلك ، يجب أن يكون استهلاكك للوقود هو الحد الأدنى؟ تم شرح ذلك من خلال خوارزمية Christofides-Serdyukov لحل مشكلة البائع المتجول. في الأصل ، يتعين على البائع زيارة مدن مختلفة "n" وعليه العودة إلى مسقط رأسه بأقل تكلفة. يمكنك تطبيقه في أي مجال من مجالات الحياة.
4. الآن ضع في اعتبارك حقيقة أن لديك خمس وظائف لأداءها ، وكل واحدة لها نفس الأهمية. كيف ستبدأ في عمل كل واحد منهم؟ هل يجب أن تبدأ بأقصر وظيفة أولاً (SJF ALGORITHM) ، أم ينبغي عليك تولي المهمة الأكثر ثقلاً أولاً؟ (LJF ALGORITHM) أم يجب أن تحاول عمل كل واحد منهم لفترة زمنية محددة ، وبهذه الطريقة ، إنهاء كل شيء على أقساط؟ (ROUND ROBBIN ALGORITHM) في علوم الكمبيوتر ، لدينا شيء يسمى جدولة الخوارزمية. هناك العديد من الخوارزميات لجدولة عمليات وحدة المعالجة المركزية ، وكل واحدة منها ضرورية للتنفيذ في الحياة الواقعية. تعتمد خوارزمية جدولة المهام عادةً على الخوارزميات الجينية (GA) لتخصيص وإنفاذ المهام الخاصة بالتطبيق. يسعى استخدام الخوارزمية الجينية لتوزيع المهام والجداول إلى مزيد من الاهتمام من العلماء. لحل صعوبة جدولة الموارد في أنظمة المجموعات غير الخطية واسعة النطاق وحققت تأثيرات مثالية ، تم تطبيق GA على نطاق واسع. الاستفادة المعقولة من موارد الحوسبة التي تخلق إجمالي ومتوسط الوقت لإكمال مهمة أقصر وأصغر تكلف مشكلة مهمة. نظرات البحث التي يمكن أن تحقق الأساليب الاصطناعية المزيد من موازنة الحمل المثلى من الأساليب التقليدية.
5. قطعت الخوارزميات طريقًا طويلاً لتصل إلى المرحلة التي نحن فيها اليوم. لا يزال التحليل الخوارزمي في العصر الحديث ينمو ويتوسع بسرعة. نظرًا لأن المزيد والمزيد من الشركات أصبحت تعتمد على البيانات ، فإن خوارزميات التعلم الآلي تكتسب أهمية أكبر. تستند معظم القرارات التي يتم اتخاذها اليوم إلى البيانات. يقولون إن "البيانات" هي نفط القرن الحادي والعشرين ، وهي حقيقة. تبذل معظم الصناعات الآن جهودًا لأتمتة عملياتها باستخدام تقنيات مثل رؤية الكمبيوتر ، والتي تساعد الكمبيوتر على عرض أي كائن وجمع البيانات الأساسية للمعالجة. يقرر الذكاء الاصطناعي ما يجب فعله بعد ذلك ، ويعلم التعلم الآلي أجهزة الكمبيوتر كيفية اتخاذ القرار الذكي من البيانات المعالجة. هناك الكثير من المشاريع عالية التقنية مثل هايبرلوب وسيارات تسلا الأوتوماتيكية والمزيد. يتمتع القطاع الصحي بتطبيقات ذكاء اصطناعي جيدة للغاية حيث يمكن للآلة في الوقت الحاضر تتبع ما إذا كانت بعض الخلايا التالفة سرطانية أم لا. بصراحة ، حصلت الصناعة الطبية وقطاع الرعاية الصحية على معظم فوائد الذكاء الآلي في الوقت الحاضر. تم التحكم في تحليل الجرائم الإلكترونية والكشف عن الاحتيال.
6. كان هناك وقت بدأ فيه الناس في تطوير الحاجة إلى أجهزة الكمبيوتر ، والتي يمكن تدريبها باستخدام نوع معين من الخوارزميات ، تسمى خوارزميات التعلم العميق. عندما بدأ التدريب على الكمبيوتر لأول مرة ، اعتدنا تدريبهم بمساعدة مجموعات البيانات الكبيرة. كان لدينا مجموعات بيانات لتدريب أجهزة الكمبيوتر على مفاهيم مختلفة. لنفترض أنه يتعين علينا تحديد الأبجدية "P". إذا كان هناك 100 طريقة مختلفة لكتابة "P" ، فقد تم تدريب الكمبيوتر على تحديده على أنه الحرف "P". لكن في النهاية ، أدركنا أنه بغض النظر عن حجم مجموعة البيانات ، فهناك احتمالات ألا يفسر الكمبيوتر الحرف. نظرًا لأن القوة الحسابية والفضاء الحسابي موردان محدودان (ليس لدينا جهاز كمبيوتر بسرعة معالجة غير محدودة وذاكرة وصول عشوائي غير محدودة) ولتدريب آلة على نمط معقد ، فقد احتجنا إلى مساحة أكبر. لهذا السبب بدأنا في استكشاف طرق جديدة لتدريب الآلة ، حيث ستكون الآلة ، مع مجموعة من الإرشادات ، قادرة على تدريب نفسها دون تدخل بشري فعلي. تم اقتراح الشبكات العصبية لأول مرة في عام 1944 من قبل وارن ماكولوغ ووالتر بيتس ، وهما باحثان من جامعة شيكاغو وانتقلوا إلى معهد ماساتشوستس للتكنولوجيا في عام 1952 كأعضاء مؤسسين لما يسمى أحيانًا أول قسم للعلوم الإدراكية. كان نفس القدر من الأبحاث جاريًا في الاتحاد السوفيتي. في النهاية ، طور عالم الرياضيات الروسي أليكسي إيفاخنينكو ، في منتصف الستينيات ، تقنية نسميها في عصرنا اليوم الشبكة العصبية الاصطناعية (ANN). يوحي الاسم نفسه ، أن فكرته مأخوذة من خلايا الدماغ والشبكة العصبية التي بناها الله في أجسادنا.
مستقبل وظيفي لدراسة الخوارزمية وهياكل البيانات
يجب أن يفكر الجميع في أنه لا بأس في جعل حياتنا اليومية أسهل كثيرًا من خلال دراسة الخوارزميات ، ولكن بعد ذلك ، كيف يمكن الخروج منها بمهنة؟ كيف يمكنني كسب لقمة العيش إذا اخترت دراسة الخوارزميات؟ ما هي الآفاق الوظيفية المتاحة لنا؟ اسمحوا لي أن أجيب على جميع أسئلتك واحدة تلو الأخرى.
يمكنك أن تصبح أكاديميًا جيدًا جدًا وباحثًا وبالطبع كلية علوم الكمبيوتر الأساسية.
توجد أماكن في صناعة يكون فيها البحث بحد ذاته نشاطًا حماسيًا بشكل خاص ، ويتم التعامل مع الباحثين باحترام شديد. هم "مختبرات" الصناعة المعروفة. قبل بضع سنوات ، كان الخمسة الكبار هم: Microsoft Labs و IBM Labs و Sun Labs و HP Labs و NOKIA labs. لقد كانوا أمثلة مشرقة لكيفية تضمين البحث في بيئة صناعية ، مما أدى إلى تطوير أحدث التقنيات مع التأثير الإيجابي أيضًا على أرباح الشركة. ولكن ، تم تحديدهم بوضوح من بقية الشركة وعملوا بشكل أساسي كقسم CS داخلي. كان أحد الأنشطة الأساسية لهذه المعامل هو "نقل التكنولوجيا" بحيث يمكن نشر الأشياء الرائعة التي توصلوا إليها إلى بقية الشركة.
أساسيات الخوارزميات
تكمن أساسيات الخوارزميات في حقيقة أننا نختار حل بيان المشكلة. في الأقسام القادمة ، سنرى كيف تساعدنا الأساليب المختلفة في تصميم خوارزميات كتابة مختلفة أهدافها النهائية هي نفسها ، للحصول على حل للمشكلة. لفهم أساسيات كتابة خوارزمية فعالة ، يجب أن نحتفظ ببعض النقاط في أذهاننا-
يجب أن تحتوي الخوارزمية على تعقيد أقل أو أقل من الفضاء الزمني.
يجب أن تكون الخوارزمية سهلة التأطير في رمز لأي لغة. يجب أن يتم تنفيذه بسهولة.
يجب أن يكون هناك نهج محدد جيدًا ، ويجب اتباع هذا النهج المعين في جميع أنحاء الخوارزمية. إذا كانت الخوارزمية تتبع نهجًا جشعًا ، فلا ينبغي أن تتحول إلى نهج آخر في منتصف الطريق. إذا لم يتم اتباع نهج واحد ، فهناك احتمالات في النهاية ، سيكون للحل تباين ، مما قد يؤدي إلى نتائج غير صحيحة.
مع وضع هذه النقاط في الاعتبار ، دعونا نرى ما هو النهج الأساسي لبناء الخوارزمية.
تحليل مقارب
قبل المجيء إلى تحليل التقارب ، أود مناقشة تعقيد الزمان والمكان. غالبًا ما يستخدم هذا المصطلح في أي برنامج كمبيوتر أو أي خوارزمية. ماذا يفعل عادة؟ هذا يعني ، في حالة محدودة الوقت (حيث ينتظر المستخدم الحصول على الرد) ، ومساحة محدودة (حيث لدينا ذاكرة وصول عشوائي محدودة وقرص صلب) ، نحتاج إلى استخدام الموارد الحسابية بعناية فائقة.
ومن ثم ، نحتاج إلى التحقق من مقدار استهلاك هذه الموارد. لذلك ، إذا كان البرنامج يستهلك الكثير من هذه الموارد ، فيجب أن نحاول معرفة (إن أمكن) كيفية الحصول على الحل الأمثل لتقليل تعقيد المكان والزمان. تعقيد الزمان والمكان هو مقايضة. يمكنك كتابة خوارزمية تحتوي على عدد أقل بكثير من الأسطر في الكود أثناء التنفيذ. بعد ذلك ، قد ينتج عن ذلك أن التعقيد الزمني ضخم (على سبيل المثال ، في حالة الوظائف المتكررة والبرامج المتكررة) ، بل من الممكن أنه مع القليل من التعقيد الزمني ، تأخذ الخوارزمية مساحة كبيرة جدًا (في حالة البرامج التكرارية) ، إذا كان عدد التكرارات كبيرًا جدًا ، فإن هذا الشيء ممكن تمامًا). لذلك ، نحن بحاجة إلى إيجاد توازن مثالي يجب ألا يستهلك الكثير من الوقت ولا يشغل مساحة كبيرة. لذلك ، هذا المفهوم المحدد يسمى تعقيد المكان والزمان. الآن قبل الانتقال إلى الموضوع التالي ، أود أن أخبركم بنقطة أساسية.
إذا وجدنا الحد الأعلى أو الحد الأدنى للخوارزمية ، فعادةً ما يكون ذلك بعد إدخال معين. قبل هذا الإدخال ، يمكن أن يكون لمنحنى الوظيفة أي تقلبات حتى تتجاوز الحد الأعلى وحتى أقل من الحد الأدنى. هذه القيمة المدخلة المعينة ، والتي يُشار إليها بالرمز N ، وبعد هذه القيمة المدخلة ، سيبدأ حسابنا الرئيسي. نظرًا لأن الخوارزميات لها التقلبات الرئيسية في القيم الأولية ، فإن N هي قيمة إدخال في نطاق بداية المدخلات. بعد ذلك ، عندما يكون المنحنى مستقرًا نوعًا ما ، نطبق جميع المفاهيم لإيجاد الحد الأعلى والحد الأدنى.
لكل كمية ، عادة ما يكون لدينا حد أعلى وحد أدنى واحد. بغض النظر عن أي شيء ، فإننا كبشر نميل إلى معرفة النطاق الذي تكمن فيه أي كمية. يوجد حد أقصى لتقديرات الربح في أي نشاط تجاري وأقصى معدل تشغيل في مباراة لعبة الكريكيت. لذلك ، أجهزة الكمبيوتر ليست استثناء. عندما ينفذ الكمبيوتر أي مهمة ، فإننا نميل إلى الاعتقاد بأنه في أسوأ السيناريوهات ، ما هو الوقت الذي يستغرقه الكمبيوتر لإكمال المهمة المحددة. بهذا المعنى ، نحتاج إلى بعض المعلمات لتحديد الحد الأعلى والحد الأدنى (والذي من شأنه أن يدل على أفضل سيناريو للحالة). أيضًا ، ليس من المؤسف دائمًا أنه سيكون السيناريو الأسوأ ، كما أنه ليس من الأفضل دائمًا. من الناحية الفنية ، نحتاج إلى بعض الحالات التي من شأنها أن تخبرنا بسيناريو الحالة المتوسطة الذي سيخبرنا الكمبيوتر بخصوصه عن مقدار الوقت الذي سيحتاجه للحصول على المخرجات إذا كان الإدخال المعطى إلى حد ما بين إدخال أفضل حالة وإدخال أسوأ حالة . الآن ، لدينا معلمة أخرى يمكن استخدامها إذا أردنا إيجاد التعقيد الحسابي. لنبدأ واحدًا تلو الآخر لاستكشاف ماهية هذه المفاهيم وكيفية تنفيذها في كل حالة.
أفضل سيناريو للحالة - يُعرف هذا أيضًا باسم أوميغا كبيرة (Ω). يصف هذا الحد الأدنى لأي منحنى أداء. سيستغرق أفضل سيناريو للحالة أقل وقت لتنفيذ الوظيفة أو البرنامج. من خلال النظر إلى الحد الأدنى لمنحنى الأداء ، يمكن لعالم الكمبيوتر بسهولة تحديد الحد الأدنى من الوقت المطلوب عندما يسير كل شيء على ما يرام. سيعطي هذا فكرة واضحة ، أنه بخلاف ذلك ، لن يكون من الممكن تحسين الخوارزمية أو البرنامج بشكل أكبر. ولكن ، في سيناريو العالم الحقيقي ، تحدث أفضل الحالات بدرجة أقل بكثير. إنه ليس شيئًا يستخدم بكثرة في جميع الحالات.
سيناريو الحالة الأسوأ- هذا هو الحال عندما تكون المدخلات المعطاة معارضة تمامًا لتدفق عمل الخوارزمية. سيناريو الحالة الأسوأ ، عندما نحتاج إلى التفكير في أسوأ سيناريو ، إذا كانت جميع المدخلات طويلة ومعقدة وحتى معقدة ، فهل أمام الكمبيوتر أي خيار ليقول ، "هذا كثير جدًا ، أنا آسف لا أستطيع التعامل مع هذا! "، لا ، أليس كذلك؟ هذا يعني أنه بغض النظر عن عدد المدخلات المعقدة المقدمة ، ليس أمام الكمبيوتر خيار سوى تنفيذه. يبدو مثاليا؟ تمامًا مثل البشر ، عندما يُطلب منا حساب قيمة 2 + 2 ، يمكننا فعل ذلك في ثوانٍ ، ولكن بعد ذلك ، إذا كانت المدخلات المعطاة لنا ، لنفترض ، 1 + xn = 1 + nx1! + nn -1 × 22! + ... أين س = 6؟ بالتأكيد سوف يستغرق الأمر بضع دقائق على الأقل ، أو حتى أكثر من ذلك لتقييم الإجابة الدقيقة. لذلك ، يعتمد الوقت الحسابي والتعقيد الحسابي على مدى بساطة أو مدى تعقيد المدخلات التي أعطيت لنا. لذلك ، كما يقول المثل القديم ، استعد للأسوأ ، واستعد للأفضل. وبنفس الطريقة ، يقوم علماء الكمبيوتر بتقييم أسوأ سيناريو ، فقط للحصول على فكرة ، سواء كانت أسوأ حالة سيئة للغاية أم لا. في بعض الأحيان ، يكون السيناريو الأسوأ محبطًا للغاية ، وقد يستغرق الأمر بضعة أيام للحصول على النتائج ، نعم ، لا أمزح ، البرامج التي تحتوي على مساحة زمنية معقدة ، والمدخلات المقدمة طويلة جدًا ، ثم قد ينتج عنها في نوع من السيناريوهات المسدودة. حتى الآن ، يجب حساب السيناريو الأسوأ للحصول على التقدير. عادة ما يتم الإشارة إليه بواسطة O الكبير.
سيناريو الحالة المتوسطة - أخيرًا ، لدينا شيء يمكننا الرجوع إليه في معظم الاستخدامات الشائعة ، وهي ليست تقنية بدرجة عالية. عندما يسألك شخص ما عن مقدار الوقت المستغرق للوصول إلى مومباي من جوا ، فمن الواضح أننا نميل إلى تقديم تقدير متوسط. قد يكون أكثر إلى حد ما أو أقل إلى حد ما من ذلك. إذا لم تكن هناك حركة مرور ، فيمكننا الحصول على أفضل حالة. إذا كانت هناك حركة مرور مزدحمة ، فيمكن أن يكون لدينا أسوأ الحالات ، ولكن ماذا لو كانت هناك حركة مرور معتدلة إلى حد ما؟ إذن هنا تأتي المعلمة الأخيرة لدينا لحساب تعقيد المكان والزمان لأي خوارزمية. يُشار إلى هذا بواسطة ثيتا الكبيرة (Ө). في بعض الأحيان ، عندما تكون هناك مشاكل صعبة ، مما يعني أنه لا يوجد حل معين لبيان المشكلة المحدد. هناك العديد من الحلول الممكنة. هذا هو السبب في أنها تسمى مشاكل غير حتمية وغير متعددة الحدود. لذلك في هذه الحالات ، من الواضح أن أسوأ وقت يمكن أن يسبب لك صدمة ، وأفضل حالة أيضًا لا تعمل في كل مرة لأن مدخلات الحالة المثلى أقل احتمالية للحدوث ، وبالتالي ، فإن هذا الترميز مفيد بشكل خاص لـ NP - حالات المشاكل الصعبة.
أمثلة على التحليل المقارب:
لنفترض أن خوارزمية البحث الشائعة جدًا هي البحث الثنائي.
في البحث الثنائي ، يتم إجراء البحث عن طريق تقسيم المصفوفة إلى جزأين ، وإيجاد العنصر الأوسط ، ثم البحث في كل نصف عن العنصر الأساسي أو العنصر الهدف. الآن ، دعنا نتحقق مما يمكن أن يكون أفضل سيناريو وما يمكن أن يكون السيناريو الأسوأ لهذه الحالة.
أفضل سيناريو-
إذا كان العنصر الذي يجب العثور عليه في الموضع الأوسط بالفعل ، فلا داعي لإجراء المزيد من العمليات الأخرى. إنه مؤشر واضح على أننا وصلنا إلى الهدف ، وبالتالي سيتوقف تنفيذ البرنامج ، وسيقوم المترجم بطباعة النتيجة. لذلك ، في هذه الحالة ، إذا قمنا بتحليل تعقيد المكان والزمان ، فسيكون ذلك تكرارًا واحدًا فقط ، حيث نقوم فقط بتقسيم المصفوفة إلى قسمين ، وسيستغرق الأمر وقتًا ثابتًا فقط. إذن فهو 0 (1).
السيناريو الأسوأ-
في أسوأ السيناريوهات ، قد يكون العنصر موجودًا في الزاوية ولا يمكن تتبعه إلا إذا واصلنا تضييق المصفوفة الرئيسية عن طريق تقسيمها إلى نصفين. بنهاية البحث ، سيكون لها التعقيد الزمني لـ log (n) ، حيث n هو العدد الإجمالي للعناصر الموجودة في المصفوفة.
سيناريو الحالة المتوسطة-
في الحالة المتوسطة ، هو متوسط أفضل حالة وأسوأ حالة. لذا فإن متوسط تعقيد الوقت هو 0 (log (n)).
الخوارزميات الجشعة
إنها فئة من الخوارزميات توفر حلولًا فعالة للغاية لبعض مشاكل الحياة الواقعية. دعونا نرى ما هو وكيف يعمل. لذلك ، كما يوحي الاسم نفسه ، جشع ، مما يعني أن لديه دائمًا بعض النية لتعظيم معلمة معينة تسمى الربح. بمصطلح الربح ، لا أقصد أنه شيء متعلق بالمال أو الثروة. في علوم الكمبيوتر ، يشير تعظيم الربح إلى أنه عندما نحل مشكلة معينة ، فإننا نريد تحسين أي شخص ، أو ربما اثنين أو في بعض الأحيان أكثر من المعلمات والحصول على أفضل النتائج. دعونا نفهم هذه النقطة أولاً. في نهج الخوارزمية الجشع ، يتم حل المشكلة الفرعية المباشرة أولاً بهدف أو هدف تعظيمها إلى أقصى حد أو إيجاد الحل الأمثل الذي يمكن تحقيقه على الإطلاق لهذه المشكلة الفرعية المعينة. مرة أخرى ، في الجزء التالي من المشكلة الفرعية ، سيكون الهدف الوحيد للبرنامج هو الحصول على أفضل نتيجة ممكنة للحصول على الأفضل. وستستمر هذه العملية حتى يتم حل المشكلة برمتها عن طريق حل جميع الأجزاء الفرعية إلى الأفضل. يمكن اعتبار حل كل جزء فرعي هو الحل الأمثل المحلي. عندما يتم جمع عدة أوبتيما محلية معًا ، يتم تجميعها جميعًا معًا في حل عالمي أمثل واحد ، وهو الحل النهائي لدينا في بيان المشكلة المحدد.
أمثلة على الخوارزميات الجشعة ، دراسة حالة موجزة:
لنأخذ بعض الخوارزميات الجشعة الشهيرة لفهم هذا المفهوم بشكل أفضل-
1. 0/1 حقيبة ظهر أو مشكلة حقيبة كسور
هذه هي المشكلة التي واجهناها عدة مرات. تساءل الكثير من الناس عما إذا كان هناك أي حل ممكن لهذه المشكلة. بيان المشكلة هو ، "لقد أعطيت كائنات معينة لها أوزان معينة ، ولكل منها قيم معينة. الآن ، لديك كيس يُشار إليه على أنه حقيبة ظهر في المشكلة ، بسعة ثابتة. الآن ، ما هي الكمية ، كل شيء يجب أن يؤخذ في الحقيبة بحيث يكون لديك أقصى فائدة. "
يمكن التفكير في هذه المشكلة بالذات لأن لديك راتبًا ثابتًا ، وذهبت للتسوق ، وعليك شراء أشياء معينة لمنزلك. كيف ستقوم بالتسوق بحيث يتم أخذ جميع العناصر ، وتستفيد أكثر من غيرها. تبدو مثيرة للاهتمام ، أليس كذلك؟ يتم حل هذه المشكلة باستخدام نهج جشع عن طريق أخذ نسبة الربح / السعر (الوزن) ثم ملء تلك العناصر أولاً في الكيس ، الذي يحتوي على هذه النسبة الأعلى. الأعلى التالي ثم الأعلى التالي وهكذا حتى يمتلئ الكيس ولا توجد مساحة لأخذ أي شيء.
2. خوارزمية Djikstras
هذه خوارزمية أخرى مشهورة جدًا ، والتي قامت بحساب أقصر مسافة في أي شجرة ممتدة دنيا. سيؤدي ذلك إلى تقليل تكلفة الانتقال من إحدى عقدة الرسم البياني إلى العقدة الأخرى في الرسم البياني ثم حساب أقل تكلفة للسفر إلى الوجهة.
3. خوارزمية بريمس
هذا يعثر على الحد الأدنى من الشجرة الممتدة عند إعطاء أي شجرة ممتدة. هذا مفيد للغاية حيث يتم استخدام الأشجار الممتدة على نطاق واسع لأغراض فنية مختلفة في علوم الكمبيوتر الأساسية.
4. خوارزمية Kruskals
تعد خوارزمية Kruskal أيضًا مثالًا رائعًا لخوارزمية جشعة ، وستقوم أيضًا بإنشاء شجرة ممتدة بحد أدنى من رسم بياني معين أو شجرة ممتدة عن طريق اختيار حافة واحدة في كل مرة وبذل قصارى جهدها في هذا الوقت المحدد ، وبالتالي تعظيم الربح .
هذه بعض الخوارزميات الجشعة الشهيرة. لذلك يجب أن تفكر ، ما فائدة استخدام الخوارزميات الجشعة؟
عدد قليل جدًا من المفاضلات ، مما يجعلها مثالية لأي تقنيات تحسين.
يعطي أفضل حل ممكن بسرعة كبيرة ، دون أي مضاعفات.
في مبادئ الشبكات ، هناك العديد من البروتوكولات ، مثل OSPF ، وعدد قليل من البروتوكولات الأخرى ، تستخدم الخوارزميات الجشعة للتأكد من أن الحزم تقضي الحد الأدنى من الوقت في الشبكة.
نهج فرق تسد: نظرة ثاقبة
لذا تبدأ أساسيات الخوارزميات بكيفية تلخيص بيان المشكلة ثم كتابة مجموعة من التعليمات للبدء. كيف نلخص مشكلتنا؟ هناك العديد من الطرق للقيام بذلك. أول شيء وقبل كل شيء هو تقسيم المشكلة إلى عدد قليل من المشاكل الفرعية ، ثم العمل بشكل مستقل على كل مشكلة فرعية للحصول على نتيجة لكل جزء. وعندما يتم حل جميع الأجزاء الفرعية بشكل مستقل ، حاول تلخيص الكل. وهذا ما يسمى بإستراتيجية فرق تسد. لفهمه بشكل أفضل ، هذه هي الطريقة نفسها التي ساعدت القوى الاستعمارية على حكم بلادنا. الوقوف متحدين يجعل من الصعب تحقيق الأهداف. وبالمثل ، يرى أخصائي الخوارزمية أولاً ما إذا كان يمكن تصنيف المشكلة إلى مجموعة من المشكلات الفرعية الأخرى. الآن ، اعتمادًا على أسلوب تلخيص حلول المشكلات الفرعية ، لدينا نوعان مختلفان من التقنيات مرة أخرى:
نهج من أعلى إلى أسفل
يُشار إلى هذا غالبًا باسم نهج الوظيفة العودية. نأخذ الشرط النهائي ثم نكتب بعض المعادلات الرياضية تسمى الدوال العودية للوصول إلى أساس الوظيفة. قد يسأل شخص ما في هذه الحالة كيف سنعرف متى نوقف المعادلة العودية؟ الجواب بسيط: هناك شرط أساسي في كل مشكلة. نحن بحاجة إلى التوقف عند الحالة الأساسية. ومن ثم نحل المشكلة كاملة. لفهم المشكلة ، دعنا نأخذ سلسلة فيبوناتشي إيجابية. ثم نعلم جميعًا أن متتالية فيبوناتشي الموجبة غير محددة للأرقام السالبة. ومن ثم ، فإن الشرط الأساسي سيكون الحد 0 والمصطلح الأول. نظرًا لأننا نحسب الحد n ، فإننا نكتب معادلات متكررة حتى نصل إلى آخر حدين ، وهما الحد 0 والحد الأول ، وهو الشرط الأساسي.
النهج التصاعدي
هذا يعني أننا نكتب معادلات تكرارية ، عادةً لتجنب كتابة وظائف متكررة ، والتي سأشرح سبب القيام بذلك بشكل أكبر. اعتبارًا من الآن ، نأخذ مثالًا واحدًا أو ، من الناحية الفنية ، وحدة نمطية ، ونكتب حلقة أو بعض العبارات التكرارية ، وبعد ذلك كما نعلم الحد الذي تصل إليه المشكلة الفرعية ، نقوم بتشغيل الحلقة التكرارية حتى هذا الحد إلى احصل على حل كامل للمشكلة. لذلك ، بهذه الطريقة ، يتم حل هدفنا.
الآن ، بالعودة إلى المشكلة الرئيسية ، لماذا نتردد في استخدام الدالة العودية ما لم يكن هناك خيار آخر؟ لذا فإن الإجابة هي ، عندما نكتب معادلة تكرارية ، نحتاج إلى بنية بيانات معينة تسمى المكدس (الذي سنراه لاحقًا) للحفاظ على وتخزين جميع قيم كل معادلة متكررة. لذلك ، بهذه الطريقة ، فإننا ننتج متطلبات مساحة إضافية ، والتي ستؤدي إلى مزيد من التعقيد في الفضاء. ومن ثم ، فمن المستحسن دائمًا محاولة استخدام التنفيذ التكراري للخوارزميات ما لم يكن ذلك ضروريًا للغاية. الآن ، دعنا نرى كيف نحصل على فكرة ، وكم من الوقت والمساحة التي ستستغرقها خوارزمية معينة أثناء تنفيذنا لأي خوارزمية.
البرمجة الديناميكية
تم تطويره في البداية بواسطة ريتشارد بيلمان في الخمسينيات من القرن الماضي ، وهو أحد الأساليب الرياضية الأكثر استخدامًا لحل البرنامج عن طريق التقسيم إلى أقسام معينة أصغر. لذلك ، هناك أوقات معينة نكتشف فيها أنماطًا قليلة ، والتي تتكرر باستمرار في بيان المشكلة. ما نقوم به بشكل عام ، هو أننا نخزن هذه القيم في جدول ، على غرار جدول التجزئة ، ثم كلما لزم الأمر في المستقبل. يبدو أنك حفظت رقم الاتصال على هاتفك الذكي. وبعد ذلك ، كلما دعت الحاجة ، ما عليك سوى فتح دفتر جهات الاتصال الخاص بك وطلب الرقم من هناك ، بدلاً من إدخال كل رقم يدويًا في برنامج الاتصال. لذلك ، تكون هذه الطريقة مفيدة عندما يكون لدينا عدد كبير من الخوارزميات ، وبعد ذلك ، لا نريد إضاعة الوقت دون داع في حساب نفس الشيء بشكل متكرر.
لحل أي مشكلة باستخدام البرمجة الديناميكية ، عادة ما نقوم بالخطوتين التاليتين
إيجاد البنية التحتية المثلى
يتم حل جميع مشاكل البرمجة الديناميكية باستخدام المعادلات المتكررة. حتى الآن ، كيف يتم اشتقاق معادلة متكررة؟ إذا كان هناك نمط ما أو جزء من المشكلة يتكرر ، فيمكن دراسة هذا النمط ووضعه في بعض المعادلات الرياضية بحيث يمكننا استخدام هذا النمط واستخدامه لحل بيان المشكلة ككل. هذا يسمى البنية التحتية المثلى في اللغة التقنية. البنية التحتية المثلى هي سلسلة متكررة من المشكلة ، والتي يمكن تأطيرها في وظائف متكررة. من خلال حل البنية التحتية المثلى ، يمكننا الحصول على حل بيان المشكلة.
تأطير المعادلة العودية - بمجرد إنشاء البنية التحتية المثلى ، سنضع إطارًا للدالة العودية لحلها.
أمثلة قليلة على نهج البرمجة الديناميكية
خوارزمية FLOYD WARSHALL
البحث عن أطول مجموعة فرعية مشتركة
إيجاد حل لمشكلة البائع المتجول
إذن ، هذه هي الطريقة التي نحتاج فيها إلى تأطير الحل.
يقودنا هذا إلى نهاية المدونة حول مقدمة إلى الخوارزميات: الاستخدامات والأنواع. نشكرك على قراءة هذه المدونة ، ونأمل أن تكون قادرًا على اكتساب بعض الأفكار القيمة.