رم حقیقی

در محاسبات، خصوص در هندسه محاسباتی ، یک RAM حقیقی ( ماشین دسترسی تصادفی ) یک مدل ریاضی از رایانه است که قادر است با اعداد حقیقی دقیق به جای اعداد نقطه ثابت باینری یا اعداد ممیز شناور که توسط بیشتر رایانه‌های حقیقی استفاده می‌شود، محاسبه کند. رم حقیقی به وسیله Michael Ian Shamos ،در پایان نامه دکترای وی در سال 1978 فرموله شد. ^[۱]

مدل

بخش "RAM" از مدل رم حقیقی کوتاه شده کلمه " ماشین دسترسی تصادفی "(random-access machine) است. این مدلی از محاسبات است که مانند یک نمونه ساده شده از معماری استاندارد کامپیوتر است. این حاوی یک برنامه ذخیره شده ، یک واحد حافظه کامپیوتر تهیه شده از آرایه ای از سلول ها، و یک واحد پردازش مرکزی با تعداد محدودی از ثبات ها است. هر سلول یا رجیستر حافظه قادر است یک عدد حقیقی را ذخیره کند. تحت کنترل برنامه، رم حقیقی می تواند اعداد حقیقی را بین حافظه و ثبات ها انتقال دهد و عملیات محاسباتی را روی مقادیر ثبت شده در ثبات ها انجام دهد.

عملیات مجاز اکثر مواقع شامل جمع، تفریق، ضرب و تقسیم و همچنین مقایسه خطی است، اما شامل پیمانه یا گرد کردن اعداد صحیح نیست. دلیل استفاده نکردن از گرد کردن اعداد صحیح و عملیات پیمانه این است که اجازه دادن به این عملیات ممکن است مقادیر غیر منطقی بزرگ محاسباتی را به رم حقیقی بدهد و آن را مجبور میکند تا مسائل PSPACE-complete را با پیچیدگی زمان حل کند. ^[۲]

هنگام تحلیل الگوریتم‌ها برای رم حقیقی، هر عملیات مجاز، معمولاً زمان اجرای الگوریتم از پیش تعیین شده ای را در برمی گیرد.

پیاده سازی

کتابخانه‌های نرم‌افزاری مانند LEDA توسعه یافته‌اند که به برنامه‌نویسان اجازه دهند تا برنامه‌های رایانه‌ای بنویسند ؛این برنامه ها به‌گونه‌ای کار می‌کنند که انگار روی یک RAM حقیقی اجرا می‌شوند. این کتابخانه ها مقادیر حقیقی را از طریق ساختمان داده نشان می دهند که به آنها اجازه می دهد محاسبات و مقایسه را با همان نتایجی که یک رم حقیقی ایجاد می کند، انجام دهند. برای نمونه، در LEDA، اعداد حقیقی به وسیله نوع داده leda_real داده می‌شوند که از ریشه‌های k -ام برای هر عدد طبیعی k ، عملگرهای گویا و عملگرهای مقایسه ای پشتیبانی می‌کند. تجزیه و تحلیل زمانی الگوریتم رم حقیقی اساسی به وسیله این نوع داده های حقیقی را می توان به وسیله شمارش بارهایی که کتابخانه مورد نیاز فراخوانده می شود را توسط یک الگوریتم معین تفسیر کرد. ^[۳]

مدل های مرتبط

رم حقیقی به دستگاه Blum–Shub–Smale بسیار شبیه است. ^[۴] با این حال، رم حقیقی معمولاً برای تجزیه و تحلیل الگوریتم‌های اساسی در هندسه محاسباتی استفاده می‌شود، در حالی که ماشین Blum–Shub–Smale پایه‌ای را برای بسط تئوری NP-کمیت به محاسبات اعداد حقیقی تشکیل می‌دهد.

یک جایگزین برای رم حقیقی word RAM است که در آن هم ورودی های یک مسئله و هم مقادیر ذخیره شده در حافظه و ثبات ها با تعداد بیت های ثابت، اعداد صحیح در نظر گرفته می شوند. مدل word RAM می تواند برخی از عملیات ها را سریعتر از رم حقیقی انجام دهد. برای نمونه : الگوریتم‌های مرتب‌سازی سریع اعداد صحیح را ارائه می‌دهد، در حالی که مرتب‌سازی روی رم حقیقی باید با الگوریتم‌های مرتب‌سازی مقایسه ای کندتر انجام شود. با این حال، برخی از مسائل هندسه محاسباتی ورودی یا خروجی هایی دارند که نمی توان آنها را به صورت دقیق و با استفاده از مختصات اعداد صحیح نشان داد. به عنوان مثال پیکربندی Perles را داریم که ترتیبی از نقاط و پاره های خطی که نمایش مختصات صحیحی ندارد.

منابع

↑ Shamos, Michael Ian (1978), Computational Geometry, Ph.D. dissertation, Yale University.
↑ Schönhage, Arnold (1979), "On the power of random access machines", Proceedings of the Sixth International Colloquium on Automata, Languages and Programming (ICALP '79), Lecture Notes in Computer Science, vol. 71, Springer, pp. 520–529, doi:10.1007/3-540-09510-1_42, ISBN 978-3-540-09510-1, MR 0573259.
↑ Mehlhorn, Kurt; Schirra, Stefan (2001), "Exact computation with leda_real—theory and geometric applications" (PDF), Symbolic Algebraic Methods and Verification Methods (Dagstuhl, 1999), Springer, pp. 163–172, doi:10.1007/978-3-7091-6280-4_16, ISBN 978-3-211-83593-7, MR 1832422.
↑ Blum, Lenore; Shub, Mike; Smale, Steve (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", Bulletin of the American Mathematical Society, 21 (1): 1–46, doi:10.1090/S0273-0979-1989-15750-9, Zbl 0681.03020.

پیوند به بیرون

منابع ماشین های دسترسی تصادفی واقعی امکان پذیر است
- محاسبات هندسی علم ساخت الگوریتم های هندسی

[1] Shamos, Michael Ian (1978), Computational Geometry, Ph.D. dissertation, Yale University.

[2] Schönhage, Arnold (1979), "On the power of random access machines", Proceedings of the Sixth International Colloquium on Automata, Languages and Programming (ICALP '79), Lecture Notes in Computer Science, vol. 71, Springer, pp. 520–529, doi:10.1007/3-540-09510-1_42, ISBN 978-3-540-09510-1, MR 0573259.

[3] Mehlhorn, Kurt; Schirra, Stefan (2001), "Exact computation with leda_real—theory and geometric applications" (PDF), Symbolic Algebraic Methods and Verification Methods (Dagstuhl, 1999), Springer, pp. 163–172, doi:10.1007/978-3-7091-6280-4_16, ISBN 978-3-211-83593-7, MR 1832422.

[4] Blum, Lenore; Shub, Mike; Smale, Steve (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", Bulletin of the American Mathematical Society, 21 (1): 1–46, doi:10.1090/S0273-0979-1989-15750-9, Zbl 0681.03020.

[۱]

[۲]

[۳]

[۴]