الگوریتم قطعی
در علم کامپیوتر یک الگوریتم قطعی الگوریتمی است که در شرایط غیررسمی رفتاری قابل پیشبینی دارد، با دادن یک ورودی خاص، همیشه خروجی خاصی را ایجاد کند و ماشین اساسی آن همیشه از مسیری یکسان برای دنبالههای وضعیت مشابه عبور کند. الگوریتم قطعی تا حد زیادی مورد مطالعه قرارگرفته و آشناترین نوع الگوریتم است، همچنین یکی از عملی ترین الگوریتمها محسوب میشود، چرا که آنها را می توان بهطور کارآمدی بر روی ماشینهای واقعی اجرا کرد.
به طور رسمی یک الگوریتم قطعی یک تابع ریاضی را محاسبه میکند. یک تابع برای هر ورودی یک مقدار منحصر بهفرد دارد، و الگوریتم فرایندی است که این مقدار منحصر به فرد را به عنوان خروجی را تولید میکند.
محتویات |
[ویرایش] تعریف رسمی
الگوریتم قطعی میتواند به عنوان یک ماشین حالت تعریف شود. حالت، فعالیت ماشین در یک لحظهی خاص را توصیف میکند. ماشین حالت با روشهای مجزایی از حالتی به حالت دیگر میرود. درست بعد از اینکه ما ورودی دادیم، ماشین در حالت ابتدایی یا حالت شروع قرار میگیرد. ماشین قطعی ماشینی است که از نقطهی شروع به بعد، حالت فعلی آن حالت بعدی را تعیین میکند و جریان بین مجموعه حالتهای آن از پیش تعیین شده است. توجه داشته باشید که یک ماشین میتواند قطعی باشد اما پایان نپذیرد و یا متوقف نشود که در این صورت در تولید خروجی شکست میخورد.
ماشین تورینگ و ماشینهای تعینپذیر حالات متناهی نمونههایی از ماشین قطعی انتزاعی هستند.
[ویرایش] چه چیز الگوریتم را غیرقطعی میکند؟
عوامل و متغیرهای زیادی میتوانند باعث شوند که یک الگوریتم بهصورت تصادفی و یا غیرقطعی رفتار کند مانند:
- زمانی که ماشین از حالتهای خارجی بهغیر از ورودی استفاده کند، مانند ورودی کاربر، متغیر جهانی، مقدار زمانسنج سختافزار، مقدار اتفاقی و یا داده ذخیره شده روی دیسک.
- زمانی که ماشین حساس به زمان عمل میکند برای مثال زمانی که میخواهید چند عمل نوشتن روی قسمتی از حافظه را بهصورت همزمان انجام دهید، در این حالت مرتبهی قیمتی که هر پردازنده برای نوشتن دادهاش میپردازد، نتیجه را تحت تاثیر قرار میدهد.
- زمانی که یک خطای سختافزاری باعث شود تا ماشین حالت خود را به یک مسیر غیرمنتظره تغییر دهد.
هرچند به ندرت برنامههای واقعی کاملا قطعی هستند امابرای انسانها و دیگر برنامهها سادهتر است که آنها را استدلال کنند. به همین دلیل اکثر زبانهای برنامهنویسی به خصوص زبانهای برنامهنویسی تابعی، تلاش میکنند تا از اتفاقات بالا به جز در شرایط خارج از کنترل، جلوگیری کنند.
فراگیری استفاده از پردازندههای چندهستهای منجر به علاقه به قطعیت در برنامه نویسی موازی و چالشهای غیرگرایی شد..[۱][۲] تعدادی از ابزارها برای کمک به مقابله با چالشها، بنبستها و شرایط مسابقه در بخش منابع برای مطالعهٔ بیشتر پیشنهاد شدهاست.
[ویرایش] مشکلات الگوریتم قطعی
متاسفانه برای برخی مسائل پیدا کردن الگوریتم قطعی سخت است. به عنوان مثال الگوریتمهای ساده و کارآمدی مبتنی بر احتمالات وجود دارد که تعیین میکند یک عدد داده شده اول است یا نه. این الگوریتمها احتمال خطای بسیار اندکی دارندو از دههی 1970 میلادی شناختهشده اند.
به عنوان مثالی دیگر، مسایل انپی کامل که شامل بسیاری از مهم ترین مسایل عملی است را میتوان با روشی به نام ماشین تورینگ غیرقطعی بهسرعت حل کرد اما الگوریتمهای کارای عملی برای هیچ یک از آنها یافت نمیشود. در بهترین حالت ما میتوانیم الگوریتمهای تقریبی یا راهحلهایی برای موارد خاص پیدا کنیم.
یکی دیگر از مشکلات عمده با الگوریتم قطعی این است که در برخی مواقع ما نمیخواهیم نتایج قابل پیشبینی باشند. برای مثال شما وقتی در حال انجام بازی بلاک جک به صورت برخط هستید و برای برزدن هر دست از تولید کنندهی اعداد تصادفی استفاده میکنید، یک قمارباز باهوش میتواند بهطور دقیق عددی را که تولیدکننده انتخاب میکند، حدس بزند و محتوای هر دست را در زمان تعیین کند، که این در واقع اجازهی تقلب را به او میدهد. برای مثال گروه امنیت نرمافزار در فناوریهای نرمافزاری مطمئن توانستند این کار را برای پوکر تگزاس که توسط AFS انتشار یافته بود انجام دهند، چنان که خروجی هر دست را جلوتر از زمان پیشبینی کردند[۳]. اشکالی مشابه در رمزنگاری رخ میدهد چرا که اغلب کلیدهای محرمانه با استفاده از چنین تولیدکنندههایی ساخته میشوند. از اینگونه مشکلات میتوان با استفاده از مولد عدد شبه تصادفی امن رمزنگارانه اجتناب کرد.
[ویرایش] منابع
- ↑ Edward A. Lee. "The Problem with Threads". http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf. Retrieved 2009-05-29.
- ↑ James Reinders. "Parallel terminology definitions". http://intel.zdnet.co.uk/parallelism/?id=260632239. Retrieved 2009-05-29.
- ↑ Gary McGraw and John Viega. Make your software behave: Playing the numbers: How to cheat in online gambling. http://www.ibm.com/developerworks/library/s-playing/#h4
[ویرایش] منابع برای مطالعهٔ بیشتر
- "Intel Parallel Inspector Thread Checker". http://software.intel.com/en-us/videos/intel-parallel-inspector-thread-checker/. Retrieved 2009-05-29.
- Yuan Lin. "Data Race and Deadlock Detection with Sun Studio Thread Analyzer". http://developers.sun.com/sunstudio/documentation/product/sd_west_threadAnalyzer.pdf. Retrieved 2009-05-29.
- avid Worthington. "Intel addresses development life cycle with Parallel Studio". http://sdtimes.com/link/33497. Retrieved 2009-05-26.
|
||||||||||||||||||||||||||||||||||||||
