لنفترض أنني أعطيتك قائمتين مختلفتين من الأرقام، أو ربما دالتين مختلفتين، وأطلب

منك التفكير في جميع الطرق التي يمكنك من خلالها الجمع بين هاتين القائمتين للحصول

على قائمة جديدة من الأرقام، أو الجمع بين الدالتين للحصول على دالة جديدة .

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

وبالمثل مع الوظائف، يمكنك إضافة جميع المخرجات المقابلة.

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

ولكن هناك نوع آخر من التركيبة لا تقل أهمية عن كليهما،

ولكنها أقل شيوعًا من حيث المناقشة، والمعروفة باسم الإلتواء.

ولكن على عكس الحالتين السابقتين، فهو ليس شيئًا

موروثًا فقط من عملية يمكنك إجراؤها على الأرقام.

إنه شيء جديد حقًا بالنسبة لسياق قوائم الأرقام أو دمج الوظائف.

إنها تظهر في كل مكان، وهي موجودة في كل مكان في معالجة الصور، وهي بناء أساسي في

نظرية الاحتمالات، ويتم استخدامها كثيرًا في حل المعادلات التفاضلية، وسياق واحد

حيث من المؤكد تقريبًا أنك رأيته، إن لم يكن بهذا الاسم، يتم ضرب كثيرتي الحدود معًا.

باعتباري شخصًا يعمل في مجال التفسيرات المرئية، يعد هذا موضوعًا رائعًا

بشكل خاص، لأن التعريف الصياغي بمعزل عن السياق وبدون سياق يمكن أن يبدو

مخيفًا نوعًا ما، ولكن إذا أخذنا الوقت الكافي لتفكيك ما يقوله، وقبل ذلك

فعليًا نحفز لماذا قد ترغب في شيء كهذا، إنها عملية جميلة بشكل لا يصدق.

ويجب أن أعترف أنني تعلمت شيئًا صغيرًا أثناء تجميع العناصر المرئية لهذا المشروع.

في حالة دمج وظيفتين مختلفتين، كنت أحاول التفكير في طرق مختلفة يمكنك من خلالها

تصور ما يمكن أن يعنيه ذلك، ومع إحداهما كانت لدي لحظة آها قليلاً لماذا تلعب

التوزيعات العادية الدور الذي يفعلون في الاحتمالية، لماذا هو شكل طبيعي لوظيفة.

لكنني أتقدم على نفسي، هناك الكثير من الإعداد لذلك.

في هذا الفيديو، سيكون تركيزنا الأساسي على الحالة المنفصلة، وعلى

وجه الخصوص بناء خوارزمية غير متوقعة للغاية ولكنها ذكية جدًا لحسابها.

وسوف أقوم بسحب المناقشة الخاصة بالحالة المستمرة إلى الجزء الثاني.

من المغري جدًا الانفتاح على أمثلة معالجة الصور، نظرًا لأنها الأكثر إثارة للاهتمام

من الناحية البصرية، ولكن هناك بعض التفاصيل الدقيقة التي تجعل حالة معالجة الصور

أقل تمثيلاً للتلافيفات بشكل عام، لذا بدلاً من ذلك دعونا نبدأ الأمور بالاحتمالية،

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

في مرحلة ما من حياتهم، وهو رمي زوج من النرد ومعرفة فرص رؤية مجاميع مختلفة مختلفة.

وقد تقول: ليست مشكلة، وليست مشكلة.

يحتوي كل من حجري النرد على ستة نتائج محتملة مختلفة، وهو ما يعطينا إجمالي 36 زوجًا محتملاً

مختلفًا من النتائج، وإذا نظرنا إليها جميعًا، يمكننا حساب عدد الأزواج التي لها مجموع معين.

وبترتيب جميع الأزواج في شبكة مثل هذه، هناك شيء جميل جدًا وهو أن جميع

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

لذا فإن حساب عدد الأقطار الموجودة في كل قطر من

تلك الأقطار سيخبرك بمدى احتمالية رؤية مجموع معين.

وأقول، جيد جدًا، جيد جدًا، ولكن هل يمكنك التفكير

في أي طرق أخرى يمكنك من خلالها تصور نفس السؤال؟

الصور الأخرى التي يمكن أن تتبادر إلى ذهنك عند

التفكير في جميع الأزواج المميزة التي لها مجموع معين؟

وربما يرفع أحدكم يده ويقول، نعم، لدي واحدة.

لنفترض أنك تصورت هاتين المجموعتين المختلفتين من

الاحتمالات في صف واحد، لكنك تقلب الصف الثاني.

وبهذه الطريقة، تصطف جميع الأزواج المختلفة التي

يصل مجموعها إلى سبعة بشكل عمودي على هذا النحو.

وإذا قمنا بتحريك هذا الصف السفلي إلى اليمين، فإن الزوج الفريد

الذي يضيف ما يصل إلى اثنين، عيون الثعبان، هو الوحيد الذي يتحاذى.

وإذا قمت بتقسيم ذلك على وحدة واحدة إلى اليمين، فإن الأزواج

المتوافقة هي الزوجين المختلفين اللذين مجموعهما ثلاثة.

وبشكل عام، تكشف قيم الإزاحة المختلفة لهذه المصفوفة السفلية، والتي تذكر

أنه كان علي أن أقلبها أولاً، عن جميع الأزواج المميزة التي لها مجموع معين.

فيما يتعلق بالأسئلة الاحتمالية، لا يزال هذا غير مثير للاهتمام بشكل خاص،

لأن كل ما نفعله هو حساب عدد النتائج الموجودة في كل فئة من هذه الفئات.

ولكن هذا مع الافتراض الضمني بأن هناك فرصة متساوية لكل من هذه الوجوه للظهور.

ولكن ماذا لو أخبرتك أن لدي مجموعة خاصة من النرد غير موحدة؟

ربما يحتوي النرد الأزرق على مجموعة أرقام خاصة به تصف احتمالات ظهور

كل وجه، بينما يحتوي النرد الأحمر على مجموعة فريدة ومميزة من الأرقام.

في هذه الحالة، إذا أردت معرفة احتمال رؤية الرقم اثنين، على سبيل المثال، فسوف تقوم

بضرب احتمال أن يكون النرد الأزرق واحدًا في احتمال أن يكون النرد الأحمر واحدًا.

وللحصول على فرص رؤية الرقم ثلاثة، انظر إلى الزوجين المتميزين حيث يكون ذلك

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

وبالمثل، فإن فرص رؤية الرقم أربعة تتضمن ضرب ثلاثة

أزواج مختلفة من الاحتمالات وجمعها جميعًا معًا.

وبروح إعداد بعض الصيغ، دعونا نسمي هذه الاحتمالات العليا a1،

a2، a3، وهكذا، ونسمي الاحتمالات السفلية b1، b2، b3، وهكذا.

وبشكل عام، هذه العملية، حيث نأخذ مصفوفتين مختلفتين من الأرقام، ونقلب

المصفوفة الثانية، ثم نرتبها بقيم إزاحة مختلفة مختلفة، ونأخذ مجموعة من

المنتجات الزوجية ونضيفها، هذا أحد الطرق الأساسية للتفكير في ما هو الإلتواء.

لذا فقط لتوضيح الأمر بشكل أكثر دقة، من خلال هذه العملية، قمنا للتو

بتوليد احتمالات لرؤية اثنين، ثلاثة، أربعة، مرارًا وتكرارًا حتى 12،

وحصلنا عليها عن طريق مزج قائمة واحدة من القيم، أ، وأخرى قائمة القيم، ب.

في اللغة، يمكننا أن نقول أن التفاف هذين التسلسلين يعطينا هذا التسلسل الجديد،

التسلسل الجديد المكون من 11 قيمة، كل منها تبدو وكأنها مجموع من المنتجات الزوجية.

إذا كنت تفضل ذلك، هناك طريقة أخرى يمكنك من خلالها التفكير في نفس العملية

وهي إنشاء جدول يضم جميع المنتجات الزوجية أولًا، ثم جمع كل هذه الأقطار.

مرة أخرى، هذه طريقة لخلط هاتين التسلسلتين من الأرقام

للحصول على تسلسل جديد مكون من 11 رقمًا.

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

مع وضع القليل من التدوين عليها، إليك كيف يمكنك رؤيتها مكتوبة.

إن التفاف a وb، المشار إليه بهذه العلامة النجمية الصغيرة، هو قائمة

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

أزواج المؤشرات المختلفة، i وj، بحيث يكون مجموع هذه المؤشرات تساوي n.

إنه نوع من الفم، ولكن على سبيل المثال، إذا كان n يساوي 6، فإن الأزواج التي سنراجعها

هي 1 و5، و2 و4، و3 و3، و4 و2، و5 و1، وكل الأزواج المختلفة التي تضيف ما يصل إلى 6.

لكن بصراحة، بغض النظر عن الطريقة التي تكتب بها، فإن التدوين يأتي في مرتبة

ثانوية من حيث الأهمية مقارنة بالصورة التي قد تحملها في رأسك أثناء هذه العملية.

هنا، ربما يكون من المفيد عمل مثال بسيط للغاية، حيث يمكنني

أن أسألك ما هو التفاف القائمة 1، 2، 3، مع القائمة 4، 5، 6.

قد تتصور أنك تأخذ كلتا القائمتين، وتقلب القائمة

الثانية، ثم تبدأ بغطاءها على طول الطريق إلى اليسار.

بعد ذلك، زوج القيمتين المحاذيتين هما 1 و4، ونضربهما

معًا، وهذا يعطينا الحد الأول من الناتج.

قم بتحريك المصفوفة السفلية بمقدار وحدة واحدة إلى اليمين، والأزواج التي تتم محاذاتها هي

1 و5، و2 و4، واضرب تلك الأزواج، وأضفها معًا، وهذا يعطينا 13، الإدخال التالي في مخرجاتنا.

مرر الأشياء مرة أخرى، وسنأخذ 1 ضرب 6، زائد 2 ضرب 5، زائد 3 ضرب 4، وهو ما يساوي 28.

شريحة أخرى، وسنحصل على 2 ضرب 6، زائد 3 ضرب 5، وهذا

يعطينا 27، وأخيرًا سيبدو الحد الأخير مثل 3 ضرب 6.

إذا كنت ترغب في ذلك، يمكنك سحب ما هي لغة البرمجة المفضلة لديك، ومكتبتك

المفضلة التي تتضمن عمليات رقمية مختلفة، ويمكنك التأكد من أنني لا أكذب عليك.

إذا أخذت التواء 1، 2، 3، مقابل 4، 5، 6، فهذه هي النتيجة التي ستحصل عليها بالفعل.

لقد رأينا حالة واحدة حيث تكون هذه عملية طبيعية ومرغوبة، وتضيف

إلى التوزيعات الاحتمالية، ومثال شائع آخر هو المتوسط المتحرك.

تخيل أن لديك قائمة طويلة من الأرقام، وأخذت قائمة

أخرى أصغر من الأرقام التي مجموعها يصل إلى 1.

في هذه الحالة، لدي قائمة صغيرة من 5 قيم، وكلها تساوي 1 على 5.

ثم إذا قمنا بعملية طي النافذة المنزلقة هذه، وأغمضنا أعيننا نوعًا ما

وتجاهلنا ما يحدث في البداية، بمجرد أن تتداخل قائمة القيم الأصغر تمامًا

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

في كل تكرار، ما تفعله هو ضرب كل قيمة من بياناتك في 15، وإضافتها جميعًا

معًا، مما يعني أنك تأخذ متوسطًا لبياناتك داخل هذه النافذة الصغيرة.

بشكل عام، تمنحك العملية نسخة مبسطة من البيانات الأصلية، ويمكنك تعديل

ذلك بدءًا بقائمة صغيرة مختلفة من الأرقام، وطالما أن هذه القائمة الصغيرة

تضيف ما يصل إلى 1، فلا يزال بإمكانك تفسيرها على أنها متحركة متوسط.

في المثال الموضح هنا، فإن المتوسط المتحرك سيعطي وزنا أكبر نحو القيمة المركزية.

وينتج عن هذا أيضًا نسخة مبسطة من البيانات.

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

ويجب أن أقول إن الرسوم المتحركة التي أنا على وشك عرضها تم تعديلها من شيء صنعته

في الأصل لجزء من مجموعة من المحاضرات التي ألقيتها مع مختبر جوليا في معهد ماساتشوستس

للتكنولوجيا لفصل دراسي معين في OpenCourseWare والذي يتضمن وحدة معالجة الصور.

لقد بذلنا المزيد من الجهد للتعمق في التعليمات البرمجية

وراء كل هذا، لذا إذا كنت مهتمًا فسأترك لك بعض الروابط.

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

مقاس 3×3 تسير على طول صورتنا الأصلية، وإذا قمنا بتكبير الصورة، فإن كل واحدة من هذه القيم

هي 1 على 9، وما أفعله في كل تكرار يتم ضرب كل من هذه القيم بالبكسل المقابل الذي يقع فوقه.

وبالطبع في علوم الكمبيوتر، نعتبر الألوان بمثابة ناقلات

صغيرة لثلاث قيم، تمثل المكونات الحمراء والخضراء والزرقاء.

عندما أضرب كل هذه القيم الصغيرة في 19 وأجمعها معًا، فإنه يعطينا متوسطًا على

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

التأثير الإجمالي، عندما نفعل ذلك لكل بكسل في الصورة، هو أن كل نوع

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

في اللغة، يمكننا القول أن الصورة الموجودة على اليمين هي

عبارة عن مجموعة من صورتنا الأصلية مع شبكة صغيرة من القيم.

أو من الناحية الفنية ربما يجب أن أقول إنه الالتواء

بنسخة مدورة 180 درجة لتلك الشبكة الصغيرة من القيم.

لا يهم أن تكون الشبكة متماثلة، ولكن من المفيد أن نأخذ في

الاعتبار أن تعريف الالتواء، كما هو موروث من سياق الرياضيات

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

إذا قمنا بتعديل هذا قليلاً يمكننا الحصول على تأثير

تمويه أكثر أناقة عن طريق اختيار شبكة مختلفة من القيم.

في هذه الحالة، لدي شبكة صغيرة مقاس 5 × 5، لكن الاختلاف لا يكمن في حجمها كثيرًا.

إذا قمنا بتكبير الصورة، نلاحظ أن القيمة في المنتصف أكبر بكثير

من القيمة الموجودة في اتجاه الحواف، ومن أين يأتي هذا هو أنها

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

بهذه الطريقة عندما نضرب كل هذه القيم بالبكسل المقابل الذي تجلس فوقه، فإننا نعطي

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

وكما كان الحال من قبل، تم تعريف البكسل المقابل على اليمين بأنه هذا المجموع.

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

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

لكن التمويه ليس هو الشيء الوحيد الذي يمكنك فعله بهذه الفكرة.

على سبيل المثال، ألقِ نظرة على شبكة القيم الصغيرة هذه، والتي تتضمن بعض الأرقام الموجبة

على اليسار وبعض الأرقام السالبة على اليمين، والتي سألونها باللون الأزرق والأحمر على

التوالي.

خذ لحظة لترى ما إذا كان بإمكانك التنبؤ وفهم التأثير الذي سيحدثه ذلك على الصورة النهائية.

لذلك في هذه الحالة سأفكر فقط في الصورة على أنها ذات تدرج رمادي بدلاً

من كونها ملونة، بحيث يتم تمثيل كل بكسل برقم واحد فقط بدلاً من ثلاثة.

والشيء الوحيد الجدير بالملاحظة هو أنه أثناء قيامنا

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

على سبيل المثال، في هذه المرحلة، إذا قمنا بتكبير النصف الأيسر من شبكتنا الصغيرة،

فسيتم وضعها بالكامل فوق وحدات البكسل السوداء، والتي ستكون قيمتها صفرًا، ولكن النصف

الأيمن من القيم السالبة كلها تقع فوق وحدات البكسل البيضاء، والتي ستكون لها قيمة واحدة.

لذلك عندما نضرب الحدود المتناظرة ونجمعها معًا ستكون النتائج سلبية

للغاية، والطريقة التي أعرض بها ذلك مع الصورة الموجودة على اليمين

هي تلوين القيم السالبة باللون الأحمر والقيم الموجبة باللون الأزرق.

شيء آخر يجب ملاحظته هو أنه عندما تكون على رقعة بنفس اللون، فإن كل

شيء يذهب إلى الصفر نظرًا لأن مجموع القيم في شبكتنا الصغيرة هو صفر.

وهذا يختلف تمامًا عن المثالين السابقين حيث كان مجموع شبكتنا الصغيرة

واحدًا، مما يسمح لنا بتفسيره على أنه متوسط متحرك وبالتالي ضبابية.

بشكل عام، تكتشف هذه العملية الصغيرة بشكل أساسي أينما يوجد

اختلاف في قيمة البكسل أثناء تحركك من اليسار إلى اليمين،

وبالتالي فهي توفر لك طريقة ما لالتقاط جميع الحواف الرأسية من صورتك.

وبالمثل، إذا قمنا بتدوير تلك الشبكة بحيث تختلف أثناء تحركك من

الأعلى إلى الأسفل، فسيتم التقاط كل الحواف الأفقية، وهو ما يؤدي

في حالة صورة مخلوق الفطيرة الصغيرة إلى بعض العيون الشيطانية الجميلة.

بالمناسبة، غالبًا ما تسمى هذه الشبكة الأصغر بالنواة، والجمال هنا

هو أنه بمجرد اختيار نواة مختلفة يمكنك الحصول على تأثيرات مختلفة

لمعالجة الصور، ليس فقط طمس اكتشاف الحواف ولكن أيضًا أشياء مثل الوضوح.

بالنسبة لأولئك منكم الذين سمعوا عن الشبكة العصبية التلافيفية، فإن

الفكرة هي استخدام البيانات لمعرفة ما يجب أن تكون عليه النوى في

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

شيء آخر ربما ينبغي عليّ طرحه هو طول الإخراج.

بالنسبة لشيء مثل مثال المتوسط المتحرك، قد ترغب فقط في التفكير في المصطلحات

عندما تتم محاذاة كلا النافذتين بشكل كامل مع بعضهما البعض، أو في مثال

معالجة الصور ربما تريد أن يكون الإخراج النهائي بنفس حجم الملف الأصلي.

الآن، تنتج عمليات التلافيف كعملية رياضية بحتة دائمًا مصفوفة أكبر من

المصفوفتين اللتين بدأت بهما، على الأقل بافتراض أن أحدهما لا يبلغ طوله واحدًا.

فقط اعلم أنه في سياقات معينة لعلوم الكمبيوتر، غالبًا ما ترغب في اقتطاع هذا الناتج عمدًا.

شيء آخر يستحق تسليط الضوء عليه هو أنه في سياق علوم الكمبيوتر، غالبًا ما

تبدو فكرة التقليب حول تلك النواة قبل السماح لها بالمرور عبر النسخة الأصلية

غريبة حقًا ولا داعي لها، ولكن لاحظ مرة أخرى أن هذا هو ما تم توريثه من سياق

الرياضيات البحتة حيث مثلنا رأيت مع الاحتمالات أنه أمر طبيعي بشكل لا يصدق.

وفي الواقع يمكنني أن أريكم مثالًا رياضيًا خالصًا آخر حيث يجب على المبرمجين الاهتمام

بهذا المثال لأنه يفتح الأبواب أمام خوارزمية أسرع بكثير لحساب كل هذه الأشياء.

لإعداد ما أعنيه بشكل أسرع هنا، دعني أعود وأقوم بسحب بعض لغة

بايثون مرة أخرى وسأقوم بإنشاء صفيفتين مختلفتين كبيرتين نسبيًا.

سيحتوي كل واحد على مائة ألف عنصر عشوائي وسأقوم

بتقييم وقت تشغيل وظيفة التحويل من مكتبة numpy.

وفي هذه الحالة، يقوم بتشغيله لعدة تكرارات مختلفة، ويحاول العثور على

متوسط، ويبدو على هذا الكمبيوتر أن متوسطه على الأقل هو 4.87 ثانية.

على النقيض من ذلك، إذا كنت أستخدم وظيفة مختلفة من مكتبة scipy تسمى

fftconvolve وهو نفس الشيء الذي تم تنفيذه للتو بشكل مختلف والذي يستغرق 4 فقط.

3 ميلي ثانية في المتوسط، أي ثلاثة أوامر من التحسن في الحجم.

ومرة أخرى، على الرغم من أنها تعمل تحت اسم مختلف، إلا أنها تعطي نفس الإخراج الذي

تقوم به وظيفة الالتفاف الأخرى، فهي تفعل شيئًا للقيام بذلك بطريقة أكثر ذكاءً.

تذكر كيف قلت في مثال الاحتمال أن الطريقة الأخرى التي يمكنك من خلالها التفكير في الالتواء

هي إنشاء هذا الجدول لجميع المنتجات الزوجية ثم جمع تلك المنتجات الزوجية على طول الأقطار.

بالطبع لا يوجد شيء محدد للاحتمال في أي وقت تقوم فيه بدمج

قائمتين مختلفتين من الأرقام التي يمكنك التفكير فيها بهذه الطريقة.

قم بإنشاء هذا النوع من جدول الضرب مع جميع المنتجات الزوجية،

ثم يتوافق كل مجموع على طول القطر مع أحد مخرجاتك النهائية.

أحد السياقات التي يكون فيها هذا الرأي طبيعيًا

بشكل خاص هو عندما تقوم بضرب متعددتي الحدود معًا.

على سبيل المثال، اسمحوا لي أن آخذ الشبكة الصغيرة الموجودة لدينا بالفعل وأستبدل

الحدود العليا بـ 1 و2x و3x مربعة واستبدل الحدود الأخرى بـ 4 و5x و6x مربعة.

فكر الآن فيما يعنيه إنشاء كل هذه المنتجات الزوجية المختلفة بين القائمتين.

ما تفعله هو في الأساس توسيع المنتج الكامل لكثيرتي الحدود اللذين كتبتهما ثم عندما

تضيف ما يصل على طول القطر الذي يتوافق مع جمع كل الحدود المتشابهة وهو أمر أنيق

جدًا، فإن توسيع كثيرة الحدود وجمع الحدود المتشابهة هو بالضبط نفس عملية الالتواء.

لكن هذا يتيح لنا القيام بشيء رائع جدًا لأننا فكرنا فيما نقوله هنا.

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

نقطي، فهذا هو نفس الشيء كما لو كنت قد استخرجت المعاملات أولاً من كل واحدة من

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

ما يجعل ذلك مثيرًا للاهتمام هو أن التلافيف تبدو من حيث المبدأ أكثر تعقيدًا من الضرب

البسيط وأنا لا أقصد فقط أنه من الصعب التفكير فيها من الناحية النظرية، أعني حسابيًا أنها

تتطلب خطوات أكثر لإجراء التلافيف أكثر مما يتطلبه إجراء عملية تلافيف.

منتج نقطي لقائمتين مختلفتين.

على سبيل المثال، لنفترض أنني أعطيتك كثيرتي حدود كبيرتين حقًا، قل لكل منهما مائة معامل

مختلف، فإذا كانت الطريقة التي تضربهما بها هي توسيع هذا المنتج، فأنت تعرف ملء هذه الشبكة

الكاملة 100 × 100 من المنتجات الزوجية التي تتطلب منك قم بتنفيذ 10000 منتج مختلف، وبعد ذلك

عندما تجمع كل المصطلحات المتشابهة على طول الأقطار، تكون هذه مجموعة أخرى من حوالي 10000

عملية.

بشكل أكثر عمومية في اللغة، يمكننا أن نقول أن الخوارزمية هي O of n مما يعني

لقائمتين من الحجم n بالطريقة التي يتناسب بها عدد مقاييس العمليات مع مربع n.

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

أخذ عينات من قيمهما في عدد قليل من المدخلات، فإن ضربهما لا يتطلب سوى عدد

من العمليات مثل عدد العينات، حيث إنها مرة أخرى عملية نقطية ومع كثيرات

الحدود تحتاج فقط عدد لا نهائي من العينات لتكون قادرة على استعادة المعاملات.

على سبيل المثال، يكفي مخرجان لتحديد متعدد الحدود الخطي بشكل فريد.

ستكون ثلاثة مخرجات كافية لتحديد كثيرة الحدود من الدرجة الثانية بشكل فريد.

وبشكل عام، إذا كنت تعرف n مخرجات مميزة فهذا يكفي لتحديد

متعدد الحدود بشكل فريد يحتوي على n معاملات مختلفة.

أو إذا كنت تفضل ذلك، يمكننا صياغة ذلك بلغة أنظمة المعادلات.

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

في مثالنا، قد تفكر في هذا باعتباره المنتج الذي نحاول اكتشافه.

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

مختلفة مثل 0، 1، 2، 3، وهكذا، وسأعطيك ما يكفي بحيث يكون لديك العديد من المعادلات لديك

مجهولين.

حتى أنه يصادف أنه نظام خطي من المعادلات، وهذا جميل.

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

لذا فإن مخطط الخوارزمية التقريبي سيكون عندما تريد دمج قائمتين

من الأرقام التي تتعامل معها كما لو كانت معاملات متعددة الحدود.

يمكنك أخذ عينات من كثيرات الحدود بمخرجات كافية، وضرب تلك العينات من حيث

النقطة، ثم حل النظام لاستعادة المعاملات كطريقة مستترة للعثور على الالتواء.

وكما ذكرت حتى الآن على الأقل، يمكن لبعضكم أن يشتكي بحق "جرانت، هذه خطة حمقاء".

نظرًا لشيء واحد، فإن مجرد حساب كل هذه العينات لواحدة من كثيرات الحدود التي

نعرفها يأخذ بالفعل ترتيب العمليات المربعة n، ناهيك عن أن حل هذا النظام سيكون

بالتأكيد صعبًا من الناحية الحسابية مثل مجرد القيام بالالتفاف في المقام الأول.

لذا، بالتأكيد لدينا هذه العلاقة بين الضرب والتلافيف،

ولكن كل التعقيد يحدث في الترجمة من وجهة نظر إلى أخرى.

ولكن هناك خدعة، وأولئك الذين يعرفون تحويلات فورييه

وخوارزمية FFT قد يدركون إلى أين يتجه هذا الأمر.

إذا لم تكن على دراية بهذه المواضيع، فقد يبدو ما سأقوله غير متوقع تمامًا.

اعلم فقط أن هناك مسارات معينة كان من الممكن أن

تسير فيها في الرياضيات والتي تجعل هذه خطوة متوقعة.

الفكرة الأساسية هي أن لدينا حرية الاختيار هنا.

إذا بدلًا من التقييم على مجموعة عشوائية من المدخلات مثل 0، 1، 2، 3،

وما إلى ذلك، اخترت التقييم على مجموعة مختارة خصيصًا من الأعداد المركبة.

على وجه التحديد تلك التي تقع على مسافات متساوية على دائرة الوحدة، ما يعرف بجذور الوحدة.

وهذا يعطينا نظامًا أكثر ودا.

الفكرة الأساسية هي أنه من خلال العثور على رقم تندرج فيه قواه ضمن نمط

التدوير هذا، فهذا يعني أن النظام الذي ننشئه سيكون لديه الكثير من

التكرار في المصطلحات المختلفة التي تحسبها، ومن خلال كونك ذكيًا بشأن

كيفية يمكنك الاستفادة من هذا التكرار، يمكنك توفير الكثير من العمل على نفسك.

هذه المجموعة من المخرجات التي كتبتها لها اسم خاص،

يطلق عليه تحويل فورييه المنفصل للمعاملات.

وإذا كنت تريد معرفة المزيد، فقد قمت في الواقع بإلقاء محاضرة أخرى لنفس فصل

جوليا في معهد ماساتشوستس للتكنولوجيا، وكانت تدور حول تحويلات فورييه المنفصلة.

وهناك أيضًا مقطع فيديو ممتاز حقًا على القناة يتحدث عن تحويل فورييه

السريع، وهو عبارة عن خوارزمية لحساب هذه التحويلات بسرعة أكبر.

كما قامت شركة Veritasium مؤخرًا بعمل مقطع فيديو

جيد حقًا حول FFT، لذلك لديك الكثير من الخيارات.

وهذه الخوارزمية السريعة هي النقطة المهمة بالنسبة لنا حقًا.

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

المخرجات، حيث بدلاً من القيام بعمليات بترتيب n تربيعية، يمكنك القيام بترتيب n

ضرب سجل n من العمليات، وهو أمر كثير أفضل بكثير عندما تقوم بالتوسع في القوائم الكبيرة.

والأهم من ذلك أن خوارزمية fft تسير في كلا الاتجاهين.

كما يتيح لك الانتقال من المخرجات إلى المعاملات.

لذا، بجمع كل ذلك معًا، دعونا نلقي نظرة على مخطط الخوارزمية الخاص بنا.

الآن يمكننا أن نقول أنه عندما يتم إعطاؤك قائمتين طويلتين من الأرقام

وتريد أن تأخذ تلافيفهما، قم أولاً بحساب تحويل فورييه السريع لكل واحد

منهما، والذي في الجزء الخلفي من عقلك يمكنك فقط التفكير في معاملتهما على

هذا النحو إنها معاملات كثيرة الحدود ويتم تقييمها في مجموعة نقاط مختارة خصيصًا.

ثم اضرب النتيجتين اللتين حصلت عليهما للتو من حيث النقطة معًا،

وهو أمر جيد وسريع، ثم قم بإجراء تحويل فورييه السريع العكسي،

وما يمنحك ذلك هو طريقة مستترة لحساب الالتواء الذي كنا نبحث عنه.

لكن هذه المرة تتضمن فقط عمليات O of n log n.

هذا رائع حقا بالنسبة لي!

هذا السياق المحدد للغاية حيث تظهر التلافيفات، بضرب كثيرتي الحدود، يفتح

الأبواب أمام خوارزمية ذات صلة في كل مكان آخر قد تظهر فيه التلافيفات.

إذا كنت تريد إضافة توزيعات احتمالية، فقم بإجراء

بعض عمليات المعالجة الكبيرة للصور، مهما كانت.

وأعتقد أن هذا مثال جيد على السبب الذي يجعلك متحمسًا عندما ترى بعض العمليات

أو المفاهيم في الرياضيات تظهر في الكثير من المجالات التي تبدو غير ذات صلة.

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

اشرح لماذا عندما تقوم بضرب رقمين مختلفين، مجرد عملية ضرب عادية بالطريقة التي نتعلمها

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

هناك بعض الخطوات المضافة مع الحمل وما شابه، ولكن الخطوة الأساسية هي الإلتواء.

في ضوء وجود خوارزمية سريعة، ما يعنيه ذلك هو أنه إذا كان لديك عددان صحيحان كبيران

جدًا، فهناك طريقة للعثور على ناتجهما أسرع من الطريقة التي نتعلمها في المدرسة الابتدائية.

هذا بدلاً من طلب عمليات O of n المربعة يتطلب فقط O of n log n، وهو ما لا يبدو أنه ممكن.

المهم هو أنه قبل أن يكون هذا مفيدًا فعليًا في

الممارسة العملية، يجب أن تكون أرقامك هائلة تمامًا.

ولكن لا يزال من الرائع وجود مثل هذه الخوارزمية.

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