القليل من المُتعة مع الأعداد الأولية بالبايثون

 

لُعبة بسيطة مُقتبسةٌ من كتاب أتمتة الأشياء المٌملة بالبايثون مع القليل من التحديثات البرمجية.

في كل مرة، سيختار البرنامج عددا أوليا ما بين 1 و100 بشكل عشوائي.
على اللاعب العثور على ذلك العدد في ظرف 5 محاولات فقط.
الهدف هو التسلية وحفظ الأعداد الأولية الأقل من 100 بطريقة مُمتعة.

رابط اللعبة  مــن هــنــا  وحظ موفق للجميع.

نُشِرت في آل خوارزمـيـات | الوسوم: , , , | أضف تعليق

القليل من المرح: تشغيل خوارزمية رياضية تاريخية بالبايثون

لمحة عامة: يتعلق الأمر ببرنامج بسيط ذو كفاءة في تحديد اليوم الموافق لأي تاريخٍ قديم أو حديث أو في المستقبل. ورغم أنَّ البايثون قد جعل من هذا الأمر مجرد إجراءٍ روتيني سهل التنفيذ (مثال) إلا أنَّ استكشاف مقدار التعقيد الذي قد تُخفيه بعض خوارزميات التأريخ الأنيقة (مثال) لأمرٌ يستحق العناء.

الاسم: برنامج تحديد اليوم الموافق لأي تاريخٍ قديم أو حديث أو في المستقبل وفق لغة البايثون.

الكود المُستخدم: قُمت بتحميله على موقع GitHub وعلى موقع repl.it تحت الاسم المُختصر DayName.

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

للمزيد من المرح: للخوارزمية عيبٌ بسيط واحدٌ له علاقة باعادة ترقيم الأشهر من خلال تأخير ترتيب شهري جانفي وفيفري في الرزنامة، لذلك إن كنت قد اخترت تاريخا يقع في شهر جانفي(11) أو فيفري(12) فإنّ البرنامج سيؤخر يوما أو يُقدّمه ثم سيعود ويصحّح نفسه بنفسه للوصول إلى “اليوم الموافق” الصحيح في النهاية. لذلك ستُصادف نتائج مُسَلية من مِثل (الأحد. عذرا، بل السبت) أو (الثلاثاء. عذرا، بل الأحد. بل هو الإثنين) سببها رغبتي في أن يقوم الكود بتصحيح خطئه مع الحفاظ على بساطته وطابعه المرِح. فالغرض استكشاف مدى تعقيد الخوارزمية التاريخية لا القضاء على عيوبها.

بعض التفاصيل البرمجية: الثغرة: تقع في شهري جانفي (11) وفيفري (12) فقط. وقد قُمت بمعالجتها لكل التواريخ في القرن الــ20 (cc==19) والقرن الــ21 (cc==20) على التوالي. الميزة: بالنسبة للأشهر الأخرى (من مارس إلى ديسمبر) فالبرنامج صالح لكل التواريخ القديمة والحديثة والمستقبلية على اختلافها.

مثال توضيحي بالصور: تحديد اليوم الموافق لاندلاع الثورة الجزائرية (1 نوفمبر 1954)

الخطوة.1- لصق الكود على القارئ المفتوح المصدر والضغط على زر التشغيل Run.

الخطوة.2- كتابة رقم اليوم: 1 ثم الضغط على الزر ENTER على جهاز الكمبيوتر.

الخطوة.3- كتابة رقم الشهر (وفقا للترقيم المُعطى) وهو: 9 ثم الضغط على ENTER.

الخطوة.4- كتابة رقم السنة: 1954 ثم الضغط على ENTER. والحصول مباشرة على اليوم الموافق: الإثنين.

لمعاينة تاريخٍ آخر، ما عليك سوى الضغط على زر التشغيل Run ليبدأ البرنامج من جديد.

وفي الأخير. أتمنى أن تستمتعوا بتجربة البرنامج على تواريخ قديمة تتعلق بأوطانكم… أو أخرى حديثة تتعلق بتاريخ ميلادكم، اهتماماتكم… أو مُستقبلية تتعلق بمواعيدكم، مناسباتكم…وأن تستعينوا بهذه الرزنامة للتأكد من النتائج أو لاستكشاف عثراتٍ أتمنى موافاتي بها هنا في التعليقات أو على بريدي الإلكتروني (math.nights@gmail.com) وشكرا مُقدما.

 

نُشِرت في آل خوارزمـيـات | الوسوم: , , , | أضف تعليق

حلول مسائل Harmash في الخوارزميات وهياكل البيانات بالبايثون

يعرض موقع  Harmash  دورة تمارين في الخوارزميات وهياكل البيانات، بهدف تطوير القدرات البرمجية لكل مهتم بالمجال. تتكون الدورة من سلسلة من التمارين المتقدمة والمتنوعة (مع الحل وبخمس لغات برمجة) وذلك على شكل تحدِّيات كالآتي:

  1. رسم أشكال هندسية: 10 تحديات (50 تمرينا)
  2. التعامل مع الأرقام والنصوص: 03 تحديات (15 تمرينا)
  3. إجراء عمليات حسابية: 09 تحديات (45 تمرينا)
  4. التعامل مع المصفوفات: 06 تحديات (30 تمرينا)
  5. تراكيب البيانات: تحدييْن اثنين (في شكل مشروعين كاملين)
  6. حساب وقت الخوارزميات: شرح مفصّل، أمثلة تطبيقية ومصادر مفيدة.

اجتزت الدورة وأتممت حل جميع تحدّياتها وفق لغة البايثون، ولأن الحلول التي اعتمدتها كانت من “مختلفة تماما” إلى”مختلفة نوعا ما” عن نظيرتها في الموقع، فقد آثرت – من باب حفظها ثم مشاركتها والإثراء –  نسخها على حساب GitHub الخاص بالمدونة.

في الرابط مـــن هـــنــا سلسلة أكواد الخوارزميات التي اعتمدتها في حل كل مسألة.

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

[صـحّـه عـيـدكـم و تـقـبَّـل الله صيامكم. كل أسبوع وأنتم من المُبرمِـجين لا المُبرمَـجين]

نُشِرت في آل خوارزمـيـات | الوسوم: , , , , , , | أضف تعليق

الرياضيات في دقيقة: المعادلات التفاضلية

يمكن لسيارة “فيراري 330 بي 4” هذه، السَير بسرعة تفوق 70 ميلا في الساعة.

تخيل أنَّك تقود على الطريق السريع بسرعة ثابتة تبلغ 70 ميلا في الساعة. في حال بلغت وجهتك بعد ساعتين، فستدرك مباشرة أنك قد قطعت مسافة 140 ميلا. في الواقع، إنَّ ما قمتَ به الآن (ومن دون أن تشعر) هو حل معادلة تفاضلية. السرعة هي معدل تغَـيُّـر المسافة بالنسبة للزمن. ومن خلال ملاحظة مُعدل التغيُّر هذا، فقد حددت قيمة المقدار الذي تَغَـيَّـر في النهاية، أي المسافة

هذا ببساطة ما تدور حوله المعادلات التفاضلية. إنَّ أغلب ما نراه وما يمكننا قياسه عند التأمل في العالم من حولنا هو التَـغَـيُّـر: كيف يتغير مقدار ما y بالنسبة للزمن، أو الفضاء، أو بالنسبة لمقدار آخر x . يمكننا وصف هذا التَـغَـيُّـر بواسطة معادلة: وهذا ما يدعى بالمعادلة التفاضلية العادية. في مثال السيارة، يُمثل y المسافة وتُمثل x الزمن. بأخذ \frac{dy}{dx} لمعدل التغيُّـر، فإن المعادلة التفاضلية العادية الموافقة هي:

\frac{dy}{dx}=70.

يتم حل المعادلة التفاضلية انطلاقا من معدل تغيُّر y بالنسبة إلى x أي قيمة y لكل قيمةٍ من x . في مثال السيارة، حل المعادلة التفاضلية العادية هو:

y(x) = 70x.

من أجل x=2 ، فإن المسافة المقطوعة بعد ساعتين هي:

y(2)=70 \times 2=140

كما ذكرنا سابقا.

السرعة هي معدل تغيُّر المسافة بالنسبة للزمن: وهو ما يُدعى بالمشتق الأول للمسافة بالنسبة للزمن. التسارع هو معدل تغيُّر السرعة بالنسبة للزمن، ما يجعله المشتق الثاني للمسافة بالنسبة للزمن. يمكنك الاستمرار على نفس المنوال. معدل تغيُّر التسارع بالنسبة للزمن هو المشتق الثالث للمسافة بالنسبة للزمن، وهكذا دواليك، مما يمنحك سلسلة كاملة من المشتقات ذات الرُتب الأعلى. المعادلة التفاضلية العادية هي معادلة تتضمن مقدارًا y ومشتقاته ذات الرتب الأعلى بالنسبة إلى مقدارٍ x .

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

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


المقال الأصلي

Maths in a minute: Differential equations

نُشِر بتاريخ: May 6, 2020

——————

ترجمة: مديحة حوري.

(تمت المراجعة يوم الأحد 2020/08/09)

نُشِرت في الرياضيات في دقيقة | الوسوم: , , , | أضف تعليق

الرياضيات في دقيقة: متتالية فيبوناتشي

ليوناردو فيبوناتشي (1175- 1250م)

متتالية فيبوناتشي

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

هي واحدة من أشهر متتاليات الأعداد على الإطلاق. والموضَّح أعلاه، الأعداد الأولى منها، لكن ما العدد التالي؟ الجواب بسيط. كل عدد في متتالية فيبوناتشي (إنطلاقا من 2) هو مجموع العددين السابقَين له:

  • 1+1 = 2
  • 1+2 = 3
  • 2+3 = 5
  • 3+5 = 8

وهكذا دواليك. لذلك من السهل جدا معرفة أن العدد التالي في المتتالية أعلاه هو 144 أي ( 55+89 ) ومعرفة (نظريا على الأقل) الأعداد التي تليه إلى المالانهاية.

مـا مصدرها؟

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

اكتمل بلوغهما بعد شهر واحد

تزاوجا، بحيث أنجبا زوجا من الأرانب (ذكرا وأنثى) بعد شهر.

اكتمل بلوغ زوج الأرانب بعد شهر، وأنجب الزوج الأول زوجا آخر من الأرانب (للمرة الثانية، ذكرا وأنثى).

مع تجاهل بعض مسائل التناسل، بعد شهر، أصبح لكلٍ من الزوجين البالغَين زوجٌ من الأرانب الصغيرة واكتمل بلوغُ زوج الأرانب من الشهر السابق.

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

A_{n}=R_{n-1}

أدرك فيبوناتشي أيضا أنَّ عدد أزواج الأرانب الصغيرة في شهر معين هو عدد أزواج الأرانب البالغة في الشهر السابق. بأخذ B_n لعدد أزواج الأرانب الصغيرة في الشهر n ينتج ما يلي:

B_ n = A_{n-1} = R_{n-2}.

وبالتالي، فإن العدد الإجمالي لأزواج الأرانب (البالغة + الصغيرة) في شهر معين هو مجموع العدد الإجمالي لأزواج الأرانب في الشهرين السابقين:

R_ n = A_ n + B_ n = R_{n-1}+R_{n-2}.

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

مــا مصيرها ؟

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


المقال الأصلي

Maths in a minute: the Fibonacci sequence

نُشِر بتاريخ: May 1, 2020

——————

ترجمة: مديحة حوري.

(تمت المراجعة يوم السبت 2020/08/08)

نُشِرت في الرياضيات في دقيقة | الوسوم: , , , | تعليق واحد

الرياضيات في دقيقة: الإنتروبيا

الإنتروبيا مفهومٌ غامض. يرى البعض أنَّ الإنتروبيا تقيس مقدار الاضطراب في النظام المادي، ويرى البعض الآخر أنَّها مقياسٌ للمعلومات، فيما يتحدث آخرون عنها في سياق المحركات البخارية. فما الإنتروبيا؟ وما الرابط بينها وبين هذه الرؤى المختلفة؟

محركات بخارية

لننطلق من البداية. شهد القرن التاسع عشر بزوغ فجر المحرك البخاري، لكنه شدَّد على واقع مزعج: كانت هذه المحركات تفتقر إلى الكفاءة بشكل مُروِّع. ما ألهم المهندس الفرنسي الشاب، سعدي كارنو، لوضع حدودٍ نظريةٍ لكفاءة المحركات البخارية (التي تعمل على تحويل الحرارة التي تتدفق من خزان ساخن نحو آخر بارد إلى شُغل). وفي عام 1824، نشر كارنو كتابا، اختار له عنوانا جميلا  ” تأملات في القدرة الدافعة للنار “، أظهر فيه أنَّه لا يوجد محرك حراري، مهما بلغت درجة كماله، كفؤٌ  بنسبة 100%. ستُبدَدُ دائما بعض الحرارة في المحرك.

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

التعريف الكلاسيكي للانتروبيا

في عملية عكوسية تتضمن إنتقال حرارة بحجم Q عند درجة الحرارة T. يتم قياس التغير في الإنتروبيا \Delta S عن طريق:

\Delta S = Q/T.

العملية العكوسية هي تلك التي لا يتم فيها تبديد الطاقة (من خلال الإحتكاك…إلخ). لمعرفة كيفية تطبيق هذه الصياغة على عمليات غير عكوسة أكثر واقعية ارجع للرابط من هـنـا

اضطراب

مكعبات ثلج في حالة ذوبان

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

هرم عيد الميلاد: يتم تشغيل شفرات المروحة أعلى اللعبة من حرارة الشموع.

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

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

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

التعريف المجهري للإنتروبيا

لنفترض أن الغاز في مادة ماكروسكوبية معينة، مثلا، له درجة حرارة أو ضغط محدد. لنعتبر W عدد التشكيلات التي يمكن أن تكون عليها جزيئاته الفردية للحفاظ على بنيته الماكروسكوبية. وبالتالي فإن الإنتروبيا S تساوي:

S = k\ln {W}

حيث k هو ثابت بولتزمان

k = 1.38062 \times 10^{-23} J/K.

حيث J بالجول، وحدة الطاقة، وK هي درجة الحرارة بالكلفن.

تم نقش هذه الصياغة في ضريح بولتزمان في فيينا.

وتتحقق عندما يكون احتمال حدوث جميع تشكيلات الجزيئات متساويا. هناك تعميم لهذه الصياغة يتحقق عندما يكون احتمال حدوثها غير متساوِ. كالآتي:

S = -k \sum _ i p_ i\ln {p_ i}

حيث p_ i هو احتمال التشكيلة i

معلومات

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

هذه هي الطريقة التي يرتبط بها مفهوم الإنتروبيا بكفاءة المحركات، بالاضطراب والمعلومات. الإنتروبيا مُقحمة أيضا في القانون الأساسي للطبيعة: ينص القانون الثاني للديناميكا الحرارية على أنَّ إنتروبيا نظام معزول لا يمكن أن ينخفض أبدا، يظل ثابتا أو يزيد. بالنسبة للمحركات، هذا يعني أنَّ أي محرك لن يصبح أبدا أكثر كفاءة من تلقاء نفسه، وهذا ما يتناسب مع الحدس. وبالنسبة للاضطراب، فهذا يعني أنَّ مصير أي نظام مادي يُِترك لفترة، أن يصبح أكثر فوضى، وهذا ما يتناغم مع الحدس أيضا (فكِّر في مطبخك أو مكتبك). أما بالنسبة للمعلومات، فمن الصعب وصف المقادير الفوضوية من تلك المرتبة.

يمكنك معرفة المزيد حول القانون الثاني للديناميكا الحرارية في مقالة الرياضيات في دقيقة: القانون الثاني للديناميكا الحرارية، حول تاريخ الإنتروبيا مـن هـنـا، وحول الإنتروبيا بشكل عام في هذه المقالات.


المقال الأصلي

Maths in a minute: Entropy

نُشِر بتاريخ: April 17, 2020

——————

ترجمة: مديحة حوري.

(تمت المراجعة يوم الخميس 2020/08/06)

نُشِرت في الرياضيات في دقيقة | الوسوم: , , , , | أضف تعليق

حلول مسائل CodingBat بالبايثون

يعرض موقع CodingBat المجاني سلسلة من المسائل البرمجية وفق لغة البايثون والجافا والتي يتطلب حلُّها بناءَ خوارزميات بسيطة لكنها أساسية في سبيل تنمية المهارات القاعدية لكل مُبرمج.

 يوفر الموقع إمكانية وضع الحل مباشرة على نافذة مخصصة لذلك أسفل كلِ مسألة، أي لن تكون مُرغما على تحميل أي نوع من البرامج الخاصة بكتابة الكود (Code).

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

Warmup-1
Warmup-2
String-1
List-1
Logic-1
Logic-2
String-2
List-2

مستوى المسائل من “بسيط” إلى “متوسط”. مع القليل من المساعدة المباشرة في الحل (المسائل التي تحمل العلامة H في الموقع) أو المساعدة غير المباشرة، الموجزة والإختيارية، لفهم قواعد المسألة ومن ثَمَ استنتاج الحل (من هــنــا).

لأولئك المحترفين، قد تبدو المسائل بسيطة جدا جدا (وهو الأمر الذي تُظهره جولة سريعة في الموقع)، لكن منظومة الخوارزميات المُعتمدة في حلِّـها أنيقة جدا جدا (وهو الأمر الذي لن تكتشفه إلا بالممارسة). [قد لا يكون الـCode الصحيح أنيقا كفاية !!]

نُشِرت في آل خوارزمـيـات | الوسوم: , , , , , | أضف تعليق

الرياضيات في دقيقة: عدد التكاثر الأساسي ومناعة القطيع

ما المقصود بمناعة القطيع؟ وما علاقتها بعدد يُدعى R_{0}

عدد الإصابات الجديدة بالعدوى بالنسبة من أجل عدد تكاثر أساسي يُساوي 2

عدد التكاثر الأساسي

بالنظر إلى الأمراض المُعدية، مثل كوفيد-19، فإن R_{0} هو عدد التكاثر الأساسي للمرض: مُعدل عدد الأشخاص الذين يُتوقع أن يُصابوا بالعدوى من الشخص المُصاب، على اعتبار أنَّ جميع أفراد السكان عُرضة للإصابة بالمرض. بالنسبة لكوفيد-19 فإن R_{0} يتراوح حاليا ما بين 2 و 2.5 . أما بالنسبة لسلالات الأنفلونزا الموسمية فهو ما بين 0.9 و 2.1. ويتضخم R_{0} ليصبح 12 إلى 18 بالنسبة للحصبة.

يمكنك أن تلاحظ كيف يؤدي مقدارٌ مُعتبرٌ من R_{0} إلى انتشار سريع للمرض. فمثلا، إذا كان R_{0} يساوي 2  فإن الشخص المُصاب سيُثير شرارة النمو التالي للإصابات الجديدة بالعدوى:

  • الجيل الأول: 2 إصابة جديدة بالعدوى.
  • الجيل الثاني: 4 إصابات جديدة بالعدوى.
  • الجيل الثالث: 8 إصابات جديدة بالعدوى.
  • الجيل الرابع: 16 إصابة جديدة بالعدوى.

بشكل عام، هناك 2^{n} إصابة جديدة بالعدوى في الجولة n من الإصابات الجديدة. بهذا المعدل، وبافتراض أن العدوى تنتشر كل أسبوع، فسيُصاب سكان العالم بأسره (7.8 مليار نسمة) بهذا المرض بعد أكثر من 32 أسبوعا بقليل.

تَظهر صورة مختلفة تماما عندما يكون عدد التكاثر الأساسي R_{0} أقل من 1. فعلى سبيل المثال، تخيل أن لدينا R_0=0.5. إن من الواضح، أنَّ الشخص المُصاب لا يمكنه التسبُب في إصابة نصف شخص بالعدوى، ولكن تذكر أن هذا مُعدل: ما يعني أنَّ 10 أشخاص قد يتسببون في إصابة 5 أشخاص آخرين بالعدوى، أو أنَّ 100 شخص قد يتسببُ في إصابة 50 شخصا آخر بالعدوى. وعلى نفس منوال المثال السابق، سنفترض في البداية أن شخصا واحدا فقط هو المُصاب، ومنه فإن عدد الإصابات الجديدة بالعدوى سيكون على النحو الآتي:

  • الجيل الأول: 0.5 إصابة جديدة بالعدوى.
  • الجيل الثاني: 0.25 إصابة جديدة بالعدوى.
  • الجيل الثالث: 0.125 إصابة جديدة بالعدوى.
  • الجيل الرابع: 0.0625 إصابة جديدة بالعدوى.

بشكل عام، هناك (0.5)^{n} إصابة جديدة بالعدوى في الجولة n من الإصابات الجديدة. يصبح هذا العدد أصغر وأصغر كلما زاد العدد n. أي أنَّ طريق انتشار المرض مسدود.

مُعدل عدد الإصابات الجديدة بالعدوى من أجل عدد تكاثر أساسي يُساوي 0.5

ماذا لو أنَّ R_0=1 ؟ في هذه الحالة سيكون المرض مُزمنا: موجودٌ دائما في مجموع السكان، لكنه ليس وباءً.

عدد التكاثر الفعّال

إذًا، ونظرا لأن R_{0} الحصبة أو بعض سلالات الأنفلونزا الموسمية، أكبر من 1، فكيف لم يُصَب العالم بأسره بهذه الأمراض منذ زمن بعيد؟ السبب أنّ R_{0} هو مُعدل عدد الأشخاص الذين يُتوقع أن يُصابوا بالعدوى من الشخص المُصاب، على اعتبار أن جميع أفراد السكان عُرضة للإصابة بالمرض. في الحياة العادية، قد يكون هذا هو الحال إذا ما دخل شخص مُصاب بمرض إلى منطقة من العالم لم يُشاهَد فيها ذاك المرض من قبل. أي ليس لدى الناس مناعة ولا لقاح يحميهم. مما يعني أنَّه في حالة R_{0} من 2 فإن عدد المصابين سيزداد بشكل كبير في البداية، كما وصفنا في المثال الأول أعلاه.

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

في حياتنا العادية، يُستحسن النظر إلى عدد التكاثر الفعال للمرض، والذي يُشار إليه أحيانا بالرمز R أي مُعدل عدد الأشخاص المُصابين بالعدوى من الشخص المُصاب في مجموع سُكانٍ لدى بعض أفراده مناعة (أو مع وجود بعض الإجراءات الأخرى لاكتساب المناعة). بالطبع فإن R_{0} و R مرتبطان. بكتابة s للدلالة على نسبة السكان المُعَرَضين للإصابة بالمرض، ينتج لدينا:

R=sR_0.

فمثلا، إذا كان نصف السكان فحسب عُرضة للإصابة، أي أنَّ s=0.5 فسينتج لدينا R=0.5R_0 في هذه الحالة، إذا كان R_{0} أقل من أو يساوي 2 فسيكون R أقل من أو يساوي 1 ولن يتحول المرض إلى وباء. إنَّ الهدف الأسمى لأي إجراء، سواء كان تطعيما أو تباعدا اجتماعيا، هو الوصول بعدد التكاثر الفعال إلى ما أقل من 1.

مناعة القطيع

ما علاقة كل هذا بمناعة القطيع؟ الفكرة العامة وراء مناعة القطيع هي أن المرض لا يمكن أن يستوطن وينمو ليصبح وباءً في مجموع سُكانٍ لدى الكثير من أفراده حصانة ضد المرض. وبالتالي حماية الأفراد غير المُحَصَنين. يحمي مجموع السكان (يُدعى مع الأسف، القطيع) الأفراد الضعفاء.

إذاً، كم عدد الأفراد من مجموع السكان، الذي يتطلب الأمر أن يكونوا مُحصَنين، لتحقيق مناعة القطيع؟ تخيل أن المرض له عدد تكاثر أساسي R_{0} أكبرَ من 1 أي تهديد بالوباء. وكما لاحظنا سابقا، إذا كان عدد التكاثر الفعّال R أقل من 1، فسيختفي المرض في النهاية. أي أن الأمر يتطلب الوصول بعدد التكاثر الفعّال R إلى ما أقل من 1 لتحقيق مناعة القطيع. ونظرا لأن R=sR_0. حيث s نسبة السكان المُعَرَضين للإصابة بالمرض فالأمر يتطلبُ:

sR_0<1.

إعادة ترتيب المتراجحة يُعطينا:

s<1/R_0.

وبعبارة أخرى، يتطلب الأمر جعل نسبة الأفراد المُعَرَضين للإصابة بالمرض من مجموع السكان أقل من 1/R_0 فكم عدد الأفراد الذين يجب أن يكونوا مُحصَنين لتحقيق ذلك؟ إذا كانت نسبة السكان المُعَرَضين للإصابة هي s فإن نسبة السكان غير المُعَرَضين للإصابة، أي المُحصَنين، هي 1-s أي أنَّ:

s<1/R_0.

تعني أن:

1-s>1-1/R_0.

وبالتالي، لتحقيق مناعة القطيع، يتطلب الأمر التأكد من أنَّ نسبة 1-1/R_0 على الأقل من السكان مُحصَنة. بالنسبة إلى R_{0} من 2.5 (وهي النهاية الأعلى لتقديرات “كوفيد-19”) فالأمر يتطلب الوصول إلى ما لا يقل عن نسبة 1-1/2.5=0.6 من السكان مُحصَنة. أي ما لا يقل عن 60% من السكان.

يمكن للقطيع أن يحمي الفرد

كيف نُحقق ذلك؟ حسنا، من الناحية المثالية، سنحقق ذلك بتطعيم ما لا يقل عن 60% من السكان. في حالة غياب لقاحٍ، قد نأمل أن يتحقق هذا المستوى من المناعة بشكل طبيعي (أن يُصاب الشخص بالمرض ومن ثَمَ يكتسب مناعة). ولكن لأن عدد الوفيات بسبب كوفيد-19 كبير جدا فلا يمكننا السماح للمرض بالانتشار لمجرد الثقة في معرفة أن المزيد من العدوى تعني المزيد من المناعة.

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

إذن، ماذا علينا أن نفعل حاليا؟ قد يكون أحد الخيارات هو الإبقاء على وضعية الإغلاق التام إلى حين توفُّرِ لقاحٍ ما، لكن هذا قد يستغرق أكثر من عام. الخيارُ الآخر هو الدخول في وضعيات الإغلاق المتقطعة لإبقاء الارتفاعات المتتالية للوباء أقل من القدرة الحرجة لأنظمة الرعاية الصحية.

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

بشكل عام، تُرسِل حساباتنا (أعلاه) أيضا رسالة مهمة حول التطعيم: فهو لا يحمي الفرد الذي تم تطعيمه ضد المرض فحسب، بل أيضا أولئك الأفراد الذين لن يتم تطعيمهم لسبب أو لآخر وبالتالي هم عُرضة للإصابة بالعدوى. التطعيم ليس لك وحدك، بل لكامل “القطيع”!

لمعرفة المزيد – وبالعربية- حول طبيعة النماذج الرياضية المُستخدمة للتنبؤ بمسار الوباء، إقرأ مقالة الرياضيات وأزمة الكورونا: الجزء الأول والجزء الثاني.


المقال الأصلي

Maths in a minute: “R nought” and herd immunity

نُشِر بتاريخ: April 2, 2020

——————

ترجمة: مديحة حوري.

(تمت المراجعة يوم الإثنين 2020/08/04)

نُشِرت في الرياضيات في دقيقة | الوسوم: , , , , , | أضف تعليق

الرياضيات في دقيقة: مخططات فورونوي

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

ليس الأمر بالصعب (قد يكون مُملا نوعا ما إذا ما قُمتَ به يدويا )، ابدأ بمستشفيين عند النقطتين (أ) و(ب) على الخريطة. ارسم القطعة المستقيمة التي تربطهما، أوجد منتصف هذه القطعة المستقيمة، ثم ارسم الخط الذي يمر عبر المنتصف ويكون عموديا على القطعة المستقيمة [أب]. يقسم هذا الخط المدينة إلى منطقتين. تحتوي إحداهما، التي تتضمن (أ)، على جميع النقاط الأقرب إلى (أ) من (ب). بينما تحتوي الأخرى على جميع النقاط الأقرب إلى (ب) من (أ). أما النقاط الموجودة على الخط المستقيم فهي على مسافةٍ واحدةٍ من (أ) و(ب)

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

استمر على نفس المنوال، في تحديد مناطق التقاطع، إلى أن تقوم بإحصاء جميع المستشفيات. المُخطط الذي ستحصل عليه في النهاية، هو تقسيم الخريطة إلى مناطق النقاط الأقرب إلى نقطة محددة من نقاط أخرى، ويُدعى مخطط فورونوي. نِسبةً إلى عالم الرياضيات الروسي غريغوري فورونوي (1868- 1908).  

مخطط فورونوي

مخططات فورونوي مُفيدة أيضا في العديد من المجالات الأخرى. فمثلا، قد تُستخدم لدراسة أنماط نمو الغابات، أو في مساعدة الروبوتات على إيجاد طرق واضحة عبر مجموعة من العقبات. تتطرق ويكيبيديا للعديد من التطبيقات الأخرى.

خريطة “جون سنو”. توضح الأشرطة عدد الوفيات عند كل عنوان، يُشير الخط المنحنى إلى مسافة مُتساوية من مضخة شارع برود ومضخة أخرى

لكننا اخترنا المُقاربة الطبية تمهيدا لحادثة قديمة. في خمسينيات القرن التاسع عشر، أدى تفشِّي الكوليرا في حي”سوهو” في “لندن” إلى مقتل 10% من السكان وإبادة أُسَرٍ بكاملها في أيام. ساد الاعتقاد آنذاك أن سبب المرض “الهواء السيئ”، لكن الطبيب “جون سنو” كان لديه رأي آخر: إذ كان يعتقد أن الكوليرا سببها إمدادات المياه الملوثة، التي كان مصدرها المضخات المنتشرة في جميع أنحاء المدينة آنذاك.

لقد كان قادرا على تأكيد نظريته، إذ قام بتوقيع علامةٍ بعدد الوفيات عند كل عنوان على خريطة سوهو أولا، ومِن ثم حدد “منطقة مستجمع المياه” لمضخة مياه في شارع برود 40 (شارع برودويك حاليا)، بحيث كانت العلامات المُوقَّعة على الخريطة ضمن “منطقة مستجمع المياه” هذه، أقربَ إلى مضخة شارع برود من أي مضخة أخرى. وعلى عكس المثال السابق، لم يستخدم سنو المسافة المباشرة، بل مسافة السير على الأقدام على طول الشوارع والأزقة. وقد اتضح في الأخير، أن مُعظم علامات الوفيات المُوقعة على الخريطة تقع داخل “منطقة مستجمع المياه” لمضخة شارع برود.

أظهر هذا، بشكل مؤكد للغاية، أن المياه الملوثة كانت بالفعل سبب الكوليرا. واليوم، تتميز البقعة التي كانت فيها المضخة سابقا، بنصب تذكاري، للتذكير بالحادثة. يمكنك قراءة المزيد في هذه المقالة.


المقال الأصلي

Maths in a minute: Voronoi diagrams

نُشِر بتاريخ: March 30, 2020

——————-

ترجمة: مديحة حوري.

(تمت المراجعة يوم الأحد 2020/08/02)

نُشِرت في الرياضيات في دقيقة | الوسوم: , , | أضف تعليق

الرياضيات في دقيقة: التباعد الاجتماعي

تخيل تواجُد عددٍ كبيرٍ من الأشخاص في حديقة ما، يريد كل شخص منهم أن يُحافظ على الأقل على مسافة 2 متر من الآخر، لكن القائمين على الحديقة يرغبون في تواجُد أكبر عدد ممكن من الأشخاص على مسافة 2م من بعضهم بعضا كحد أدنى. كيف ينبغي للناس ترتيبُ أنفسهم من أجل تحقيق ذلك؟ وما عدد الأشخاص الواجب على الفرد الابتعاد عنهم مسافة 2م بالضبط ضمن هذا الترتيب؟

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

كم عدد المثلثات (مِثل المثلث أعلاه) التي يُمكن وضعُها حول (أ) بحيث لا تتداخل؟ حسنا، مقدار كل زاوية في المثلث المتساوي الأضلاع 60 درجة. هناك ما مجمُوعه 360 درجة مُتاحة حول (أ)، مما يعني أن بإمكانك وضع 6 = \frac{360}{60} مثلثات متساوية الأضلاع بالضبط حول (أ). أي بعبارة أخرى، فإن عدد الأشخاص الذين يمكنهم أن يتموضعوا على مسافة 2م من (أ) و 2م من بعضهم بعضا على الدائرة هو ستَّة.

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

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


المقال الأصلي

Maths in a minute: Social distancing

نُشِر بتاريخ: March 27, 2020

——————

ترجمة: مديحة حوري.

(تمت المراجعة يوم السبت 2020/08/01)

نُشِرت في الرياضيات في دقيقة | الوسوم: , , , , , | أضف تعليق