الفرص الرقمية

الدرس 4: ما هي الخوارزمية؟

مستعدون؟
ابدأوا الدرس

أساسيات الخوارزميات

أخبر طلابك

هل تساءلتم يومًا كيف يصنع مطعمكم المفضّل طبقكم المفضّل بطريقة مثالية في كل مرة؟ أو كيف يمكن لـ Siri أو Alexa الرد على سؤال تطرحونه؟ كيف تعمل السيارات ذاتية القيادة؟ صدّقوا أو لا تصدّقوا، كل هؤلاء لديهم شيء واحد في جوهرهم: الخوارزميات.
الخوارزمية هي مجموعة تعليمات مُقدّمة بوضوح، خطوة بخطوة، لحل مشكلة أو إنجاز مهمة.

تفاعُل الصف

اعرض هذا التعريف، النقطة الثانية في منشور "ما هي الخوارزمية؟" على شاشة عرض. مرّر منشور "ما هي الخوارزمية؟"

أخبر طلابك

يمكن التعبير عن الخوارزميات بالكلمات أو برامج الكمبيوتر أو الرموز أو حتى في شكل وصفات. قد تكون بعض الخوارزميات عبارة عن إجراءات روتينية أو توجيهات أو عمليات بسيطة نستخدمها في حياتنا اليومية.
مثلاً، من أجل أن توقظوا أنفسكم في الصباح، يمكنكم النهوض من السرير والذهاب إلى الحمام وتحويل صنبور الماء إلى البارد، وتركه يعمل لمدة 30 ثانية، ورشّ وجهكم بالماء ثلاث مرات ثم تجفيفه بمنشفة.
لاحظوا هنا أن هذه خطوات لإنجاز مهمة وهي واضحة ومفصّلة للغاية. على سبيل المثال، يتم تدوين مقدار الوقت الذي يتم فيه تشغيل الصنبور وعدد مرات رش وجهكم بالماء.
مثال آخر على الخوارزمية هو وصفة الكوكيز المفضلة لديكم، حيث يتم تقديم الإرشادات بوضوح؛ خطوة بخطوة.
ولكن كل هذه الإجراءات الروتينية/الوصفات ليست بالضرورة خوارزميات. سنصل إلى هذه النقطة قريبًا!

اسأل طلابك

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

أخبر طلابك

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

اسأل طلابك

• هل يمكنكم التفكير في أمثلة أخرى في الرياضيات حيث استخدمتم خوارزمية لحل مسألة رياضية؟ تشمل الأمثلة المحتملة جمع الكسور وضربها (مثلاُ، 34 + 18 = 68 + 18 = 78) و/أو حل المعادلات (مثلاً، 3x + 2 = 5).

أخبر طلابك

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

تفاعُل الصف

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

أخبر طلابك

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

تفاعُل الصف

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

اسأل طلابك

• لنعود للتجمّع سويًا. ماذا لاحظتم؟ هل تعتقدون أن الوصفة عبارة عن خوارزمية؟ لماذا أو لِم لا؟

أخبر طلابك

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

أخبر طلابك

دعونا نلقي نظرة على شكل هذه الوصفة كخوارزمية!
الآن، من المهم ملاحظة أن هناك العديد من الخصائص الأساسية للخوارزمية.

تفاعُل الصف

اكتب الخصائص التالية بالخط العريض على لوحة ورقية/ملصق أو سبورة.

أخبر طلابك

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

اسأل طلابك

• يمكننا التفكير في عدد حصص الحمّص ومكاييل المكونات المقابلة كمُدخلات في مثال الوصفة الذي نطرحه. ينتج عن اتباع خطوات الوصفة (كما هو موضح في "الوصفة" - منشور المعلم) تحضير 3-4 حصص من الحمّص - مُخرجاتنا. ولكن ماذا لو احتجنا إلى تحضير 10 حصص من الحمّص؟ هل علينا أن نكتب خوارزمية جديدة تمامًا؟

أخبر طلابك

كلا، يمكننا بسهولة ضبط كمية المكونات حتى نتمكن من إدخال أي عدد من الحصص، من حصة فردية إلى 8 أو 9 أو 20 أو حسبما يُطلَب!
رغم أن فاعلية الخوارزمية ليست ضرورة حتمية، إلا أنها قد تكون ذات أهمية بالغة في مواقف معيّنة. بشكل عام، تشير الفاعلية إلى المواقف التي يتم فيها استخدام الموارد مثل المواد أو العمالة أو الوقت بشكل جيد، بدون إهدارها. في سياق خوارزميات الكمبيوتر، تشير الفاعلية عادةً إلى الوقت المستغرَق لإكمال الخوارزمية أو المساحة (أي الذاكرة) التي تشغلها الخوارزمية على الكمبيوتر. ولكن، في وصفة الحمّص الموجودة في منشوركم، نرى استخدامًا غير فعال للموارد (أي المال والتخزين) عندما نرى أن المكونات تتطلب كمية مُبالَغ فيها من الحمّص.
في أي وصفة، تعد الفاعلية مهمة بشكل خاص لكبير الطهاة في مطعم شهير ومزدحم! وفي مثال الوصفة الموجودة في المنشور، فإن أخذ قسط من الراحة لمشاهدة برنامجكم التلفزيوني المفضّل لن يطيل فقط من مدة تحضيركم للوصفة، بل قد يكون أيضًا كارثيًا في هذه الحالة.
ستلاحظون أيضًا في أعلى الوصفة أن لديّ نتيجة أو هدف - أن ينتج عن الوصفة 3 إلى 4 حصص من الحمّص.

أخبر طلابك

عند ترجمة هذه الخصائص إلى خوارزميات الكمبيوتر، لنُلقِ نظرة مرة أخرى على كيفية وصفنا للخوارزميات التي تعمل على أجهزة الكمبيوتر. [اقرأ النقطة الثانية في منشور "ما هي الخوارزمية؟" .]

تفاعُل الصف

اعرض هذا التعريف، النقطة الثانية في منشور "ما هي الخوارزمية؟" على شاشة عرض.

أخبر طلابك

طريقة أخرى لاستعراض خوارزميات الكمبيوتر، هي [اقرأ النقطة الثالثة في منشور "ما هي الخوارزمية؟"]. .]

تفاعُل الصف

اعرض هذا التعريف، النقطة الثانية في منشور "ما هي الخوارزمية؟" على شاشة عرض.

أخبر طلابك

كما تعلمنا للتو، من الميزات المرغوبة في الخوارزمية هي أن تكون ذات فاعلية، والتي تتضمن، من بين أشياء أخرى، الوقت الذي يستغرقه الكمبيوتر لتشغيل الخوارزمية. ولكن، من الضروري لخوارزميات الكمبيوتر أن تكون المسألة/المهمة محددة جيدًا، والخطوات التفصيلية للإرشادات مُدرَجة بدقة وقابلة للتنفيذ بواسطة الكمبيوتر. لا يمكن أن تعمل خوارزميات الكمبيوتر وفقًا لأهداف وتعليمات غامضة.
طبيعة خوارزميات الكمبيوتر (كما هو موضح في التعريف الثالث في منشور "ما هي الخوارزمية؟" الخاص بكم) هي أن مُدخلاً أو مجموعة من المدخلات ذات الصلة بهدف الخوارزمية تنتج، عن طريق سلسلة من تعليمات الكمبيوتر القابلة للتنفيذ، مُخرجًا أو مخرجات وتحاول حل المسألة بشكل صحيح.
فيما يلي بعض الأمثلة على خوارزميات الكمبيوتر التي قد تقابلونها.
عندما تقودون سيارة، هناك مجموعة من خوارزميات الكمبيوتر التي تعمل. مثلاً، تكتشف المستشعرات البيانات التي يتم إدخالها مثل الكيلومترات المقطوعة والوقود المستهلَك وتحسب الكيلومترات المقطوعة باستهلاك الوقود (أي المخرجات). عند إدخال وجهة ما على خرائط Google (المُدخَل)، تنتج خرائط Google الطريق الأقصر كمُخرَج. عند طرح سؤال على Siri أو Alexa أو Google Assistant (المُدخَل)، فإن هذه الأنظمة (كما يُفترض!) يجب أن تنتج إجابات مفيدة (المُخرجات). وعندما تتصلون بالإنترنت للبحث عن شيء ما على محرك بحث، مثل Google، فإن نص الإدخال تنتج عنه مخرجات من أكثر المواقع الإلكترونية صلةً بالأمر.

أخبر طلابك

اليوم، تتواجد خوارزميات الكمبيوتر في كل مكان.  فهي موجودة في أجهزتنا المحمولة، وأجهزة اللاب توب، والسيارات، والأجهزة المنزلية التي نستخدمها يوميًا. الخوارزميات - سواء كانت تساعدكم في تحضير كعكاتكم المفضلة أو الاستجابة لعمليات بحثكم عبر الإنترنت - موجودة حولنا في كل مكان.
ترتيب غير صحيح ــ الخوارزميات هنا لمساعدتكم!

تفاعُل الصف

قم بتجميع الأكواب البيضاء المرقمة بالترتيب التالي على الطاولة أمامك، من الأول إلى الأخير: 64، 23، 5، 98، 125، 110، 28، 37.
راجعوا صورة الترتيب بالفقاقيع رقم 1 من المنشور.

أخبر طلابك

لنستكشف نوعًا معينًا من الخوارزميات، يُسمّى خوارزمية الترتيب. عادةً ما يشير "الترتيب" إلى تنظيم قائمة من العناصر بحسب ترتيبٍ رقمي أو أبجدي. هناك العديد من الأمثلة على الحالات التي يكون فيها وجود الأشياء بترتيب معيّن أمرًا مهمًا حقًا، كما هو الحال في قائمة جهات اتصال الهاتف المحمول.

اسأل طلابك

• هل يمكن لأحدكم التفكير في أمثلة أخرى؟ قد تتضمن الأمثلة الأخرى فهرس الكتب أو مُدخلات القواميس أو ترتيب الكتب في المكتبة.

أخبر طلابك

تُعد خوارزميات الترتيب عائلة أساسية من الخوارزميات في علوم الكمبيوتر ولها نطاق واسع من التطبيقات. عندما تقوم منظمة الصحة العالمية، على سبيل المثال، بجمع تواليات (أي معدلات) الإصابة بمرض معيّن عبر مئات المناطق حول العالم، تقوم خوارزميات الترتيب في الكمبيوتر بتنظيم البيانات بشكل منهجي تصاعديًا أو تنازليًا في جداول ورسوم بيانية وتحليلات للبيانات.
لننظر في بعض الأمثلة الأخرى لخوارزميات الترتيب. في كل مرة تقومون فيها بالبحث عبر الإنترنت باستخدام محرك بحث، مثل Google، تتم معالجة بحثكم بواسطة العديد من الخوارزميات المعقدة، باستخدام خوارزميات الترتيب المُدمَجة في العملية. وعندما تدخلون على الإنترنت للعثور على المطعم الأكثر شهرة بالقرب منكم، تقوم خوارزميات الكمبيوتر، على مواقع الويب مثل TripAdvisor، بفرز هذه المطاعم حسب القرب والتقييمات التي يوفرها مستخدمو موقع الويب.

أخبر طلابك

لنطَّلِع على خوارزميتيّ ترتيب بالكمبيوتر. إحداها تُعرَف بالترتيب بالفقاقيع. والأخرى بالترتيب بالدمج ـ أي ترتيب قائم على استراتيجية فرِّق تسُد.
اعرض التعريف التالي للترتيب بالفقاقيع على شاشة العرض.
الترتيب بالفقاقيع هو عبارة عن خوارزمية ترتيب بسيطة تتصفح بشكل متكرر قائمة العناصر، وتقارن العناصر المتجاورة، وتبدّلها إذا لم تكن مُرتّبة ترتيبًا صحيحًا. تتكرر هذه العملية حتى يتم ترتيب العناصر.
الآن، سأشرح لكم ما هو الترتيب بالفقاقيع باستخدام هذه الأكواب الثمانية المرقّمة أمامي. هدفي هو ترتيب هذه الأكواب تصاعديًا. ابدأ بزوج الأكواب المرقميْن بـ 64 و23.
لنقارن أول كوبين ـ 64 و23.
إنهما غير مُرتّبَين ـ 23 أصغر من 64. إذًا، يجب تبديل هذين الكوبين بحيث يأتي 23 قبل 64.
راجعوا صورة الترتيب بالفقاقيع رقم 2 من المنشور.
الآن، لننظر إلى الكوبيْن المجاوريْن المرقميْن بـ 64 و5. بما إن 5 أصغر من 64، فإن ترتيب الكوبيْن غير صحيح. بالتالي، سأقوم بتبديلهما.
راجعوا صورة الترتيب بالفقاقيع رقم 3 من المنشور.
بعد ذلك، لنقارن الزوج المجاور المرقميْن 64 و98. لأن ترتيب الزوج صحيح، لن أقوم بتبديل هذيْن الكوبيْن.
بعد ذلك، سأقارن الزوج المجاور المرقميْن 98 و125. كما سبق، لأن ترتيب الزوج صحيح، لن أقوم بتبديل هذيْن الكوبيْن.
سأتابع على النحو ذاته مع زوج الأكواب المجاور، المرقميْن 125 و110، وسأقوم بتبديلهما.
راجعوا صورة الترتيب بالفقاقيع رقم 4 من المنشور.
بعد ذلك، سأبدِّل الكوبيْن المرقميْن 125 و28.
راجعوا صورة الترتيب بالفقاقيع رقم 5 من المنشور.
وأخيرًا، سأبدِّل الكوبيْن المرقميْن 125 و37.
راجعوا صورة الترتيب بالفقاقيع رقم 6 من المنشور.
يمكننا أن نرى أن ترتيب الأكواب لا يزال غير تصاعدي. ولكن، لنلاحظ بضع الأمور.
أولاً، لقد أجريْتُ مقارنات بين سبع أزواج من الأرقام.
ثانيًا، انتقلَ الكوب الذي يحمل الرقم الأكبر في هذه القائمة، 125، إلى نهاية الصف، حيث يجب أن يكون. تصاعد هذا الرقم كالفقاعة إلى نهاية القائمة.
سأكرر هذه العملية بالعودة إلى أول كوبين في الصف، المرقمين 23 و5.
هذه المرة، لنقارن الأكواب معًا - ونختر بين التبديل أو عدم التبديل.

تفاعُل الصف

أثناء تنقلك على طول الصف، اسأل المشاركين إن كانوا يرون إنه يجب تبديل الأكواب أم لا، "تبديل أم عدم تبديل؟" إجراء هذه العملية للمرة الثانية ينتج عنه الترتيب التالي للأكواب: 5، 23، 64، 98، 28، 37، 110، 125. اجذب انتباه المشاركين إلى أنه في هذه المرة، كان علينا فقط إجراء ست مقارنات، لأننا عرفنا من جولة المقارنات الأولى أن 125 هو الرقم الأكبر. لهذا، لم نكن بحاجة إلى المقارنة بين 110 و125.

اسأل طلابك

• هل ترى ما حققناه في الجولة الثانية من المقارنات؟

تفاعُل الصف

لا يزال ترتيب الأكواب غير صحيح، ولكن ثاني أكبر رقم (110) يوجد الآن قبل أكبر رقم، 125، حيث يجب أن يكون.

أخبر طلابك

بما إن ترتيب الأكواب لا يزال غير صحيح، نحن نحتاج إلى مراجعة الصف مرة أخرى. مرة أخرى، نبدأ من البداية، بالكوبيْن رقم 5 و23. أثناء تنقلك على طول الصف، اسأل المشاركين إن كانوا يرون إنه يجب تبديل الأكواب أم لا، "تبديل أم عدم تبديل؟" إجراء هذه العملية للمرة الثالثة ينتج عنه الترتيب التالي للأكواب: 5، 23، 64، 28، 37، 98، 110، 125.

اسأل طلابك

• هل ترون لماذا احتجنا إلى إجراء خمس مقارنات فقط في الجولة الثالثة؟

تفاعُل الصف

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

أخبر طلابك

نحن نحرز تقدمًا، لكن لا يزال ترتيب الأكواب غير تصاعدي. أعلم أن هذا يبدو أنه يستغرق وقتًا أطول مما يجب! لكن أجهزة الكمبيوتر أسرع بكثير من البشر، كما سنرى طريقة أسرع لترتيب هذه الأرقام قريبًا جدًا!
الآن، لنراجع الصف مرة أخرى باستخدام نفس العملية. كما سبق، سنعود إلى بداية الصف، بالأكواب المرقّمة 5 و23.

تفاعُل الصف

أثناء تنقلك على طول الصف، اسأل المشاركين إن كانوا يرون إنه يجب تبديل الأكواب أم لا، "تبديل أم عدم تبديل؟" إجراء هذه العملية للمرة الرابعة ينتج عنه الترتيب التالي للأكواب: 5، 23، 28، 37، 64، 98، 110، 125. اجذب انتباه المشاركين إلى أننا قمنا هذه المرة بأربع مقارنات فقط. من الجولة الثالثة، علمنا أن أكبر ثلاثة أرقام في المجموعة (98 و110 و125) تم وضعها بشكل صحيح في النهاية. لهذا، لم نكن بحاجة إلى المقارنة بين الأزواج 64 و98، و98 و110، و110 و125.

أخبر طلابك

الآن تم ترتيب الأكواب تصاعديًا.
راجعوا صورة الترتيب بالفقاقيع رقم 7 من المنشور.

اسأل طلابك

• ما رأيكم في الترتيب بالفقاقيع من حيث كمّ العمل الذي تطلبّه؟ الإجابة المحتملة هي أنه على الرغم من أن الترتيب بالفقاقيع بسيط، إلا أنه قد يستغرق وقتًا طويلاً للغاية بسبب كل المقارنات التي تم إجراؤها.

أخبر طلابك

تضمّن هذا الترتيب 22 مقارنة [محسوبة بإجمالي 7 مقارنات (الجولة الأولى) + 6 مقارنات (الجولة الثانية) + 5 مقارنات (الجولة الثالثة) + 4 مقارنات (الجولة الرابعة)].
لنفترض أن كل مقارنة تستغرق ثانية واحدة. إذًا، سيستغرق إتمام هذا الترتيب 22 ثانية.
ولكن لنفترض الآن أن شخصًا ما قد أعطانا قائمة تشمل 1000 رقم لترتيبهم تصاعديًا. في هذه الحالة، قد يتطلب الترتيب بالفقاقيع ما يقرب من نصف مليون مقارنة. سيستغرقنا هذا الأمر 5.8 يومًا حتى يكتمل - بدون أخذ أي استراحة!
أما تشغيل هذه الخوارزمية على جهاز كمبيوتر، مع قائمة غير مرتّبة من ثمانية أرقام (كما في مثالنا)، فمن شأنه أن يرتّب القائمة على الفور تقريبًا!
ولكن في حالة قائمة غير مُرتّبة من 1000 رقم، ستستغرق الخوارزمية بضع دقائق، وهو في الواقع وقت طويل بالنسبة للكمبيوتر.
الترتيب بالفقاقيع بسيط ولكنه غير فعال. تقوم العديد من خوارزميات الكمبيوتر الأخرى بالترتيب بشكل أسرع وأكثر كفاءة. من بينها الترتيب بالدمج.

أخبر طلابك

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

تفاعُل الصف

أعِد ترتيب الأكواب مرة أخرى بحيث تظهر الأكواب المرقّمة بنفس الترتيب الذي ظهرت به في بداية هذا النشاط: 64، 23، 5، 98، 125، 110، 28، و37.
راجعوا صورة الترتيب بالفقاقيع رقم 1 من المنشور.

أخبر طلابك

الجزء الأول من الترتيب بالدمج هو "فرِّق".

تفاعُل الصف

اعرض الترتيب بالدمج — الخطوة الأولى: مخطط فرِّق على شاشة العرض.
عُد إلى الخطوة الأولى: مُخطط فرِّق.

أخبر طلابك

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

تفاعُل الصف

فرِّق الأكواب الثمانية.

أخبر طلابك

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

تفاعُل الصف

اعرض الترتيب بالدمج — الخطوة الثانية: مخطط تسُد على شاشة العرض.
عُد إلى الخطوة الثانية: مخطط تسُد.

أخبر طلابك

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

تفاعُل الصف

حرّك الكوب المرقّم 23 أمام الكوب المرقّم 64.
إذًا، ما تبقّى هو القائمة المرقّمة الفردية 64. نأخذ هذا الكوب ونضعه بجانب 23.
ثم نضع الكوب المرقّم 64 بجانب الكوب المرقّم 23.

أخبر طلابك

سنكرر هذه العملية للأكواب المتبقية.
إذا واصلنا على هذا النحو، فسننتهي بأربع قوائم، كل منها مرتّب.

تفاعُل الصف

ضع الأكواب بالترتيب الموضّح في صف "القوائم الأربع" للترتيب بالدمج - الخطوة الثانية: مخطط تسُد.

أخبر طلابك

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

تفاعُل الصف

ضعوا هذا الكوب المرقّم أمام الأكواب الأخرى.
ثم، في القائمتين المتبقيّتين [القائمة التي تحتوي على 23 و64 والقائمة التي تحتوي على 98، مع ملاحظة إزالة الـ 5 في الخطوة السابقة]، ننظر مرة أخرى إلى الكوب الأول في كل من هاتين القائمتين.
سنقوم بسحب الكوب الأصغر من حيث العدد. في هذه الحالة، هو 23.
خذ الكوب 23 وضَعه بجانب الكوب المرقّم 5.
الآن، تتبقى لدينا قائمتان برقم واحد في كل منهما.
سنأخذ الرقم الأصغر من هاتين القائمتين، وهو 64 ونضعه بجوار 23. [خذوا الكوب 64 وضعوه بجانب الكوب المرقّم 23.]
أخيرًا، سنضع آخر كوب مُرقَّم، 98، بجوار 64.
خذوا الكوب 98 وضعوه بجانب الكوب المرقّم 64.

أخبر طلابك

الآن، لدينا قائمة بأربعة أكواب مرقّمة مرتّبة.
بعد ذلك، سنكرر نفس العملية مع هذين الزوجين من الأكواب. [أشِر إلى أزواج الأكواب المرقّمة 110 و125 و28 و37.]

تفاعُل الصف

لا تنفّذ هذه العملية فعليًا. بدلاً من ذلك، حدد الشكل الذي ستبدو عليه النتيجة النهائية بالإشارة إلى الطريقة التي سيتم بها دمج الأكواب المرقمة 110 و125 و28 و37، المتوفرة في صف "القائمتين" من الترتيب بالدمج - الخطوة الثانية: مخطط تسُد.

أخبر طلابك

أخيرًا، كما يوضح المخطط، لدينا قائمتان مرتّبتان. الآن، سندمج هاتين القائمتين. سنتبع نفس النهج الذي اتبعناه سابقًا (حيث دمجنا أربع قوائم في قائمتين).

تفاعُل الصف

أشر إلى صف "القوائم الأربع" وصف "القائمتين" في الترتيب بالدمج - الخطوة الثانية: مخطط تسُد.
الآن قد اكتمل ترتيب قائمة الأكواب المرقّمة الخاصة بنا!
أشر إلى صف "القائمة الواحدة المرتّبة" من الترتيب بالدمج - الخطوة الثانية: مخطط تسُد.
تم حل المسألة!

أخبر طلابك

اشتمل هذا الترتيب بالدمج على 15 مقارنة، مقابل 22 مقارنة في مثالنا الذي استخدمنا فيه الترتيب بالفقاقيع.
الرابح هو الترتيب بالدمج!
عند تنفيذ الترتيب بالفقاقيع والترتيب بالدمج على جهاز كمبيوتر للحصول على قائمة بآلاف الأرقام، يستغرق الترتيب بالدمج أجزاء من الثانية، بينما يُحسَب وقت تشغيل الترتيب بالفقاقيع بالدقائق. الترتيب بالدمج أكثر كفاءة بشكلٍ كبير من الترتيب بالفقاقيع.
في هذا النشاط، استعرضنا طريقتين، من ضمن طرقٍ متعددة، تستخدمهما أجهزة الكمبيوتر لترتيب البيانات.
وليس من غير المألوف أن تقوم خوارزميات متعددة بإنجاز نفس المهمة. ومع ذلك، فإن بعض الخوارزميات أسرع وأكثر كفاءة من غيرها، كما رأينا في حالة الترتيب بالدمج وفقًا لطريقة فرِّق تسُد، في مقابل الترتيب بالفقاقيع البسيط ولكن الذي يستغرق وقتًا أطول.
تُعدّ خوارزميات الفرز عائلة مهمة من خوارزميات الكمبيوتر، ولها العديد من التطبيقات المفيدة.
تشمل عائلات الخوارزميات الأخرى خوارزميات البحث، وخوارزميات البحث عن الطرق التي تستخدمها أنظمة GPS لتحديد المواقع، وخوارزميات التشفير التي تؤمّن الرسائل عبر الإنترنت.
في السنوات الأخيرة، ربما تكونون قد سمعتم عن خوارزميات التعلّم الآلي للذكاء الاصطناعي، ومن المرجّح أنكم صادفتموها. تنشأ هذه الخوارزميات عن خوارزميات الكمبيوتر التقليدية القابلة للبرمجة. الأمر المهم في خوارزميات التعلّم الآلي للذكاء الاصطناعي هو أنها تتعلّم (تتدرّب) بمفردها من البيانات والكثير منها، بهدف تحسين استجاباتها. بعض الأمثلة على التعلّم الآلي للذكاء الاصطناعي هي عندما يشير Facebook لكم في صوركم، ويجيب مساعد Google على أسئلتكم، وعندما تظهر السيارات ذاتية القيادة على الطرق.

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

أخبر طلابك

دعونا نلقي نظرة على مسألة دفعت حدود التفكير الخوارزمي لأكثر من 2000 عام - إيجاد الأعداد الأولية.
للتذكير، العدد الأولي هو مجرد عدد صحيح أكبر من 1 لا يقبل القسمة إلا على 1 وعلى نفسه. مثلاً، 2 و3 و5 و7 و11 هي أعداد أولية.
والرقم 6 ـ على سبيل المثال ـ ليس عددًا أوليًا، لأن 6 يقبل القسمة على 1 و2 و3 و6. كذلك الرقم 15 ليس عددًا أوليًا ـ لأنه يقبل القسمة على 1 و3 و5 و15.
في الواقع، تُعدّ الأعداد الأولية اللبنات الأساسية لنظام الأرقام لدينا، وهي تلعب اليوم دورًا مهمًا في التشفير وأمان الإنترنت.
إن أمان المعاملات عبر الإنترنت، مثل شراء السلع ببطاقة الائتمان، يعتمد على التشفير (أي علم تشفير الرسائل) بأعداد أولية كبيرة جدًا - أعداد أولية بمئات أو حتى آلاف الأرقام.
على الرغم من وجود عدد لا حصر له من الأعداد الأولية، إلا أن العثور على أعداد أولية كبيرة جدًا أمر صعب للغاية.
لنُلقِ نظرة على مشكلة أبسط - العثور على جميع الأعداد الأولية حتى 100، مع تمرين ممتع يمكنكم القيام به في ثنائيات.

تفاعُل الصف

وزع منشورات "الخوارزميات في حقبة الأعداد الأولية" مع أقلام جافة ورصاص.

أخبر طلابك

لنستعرض الأعداد الصحيحة حتى 100 بترتيب تصاعدي باستخدام المصفوفة العشرية المُبيّنة في منشوركم.
اشطبوا 1 ثم اشطبوا جميع الأعداد الزوجية - مضاعفات 2 (أي الأرقام التي تقبل القسمة على 2) - باستثناء 2. ثم ارسموا دائرة حول 2، لأنها عدد أولي.

اسأل طلابك

• في رأيكم، ما الخطوة التالية؟
• اشطبوا جميع مضاعفات 3 (أي الأرقام القابلة للقسمة على 3)، باستثناء 3. ارسموا دائرة حول 3، لأنها عدد أولي. لاحظوا أن بعض الأرقام ربما تم شطبها بالفعل، مثل 6 (لأنه من مضاعفات كل من 2 و3).

أخبر طلابك

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

• هل تسمح لكم الخوارزمية بتحديد جميع الأعداد الأولية حتى 100؟ بعبارةٍ أخرى، هل تُحقق الهدف منها؟
• هل هناك طرق لجعل خوارزميتكم أكثر كفاءة؟

تفاعُل الصف

نظّم المشاركين في أزواج. امنحهم 15 دقيقة لهذا التمرين.

أخبر طلابك

لنعود للتجمّع سويًا. إليكم طريقة واحدة للتعبير عن خطوات هذه الخوارزمية.

تفاعُل الصف

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

أخبر طلابك

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

اسأل طلابك

• كيف تعرفون أن الخوارزمية التي طوّرتموها في مجموعات تحدد جميع الأعداد الأولية حتى 100؟
  • ○قد تكون الإجابة المُحتَملة هي أن المشاركين حددوا جميع الأرقام التي تمثل مضاعفات الرقم 1 وأنفسها (أي أن هذه الأرقام قابلة للقسمة على 1 وأنفسها فقط) ووضعوا دائرة حول هذه الأرقام.

• هل وجدتم في فريقكم الثنائي طرقًا لجعل هذه الخوارزمية أكثر كفاءة؟
  • قد تكون الإجابة المحتمَلة أنه بمجرد وصول المشاركين إلى العدد الأولي 11، لاحَظوا أنه تم شطب جميع مضاعفاته. مثلاً، تم شطب 44 كمضاعف لـ 2. وتم شطب 33 كمضاعف لـ 3. علاوة على ذلك، بمجرد أن نصل إلى 11 × 11، نلاحظ أن حاصل الضرب (121) أكبر من 100. يمكننا بعد ذلك رسم دائرة حول جميع الأرقام المتبقية (أي الأرقام التي لم يتم شطبها بالفعل)، وهي كلها أعداد أولية.

أخبر طلابك

يمكننا تعديل هذه الخطوة الرابعة [أشر إلى الخطوة الرابعة في "الخوارزميات في حقبة الأعداد الأولية: منشور المعلم"] للإشارة إلى أنه يمكننا التوقف عند الرقم 11، أول عدد أولي يكون مرّبعه (أي حاصل ضرب 11 × 11) أكبر من 100.
ثم، على "الخوارزميات في حقبة الأعداد الأولية: نسخة المُعلِّم،" أشِر إلى مُدخَل 100.

اسأل طلابك

• هل مُدخَل 100 هذا صحيح؟
  • نعم، كما يشير هدف هذه الخوارزمية، نحن نهدف إلى إيجاد كل الأعداد الأولية حتى 100.

أخبر طلابك

يمكننا بالفعل إدخال أي عدد صحيح موجب وتعديل الخوارزمية وفقًا لذلك للعثور على جميع الأعداد الأولية حتى هذا العدد الصحيح.
لنفترض أنه بدلاً من إدخال 100، كان مُدخلنا 1000. يمكننا استخدام غربال إراتوستينس لإيجاد جميع الأعداد الأولية حتى 1000 باستخدام ورقة وقلم رصاص. سيستغرق منا هذا وقتًا طويلاً. ولكن يمكن للكمبيوتر إجراء خطوات هذه الخوارزمية بشكلٍ شبه فوري.
يستطيع غربال إراتوستينس، المكتوب بلغة البرمجة بايثون (أو بأي لغة برمجة) أن يطبع جميع الأعداد الأولية حتى 1000 في جزء من الثانية.
ولكن، إذا حاولتم العثور على أعداد أولية كبيرة جدًا - أعداد أولية بمئات أو آلاف الأرقام، والتي تلعب دورًا مهمًا في التشفير وتأمين الإنترنت - تصبح خوارزمية الكمبيوتر غربال إراتوستينس غير فعالة أبدًا.
على مدى عقود عديدة، طوّر علماء الرياضيات وعلماء الكمبيوتر والمهندسون مجموعة واسعة من الأساليب/الخوارزميات لتحديد هذه الأعداد الأولية الكبيرة جدًا - بعضها عبارة عن مشتقات من غربال إراتوستينس والبعض الآخر مستلهَم من نظرية الاحتمالات. حتى الكيمياء الجزيئية لعبت دورًا في هذا!

مهمة

أخبر طلابك

الآن وقد تحدثنا عن ماهية الخوارزمية (وما ليس بخوارزمية!) وأوضحنا العديد من الخوارزميات المختلفة، أريدكم أن تطبقوا ما تعلّمتموه لإنشاء خوارزمية خاصة بكم.
يمكن أن ترتبط هذه الخوارزمية بأي موضوع تريدونه — مجموعة من الخطوات التي تحل مسألة حسابية أو ربما حتى الخطوات التي تؤدي إلى تنفيذ إجراء ما في تطبيق الهاتف المحمول أو لعبة الفيديو المفضّلة لديكم.
قبل كتابة الخطوات، تأكدوا من تحديد هدفكم في الأعلى. ثم اكتبوا خطوات الخوارزمية المعطاة. يفترض أن تتألف خوارزميتكم من خمس إلى 10 خطوات. تأكدوا أيضًا من كتابة (المُدخَل) المُدخلات و(المُخرج) المُخرجات الخاصة بخوارزميتكم!
أثناء قيامكم بتطوير الخوارزمية، ضعوا في اعتباركم خصائص الخوارزمية الأساسية التي ناقشناها سابقًا: تعليمات الخوارزمية محددة بدقة، والخوارزمية تحقق هدفكم، و(على الرغم من أن ذلك ليس متطلبًا) يُفضّل أن تكون فعالة.

تفاعُل الصف

امنح المشاركين 25 دقيقة لإكمال المنشور. تبعًا للوقت المخصص، في اجتماع المجموعة الحالية أو الثانية، شارك في المناقشة التالية.

مناقشة

تفاعُل الصف

نظّم المشاركين في أزواج.

أخبر طلابك

في أزواج، أريد منكم أن تشاركوا خوارزمياتكم وتناقشوا:

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

ستتاح لكم 15 دقيقة لإتمام هذا التمرين.

تفاعُل الصف

امنح المشاركين 15 دقيقة للمشاركة في هذا التمرين مع شركائهم. بعد ذلك، امنح 10 دقائق للثنائيات لمشاركة أ) أي طرق يمكنهم من خلالها جعل الخوارزمية الخاصة بهم أكثر كفاءة، بناءً على مناقشتهم مع شركائهم، و/أو ب) شيء جديد أو مفاجئ تعلموه أثناء تطوير الخوارزمية الخاصة بهم أو مراجعة خوارزمية شركائهم.

ممتاز!
لقد أتممتُم الدرس.

الدرس السابق الدرس التالي