مشكلة الحوسبة العابرة
في نظرية التعقيد الحسابي ، تُعرَّف المسألة الحسابية العابرة بأنها مسألة تتطلب معالجة أكثر من 10⁹³ بت من المعلومات. [ 1 ] يُطلق على أي عدد أكبر من 10⁹³ اسم العدد الحسابي العابر . ويُعرف العدد 10⁹³ ، الذي يُسمى حد بريمرمان ، بأنه، وفقًا لهانز يواكيم بريمرمان ، إجمالي عدد البتات التي يُمكن معالجتها بواسطة حاسوب افتراضي بحجم الأرض خلال فترة زمنية تُعادل العمر المُقدَّر للأرض. [ 1 ] [ 2 ] وقد صاغ بريمرمان مصطلح "الحساب العابر" . [ 3 ]
أمثلة
اختبار الدوائر المتكاملة
يتطلب اختبار جميع تركيبات الدائرة المتكاملة ذات 309 مدخلات منطقية ومخرج واحد اختبار 2309 تركيبة من المدخلات. ولأن العدد 2309 هو عددٌ عابرٌ للحسابات (أي عدد أكبر من 1093 ) ، فإن مشكلة اختبار نظام الدوائر المتكاملة هذا تُعدّ مشكلة عابرة للحسابات. وهذا يعني أنه لا يمكن التحقق من صحة الدائرة لجميع تركيبات المدخلات باستخدام التجربة والخطأ فقط. [ 1 ] [ 4 ]
التعرف على الأنماط
لنفترض مصفوفة من نوع رقعة الشطرنج بحجم q × q ، حيث يمكن أن يحتوي كل مربع فيها على لون واحد من بين k لونًا . يوجد إجمالًا k ^n نمطًا لونيًا ، حيث n = q^ 2 . يمكن حل مشكلة تحديد أفضل تصنيف للأنماط، وفقًا لمعيار مُختار، من خلال البحث في جميع الأنماط اللونية الممكنة. بالنسبة للونين، يصبح هذا البحث متعدد العمليات الحسابية عندما تكون المصفوفة 18 × 18 أو أكبر. أما بالنسبة لمصفوفة 10 × 10، فتصبح المشكلة متعددة العمليات الحسابية عندما يكون هناك 9 ألوان أو أكثر. [ 1 ]
لهذا الأمر أهمية في الدراسات الفيزيولوجية للشبكية . تحتوي الشبكية على حوالي مليون خلية حساسة للضوء . حتى لو كان لكل خلية حالتان محتملتان فقط (مثلاً، حالة نشطة وحالة غير نشطة)، فإن معالجة الشبكية ككل تتطلب معالجة أكثر من 10300000 بت من المعلومات. وهذا يتجاوز بكثير حد بريمرمان . [ 1 ]
مشاكل الأنظمة العامة
يمكن لنظام مكون من n متغيرًا، يمكن لكل منها أن يتخذ k حالة مختلفة، أن يحتوي على kⁿ حالة نظام ممكنة. لتحليل مثل هذا النظام، يجب معالجة ما لا يقل عن kⁿ بت من المعلومات. تصبح المسألة حسابية متعددة الحدود عندما يكون kⁿ > 10⁹³ . يحدث هذا للقيم التالية لـ k و n : [ 1 ]
| ك | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| ن | 308 | 194 | 154 | 133 | 119 | 110 | 102 | 97 | 93 |
تداعيات
إن وجود مشاكل الحوسبة العابرة في العالم الحقيقي يشير إلى محدودية الحواسيب كأدوات لمعالجة البيانات. ويمكن تلخيص هذه النقطة على أفضل وجه بكلمات بريمرمان نفسه: [ 2 ]
- يبدو أن تجارب مختلف المجموعات العاملة في مجال حل المشكلات، وإثبات النظريات، والتعرف على الأنماط ، تشير جميعها إلى اتجاه واحد: هذه المشكلات معقدة. لا يبدو أن هناك حلاً سحرياً أو طريقة بسيطة قادرة على حل جميع مشكلاتنا دفعة واحدة. يمكن تلخيص مناقشتي للقيود القصوى على سرعة وكمية معالجة البيانات على النحو التالي: لن تُحل المشكلات التي تنطوي على عدد هائل من الاحتمالات بمجرد زيادة كمية معالجة البيانات. يجب أن نبحث عن الجودة، والتحسينات، والحيل، وكل ابتكار يمكننا التفكير فيه. ستكون الحواسيب الأسرع من حواسيب اليوم عوناً كبيراً لنا، وسنحتاج إليها. مع ذلك، عندما نهتم بالمشكلات من حيث المبدأ، فإن سرعة حواسيب اليوم هي أقصى ما يمكن أن تصل إليه على الإطلاق.
- يمكننا أن نتوقع أن تتطور تقنية معالجة البيانات تدريجياً، تماماً كما هو الحال مع التقنيات الأخرى. هناك تحدٍّ لا حدود له للإبداع المطبق على المشكلات المحددة. كما أن هناك حاجة دائمة إلى مفاهيم ونظريات عامة لتنظيم التفاصيل الكثيرة.
انظر أيضاً
- هايبر تاسك
- دماغ ماتريوشكا ، بنية حاسوبية نظرية ضخمة
- المذهب المحدود الصارم
مراجع
- 1 2 3 4 5 6 كلير، جورج ج. (1991). جوانب علم الأنظمة . سبرينغر. ص 121-128 . ISBN 978-0-306-43959-9.
- 1 2 بريمرمان، إتش جيه (1962) التحسين من خلال التطور وإعادة التركيب في: الأنظمة ذاتية التنظيم 1962، حرره إم سي يوفيتس وآخرون، كتب سبارتان، واشنطن العاصمة، ص 93-106.
- ↑ هاينز مولينباين. "الخوارزميات والبيانات والفرضيات : التعلم في العوالم المفتوحة" (ملف PDF) . المركز الوطني الألماني لأبحاث علوم الحاسوب . تم الاطلاع عليه بتاريخ 3 مايو 2011 .
- ↑ مايلز، ويليام. "حدود بريمرمان" . تم الاسترجاع في 1 مايو 2011 .بينما يستخدم المصدر 308 كعدد المدخلات، فإن هذا الرقم مبني على خطأ: 2308 < 1093 .
- نظرية الحوسبة
- نظرية التعقيد الحسابي
- حدود الحساب