موضوع مقاله: الگوریتم قطعی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم قطعی | مقدمه: در علم کامپیوتر یک الگوریتم قطعی الگوریتمی است که در شرایط غیررسمی رفتاری قابل پیش‌بینی دارد، با دادن یک ورودی خاص، همیشه خروجی خاصی را ایجاد کند و ماشین اساسی آن همیشه از مسیری یکسان برای دنباله‌های وضعیت مشابه عبور کند. | ## بخش 1: الگوریتم قطعی | الگوریتم قطعی تا حد زیادی مورد مطالعه قرارگرفته و آشناترین نوع الگوریتم است، همچنین یکی از عملی‌ترین الگوریتم‌ها محسوب می‌شود، چرا که آن‌ها را می‌توان به‌طور کارآمدی بر روی ماشین‌های واقعی اجرا کرد. یک تابع برای هر ورودی یک مقدار منحصربه‌فرد دارد، و الگوریتم فرایندی است که این مقدار منحصربه‌فرد را به عنوان خروجی را تولید می‌کند. درست بعد از این‌که ما ورودی دادیم، ماشین در حالت ابتدایی یا حالت شروع قرار می‌گیرد. ماشین قطعی ماشینی است که از نقطۀ شروع به بعد، حالت فعلی آن حالت بعدی را تعیین می‌کند و جریان بین مجموعه حالت‌های آن از پیش تعیین شده‌است. توجه داشته باشید که یک ماشین می‌تواند قطعی باشد اما پایان نپذیرد یا متوقف نشود که در این صورت در تولید خروجی شکست می‌خورد. ماشین تورینگ و ماشین‌های تعین‌پذیر حالات متناهی نمونه‌هایی از ماشین قطعی انتزاعی هستند. عوامل و متغیرهای زیادی می‌توانند باعث شوند که یک الگوریتم به‌صورت تصادفی یا غیرقطعی رفتار کند مانند: زمانی که ماشین از حالت‌های خارجی به‌غیر از ورودی استفاده کند، مانند ورودی کاربر، متغیر جهانی، مقدار زمان‌سنج سخت‌افزار، مقدار اتفاقی یا داده ذخیره شده روی دیسک. | ## بخش 2: الگوریتم قطعی | زمانی که ماشین حساس به زمان عمل می‌کند برای مثال زمانی که می‌خواهید چند عمل نوشتن روی قسمتی از حافظه را به‌صورت همزمان انجام دهید، در این حالت مرتبۀ قیمتی که هر پردازنده برای نوشتن داده‌اش می‌پردازد، نتیجه را تحت تأثیر قرار می‌دهد. زمانی که یک خطای سخت‌افزاری باعث شود تا ماشین حالت خود را به یک مسیر غیرمنتظره تغییر دهد. هرچند به ندرت برنامه‌های واقعی کاملاً قطعی هستند امابرای انسان‌ها و دیگر برنامه‌ها ساده‌تر است که آن‌ها را استدلال کنند. به همین دلیل اکثر زبان‌های برنامه‌نویسی به خصوص زبان‌های برنامه‌نویسی تابعی، تلاش می‌کنند تا از اتفاقات بالا به جز در شرایط خارج از کنترل، جلوگیری کنند. فراگیری استفاده از پردازنده‌های چندهسته‌ای منجر به علاقه به قطعیت در برنامه نویسی موازی و چالش‌های غیرگرایی شد.. به عنوان مثال الگوریتم‌های ساده و کارآمدی مبتنی بر احتمالات وجود دارد که تعیین می‌کند یک عدد داده شده اول است یا نه. این الگوریتم‌ها احتمال خطای بسیار اندکی دارندو از دهۀ 1970 میلادی شناخته‌شده‌اند. | ## بخش 3: الگوریتم قطعی | به عنوان مثالی دیگر، مسایل ان‌پی کامل که شامل بسیاری از مهم‌ترین مسایل عملی است را می‌توان با روشی به نام ماشین تورینگ غیرقطعی به‌سرعت حل کرد اما الگوریتم‌های کارای عملی برای هیچ یک از آن‌ها یافت نمی‌شود. در بهترین حالت ما می‌توانیم الگوریتم‌های تقریبی یا راه‌حل‌هایی برای موارد خاص پیدا کنیم. یکی دیگر از مشکلات عمده با الگوریتم قطعی این است که در برخی مواقع ما نمی‌خواهیم نتایج قابل پیش‌بینی باشند. برای مثال شما وقتی در حال انجام بازی بلاک جک به صورت برخط هستید و برای برزدن هر دست از تولید کنندۀ اعداد تصادفی استفاده می‌کنید، یک قمارباز باهوش می‌تواند به‌طور دقیق عددی را که تولیدکننده انتخاب می‌کند، حدس بزند و محتوای هر دست را در زمان تعیین کند، که این در واقع اجازۀ تقلب را به او می‌دهد. اشکالی مشابه در رمزنگاری رخ می‌دهد چرا که اغلب کلیدهای محرمانه با استفاده از چنین تولیدکننده‌هایی ساخته می‌شوند. | ## جمع‌بندی | از این‌گونه مشکلات می‌توان با استفاده از مولد عدد شبه تصادفی امن رمزنگارانه اجتناب کرد.