طريقة “بلانكنشب” في حساب القاسم المشترك الأكبر

بحثت على شبكة الأنترنت عن أي تعريف أو شرح لها باللغة العربية ولم أجد! وبعد أن أتقنت الطريقة مبدئيا والحمد لله أنجزت هذا المقال البسيط عنها. بالاعتماد 90% على كتاب “مقدمة في نظرية الأعداد” للدكتور فالح الدوسري.

يمكن حساب القاسم المشترك الأكبر d للعددين a,b وإيجاد m,n\in Z بحيث d=am+bn باسخدام طريقة بلانكنشب (Blankinship).

التعريف

وهي طريقة لايجاد الحلول m و n للتطابق الخطي:

am+bn=d

من خلال إنشاء مصفوفة، يتم فيها محاذاة شعاع (متجه) يحتوي على a و b مع مصفوفة الوحدة \begin{bmatrix} 1 & 0\\ 0& 1 \end{bmatrix} وذلك كالآتي:

A=\begin{bmatrix} a & 1 & 0 \\ b & 0 & 1\\ \end{bmatrix}

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

الطريقة

نفرض أن a> b> 0  وأن A=\begin{bmatrix} a & 1 & 0 \\ b & 0 & 1\\ \end{bmatrix} ونضيف (بالتعاقب) مضاعفات أحد الصفوف إلى الصف الآخر ويُسمى مثل تلك العمليات عمليات صفوف أولية ar_{i}+r_{j} إلى أن نصل إلى مصفوفة بالشكل \begin{bmatrix} 0 & x & y\\ d& m & n \end{bmatrix}  أو  \begin{bmatrix} d & m & n\\ 0& x & y \end{bmatrix}  فيكون d=(a,b)=am+bn

الأمثلة

أوجد d=(a,b) ثم أوجد m,n\in Z بحيث أن  d=am+bn عندما:

(أ) a=39 , b=18

بما أن A=\begin{bmatrix} 39 & 1 & 0 \\ 18 & 0 & 1\\ \end{bmatrix} ، وبما أن 39=2(18)+3 إذا نضرب الصف الثاني r_{2} (row_{2}) في (2-) ونجمعه مع الصف الأول r_{1} فنجد أن

A=\begin{bmatrix} 39& 1& 0\\ 18& 0 & 1 \end{bmatrix}\xrightarrow[]{-2r_{2}+r_{1}}\begin{bmatrix} 3 & 1 &-2 \\ 18& 0 & 1 \end{bmatrix}

وبما أن 18=6(3). إذا نضرب الصف الأول في (6-) ونجمعه مع الصف الثاني فنجد أن

\begin{bmatrix} 3& 1& -2\\ 18& 0 & 1 \end{bmatrix}\xrightarrow[]{-6r_{1}+r_{2}}\begin{bmatrix} 3 & 1 &-2 \\ 0& -6 & 13 \end{bmatrix}

إذا d=(39,18)=3=39(1)+18(-2)

(ب) a=1976 , b=365

بما أن A=\begin{bmatrix} 1976 & 1 & 0 \\ 365 & 0 & 1\\ \end{bmatrix} ، وبما أن 1976=365(5)+151 إذا نضرب الصف الثاني r_{2} في (5-) ونجمعه مع الصف الأول r_{1} فنجد أن

A=\begin{bmatrix} 1976& 1& 0\\ 365& 0 & 1 \end{bmatrix}\xrightarrow[]{-5r_{2}+r_{1}}\begin{bmatrix} 151 & 1 &-5 \\ 365& 0 & 1 \end{bmatrix}

وبما أن 365=2(151)+63. إذا نضرب الصف الأول في (2-) ونجمعه مع الصف الثاني فنجد أن

\begin{bmatrix} 151& 1& -5\\ 365& 0 & 1 \end{bmatrix}\xrightarrow[]{-2r_{1}+r_{2}}\begin{bmatrix} 151 & 1 &-5 \\ 63& -2 & 11 \end{bmatrix}

وبما أن 151=2(63)+25. إذا نضرب الصف الثاني في (2-) ونجمعه مع الصف الأول فنجد أن

\begin{bmatrix} 151& 1& -5\\ 63& -2 & 11 \end{bmatrix}\xrightarrow[]{-2r_{2}+r_{1}}\begin{bmatrix} 25 & 5 &-27 \\ 63& -2 & 11 \end{bmatrix}

وبما أن 63=2(25)+13. إذا نضرب الصف الأول في (2-) ونجمعه مع الصف الثاني فنجد أن

\begin{bmatrix} 25& 5& -27\\ 63& -2 & 11 \end{bmatrix}\xrightarrow[]{-2r_{1}+r_{2}}\begin{bmatrix} 25 & 5 &-27 \\ 13& -12 & 65 \end{bmatrix}

وبما أن 25=13(1)+12. إذا نضرب الصف الثاني في (1-) ونجمعه مع الصف الأول فنجد أن

\begin{bmatrix} 25& 5& -27\\ 13& -12 & 65 \end{bmatrix}\xrightarrow[]{-r_{2}+r_{1}}\begin{bmatrix} 12 & 17 &-92 \\ 13& -12 & 65 \end{bmatrix}

وبما أن 13=12(1)+1. إذا نضرب الصف الأول في (1-) ونجمعه مع الصف الثاني فنجد أن

\begin{bmatrix} 12& 17& -92\\ 13& -12 & 65 \end{bmatrix}\xrightarrow[]{-r_{1}+r_{2}}\begin{bmatrix} 12 & 17 &-92 \\ 1& -29 & 157 \end{bmatrix}

وبما أن 12=12(1). إذا نضرب الصف الثاني في (1-) ونجمعه مع الصف الأول فنجد أن

\begin{bmatrix} 12& 17& -92\\ 1& -29 & 157 \end{bmatrix}\xrightarrow[]{-r_{2}+r_{1}}\begin{bmatrix} 0 & 46 &-249 \\ 1& -29 & 157 \end{bmatrix}

وعليه فإن d=(1976,365)=1=1976(-29)+365(157)


المراجع: [1] (ص35،34). [2]

نُشِرت في ليالي الرياضيات, اليوم 3) أشياء أكتبها | الوسوم: , , , , | أضف تعليق

الرياضيات في دقيقة: توزيع ذي الحدين

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

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

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

توزيع ذي الحدين لأزواج مختلفة من قيم n و k. التمثيل البياني يوضح احتمالات أن يكون k  نجاح من n محاولة، مقابل قيمة k.

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

p\times p\times (1-p).

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

نجاح، نجاح، فشل

نجاح، فشل، نجاح

فشل، نجاح، نجاح.

كل من هذه لها احتمالية p\times p\times (1-p). وبالتالي فإن احتمالية واحد من النتائج الثلاث الممكنة الحدوث هي

3\times p\times p\times (1-p)=3p^{2}(1-p).

كتابة هذا بشكل أعم تعطينا

P=\binom{n}{k}p^{k}(1-p)^{n-k}.

حيث P هو (k نجاح من n محاولة)

وهنا يمكن للمتغير k أن يأخذ القيم 0، 1، 2، وصولا إلى n، والتعبير الأول هو معامل ذي الحدين

\binom{n}{k}=\frac{n!}{(n-k)!k!}

علامة التعجب (!) تشير إلى العاملي والذي يُعرَف كالآتي

n!=n\times (n-1)\times (n-2)...\times 2\times 1.

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

توزيع ذي الحدين له متوسط حسابي np وتباين np(1-p). للاضطلاع على مثال عملي، إقرأ هذه المقالة.


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

Maths in a minute: The binomial distribution

July 13, 2017

——————-

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

math.nights@gmail.com

——————–

نُشِرت في ليالي الرياضيات, اليوم 4) وأخرى أكتب عنها | الوسوم: , , , | أضف تعليق

كتاب [مذكرات التاريخ والجغرافيا] للسنة الثالثة ثانوي.pdf

رابط التحميل: هــــنـــا

بالتوفيق والنجاح للجميع

——-

نُشِرت في ما بينهما, اليوم 5) أشياء أكتبها | الوسوم: , , | أضف تعليق

التاريخ والجغرافيا/ جميع السنوات/ جميع مذكرات الأستاذ بوشيخ عبد الحاكم (tachfin)/ للتحميل المباشر

السنة الأولى ثانوي

أ/ التاريخ

الوحدة الأولى + الوحدة الثانية.

الوحدة الثالثة: الوضعية (1)الوضعية (2)الوضعية (3)

ب/ الجغرافيا

الوحدة الأولى + الوحدة الثانية + الوحدة الثالثة.


السنة الثانية ثانوي

أ/ التاريخ

الوحدة الأولى الوحدة الثانيةالوحدة الثالثة تاريخ+جغرافيا

ب/ الجغرافيا

الوحدة الأولىالوحدة الثانية – الوحدة الثالثة تاريخ+جغرافيا


السنة الثالثة ثانوي

أ/ التاريخ

الوحدة الأولىالوحدة الثانيةالوحدة الثالثة.

ب/ الجغرافيا

الوحدة الأولىالوحدة الثانيةالوحدة الثالثة.


ولا تنسونا من صالح دعائكم./ أ. مديحه حوري.

نُشِرت في ما بينهما, اليوم 6) وأخرى أكتب عنها | الوسوم: , , , , , , , , | أضف تعليق

الرياضيات في دقيقة: الإحداثيات القطبية

الإحداثيات الديكارتية

كيف يمكنك تحديد نقطة على المستو؟ من الطرق لانجاز ذلك، والتي أنت على دراية بها على الغالب، هي في استخدام نظام الإحداثيات الديكارتية. ارسم محورين متعامدين وصف موضع النقطة p باحداثيتين (x_{0},y_{0}) . لايجاد p تنطلق من النقطة (0,0) وتسير مسافة x_{0} على طول المحور الأفقي ومسافة y_{0} على طول المحور العمودي.

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

في الصورة الموضحة في المقال الأصلي انقر على النقطة واسحبها لتلاحظ كيفية تغير احداثياتها القطبية (r,\theta ) (قياس الزوايا مُمَثل بالراديان).

بعض الأشكال التي يصعُب وصفها في الإحداثيات الديكارتية هي سهلة الوصف باستحدام الإحداثيات القطبية. على سبيل المثال، فكر في دائرة نصف قطرها 2 ترتكز على النقطة (0,0). وهي تتكون من جميع النقاط التي تقع على مسافة 2 من (0,0). في الإحداثيات القطبية هذه هي جميع النقاط ذات الإحداثيات (2,\theta )، حيث \theta يمكن أن تأخذ أي قيمة على الاطلاق.

في الإحداثيات الديكارتية يصعب وصف هذه الدائرة، هي تتكون من جميع النقاط ذات الإحداثيات (x,y) حيث:

x^{2}+y^{2}=2^{2}=4

(وذلك حسب نظرية فيثاغورس)

دائرة. تتكون من جميع النقاط التي إحداثياتها الديكارتية (x, y) تحقق x^2+y^2=4  واحداثياتها القطبية (r, θ) تحقق r=2 . النقاط الموضحة إحداثياتها الديكارتية (2√, 2√) واحداثياتها القطبية (2,45)، مع زاوية مقاسة بالدرجات.

مثال آخر جميل يأتي من النظر إلى جميع النقاط التي تتساوى إحداثيتها القطبية الأولى مع إحداثيتها القطبية الثانية. بعبارة أخرى، كل النقاط من الشكل (r,r). ومع نمو r، النقطة (r,r) تتحرك مبتعدة عن النقطة (0,0). الزاوية \theta=r تنمو بنفس المعدل. وكلما أصبحت  r أكبر، الزاوية \theta=r تدور وتدور حول النقطة (0,0). النتيجة هي حلزون أرخميدس. يظهر الفيديو النقاط ذات الإحداثيات (r,r) عندما تنمو r من 0 إلى 20\pi (أي ما يعادل 10 دورات كاملة من \theta=r). من الصعب جدا وصف حلزون أرخميدس في الإحداثيات الديكارتية!

أخيرا، ننظر إلى النقاط التي إحداثيتها القطبية الأولى r تساوي r=e^{\frac{\theta }{5}}، حيث \theta هي الإحداثية القطبية الثانية و e\approx 2.718 هي قاعدة اللوغاريتم الطبيعي. في هذه الحالة، الإحداثية الأولى r=e^{\frac{\theta }{5}} (المسافة من النقطة المقابلة إلى (0,0)) تنمو بشكل أسرع من الإحداثية الثانية \theta (الزاوية). والنتيجة هي حلزون لا يدور بنفس نموذج دوران حلزون أرخميدس – هو مثال على حلزون لوغاريتمي. يوضح الفيديو النقاط ذات الإحداثيات (e^{\frac{\theta }{5}},\theta ) عندما تنمو \theta من 0 إلى 8\pi (أي ما يعادل 4 دورات كاملة).

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


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

Maths in a minute: Polar coordinates

June 23, 2017

—————

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

math.nights@gmail.com

 

نُشِرت في ليالي الرياضيات, اليوم 4) وأخرى أكتب عنها | الوسوم: , , , | أضف تعليق

ساعة سماوية عقاربها الأرض والمريخ

الشكل (1)

“يمكن اعتبار الشكل ساعة سماوية، ولكن العقارب ليست الساعات والثواني: SE عقرب الأرض وSM عقرب المريخ” ص25.

هي طريقة في حل مسألة لفتت انتباهي أثناء قراءتي لكتاب جورج بوليا، الطرق الرياضية في العلوم. وذلك ضمن عنوان “سنة المريخ” الذي يوضح فيه الكاتب طريقة كبلر للاجابة على هذا السؤال: ما مقدار سنة المريخ؟ والتي سأختصرها ضمن هذا المقال.

“فرضية كبلر الأساسية كانت أن المريخ والأرض يدوران في نفس المستوي بحركة دائرية منتظمة حول الشمس” (حاليا نحن ندرك أن هذا غير صحيح، لكن فرضيته تمثل تقريبا أوليا مكنه من معالجة المسألة قيد الدراسة)

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

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

لدينا:

SE عقرب الأرض.

SM عقرب المريخ.

لنفرض:

T_{E}: سنة الأرض (الوقت اللازم ليتم عقرب الأرض دورة كاملة).

P: الفترة الزمنية بين تطابقين متتاليين لعقارب ساعتنا هذه.

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

الشكل (2)

بما أن سرعة SE أكبر من سرعة SM ولذا تلحق الأرض E بــالمريخ M عاجلا أو آجلا. ولنفرض أن هذا يحدث عندما يدور SE بمقدار زاوية a (تقاس الزاوية من خط البداية). لاحظ الشكل (3)

الشكل (3)

أثناء الفترة P بين تقابلين متتاليين، يدور “عقرب المريخ” بزاوية a و”عقرب الأرض” بزاوية 360^{\circ}+a. ومن مراقبة المريخ والأرض. نحصل على الجدول الآتي:

في حالة الدوران بسرعة منتظمة، يتناسب زمن الدوران طرديا مع زاوية الدوران:

من بيانات المريخ نجد: (1)……\frac{P}{T_{M}}=\frac{a}{360}

من بيانات الأرض نجد: (2)……\frac{P}{T_{E}}=\frac{360+a}{360}

للربط بين T_{M} و T_{E} نتخلص من a من (2)

\frac{P}{T_{E}}=1+\frac{a}{360}

\frac{P}{T_{E}}=1+\frac{P}{T_{M}}

وبهذا نكون قد حصلنا على العلاقة بين T_{M} و P و T_{E}، حيث T_{E} معلوم وP معلوم (حسَبَه اليونانيون). وبالتالي استطاع كبلر حساب سنة المريخ T_{M}.


ملاحظة | Posted on by | الوسوم: , , | أضف تعليق

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

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

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

بصفة أعم، يمكن تعريف الميكنة الخلوية في أي بُعد (على سبيل المثال، يمكن أن يكون لديك مجرد صف أحادي-البعد من الخلايا، أو شبكة ثلاثية-الأبعاد من الخلايا)، ويمكن أن تشتمل على أكثر من لون واحد، ويمكن أن تشتمل أيضا على عنصر الفرصة.

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

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

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


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

Maths in a minute: Cellular automata

May 16, 2017

—————

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

math.nights@gmail.com

 

نُشِرت في ليالي الرياضيات, اليوم 4) وأخرى أكتب عنها | الوسوم: , | أضف تعليق