الگوریتم قطعی
در علم کامپیوتر یک الگوریتم قطعی الگوریتمی است که در شرایط غیررسمی رفتاری قابل پیش‌بینی دارد، با دادن یک ورودی خاص، همیشه خروجی خاصی را ایجاد کند و ماشین اساسی آن همیشه از مسیری یکسان برای دنباله‌های وضعیت مشابه عبور کند. الگوریتم قطعی تا حد زیادی مورد مطالعه قرارگرفته و آشناترین نوع الگوریتم است، همچنین یکی از عملی‌ترین الگوریتم‌ها محسوب می‌شود، چرا که آن‌ها را می‌توان به‌طور کارآمدی بر روی ماشین‌های واقعی اجرا کرد.
به‌طور رسمی یک الگوریتم قطعی یک تابع ریاضی را محاسبه می‌کند. یک تابع برای هر ورودی یک مقدار منحصربه‌فرد دارد، و الگوریتم فرایندی است که این مقدار منحصربه‌فرد را به عنوان خروجی را تولید می‌کند.
تعریف رسمی
الگوریتم قطعی می‌تواند به عنوان یک ماشین حالت تعریف شود. حالت، فعالیت ماشین در یک لحظۀ خاص را توصیف می‌کند. ماشین حالت با روش‌های مجزایی از حالتی به حالت دیگر می‌رود. درست بعد از این‌که ما ورودی دادیم، ماشین در حالت ابتدایی یا حالت شروع قرار می‌گیرد. ماشین قطعی ماشینی است که از نقطۀ شروع به بعد، حالت فعلی آن حالت بعدی را تعیین می‌کند و جریان بین مجموعه حالت‌های آن از پیش تعیین شده‌است. توجه داشته باشید که یک ماشین می‌تواند قطعی باشد اما پایان نپذیرد یا متوقف نشود که در این صورت در تولید خروجی شکست می‌خورد.
ماشین تورینگ و ماشین‌های تعین‌پذیر حالات متناهی نمونه‌هایی از ماشین قطعی انتزاعی هستند.
چه چیز الگوریتم را غیرقطعی می‌کند؟
عوامل و متغیرهای زیادی می‌توانند باعث شوند که یک الگوریتم به‌صورت تصادفی یا غیرقطعی رفتار کند مانند:
- زمانی که ماشین از حالت‌های خارجی به‌غیر از ورودی استفاده کند، مانند ورودی کاربر، متغیر جهانی، مقدار زمان‌سنج سخت‌افزار، مقدار اتفاقی یا داده ذخیره شده روی دیسک.
- زمانی که ماشین حساس به زمان عمل می‌کند برای مثال زمانی که می‌خواهید چند عمل نوشتن روی قسمتی از حافظه را به‌صورت همزمان انجام دهید، در این حالت مرتبۀ قیمتی که هر پردازنده برای نوشتن داده‌اش می‌پردازد، نتیجه را تحت تأثیر قرار می‌دهد.
- زمانی که یک خطای سخت‌افزاری باعث شود تا ماشین حالت خود را به یک مسیر غیرمنتظره تغییر دهد.
هرچند به ندرت برنامه‌های واقعی کاملاً قطعی هستند امابرای انسان‌ها و دیگر برنامه‌ها ساده‌تر است که آن‌ها را استدلال کنند. به همین دلیل اکثر زبان‌های برنامه‌نویسی به خصوص زبان‌های برنامه‌نویسی تابعی، تلاش می‌کنند تا از اتفاقات بالا به جز در شرایط خارج از کنترل، جلوگیری کنند.
فراگیری استفاده از پردازنده‌های چندهسته‌ای منجر به علاقه به قطعیت در برنامه نویسی موازی و چالش‌های غیرگرایی شد.. تعدادی از ابزارها برای کمک به مقابله با چالش‌ها، بن‌بست‌ها و شرایط مسابقه در بخش منابع برای مطالعهٔ بیشتر پیشنهاد شده‌است.
مشکلات الگوریتم قطعی
متأسفانه برای برخی مسائل پیدا کردن الگوریتم قطعی سخت است. به عنوان مثال الگوریتم‌های ساده و کارآمدی مبتنی بر احتمالات وجود دارد که تعیین می‌کند یک عدد داده شده اول است یا نه. این الگوریتم‌ها احتمال خطای بسیار اندکی دارندو از دهۀ 1970 میلادی شناخته‌شده‌اند.
به عنوان مثالی دیگر، مسایل ان‌پی کامل که شامل بسیاری از مهم‌ترین مسایل عملی است را می‌توان با روشی به نام ماشین تورینگ غیرقطعی به‌سرعت حل کرد اما الگوریتم‌های کارای عملی برای هیچ یک از آن‌ها یافت نمی‌شود. در بهترین حالت ما می‌توانیم الگوریتم‌های تقریبی یا راه‌حل‌هایی برای موارد خاص پیدا کنیم.
یکی دیگر از مشکلات عمده با الگوریتم قطعی این است که در برخی مواقع ما نمی‌خواهیم نتایج قابل پیش‌بینی باشند. برای مثال شما وقتی در حال انجام بازی بلاک جک به صورت برخط هستید و برای برزدن هر دست از تولید کنندۀ اعداد تصادفی استفاده می‌کنید، یک قمارباز باهوش می‌تواند به‌طور دقیق عددی را که تولیدکننده انتخاب می‌کند، حدس بزند و محتوای هر دست را در زمان تعیین کند، که این در واقع اجازۀ تقلب را به او می‌دهد. برای مثال گروه امنیت نرم‌افزار در فناوری‌های نرم‌افزاری مطمئن توانستند این کار را برای پوکر تگزاس که توسط AFS انتشار یافته بود انجام دهند، چنان که خروجی هر دست را جلوتر از زمان پیش‌بینی کردند. اشکالی مشابه در رمزنگاری رخ می‌دهد چرا که اغلب کلیدهای محرمانه با استفاده از چنین تولیدکننده‌هایی ساخته می‌شوند. از این‌گونه مشکلات می‌توان با استفاده از مولد عدد شبه تصادفی امن رمزنگارانه اجتناب کرد.
جستارهای وابسته
منابع
- ↑ Edward A. Lee. "The Problem with Threads" (PDF). Retrieved 2009-05-29.
- ↑ James Reinders. "Parallel terminology definitions". Archived from the original on 24 February 2012. 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". Retrieved 2009-05-29.
- Yuan Lin. "Data Race and Deadlock Detection with Sun Studio Thread Analyzer" (PDF). Retrieved 2009-05-29.
- avid Worthington. "Intel addresses development life cycle with Parallel Studio". Archived from the original on 28 May 2009. Retrieved 2009-05-26.