ذاكرة الوصول العشوائي الحقيقية

الموسوعة الحرة

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

نموذج

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

تشمل العمليات المسموح بها عادةً الجمع والطرح والضرب والقسمة، بالإضافة إلى المقارنات، ولكن لا تشمل عملية حساب باقي القسمة أو التقريب إلى أعداد صحيحة. والسبب في تجنب عمليات التقريب إلى أعداد صحيحة وحساب باقي القسمة هو أن السماح بهذه العمليات قد يمنح ذاكرة الوصول العشوائي الحقيقية قدرة حسابية هائلة، مما يُمكّنها من حل مسائل كاملة من فئة PSPACE في وقت متعدد الحدود. [ 2 ]

عند تحليل الخوارزميات الخاصة بذاكرة الوصول العشوائي الحقيقية، يُفترض عادةً أن كل عملية مسموح بها تستغرق وقتًا ثابتًا .

تطبيق

طُوِّرت مكتبات برمجية مثل LEDA تُمكِّن المبرمجين من كتابة برامج حاسوبية تعمل كما لو كانت تعمل على ذاكرة وصول عشوائي (RAM) حقيقية. تُمثِّل هذه المكتبات القيم الحقيقية باستخدام هياكل بيانات تُتيح لها إجراء العمليات الحسابية والمقارنات بنفس نتائج ذاكرة الوصول العشوائي الحقيقية. على سبيل المثال، في LEDA، تُمثَّل الأعداد الحقيقية باستخدام leda_realنوع البيانات الذي يدعم الجذور من الرتبة k لأي عدد طبيعي k ، والمعاملات الكسرية، ومعاملات المقارنة. [ 3 ] يُمكن تفسير تحليل الوقت لخوارزمية ذاكرة الوصول العشوائي الحقيقية الأساسية باستخدام أنواع البيانات الحقيقية هذه على أنه حساب عدد استدعاءات المكتبة اللازمة لخوارزمية مُحدَّدة. [ 4 ]

مقارنة بالنماذج الحسابية الأخرى

  • في نموذج آلة تورينج ، تتكون وحدة الحساب الأساسية من بت واحد. لذا، يعتمد تعقيد الوقت والمساحة للخوارزميات العددية على عدد البتات اللازمة لتمثيل الأعداد. في المقابل، في نموذج ذاكرة الوصول العشوائي الحقيقية (Real RAM)، تتكون وحدة الحساب الأساسية من عدد حقيقي، بغض النظر عن عدد البتات المطلوبة لتمثيله. هذا الاختلاف مهم عند تحليل خوارزميات مثل خوارزمية الحذف الغاوسي : تتطلب هذه الخوارزمية عددًا متعدد الحدود من العمليات الحسابية على الأعداد الحقيقية، لذا فهي متعددة الحدود في نموذج ذاكرة الوصول العشوائي الحقيقية؛ ومع ذلك، قد تنمو الأعداد المستخدمة في العمليات الحسابية الوسيطة (إذا تم تنفيذها بشكل بسيط) بشكل أُسّي، لذا فإن وقت تشغيلها في نموذج آلة تورينج أُسّي. [ 5 ] : القسم 1.4
  • يشبه جهاز RAM الحقيقي إلى حد كبير جهاز Blum–Shub–Smale اللاحق . [ 6 ] ومع ذلك، يُستخدم جهاز RAM الحقيقي عادةً لتحليل الخوارزميات الملموسة في الهندسة الحسابية ، بينما يشكل جهاز Blum–Shub–Smale أساسًا لتوسيع نظرية اكتمال NP إلى حساب الأعداد الحقيقية.
  • يُعدّ نموذج ذاكرة الوصول العشوائي للكلمات (Word RAM) بديلاً لذاكرة الوصول العشوائي الحقيقية ( RAM )، حيث يُفترض أن تكون كل من مدخلات المسألة والقيم المخزنة في الذاكرة والسجلات أعدادًا صحيحة ذات عدد ثابت من البتات. يُمكن لنموذج ذاكرة الوصول العشوائي للكلمات تنفيذ بعض العمليات بسرعة أكبر من ذاكرة الوصول العشوائي الحقيقية؛ فعلى سبيل المثال، يسمح باستخدام خوارزميات فرز الأعداد الصحيحة السريعة ، بينما يتطلب الفرز في ذاكرة الوصول العشوائي الحقيقية استخدام خوارزميات فرز مقارنة أبطأ . مع ذلك، تحتوي بعض مسائل الهندسة الحسابية على مدخلات أو مخرجات لا يُمكن تمثيلها بدقة باستخدام إحداثيات الأعداد الصحيحة؛ انظر على سبيل المثال تكوين بيرلز ، وهو ترتيب للنقاط وقطع مستقيمة لا يُمكن تمثيله بإحداثيات الأعداد الصحيحة.

مراجع

  1. ↑ شاموس، مايكل إيان (1978)، الهندسة الحسابية ، أطروحة دكتوراه، جامعة ييل.
  2. ↑ شونهاج، أرنولد (1979)، "حول قوة آلات الوصول العشوائي"، وقائع الندوة الدولية السادسة حول الأوتوماتا واللغات والبرمجة (ICALP '79) ، سلسلة محاضرات في علوم الحاسوب ، المجلد 71، سبرينغر، الصفحات 520-529 ، doi : 10.1007/3-540-09510-1_42 ، ISBN   978-3-540-09510-1، MR 0573259 .
  3. ↑ ميلهورن، كورت؛ ناهر، ستيفان (1999). منصة LEDA للحوسبة التوافقية والهندسية . مطبعة جامعة كامبريدج . تم الاطلاع عليه بتاريخ 12 نوفمبر 2019 .
  4. ↑ ميلهورن، كورت ؛ شيرا، ستيفان (2001)، "الحساب الدقيق باستخدام النظرية والتطبيقات الهندسية" (ملف PDF) ، الطرق الجبرية الرمزية وطرق التحقق (داغشتول، 1999) ، سبرينغر، ص 163-172 ، doi : 10.1007/978-3-7091-6280-4_16 ، ISBNleda_real  978-3-211-83593-7MR 1832422​ .
  5. ↑ غروتشل، م .؛ لوفاس، ل.؛ شريجفر، أ. (1981-06-01). "طريقة القطع الناقص ونتائجها في التحسين التوافقي" . كومبيناتوريكا . 1 (2): 169-197 . doi : 10.1007/BF02579273 . ISSN 1439-6912 . S2CID 43787103 .  
  6. ↑ بلوم، لينور ؛ شوب، مايك ؛ سميل، ستيف (1989)، "حول نظرية الحوسبة والتعقيد على الأعداد الحقيقية: اكتمال NP، والدوال التكرارية، والآلات الشاملة"، نشرة الجمعية الرياضية الأمريكية ، 21 (1): 1-46 ، doi : 10.1090/S0273-0979-1989-15750-9 ، Zbl 0681.03020 .