فرمت فایل: فایل Word ورد 2007 یا 2003 (Docx یا Doc) قابل ویرایش
چکیده:
در این مقاله ما نشان می دهیم که الگوریتم ها چطور می توانند در الگوریتم های روان مربوط به برخی مشکلات ترکیبی کلاسیک در مدل W-Stream، موثر و کارآمد باشند. در این مدل، در هر مرحله، یک مسیر ورودی خوانده می شود، یک مسیر خروجی نوشته شده و آیتم های داده باید با استفاده از فضای محدود، پردازش شوند؛ جریان ها با شیوه ای مانند شیوه ای که جریان خروجی در مرحله i با آن پردازش شد، به عنوان جریان ورودی در مرحله i+1 مسیردهی (لوله کشی) می شوند. ما ابتدا یک تکنیک شبیه سازی را معرفی می کنیم که امکان تبدیل الگوریتم های موثر PRAM به الگوریتم های بهینه W-Stream به ازای بسیاری از مشکلات ترکیبی کلاسیک بالاخص گراف نمودن مشکلات را فراهم می نماید، به هرحال این تکنیک، الگوریتم های نسبتاً بهینه ای را به همراه دارد. برای فائق آمدن بر این مشکل، ما مدل محاسباتی Relaxed PRAM (RPRAM) را به عنوان یک مدل میانی بین PRAM و W-Stream مطرح می کنیم.
