الآن أصبح الأمر علميًا: لا يوجد شيء مثالي

يؤكد علماء الكمبيوتر من معهد وايزمان للعلوم وجامعة تل أبيب المشاعر التي وصفها العديد من الكتاب والشعراء والمفكرين: لا توجد عوالم مثالية والحياة مليئة بالتنازلات الكبيرة والصغيرة

مجلة "المعهد".

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

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

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

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

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

https://www.hayadan.org.il/BuildaGate4/general2/data_card.php?Cat=~~~457044752~~~174&SiteName=hayadan