در علم کامپیوتر یک الگوریتم قطعی الگوریتمی است که در شرایط غیررسمی رفتاری قابل پیش بینی دارد، با دادن یک ورودی خاص، همیشه خروجی خاصی را ایجاد کند و ماشین اساسی آن همیشه از مسیری یکسان برای دنباله های وضعیت مشابه عبور کند. الگوریتم قطعی تا حد زیادی مورد مطالعه قرارگرفته و آشناترین نوع الگوریتم است، همچنین یکی از عملی ترین الگوریتم ها محسوب می شود، چرا که آن ها را می توان به طور کارآمدی بر روی ماشین های واقعی اجرا کرد. به طور رسمی یک الگوریتم قطعی یک تابع ریاضی را محاسبه می کند. یک تابع برای هر ورودی یک مقدار منحصربه فرد دارد، و الگوریتم فرایندی است که این مقدار منحصربه فرد را به عنوان خروجی را تولید می کند.
الگوریتم قطعی می تواند به عنوان یک ماشین حالت تعریف شود. حالت، فعالیت ماشین در یک لحظۀ خاص را توصیف می کند. ماشین حالت با روش های مجزایی از حالتی به حالت دیگر می رود. درست بعد از این که ما ورودی دادیم، ماشین در حالت ابتدایی یا حالت شروع قرار می گیرد. ماشین قطعی ماشینی است که از نقطۀ شروع به بعد، حالت فعلی آن حالت بعدی را تعیین می کند و جریان بین مجموعه حالت های آن از پیش تعیین شده است. توجه داشته باشید که یک ماشین می تواند قطعی باشد اما پایان نپذیرد یا متوقف نشود که در این صورت در تولید خروجی شکست می خورد. ماشین تورینگ و ماشین های تعین پذیر حالات متناهی نمونه هایی از ماشین قطعی انتزاعی هستند.
عوامل و متغیرهای زیادی می توانند باعث شوند که یک الگوریتم به صورت تصادفی یا غیرقطعی رفتار کند مانند:
• زمانی که ماشین از حالت های خارجی به غیر از ورودی استفاده کند، مانند ورودی کاربر، متغیر جهانی، مقدار زمان سنج سخت افزار، مقدار اتفاقی یا داده ذخیره شده روی دیسک.
• زمانی که ماشین حساس به زمان عمل می کند برای مثال زمانی که می خواهید چند عمل نوشتن روی قسمتی از حافظه را به صورت همزمان انجام دهید، در این حالت مرتبۀ قیمتی که هر پردازنده برای نوشتن داده اش می پردازد، نتیجه را تحت تأثیر قرار می دهد.
• زمانی که یک خطای سخت افزاری باعث شود تا ماشین حالت خود را به یک مسیر غیرمنتظره تغییر دهد.
هرچند به ندرت برنامه های واقعی کاملاً قطعی هستند امابرای انسان ها و دیگر برنامه ها ساده تر است که آن ها را استدلال کنند. به همین دلیل اکثر زبان های برنامه نویسی به خصوص زبان های برنامه نویسی تابعی، تلاش می کنند تا از اتفاقات بالا به جز در شرایط خارج از کنترل، جلوگیری کنند. فراگیری استفاده از پردازنده های چندهسته ای منجر به علاقه به قطعیت در برنامه نویسی موازی و چالش های غیرگرایی شد. . [ ۱] [ ۲] تعدادی از ابزارها برای کمک به مقابله با چالش ها، بن بست ها و شرایط مسابقه در بخش منابع برای مطالعهٔ بیشتر پیشنهاد شده است.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفالگوریتم قطعی می تواند به عنوان یک ماشین حالت تعریف شود. حالت، فعالیت ماشین در یک لحظۀ خاص را توصیف می کند. ماشین حالت با روش های مجزایی از حالتی به حالت دیگر می رود. درست بعد از این که ما ورودی دادیم، ماشین در حالت ابتدایی یا حالت شروع قرار می گیرد. ماشین قطعی ماشینی است که از نقطۀ شروع به بعد، حالت فعلی آن حالت بعدی را تعیین می کند و جریان بین مجموعه حالت های آن از پیش تعیین شده است. توجه داشته باشید که یک ماشین می تواند قطعی باشد اما پایان نپذیرد یا متوقف نشود که در این صورت در تولید خروجی شکست می خورد. ماشین تورینگ و ماشین های تعین پذیر حالات متناهی نمونه هایی از ماشین قطعی انتزاعی هستند.
عوامل و متغیرهای زیادی می توانند باعث شوند که یک الگوریتم به صورت تصادفی یا غیرقطعی رفتار کند مانند:
• زمانی که ماشین از حالت های خارجی به غیر از ورودی استفاده کند، مانند ورودی کاربر، متغیر جهانی، مقدار زمان سنج سخت افزار، مقدار اتفاقی یا داده ذخیره شده روی دیسک.
• زمانی که ماشین حساس به زمان عمل می کند برای مثال زمانی که می خواهید چند عمل نوشتن روی قسمتی از حافظه را به صورت همزمان انجام دهید، در این حالت مرتبۀ قیمتی که هر پردازنده برای نوشتن داده اش می پردازد، نتیجه را تحت تأثیر قرار می دهد.
• زمانی که یک خطای سخت افزاری باعث شود تا ماشین حالت خود را به یک مسیر غیرمنتظره تغییر دهد.
هرچند به ندرت برنامه های واقعی کاملاً قطعی هستند امابرای انسان ها و دیگر برنامه ها ساده تر است که آن ها را استدلال کنند. به همین دلیل اکثر زبان های برنامه نویسی به خصوص زبان های برنامه نویسی تابعی، تلاش می کنند تا از اتفاقات بالا به جز در شرایط خارج از کنترل، جلوگیری کنند. فراگیری استفاده از پردازنده های چندهسته ای منجر به علاقه به قطعیت در برنامه نویسی موازی و چالش های غیرگرایی شد. . [ ۱] [ ۲] تعدادی از ابزارها برای کمک به مقابله با چالش ها، بن بست ها و شرایط مسابقه در بخش منابع برای مطالعهٔ بیشتر پیشنهاد شده است.
wiki: الگوریتم قطعی