آیا n اول است؟ الگوریتمی همه فهم با زمان اجرای چندجمله ای
Publish Year: 1382
نوع سند: مقاله ژورنالی
زبان: Persian
View: 56
نسخه کامل این Paper ارائه نشده است و در دسترس نمی باشد
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_MCT-22-2_002
تاریخ نمایه سازی: 29 آبان 1402
Abstract:
در دوره آموزش ابتدایی با غرابل اراتستن آشنا می شویم. متاسفانه استفاده از این روش برای تعیین اول بودن یک عدد طبیعی مستلزم زمان محاسبه ای متناسب با خود عدد است. از طرفی، طول عدد ورودی به غربال اراتستن با تعداد ارقام دودویی آن متناسب است و لذا الگوریتمی در پیش داریم که زمان اجرای نمایی دارد. به این ترتیب آیا اصلا می توان درباره اول بودن اعداد خیلی بزرگ تصمیم گرفت؟ تعبیر یاضی این پرسش در چارچوب نظریه پیچیدگی محاسبات، ارائه الگوریتمی با زمان اجرای چندجمله ای است. در این مقالهT شرحی توصیفی - تاریخی درباره حل این مساله و ارائه الگوریتم مورد بحث است.
Keywords:
Authors
روح الله جهانی پور
دانشگاه کاشان، گروه ریاضی