الگوریتم قطعی

در علم کامپیوتر یک الگوریتم قطعی الگوریتمی است که در شرایط غیررسمی رفتاری قابل پیش‌بینی دارد، با دادن یک ورودی خاص، همیشه خروجی خاصی را ایجاد کند و ماشین اساسی آن همیشه از مسیری یکسان برای دنباله‌های وضعیت مشابه عبور کند. الگوریتم قطعی تا حد زیادی مورد مطالعه قرارگرفته و آشناترین نوع الگوریتم است، همچنین یکی از عملی‌ترین الگوریتم‌ها محسوب می‌شود، چرا که آن‌ها را می‌توان به‌طور کارآمدی بر روی ماشین‌های واقعی اجرا کرد.
به طور رسمی یک الگوریتم قطعی یک تابع ریاضی را محاسبه می‌کند. یک تابع برای هر ورودی یک مقدار منحصربه‌فرد دارد، و الگوریتم فرایندی است که این مقدار منحصربه‌فرد را به عنوان خروجی را تولید می‌کند.
تعریف رسمی
الگوریتم قطعی می‌تواند به عنوان یک ماشین حالت تعریف شود. حالت، فعالیت ماشین در یک لحظه خاص را توصیف می‌کند. ماشین حالت با روش‌های مجزایی از حالتی به حالت دیگر می‌رود. درست بعد از این‌که ما ورودی دادیم، ماشین در حالت ابتدایی یا حالت شروع قرار می‌گیرد. ماشین قطعی ماشینی است که از نقطه شروع به بعد، حالت فعلی آن حالت بعدی را تعیین می‌کند و جریان بین مجموعه حالت‌های آن از پیش تعیین شده است. توجه داشته باشید که یک ماشین می‌تواند قطعی باشد اما پایان نپذیرد یا متوقف نشود که در این صورت در تولید خروجی شکست می‌خورد.
ماشین تورینگ و ماشین‌های تعین‌پذیر حالات متناهی نمونه‌هایی از ماشین قطعی انتزاعی هستند.
چه چیز الگوریتم را غیرقطعی می‌کند؟
عوامل و متغیرهای زیادی می‌توانند باعث شوند که یک الگوریتم به‌صورت تصادفی یا غیرقطعی رفتار کند مانند:
زمانی که ماشین از حالت‌های خارجی به‌غیر از ورودی استفاده کند، مانند ورودی کاربر، متغیر جهانی، مقدار زمان‌سنج سخت‌افزار، مقدار اتفاقی یا داده ذخیره شده روی دیسک.
زمانی که ماشین حساس به زمان عمل می‌کند برای مثال زمانی که می‌خواهید چند عمل نوشتن روی قسمتی از حافظه را به‌صورت همزمان انجام دهید، در این حالت مرتبه قیمتی که هر پردازنده برای نوشتن داده‌اش می‌پردازد، نتیجه را تحت تاثیر قرار می‌دهد.
زمانی که یک خطای سخت‌افزاری باعث شود تا ماشین حالت خود را به یک مسیر غیرمنتظره تغییر دهد.
هرچند به ندرت برنامه‌های واقعی کاملا قطعی هستند امابرای انسان‌ها و دیگر برنامه‌ها ساده‌تر است که آن‌ها را استدلال کنند. به همین دلیل اکثر زبان‌های برنامه‌نویسی به خصوص زبان‌های برنامه‌نویسی تابعی، تلاش می‌کنند تا از اتفاقات بالا به جز در شرایط خارج از کنترل، جلوگیری کنند.
فراگیری استفاده از پردازنده‌های چندهسته‌ای منجر به علاقه به قطعیت در برنامه نویسی موازی و چالش‌های غیرگرایی شد.. تعدادی از ابزارها برای کمک به مقابله با چالش‌ها، بن‌بست‌ها و شرایط مسابقه در بخش منابع برای مطالعه بیشتر پیشنهاد شده‌است.
مشکلات الگوریتم قطعی
متاسفانه برای برخی مسائل پیدا کردن الگوریتم قطعی سخت است. به عنوان مثال الگوریتم‌های ساده و کارآمدی مبتنی بر احتمالات وجود دارد که تعیین می‌کند یک عدد داده شده اول است یا نه. این الگوریتم‌ها احتمال خطای بسیار اندکی دارندو از دهه 1970 میلادی شناخته‌شده‌اند.
به عنوان مثالی دیگر، مسایل ان‌پی کامل که شامل بسیاری از مهم‌ترین مسایل عملی است را می‌توان با روشی به نام ماشین تورینگ غیرقطعی به‌سرعت حل کرد اما الگوریتم‌های کارای عملی برای هیچ یک از آن‌ها یافت نمی‌شود. در بهترین حالت ما می‌توانیم الگوریتم‌های تقریبی یا راه‌حل‌هایی برای موارد خاص پیدا کنیم.
یکی دیگر از مشکلات عمده با الگوریتم قطعی این است که در برخی مواقع ما نمی‌خواهیم نتایج قابل پیش‌بینی باشند. برای مثال شما وقتی در حال انجام بازی بلاک جک به صورت برخط هستید و برای برزدن هر دست از تولید کننده اعداد تصادفی استفاده می‌کنید، یک قمارباز باهوش می‌تواند به‌طور دقیق عددی را که تولیدکننده انتخاب می‌کند، حدس بزند و محتوای هر دست را در زمان تعیین کند، که این در واقع اجازه تقلب را به او می‌دهد. برای مثال گروه امنیت نرم‌افزار در فناوری‌های نرم‌افزاری مطمئن توانستند این کار را برای پوکر تگزاس که توسط AFS انتشار یافته بود انجام دهند، چنان که خروجی هر دست را جلوتر از زمان پیش‌بینی کردند . اشکالی مشابه در رمزنگاری رخ می‌دهد چرا که اغلب کلیدهای محرمانه با استفاده از چنین تولیدکننده‌هایی ساخته می‌شوند. از این‌گونه مشکلات می‌توان با استفاده از مولد عدد شبه تصادفی امن رمزنگارانه اجتناب کرد.