ذاكرة الوصول العشوائي للكلمات

في علم الحاسوب النظري ، يُعد نموذج ذاكرة الوصول العشوائي للكلمات (Word RAM ) نموذجًا للحوسبة حيث تقوم آلة الوصول العشوائي بإجراء عمليات حسابية وعمليات على مستوى البتات على كلمة مكونة من $w$ بت. وقد ابتكره مايكل فريدمان ودان ويلارد عام 1990 لمحاكاة لغات البرمجة مثل لغة C. ^{[ 1 ]}

نموذج

نموذج ذاكرة الوصول العشوائي للكلمات هو آلة مجردة تشبه آلة الوصول العشوائي ، ولكن بذاكرة محدودة وطول كلمة محدود. وهو يعمل مع كلمات يصل حجمها إلى $w$ بت، مما يعني أنه يمكنه تخزين أعداد صحيحة تصل إلى $2^{w}-1$ لأن النموذج يفترض أن حجم الكلمة يطابق حجم المشكلة، أي بالنسبة لمشكلة بحجم $n$ ، $w\geq \log n$ ، نموذج ذاكرة الوصول العشوائي (RAM) هو نموذج ثنائي التفرع . ^{[ 2 ]} يسمح هذا النموذج بإجراء العمليات الحسابية والعمليات على مستوى البت، بما في ذلك عمليات الإزاحة المنطقية، في وقت ثابت (قد تختلف مجموعة التعليمات الدقيقة التي تفترضها الخوارزمية أو البرهان باستخدام النموذج).

الخوارزميات وهياكل البيانات

في نموذج ذاكرة الوصول العشوائي للكلمات، يمكن فرز الأعداد الصحيحة بكفاءة عالية. ابتكر ييجي هان وميكيل ثورب خوارزمية عشوائية لفرز الأعداد الصحيحة في وقت متوقع قدره (باستخدام ترميز Big O ). $O(n{\sqrt {\log \log n}})$ [ ^{3 ] بينما ابتكر} هان أيضًا نسخة حتمية بوقت تشغيل $O(n\log \log n)$ [ ⁴^]

تُحلل مشكلة السلف الديناميكي بشكل شائع في نموذج ذاكرة الوصول العشوائي للكلمات، وكانت الدافع الأصلي لهذا النموذج. استخدم دان ويلارد محاولات y-fast لحل هذه المشكلة. $O(\log w)$ الوقت، أو بتعبير أدق، $O(\log \log U)$ حيث $U$ حدٌّ للقيم المخزنة. ^{[ 5 ]} كما حلّ مايكل فريدمان وويلارد المشكلة باستخدام أشجار الاندماج في $O(\log _{w}n)$ [ ^{1 ]} باستخدام أشجار البحث الأسية ^، يمكن تنفيذ الاستعلام في $O({\sqrt {\log n/\log \log n}})$ [ ⁶^]

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

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

انظر أيضاً

نموذج ثنائي التفرع

مراجع

1 2 فريدمان، مايكل ؛ ويلارد، دان (1990). "اختراق حاجز نظرية المعلومات باستخدام أشجار الاندماج". ندوة حول نظرية الحوسبة : 1-7 .
↑ في الواقع، يُفترض عادةًأن $n أصغر من$ $2^{w}$ ، بحيث يمكن فهرسة بنية البيانات المعتبرة باستخدام عناوين مكونة $من w$ بت.
↑ هان، ييجي؛ ثورب، م. (2002)، "فرز الأعداد الصحيحة في زمن متوقع $O($ $n$ $\sqrt$ $log log$ $n$ $)$ ومساحة خطية"، وقائع الندوة السنوية الثالثة والأربعين حول أسس علوم الحاسوب (FOCS 2002) ، جمعية مهندسي الكهرباء والإلكترونيات، ص 135-144 ، CiteSeerX 10.1.1.671.5583 ، doi : 10.1109/SFCS.2002.1181890 ، ISBN 978-0-7695-1822-0
↑ هان، ييجي (2004)، "الفرز الحتمي في زمن $O$ $($ $n$ $log log$ $n$ $)$ ومساحة خطية"، مجلة الخوارزميات ، 50 (1): 96-105 ، doi : 10.1016/j.jalgor.2003.09.001 ، MR 2028585
↑ ويلارد، دان إي. (1983). "استعلامات النطاق في أسوأ الحالات اللوغاريتمية ممكنة في الفضاء Θ (N)". رسائل معالجة المعلومات . 17 (2): 81-84 . doi : 10.1016/0020-0190(83)90075-3 .
↑ أندرسون، آرني؛ ثورب، ميكيل (2007). "المجموعات المرتبة الديناميكية مع أشجار البحث الأسية". مجلة ACM . 54 (3): 13. arXiv : cs/0210006 . doi : 10.1145/1236457.1236460 .

[Fredman90-1] 1 2 فريدمان، مايكل ؛ ويلارد، دان (1990). "اختراق حاجز نظرية المعلومات باستخدام أشجار الاندماج". ندوة حول نظرية الحوسبة : 1-7 .

[2] في الواقع، يُفترض عادةًأن $n أصغر من$ $2^{w}$ ، بحيث يمكن فهرسة بنية البيانات المعتبرة باستخدام عناوين مكونة $من w$ بت.

[Han02-3] هان، ييجي؛ ثورب، م. (2002)، "فرز الأعداد الصحيحة في زمن متوقع $O($ $n$ $\sqrt$ $log log$ $n$ $)$ ومساحة خطية"، وقائع الندوة السنوية الثالثة والأربعين حول أسس علوم الحاسوب (FOCS 2002) ، جمعية مهندسي الكهرباء والإلكترونيات، ص 135-144 ، CiteSeerX 10.1.1.671.5583 ، doi : 10.1109/SFCS.2002.1181890 ، ISBN 978-0-7695-1822-0

[Han04-4] هان، ييجي (2004)، "الفرز الحتمي في زمن $O$ $($ $n$ $log log$ $n$ $)$ ومساحة خطية"، مجلة الخوارزميات ، 50 (1): 96-105 ، doi : 10.1016/j.jalgor.2003.09.001 ، MR 2028585

[5] ويلارد، دان إي. (1983). "استعلامات النطاق في أسوأ الحالات اللوغاريتمية ممكنة في الفضاء Θ (N)". رسائل معالجة المعلومات . 17 (2): 81-84 . doi : 10.1016/0020-0190(83)90075-3 .

[6] أندرسون، آرني؛ ثورب، ميكيل (2007). "المجموعات المرتبة الديناميكية مع أشجار البحث الأسية". مجلة ACM . 54 (3): 13. arXiv : cs/0210006 . doi : 10.1145/1236457.1236460 .

[ 1 ]

[ 2 ]

3 ] بينما ابتكر

4

[ 5 ]

6

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗