ما هي مسألتك؟

التقرير بصيغة PDF متوفر هــنــا.

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

هذا مكعب روبيك 5×5، الذي له 25 وجها مكعبا صغيرا، تشكل الوجه الأكبر. كلما قمت بزيادة عدد المكعبات الصغيرة المشكلة لمكعب روبيك، سيصبح حل المكعب أصعب وأصعب.

يحدد علماء الكمبيوتر ما إذا كانت مسألة ما سهلة أو صعبة من خلال احتساب كَم الوقت الذي تستغرقه لايجاد حلها. هناك العديد من المسائل العملية التي تقع ضمن فئة “الصعبة”. وهذا له آثار هامة في تحديد أي المسائل التي يمكن حلها بفعالية ودقة، وتلك التي لايمكن حلها إلا تقريبيا. بعبارة أخرى، هناك حد لما يمكن حسابه بطريقة دقيقة وفعالة، والعديد من المسائل العملية التي تتطلب طرق حل بديلة وتقريبية. تعريف الصعوبة من الناحية النظرية يقودنا إلى واحدة من الأسئلة المفتوحة الأكثر إثارة للاهتمام في الرياضيات، تدعى مسألة P مقابل NP. لذلك دعنا نلقي نظرة أقرب على المفاهيم المطلوبة.

مسائل سهلة

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

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

لنفترض، على سبيل المثال، أنك تُعطى تسلسلا من n أعداد متمايزة وفق ترتيب عشوائي من نوع ما، وعليك فرزها من الأصغر إلى الأكبر. إنه من السهل جدا إنشاء خوارزمية فرز بسيطة لن تتطلب أكثر من \frac{1}{2}n (n-1)= \frac{1}{2}n^2-\frac{1}{2}n  من الخطوات لانجاز ذلك. في أسوأ الأحوال ستحتاج إلى مقارنة كل عدد من n مع كل عدد من n-1 الأخرى، ما يعطينا n(n-1) من المقارنات. لكن وعلى اعتبار أنك لست في حاجة إلى مقارنة زوج معين من الأعداد مرتين (عند مقارنة a مع b لا تحتاج إلى مقارنة b مع a) وعليه يمكن تقسيم n(n-1) على 2. وبالتالي، أسوء-حالة وقت التشغيل لخوارزمية الفرز البسيطة هذه هو \frac{1}{2}n^2-\frac{1}{2}n خطوة. عموما، يقال أن الخوارزمية التي تحتاج إلى أقصى عدد من الخطوات والتي تنمو تناسبيا مع n^2 لديها أسوء-حالة وقت تشغيل من O(n^2).

( التعريف بالرمز O: نكتب S(n) لأسوء-حالة وقت تشغيل لخوارزمينة معينة (مثلا، وضع قائمة من n عدد، داخل ترتيب عددي ما). إذا كانت هناك أعداد صحيحة موجبة m و K بحيث من أجل n كبير بما فيه الكفاية لدينا

S(n) \leq Kn^ m,

ومنه يقال أن أسوء-حالة وقت تشغيل هي O(n^ m). هذا يعني أن أي أسوأ-حالة وقت تشغيل على شكل كثير حدود من الدرجة m من n هي O(n^ m))

أسوأ-حالة وقت تشغيل من الشكل O(n^ m) لبعض القيم (المحدودة) من m، تدعى كثير حدود وقت التشغيل (polynomial running time). على سبيل المثال، خوارزمية الفرز البسيطة الخاصة بنا لها كثير حدود أسوأ-حالة وقت تشغيل من m=2. حتى مع سلاسل طويلة جدا من الأعداد (أي القيم الكبيرة من n)، لا يزال بامكاننا أن نتوقع الحصول على قائمة مرتبة بشكل صحيح ضمن عدد معقول من الخطوات (لا يمكن أن تتعدى n^2، في هذه الحالة). في الواقع، هناك أسرع خوارزميات الفرز حتى مع أسوء-حالة وقت تشغيل من O(nlog(n))

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

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

نعم أو لا؟

كجانب تقني، غالبا ما يُشار إلى المسائل الحسابية باعتبارها مسائل قرار (.decision problems). بعبارة أخرى، بدلا من أن نسأل عن ماهو أقصر الطرق بين الموضعين A وB، نسأل: هل هناك طريق بين A وB يبلغ طوله k على الأكثر؟ هذا السؤال له جواب من صيغة نعم/لا، لهذا يُدعى مسألة قرار. إذا أرجعت خوارزميتك “نعم” كجواب، فيجب عليها أيضا أن تعطي مسارا واحدا على الأقل كمثال، بحيث يمكنك بعد ذلك التحقق بسهولة من أن طوله بالفعل ليس أطولا من k.

إصدار القرار هذا لمسألة أقصر مسار، يمكن تحويله مباشرة إلى إصدار علينا أن نبدأ منه، ويدعى الإصدار الأمثل. أولا، نجد الحد الأعلى k للمسافة بين A وB. أحد أيسر وأسهل الطرق لحساب الحد الأعلى هي ببساطة جمع المسافات بين الأزواج المتجاورة من n تقاطع في شبكة الطرق (أي على الأكثر n^2 عملية جمع). ثم طرح السؤال: هل هناك طريق بين A وB يبلغ طوله k على الأكثر؟ من خلال بُنية الحد الأعلى k، سيكون الجواب بالطبع “نعم”. ومنه نطرح السؤال التالي: هل هناك طريق بين A وB يبلغ طوله k-1 على الأكثر؟ ونواصل هذا إلى غاية قيمة معينة l حيث لا يزال الجواب “نعم”، لكن من أجل l-1 فالجواب “لا”. وبالتالي فالواضح أن أقصر الطرق بين A وB سيكون بطول l (وخوارزميتك ستعطيك على الأقل أحد هذه الطرق ).

إذا كانت خوارزميتك لحل إصدار القرار لمسألة أقصر مسار فعالة (أي أن أسوأ-حالة وقت تشغيل هي كثير حدود من n)، فإن خوارزمية تحويلها إلى مسألة أمثل مقابلة، فعالة أيضا. لملاحظة هذا في المثال المُعطى، لاحظ أن الحد الأعلى k هو على الأكثر d\times n^2، حيث d هي أطول مسافة بين أي أزواج متجاورة من n نقطة. لذلك، نحن في حاجة إلى تشغيل خوارزمية إصدار القرار dn^2 مرة على الأكثر. وبما أن خوارزمية إصدار القرار لها أسوأ-حالة وقت تشغيل من O(n^2)، فإن خوارزمية الإصدار الأمثل سيكون لها أسوأ-حالة وقت تشغيل من O(n^4)، والتي من الواضح أنها لا تزال كثير حدود. مع ذلك، وكما اشرنا أعلاه، من الممكن في الواقع بناء خوارزمية O(n^2) لمسألة أقصر مسار لحل الإصدار الأمثل للمسألة كذلك.

مسائل صعبة

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

ما هي أقصر جولة لزيارة جميع المواقع المفضلة لديك؟

تعرف هذه المسألة بمسألة البائع المتجول (travelling salesman problem .TSP). وتبدو للوهلة الأولى مُشابهة جدا لمسألة أقصر مسار. مع ذلك وإلى الآن، لا أحد قادر على بناء خوارزمية كثير حدود-زمني لحل هذه المسألة على النحو الأمثل. عمليا، الطريقة الوحيدة لضمان العثور الدائم على أقصر جولة، لأي نموذج مُعطى من “مسألة البائع المتجول”، هي التقييم الشامل لكل الترتيبات الممكنة للــn مدينة، ثم ببساطة اختيار ذلك الترتيب الذي يؤدي لأقصر جولة.

مع ذلك، فإن عدد الترتيبات الممكنة للمدن ينمو بسرعة هائلة مع تزايد عدد المدن. في الواقع، عدد الترتيبات الممكنة هو

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

عمليا، هذا يعني أنه وفي كل مرة تقوم فيها بزيادة عدد المدن n بواحدة، فإن عدد الترتيبات الممكنة للمدن سيزيد عن الضعف. لذلك، فإن خوارزمية التقييم الشامل سيكون لها أسوأ-حالة وقت تشغيل لا يقل عن O(2^ n) (أي العدد 2 مضروبا في نفسه n مرة) وهو ما يُسمى الأسية.

على سبيل المثال، في نموذج مسألة مع 5 مدن (n=5)، هناك 120 ترتيبا ممكنا، أو جولة. هذا مقبول. لكن من أجل n=10 مدينة، عدد الجولات المُحتملة فعليا هو أكثر من ثلاثة ملايين. أما بالنسبة إلى 50 مدينة فإن تقييم جميع الجولات المحتملة قد يستغرق وقتا أطول من عمر الكون، حتى لأسرع أجهزة الكمبيوتر. ومن الواضح، أن مثل هذه الخوارزميات الشاملة ليست فعالة.

لإدراك الفرق بين أسوأ-حالة وقت تشغيل في كثير حدود (مثل O(n^2)) وأسية (مثل O(2^ n))، ألق نظرة على الشكل أدناه. مع تزايد قيم n (على طول المحور الأفقي)، كثير حدود وقت التشغيل (اللون الأزرق) ينمو ببطء نسبيا، لكن أسية وقت التشغيل (اللون الأحمر) تُسرع نحو الذروة. مسائل مثل “مسألة البائع المتجول”، والتي لا تتوفر إلا خوارزميات أسية-الزمن (أو أسوأ) فقط لحلها على نحو أمثل، تدعى تقريبا بالمستعصية – قد نضطر للانتظار “إلى الأبد” للحصول على إجابة.

صعبة، لكن يسهل التحقق منها

من بين تلك المسائل المستعصية، هناك فئة خاصة من المسائل: تلك التي إذا ما تم حلها نوعا ما، فلا يزال بالامكان التحقق منها بكفاءة. على سبيل المثال، اعتبر “إصدار القرار” لمسألة البائع المتجول كالآتي: هل هناك جولة تزور من خلالها كل المدن ويبلغ طولها k على الأكثر؟ افرض أن أحدا ما أخبرك أن الجواب “نعم”، شريطة تزويدك بهذه الجولة. ومنه فمن السهل التحقق أن طولها حقا لا يتجاوز k عن طريق جمع المسافات الفردية بين المدن على طول الجولة المُعطاة ببساطة. إذا كان هناك n فالأمر يتطلب n عملية جمع، أي أن الجواب “نعم” يمكن التحقق منه بكثير حدود زمني (بغض النظر عن كم الوقت المستغرق للحصول على هذا الجواب). المسائل التي لها هذه الخاصية، وبالترافق مع مسائل مصنفة مسبقا في الفئة P، تُشكل فئة المسألة الأكبر NP (لكثيرات الحدود غير-القطعية).

مسائل صعبة جدا

تدعى المسألة التي لا تقل صعوبتها عن أي مسألة في فئة NP بــمسألة NP-الصعبة. مسائل NP-الصعبة لا تحتاج أن يكون لها حلولا يمكن التحقق منها بكفاءة، لذلك لا تحتاج أن تكون في NP ذاتها. لكن مسائل NP-الصعبة تلك والتي هي ذاتها في NP تشكل فئة فرعية خاصة: تُدعى مسائل NP-التامة (أو NP-الكاملة). إذا إختلط عليك أمر جميع مسائل الفئات تلك، فالرسم البياني أدناه قد يساعدك على الفهم:

NP تشمل P وتتقاطع مع فئة مسائل NP-الصعبة. التقاطع يؤلف مسائل NP-التامة.

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

في عام 1971 نشر عالم الكمبيوتر والرياضياتي ستيفن كوك (Stephen Cook) إثباتا معقدا أن أي مسألة في NP يمكن اختزالها إلى ما يُسمى مسألة المنطق القابل للإرضاء (Boolean satisfiability problem أو SAT). وفي نفس الفترة تم تطوير إثبات مماثل، لكن بشكل مستقل، من طرف ليونيد ليفين (Leonid Levin) في الإتحاد السوفياتي (آنذاك). مع هذا، فقد تم التأسيس لأول كيان معروف لمسألة NP-التامة آنذاك.

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

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

الحلول التقريبية

مسائل NP-التامة مثل مسألة البائع المتجول ليست مجرد قضية نظرية. إنها تظهر في كل مكان: في الاتصالات السلكية واللاسلكية، الخدمات اللوجيستية، الهندسة، الجدولة، تصميم الرقائق، أمن البيانات، وما لا يحصى من التطبيقات التجارية الأخرى يوما بعد يوم. وغالبا ما تتكون نماذج هذه المسألة في عالمنا من المئات أو حتى الآلاف من “المدن” (أي أن لديهم حجم مُدخلات كبير n). مستعصية للغاية، للأسف. لذلك، هناك حد فعلي لأي المسائل العملية التي يمكن حلها بطريقة دقيقة وفعالة وبكفاءة.

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

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


المصدر

What’s your problem?

January 24, 2018

——————-

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

math.nights@gmail.com

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

الرياضيات في دقيقة: الفائدة المركبة وعدد أويلر

الفائدة المركبة هي نعمة في الإدخار، لكن هي لعنة في الدَين.

الشئ الوحيد الجيد عن الدَين واجب الدفع هو أنه متصل بأحد الثوابت الأكثر أهمية في عالم الرياضيات: عدد أويلر e 

لمعرفة الصلة، لنفترض أنك اقترضت 100£ (£: جنيه استرليني) بسعر فائدة سنوي قدره 3٪. كم ستصبح مَدينا بعد ثلاث سنوات إذا لم تقم بأي تسديدات؟ من المغر التفكير أنك ستصبح مَدينا بالمبلغ الأصلي 100£ بالاضافة إلى 9٪ من 100£، أي ما مقداره 9£، أي ما مجموعه  109£.

لسوء الحظ، مع ذلك، هذه العملية الحسابية غير صحيحة تماما. بعد عام واحد ستكون مَدينا بالمبلغ الأصلي، 100£، بالاضافة إلى مقدار الفائدة من العام الأول، أي ما مقداره

0.03\times 100=3

وهذا يعطينا قيمة الدَين الإجمالي

100+0.03\times 100=100\times (1+0.03)=103

لمعرفة مقدار الدَين الواجب تسديده بعد عام آخر، عليك إضافة مقدار الفائدة من العام الثاني، أي ما يُعادل

0.03\times(100\times (1+0.03))=3.09

أي بقيمة دَين إجمالي

100\times (1+0.03)+0.03\times (100\times (1+0.03))=100\times (1+0.03)^{2}=106.09

مقدار الفائدة في العام الثالث سيكون

0.03\times (100\times (1+0.03)^{2})=3.18

أي بعد العام الثالث ستكون مَدينا بما مجموعه

100\times(1+0.03)^{3}=109.27

يمكنك أن تلاحظ أن مبلغ الفائدة المستحقة في كل سنة هو أكبر من المبلغ المستحق في السنة السابقة. إذا كنت قد اقترضت أكثر من 100£ فإن هذا النمو، أو التركيب، في سعر الفائدة سيكون بارزا أكثر: هي لعنة الديون، أو بالتزامن، هي نعمة الادخار.

ربما لاحظت وجود نمط ما في العبارات أعلاه! بالفعل، هناك عبارة عامة تصف كيفية نمو إجمالي دُيونك:

P(1+r)^{n}

حيث P هو المبلغ الابتدائي الذي اقترضته، r هو معدل الفائدة (حيث تُكتب r كعدد عشري، مثل 0.03، لا على شكل نسبة مئوية، 3٪) و n هو عدد مرات تركيب الفائدة. يزداد تركيب الفائدة غالبا، كلما زاد إجمالي المبلغ، مما يستدع أن تكون دائما على حذر.

لجعل الأمور أكثر بساطة، افترض أنك اقترضت 1£ (P=1) بمعدل فائدة سنوي قدره 100٪ (r=1). إذا قام البنك بحساب مبلغك الاجمالي في نهاية السنة الأولى فقط، إذن عليك تسديد:

1\times (1+1)^{1}=1\times 2=2

لكن ماذا لو قرر البنك تركيب سعر الفائدة فصليا (كل ثلاثة أشهر)، الزيادة في إجمالي المبلغ كل ثلاثة أشهر باستخدام معدل الفائدة 100\div 4=25 أي 25٪؟ وبالتالي بعد سنة واحدة عليك تسديد

1\times (1+1/4)^{4}=2.44

التركيب شهريا من شأنه أن يُنتج ما مجموعه

1\times (1+1/12)^{12}=2.61

التركيب يوميا يعطينا

1\times (1+1/365)^{365}=2.71

إذا كان البنك يُرَكب n مرة في السنة، عليك تسديد:

1\times (1+1/n)^{n}

وكلما زادت مرات التركيب، كلما زادت قيمة n، كلما زاد ما عليك تسديده من ديون.

إذا أخذت الأمور إلى نهايتها، فاحسب ذلك لقيم n الأعلى والأعلى، وستجد أن إجمالي المبلغ الذي عليك تسديده يتقارب إلى

2.7182818284590452353602875...

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

(1+\frac{1}{n})^{n}

عندما n تؤول إلى المالانهاية وتمكن من إيجادها وكانت بين 2 و3. كانت هذه هي المرة الأولى في التاريخ التي يُعرف فيها عدد ما على أنه نهاية.


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

Maths in a minute: Compound interest and e

February 7, 2018

——————-

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

math.nights@gmail.com

——————–

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

نبذة عن مقررات مادة [نظرية الأعداد] من معهد ماساشوستيس للتقنية.

يوفر معهد ماساشوستيس للتقنية، ضمن موقعه للمساقات المفتوحة، اصدارين لمقرر مادة “نظرية الأعداد” لفئة ما قبل التدرج، أحدهما يعود لسنة 2003 والآخر لسنة 2012.

أ/ مقرر نظرية الأعداد. ربيع 2003

اشراف البروفيسور مارتين السون، تحت الرقم 18.781، ربيع 2003 لفئة ما قبل التدرج. المقرر يوفر مقدمة ابتدائية أولية لنظرية الأعداد من دون أي خلفيات جبرية مسبقة. تشمل موضوعاته الأعداد الأولية، التطابق، التقابلات التربيعية، المعادلات الديوفانتية، الأعداد الصماء، الكسور المستمرة والمنحنيات الاهليجية.

ب/ مقرر نظرية الأعداد. ربيع 2012

اشراف البروفيسور أبهيناف كومار، تحت الرقم 18.781، ربيع 2012 لفئة ما قبل التدرج. يوفر المقرر مقدمة أولية لنظرية الأعداد من دون أي خلفيات جبرية مسبقة. تشمل موضوعاته الأعداد الأولية، التطابق، التقابلات التربيعية، المعادلات الديوفانتية، الأعداد الصماء، الكسور المستمرة، والتجزئة.

========================

المزيد من المقررات ذات الصلة لفئات ما قبل وما بعد التدرج تجدها ضمن هذه التشكيلات والمجموعات

 

 

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

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

إذا كنت تشعر بالملل من المعدل، إذا فانتقل إلى التباين!

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

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

20000

20000

20000

20000

100000

 

 

 

 

معدل هذه المجموعة من الأعداد هو

(4\times 20000 +100000)/5=36000

لكن معرفة هذا العدد لا تمنحك أي مؤشر على حقيقة أن هناك راتبا واحدا أكبر بكثير من الأربعة الآخرين.

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

(4\times (36000-20000)^{2}+(36000-100000)^{2})/5=(4\times 16000^{2}+64000^{2})/5=1024000000.

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

20000

20000

20000

20000

20001

المعدل هو

(4\times 20000 +20001)/5=100001/5=20000.2

تباين العينة في هذه الحالة هو

(4\times (20000.2-20000)^{2}+(20000.2-20001)^{2})/5=0.16.

وهو عدد صغير جدا، مما يشير إلى أن مجموعة الأعداد غير منتشرة جدا على الإطلاق.

في ما يلي التعريف الرسمي لتباين العينة v من القائمة x_{1},x_{2},x_{3},...,x_{n}. من n عدد، معدلها هو \bar{x}:

v=\frac{1}{n}((x_{1}-\bar{x})^{2}+(x_{2}-\bar{x})^{2}+...+(x_{n}-\bar{x})^{2}).

هذا التعريف صالح لقائمة معينة من الأعداد، ولكن هناك أيضا تعريف للتباين صالح عند التعامل مع عملية عشوائية، مثل عملية دحرجة حجر نرد، والرغبة في معرفة كيفية إنتشار قائمة من النتائج المرجحة. افرض أن عمليتك العشوائية لديها n نتيجة، يمكن جدولتها x_{1},x_{2},x_{3},...,x_{n}.. إذا قمت بدحرجة حجر النرد، فإن n=6 و x_{1}=1,x_{2}=2,...,x_{6}=6.. افرض أيضا أنك تعرف احتمال p_{1},p_{2},...,p_{n}. لكل نتيجة. في حالة حجر النرد المتعادل لدينا p_{1}=p_{2}=...=p_{6}=1.، لكن عموما احتمالات نتائج مختلفة قد تكون متنوعة. نحدد القيمة المتوقعة كالآتي

E=p_{1}x_{1}+p_{2}x_{2}+...+p_{n}x_{n}.

وهي نوع من المعدل المثالي، لمعرفة المزيد هــنــا. نحدد التباين السكاني كالآتي

var=p_{1}(x_{1}-E)^{2}+p_{2}(x_{2}-E)^{2}+...+p_{n}(x_{n}-E)^{2}.

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

الجذر التربيعي الموجب للتباين يدعى الانحراف المعياري.

يمكنك أيضا تحديد التباين لمتغير عشوائي لا نهائي أو مستمر. أنظر هـنا لمعرفة المزيد.


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

Maths in a minute: Variance

December 18, 2017

——————-

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

math.nights@gmail.com

——————–

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

More Fun with Prime Numbers: the summary

5 weeks

Week 1 What are Prime Numbers?

Homework 1 Review

Week 2 Sums of Two Squares

Homework 2 Review

Week 3 The Reciprocity Laws

Homework 3 Review

Week 4 Prime Numbers and Cryptography

Homework 4 Review

Week 5 Mystery of Prime Numbers: Past, Present, and Future

Homework 5 Review

————–

Final Exam Review


My Course Progress 97%

2017-12-06_112138

نُشِرت في في فهم الأعداد الأولية, ملخصات بالإنجليزية | الوسوم: , , , , | أضف تعليق

نبذة عن مساق: المزيد من المرح مع الأعداد الأولية/ Edx

مساق المزيد من المرح مع الأعداد الأولية (More Fun with Prime Numbers): غوص عميق في الأعداد الأولية – هي واحدة من أكثر الموضوعات غموضا وأهمية في الرياضيات! (ينطلق في 2017/11/02) بإذن الله.

فيما يلي استعراض لنبذة حول المساق (الكورس) بالانجليزية مُقدمة من طرف المُدرب


مساق

المزيد من المرح مع الأعداد الأولية

مقدم بواسطة Edx

ينطلق في 2017/11/02

——————–

إحصائيات سريعة

طول المساق: 05 اسابيع ابتداءا من (November 2, 2017)

الجُهد المُقدر:  1 إلى 2 ساعة/ في الأسبوع

شروط مُسبقة: لا شيء. يوصى فقط بمعرفة عامة بالجبر، مستوى المدارس الثانوية.

_______________

بطاقة تقنية حول المساق

الطول: 05 أسابيع

الجُهد: 1-2 ساعة/ الأسبوع

السعر: مجاني للحصول على شهادة عادية/ للحصول على شهادة مُصادق عليها  49 دولار

المعهد kyotoux

الموضوع: الرياضيات

المستوى: متوسط

اللغة: الانجليزية

المرئيات (الفيديوهات): الانجليزية

————————————

ماذا سأتعلم

  • الخصائص الأساسية للأعداد الأولية.
  • الحسابيات النمطية ونظرية فيرما الصغرى.
  • قوانين الأعداد الأولية.
  • تطبيقات الأعداد الأولية في التشفير.
  • مسائل مفتوحة وأحدث التطورات.

——————————————————–

المُدرب Tetsushi Ito

————————

المصدر: More Fun with Prime Numbers

 

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

الرياضيات في دقيقة: مسألة المغلفين

تخيل أن لديك مغلفين. كلاهما يحتوي مالا، أحدهما ضعف الآخر. بامكانك اختيار أحدهما والاحتفاظ بالمال داخله. ولكن فقط قبل أن تفتح المغلف الذي اخترته يتم اعطاؤك فرصة لتغيير وجهة نظرك. ماذا عليك أن تفعل؟

 

اكتب x للمبلغ الموجود في المغلف الذي اخترته. وهذا يعني أن مبلغ النقود الموجود في المغلف الآخر هو إما  2x أو \frac{x}{2}.  احتمال أن يكون 2x هو \frac{1}{2} وكذلك هو احتمال أن يكون \frac{x}{2} وبالتالي فإن المبلغ المتوقع الحصول عليه هو

مارتين هيرر (Martin Hairer) الحاصل على جائزة فيلدز في الرياضيات، يتحدث في مؤتمر هايدلبرغ 2017.

\frac{1}{2}(2x+\frac{x}{2})=x+\frac{x}{4}=\frac{5x}{4}

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

الجواب (في تعليق أسفل المقال الأصلي). مغلفك له القيمة x أو 2x وفق احتمال متساو أو قيمة متوقعة قدرها 1.5x (\frac{2x+x}{2}=1.5x). إذا كان معك x وقمت بالتبديل ستحصل على 2x وإذا كان معك 2x وقمت بالتبديل ستحصل على x مع احتمال متساو في كلا الحالتين – لايزال لديك قيمة متوقعة قدرها 1.5x. وبالتالي فلا ميزة إضافية ولا عيب قد يظهر بسبب عملية تبديل المغلفين.


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

Maths in a minute: The two envelopes problem

September 26, 2017

——————-

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

math.nights@gmail.com

——————–

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