مبانی نظریه پیچیدگی محاسباتی EITC/IS/CCTF برنامه صدور گواهینامه فناوری اطلاعات اروپا در جنبه های نظری مبانی علوم کامپیوتر است که همچنین پایه ای از رمزنگاری کلید عمومی نامتقارن کلاسیک است که به طور گسترده در اینترنت استفاده می شود.
برنامه درسی مبانی نظریه پیچیدگی محاسباتی EITC/IS/CCTF دانش نظری در مورد مبانی علوم کامپیوتر و مدلهای محاسباتی بر روی مفاهیم اساسی مانند ماشینهای حالت محدود قطعی و غیر قطعی، زبانهای منظم، گرامرها و نظریه زبانها، نظریه خودکار، تورینگ را پوشش میدهد. ماشینها، قابلیت تصمیمگیری مشکلات، بازگشت، منطق و پیچیدگی الگوریتمها برای کاربردهای امنیتی اساسی در ساختار زیر، شامل محتوای آموزشی ویدیویی جامع به عنوان مرجع برای این گواهینامه EITC.
پیچیدگی محاسباتی یک الگوریتم مقدار منابع مورد نیاز برای اجرای آن است. به منابع زمان و حافظه توجه ویژه ای می شود. پیچیدگی یک مسئله به عنوان پیچیدگی بهترین الگوریتم ها برای حل آن تعریف می شود. تحلیل الگوریتمها مطالعه پیچیدگی الگوریتمهایی است که به صراحت داده شدهاند، در حالی که نظریه پیچیدگی محاسباتی مطالعه پیچیدگی راهحلهای مسائل با بهترین الگوریتمهای شناختهشده است. هر دو حوزه در هم تنیده هستند زیرا پیچیدگی الگوریتم همیشه محدودیت بالایی برای پیچیدگی مسئله ای است که آن را حل می کند. علاوه بر این، اغلب لازم است که پیچیدگی یک الگوریتم خاص را با پیچیدگی مسئله ای که باید حل شود در حین ساخت الگوریتم های کارآمد مقایسه کرد. در بیشتر شرایط، تنها اطلاعات موجود در مورد دشواری یک مشکل این است که پیچیدگی آن کمتر از کارآمدترین تکنیک های شناخته شده است. در نتیجه، همپوشانی زیادی بین تحلیل الگوریتم و نظریه پیچیدگی وجود دارد.
نظریه پیچیدگی نه تنها در مبانی مدلهای محاسباتی بهعنوان پایهای برای علوم رایانه، بلکه در مبانی رمزنگاری نامتقارن کلاسیک (به اصطلاح رمزنگاری کلید عمومی) که بهطور گسترده در شبکههای مدرن، بهویژه در اینترنت منتشر میشود، مهم است. رمزگذاری کلید عمومی مبتنی بر دشواری محاسباتی برخی از مسائل ریاضی نامتقارن است، به عنوان مثال، فاکتورسازی اعداد بزرگ در فاکتورهای اول آن (این عملیات یک مشکل سخت در طبقهبندی نظریه پیچیدگی است، زیرا الگوریتمهای کلاسیک کارآمدی برای حل وجود ندارد. آن را با مقیاس چند جمله ای منابع به جای نمایی با افزایش اندازه ورودی مسئله، که بر خلاف یک عملیات معکوس بسیار ساده از ضرب به فاکتورهای اول شناخته شده برای به دست آوردن عدد بزرگ اصلی است. با استفاده از این عدم تقارن در معماری رمزنگاری کلید عمومی (با تعریف یک رابطه نامتقارن محاسباتی بین کلید عمومی، که می تواند به راحتی از یک کلید خصوصی محاسبه شود، در حالی که کلید خصوصی نمی تواند به راحتی از یک کلید عمومی کامپیوتر شود، می توان به صورت عمومی کلید عمومی را اعلام کرده و سایر طرفهای ارتباطی را قادر میسازد تا از آن برای رمزگذاری نامتقارن دادهها استفاده کنند، که پس از آن فقط میتوان با کلید خصوصی کوپل شده رمزگشایی کرد و از نظر محاسباتی در دسترس اشخاص ثالث نیست، بنابراین ارتباط را ایمن میکند.
نظریه پیچیدگی محاسباتی عمدتاً بر روی دستاوردهای پیشگامان علم کامپیوتر و الگوریتم، مانند آلن تورینگ، که کارش برای شکستن رمز انیگما آلمان نازی، که نقش عمیقی در پیروزی متحدان در جنگ جهانی دوم داشت، حیاتی بود، توسعه یافت. تحلیل رمز با هدف ابداع و خودکارسازی فرآیندهای محاسباتی تجزیه و تحلیل داده ها (عمدتاً ارتباطات رمزگذاری شده) به منظور کشف اطلاعات پنهان برای نقض سیستم های رمزنگاری و دسترسی به محتوای ارتباطات رمزگذاری شده، معمولاً دارای اهمیت نظامی استراتژیک، مورد استفاده قرار گرفت. همچنین آنالیز رمزنگاری بود که توسعه اولین کامپیوترهای مدرن را تسریع کرد (که در ابتدا برای هدف استراتژیک شکستن کد اعمال می شد). پیش از کولوسوس بریتانیا (که به عنوان اولین کامپیوتر الکترونیکی و برنامه ای مدرن در نظر گرفته می شود) "بمب" لهستانی، یک دستگاه محاسباتی الکترونیکی که توسط ماریان رجوسکی برای کمک به شکستن رمزهای انیگما طراحی شده بود، توسط اطلاعات لهستانی به بریتانیا تحویل داده شد. دستگاه رمزگذاری آلمانی Enigma پس از تهاجم آلمان به لهستان در سال 1939. بر اساس این دستگاه آلن تورینگ همتای پیشرفته تر خود را برای شکستن موفقیت آمیز ارتباطات رمزگذاری شده آلمانی که بعداً به رایانه های مدرن تبدیل شد، توسعه داد.
از آنجایی که مقدار منابع مورد نیاز برای اجرای یک الگوریتم با اندازه ورودی متفاوت است، پیچیدگی معمولاً به صورت تابع f(n) بیان میشود، که در آن n اندازه ورودی و f(n) یا بدترین پیچیدگی است. حداکثر مقدار منابع مورد نیاز برای همه ورودیهای اندازه n) یا پیچیدگی متوسط موردی (میانگین مقدار منابع در تمام ورودیهای اندازه n). تعداد عملیات ابتدایی مورد نیاز در ورودی با اندازه n معمولاً به عنوان پیچیدگی زمانی بیان میشود، جایی که اعتقاد بر این است که عملیات ابتدایی مقدار ثابتی از زمان را در یک رایانه خاص میبرد و تنها با یک عامل ثابت زمانی که روی ماشین دیگری اجرا میشود تغییر میکند. مقدار حافظه مورد نیاز یک الگوریتم در ورودی با اندازه n به عنوان پیچیدگی فضا شناخته می شود.
زمان رایج ترین منبعی است که در نظر گرفته می شود. هنگامی که اصطلاح "پیچیدگی" بدون واجد شرایط استفاده می شود، معمولاً به پیچیدگی زمان اشاره دارد.
واحدهای سنتی زمان (ثانیه، دقیقه و غیره) در تئوری پیچیدگی به کار نمی روند، زیرا آنها بیش از حد به رایانه انتخاب شده و پیشرفت فناوری وابسته هستند. به عنوان مثال، یک کامپیوتر امروزی می تواند الگوریتمی را به طور قابل ملاحظه ای سریعتر از یک کامپیوتر دهه 1960 اجرا کند، با این حال، این به دلیل پیشرفت های تکنولوژیکی در سخت افزار کامپیوتر است تا کیفیت ذاتی الگوریتم. هدف نظریه پیچیدگی تعیین کمیت نیازهای زمانی ذاتی الگوریتم ها یا محدودیت های زمانی اساسی است که یک الگوریتم بر روی هر کامپیوتری اعمال می کند. این با شمارش تعداد عملیات اساسی انجام شده در طول محاسبه انجام می شود. این رویهها معمولاً به عنوان مراحل نامیده میشوند زیرا در نظر گرفته میشوند که زمان ثابتی روی یک ماشین خاص دارند (یعنی تحت تأثیر مقدار ورودی نیستند).
یکی دیگر از منابع مهم، میزان حافظه کامپیوتر مورد نیاز برای اجرای الگوریتم ها است.
یکی دیگر از منابعی که اغلب مورد استفاده قرار می گیرد، میزان عملیات حسابی است. در این سناریو از اصطلاح "پیچیدگی حسابی" استفاده می شود. پیچیدگی زمانی عموماً حاصل ضرب پیچیدگی حسابی توسط یک عامل ثابت است، اگر محدودیت بالایی در اندازه نمایش دودویی اعدادی که در طول محاسبه رخ میدهند شناخته شود.
اندازه اعداد صحیح مورد استفاده در طول محاسبات برای بسیاری از روشها محدود نمیشود و این غیرواقعی است که فرض کنیم عملیاتهای حسابی به زمان ثابتی نیاز دارند. در نتیجه، پیچیدگی زمانی، که به عنوان پیچیدگی بیت نیز شناخته می شود، ممکن است به طور قابل توجهی بیشتر از پیچیدگی حسابی باشد. برای مثال، دشواری محاسباتی تعیین کننده یک ماتریس عدد صحیح nn برای تکنیک های استاندارد (حذف گاوسی) O(n^3) است. از آنجایی که اندازه ضرایب ممکن است به صورت تصاعدی در طول محاسبه گسترش یابد، پیچیدگی بیت روشهای مشابه در n نمایی است. اگر این تکنیک ها همراه با محاسبات چند مدولار استفاده شوند، پیچیدگی بیت را می توان به O(n^4) کاهش داد.
پیچیدگی بیت، در اصطلاح رسمی، به تعداد عملیات روی بیت های مورد نیاز برای اجرای یک الگوریتم اشاره دارد. این معادل پیچیدگی زمانی تا یک عامل ثابت در اکثر پارادایمهای محاسباتی است. تعداد عملیات روی کلمات ماشینی مورد نیاز کامپیوترها متناسب با پیچیدگی بیت است. بنابراین برای مدلهای واقعی محاسبات، پیچیدگی زمانی و پیچیدگی بیت یکسان هستند.
منبعی که اغلب در مرتب سازی و جستجو در نظر گرفته می شود، میزان مقایسه ورودی ها است. اگر داده ها به خوبی مرتب شده باشند، این نشانگر خوبی از پیچیدگی زمانی است.
در تمام ورودی های بالقوه، شمارش تعداد مراحل در یک الگوریتم غیرممکن است. از آنجا که پیچیدگی یک ورودی با اندازه آن افزایش مییابد، معمولاً به عنوان تابعی از اندازه ورودی n (در بیت) نشان داده میشود، و بنابراین پیچیدگی تابعی از n است. با این حال، برای ورودی های هم اندازه، پیچیدگی یک الگوریتم می تواند به طور قابل توجهی متفاوت باشد. در نتیجه، انواع توابع پیچیدگی به طور معمول مورد استفاده قرار می گیرند.
پیچیدگی در بدترین حالت، مجموع تمام پیچیدگیها برای همه ورودیهای اندازه n است، در حالی که پیچیدگی حالت متوسط، مجموع تمام پیچیدگیها برای همه ورودیهای اندازه n است (این منطقی است، زیرا تعداد ورودیهای ممکن با اندازه معین برابر است. محدود، فانی). هنگامی که اصطلاح "پیچیدگی" بدون تعریف بیشتر استفاده می شود، پیچیدگی زمانی در بدترین حالت در نظر گرفته می شود.
محاسبه صحیح پیچیدگی در بدترین حالت و پیچیدگی متوسط بسیار دشوار است. علاوه بر این، این مقادیر دقیق کاربرد عملی کمی دارند زیرا هر تغییری در ماشین یا الگوی محاسباتی پیچیدگی را کمی تغییر میدهد. علاوه بر این، استفاده از منابع برای مقادیر کوچک n مهم نیست، بنابراین سهولت پیاده سازی اغلب جذاب تر از پیچیدگی کم برای n کوچک است.
به این دلایل، بیشترین توجه به رفتار پیچیدگی برای n بالا است، یعنی رفتار مجانبی آن با نزدیک شدن n به بی نهایت. در نتیجه، علامت O بزرگ معمولا برای نشان دادن پیچیدگی استفاده می شود.
مدل های محاسباتی
انتخاب یک مدل محاسباتی، که شامل مشخص کردن عملیات ضروری است که در یک واحد زمان انجام می شود، در تعیین پیچیدگی بسیار مهم است. هنگامی که الگوی محاسباتی به طور خاص توضیح داده نشده است، گاهی اوقات به عنوان ماشین تورینگ چند نواری نامیده می شود.
یک مدل قطعی محاسبات مدلی است که در آن حالتهای بعدی ماشین و عملیاتی که باید انجام شوند کاملاً با حالت قبلی تعریف میشوند. توابع بازگشتی، حساب لامبدا و ماشین های تورینگ اولین مدل های قطعی بودند. ماشینهای با دسترسی تصادفی (همچنین به عنوان ماشینهای RAM شناخته میشوند) یک پارادایم محبوب برای شبیهسازی رایانههای دنیای واقعی هستند.
هنگامی که مدل محاسباتی تعریف نشده است، معمولاً یک ماشین تورینگ چند نواری در نظر گرفته می شود. در ماشینهای تورینگ چند نواری، پیچیدگی زمانی مانند ماشینهای RAM برای اکثر الگوریتمها است، اگرچه ممکن است توجه قابل توجهی در نحوه ذخیره دادهها در حافظه برای دستیابی به این معادل مورد نیاز باشد.
در یک مدل غیر قطعی محاسبات، مانند ماشینهای تورینگ غیر قطعی، ممکن است در برخی مراحل محاسبه، انتخابهای مختلفی انجام شود. در تئوری پیچیدگی، همه گزینه های امکان پذیر به طور همزمان در نظر گرفته می شوند و پیچیدگی زمانی غیر قطعی، مقدار زمان مورد نیاز است که بهترین انتخاب ها همیشه انجام می شود. به بیان دیگر، محاسبات به طور همزمان بر روی تعداد زیادی پردازنده (یکسان) که مورد نیاز است انجام می شود و زمان محاسبه غیر قطعی، زمانی است که اولین پردازنده برای تکمیل محاسبات صرف می کند. این توازی را می توان در محاسبات کوانتومی با استفاده از حالت های درهم تنیده روی هم در هنگام اجرای الگوریتم های کوانتومی تخصصی، مانند فاکتورسازی Shor از اعداد صحیح کوچک استفاده کرد.
حتی اگر چنین مدل محاسباتی در حال حاضر عملی نباشد، اهمیت نظری دارد، بهویژه در رابطه با مسئله P = NP، که میپرسد آیا کلاسهای پیچیدگی تولید شده با استفاده از «زمان چند جملهای» و «زمان چند جملهای غیر قطعی» بهعنوان حداقل بالا هستند یا خیر. حدود یکسان است در یک کامپیوتر قطعی، شبیه سازی یک الگوریتم NP به "زمان نمایی" نیاز دارد. اگر تکلیفی را بتوان در زمان چند جمله ای در یک سیستم غیر قطعی حل کرد، به کلاس سختی NP تعلق دارد. اگر مشکلی در NP باشد و آسانتر از هر مشکل NP دیگری نباشد، می گویند NP-complete است. مسئله کوله پشتی، مسئله فروشنده دوره گرد، و مسئله رضایت پذیری بولی، همه مسائل ترکیبی NP-complete هستند. شناخته شده ترین الگوریتم دارای پیچیدگی نمایی برای همه این مسائل است. اگر هر یک از این مسائل را بتوان در زمان چند جمله ای در یک ماشین قطعی حل کرد، آنگاه تمام مسائل NP را می توان در زمان چند جمله ای نیز حل کرد و P = NP ایجاد می شود. از سال 2017، به طور گسترده فرض میشود که P NP، به این معنی که بدترین موقعیتهای مسائل NP اساساً دشوار است، به عنوان مثال، با توجه به طولهای ورودی جالب، بسیار بیشتر از هر بازه زمانی ممکن (دهها) طول میکشد.
محاسبات موازی و توزیع شده
محاسبات موازی و توزیع شده شامل تقسیم پردازش بین چندین پردازنده است که همگی در یک زمان کار می کنند. تمایز اساسی بین مدل های مختلف، روش ارسال داده ها بین پردازنده ها است. انتقال داده بین پردازندهها معمولاً در محاسبات موازی بسیار سریع است، در حالی که انتقال داده بین پردازندهها در محاسبات توزیعشده در سراسر شبکه انجام میشود و بنابراین به طور قابلتوجهی کندتر است.
محاسبات بر روی N پردازنده حداقل ضریب N از زمانی را که روی یک پردازنده صرف می کند، می گیرد. در واقع، از آنجا که برخی از وظایف فرعی را نمی توان موازی کرد و برخی از پردازنده ها ممکن است نیاز داشته باشند تا برای نتیجه از پردازنده دیگری منتظر بمانند، این حد از لحاظ نظری ایده آل هرگز به دست نمی آید.
بنابراین مسئله پیچیدگی کلیدی توسعه الگوریتمهایی است که حاصل ضرب زمان محاسبه برحسب تعداد پردازندهها تا حد امکان به زمان مورد نیاز برای انجام همان محاسبات روی یک پردازنده نزدیک باشد.
محاسبات کوانتومی
کامپیوتر کوانتومی کامپیوتری با مدل محاسباتی مبتنی بر مکانیک کوانتومی است. تز چرچ-تورینگ برای کامپیوترهای کوانتومی صادق است، به این معنی که هر مشکلی که یک کامپیوتر کوانتومی بتواند حل کند ممکن است توسط ماشین تورینگ نیز حل شود. با این حال، برخی از کارها ممکن است از نظر تئوری با استفاده از یک کامپیوتر کوانتومی به جای یک کامپیوتر کلاسیک با پیچیدگی زمانی بسیار کمتر حل شوند. در حال حاضر، این کاملاً تئوری است، زیرا هیچ کس نمی داند چگونه یک کامپیوتر کوانتومی عملی ایجاد کند.
نظریه پیچیدگی کوانتومی برای بررسی انواع مختلفی از مسائلی که توسط کامپیوترهای کوانتومی قابل حل هستند ایجاد شد. این در رمزنگاری پس کوانتومی، که فرآیند ایجاد پروتکلهای رمزنگاری است که در برابر حملات کامپیوتری کوانتومی مقاوم هستند، استفاده میشود.
پیچیدگی مسئله (مرزهای پایین تر)
تعداد کمی از پیچیدگی های الگوریتم هایی که ممکن است مشکل را حل کنند، از جمله تکنیک های کشف نشده، پیچیدگی مسئله است. در نتیجه، پیچیدگی یک مسئله برابر است با پیچیدگی هر الگوریتمی که آن را حل می کند.
در نتیجه، هر پیچیدگی داده شده در نماد O بزرگ نشان دهنده پیچیدگی الگوریتم و مسئله همراه است.
از سوی دیگر، دستیابی به مرزهای پایینتر غیر ضروری در پیچیدگی موضوع اغلب دشوار است و استراتژیهای کمی برای انجام این کار وجود دارد.
برای حل اکثر مسائل، تمام داده های ورودی باید خوانده شوند، که متناسب با بزرگی داده ها زمان می برد. در نتیجه، چنین مسائلی حداقل دارای پیچیدگی خطی، یا در نماد امگا بزرگ، پیچیدگی Ω(n) هستند.
برخی از مسائل، مانند مسائل جبر کامپیوتری و هندسه جبری محاسباتی، راه حل های بسیار بزرگی دارند. از آنجا که خروجی باید نوشته شود، پیچیدگی با حداکثر اندازه خروجی محدود می شود.
تعداد مقایسههای مورد نیاز برای یک الگوریتم مرتبسازی دارای کران پایینی غیرخطی Ω (nlogn) است. در نتیجه، بهترین الگوریتمهای مرتبسازی کارآمدترین الگوریتمها هستند زیرا پیچیدگی آنها O(nlogn) است. این واقعیت که n وجود دارد! روش های سازماندهی n چیز به این حد پایین منجر می شود. زیرا هر مقایسه این مجموعه n را تقسیم می کند! سفارشات به دو بخش، تعداد N مقایسه مورد نیاز برای متمایز کردن همه سفارشات باید 2N > n! باشد، که به معنای O(nlogn) با فرمول استرلینگ است.
کاهش یک مشکل به مشکل دیگر یک استراتژی رایج برای به دست آوردن محدودیت های پیچیدگی کاهش یافته است.
توسعه الگوریتم
ارزیابی پیچیدگی یک الگوریتم یک عنصر مهم در فرآیند طراحی است زیرا اطلاعات مفیدی در مورد عملکردی که ممکن است مورد انتظار باشد ارائه می دهد.
این یک سوء تفاهم مکرر است که در نتیجه قانون مور، که رشد تصاعدی قدرت کامپیوتری مدرن را پیشبینی میکند، ارزیابی پیچیدگی الگوریتمها کمتر مرتبط میشود. این نادرست است زیرا افزایش قدرت امکان پردازش حجم عظیمی از داده ها (داده های بزرگ) را فراهم می کند. به عنوان مثال، هر الگوریتمی باید در کمتر از یک ثانیه به خوبی عمل کند، وقتی فهرستی از چند صد مدخل را بر اساس حروف الفبا مرتب می کند، مانند کتابشناسی یک کتاب. از سوی دیگر، برای یک میلیون ورودی (به عنوان مثال، شماره تلفن های یک شهر بزرگ)، الگوریتم های اساسی که نیاز به مقایسه O(n2) دارند باید یک تریلیون مقایسه انجام دهند که سه ساعت با سرعت 10 طول می کشد. میلیون مقایسه در ثانیه از طرف دیگر، مرتبسازی سریع و مرتبسازی ادغام فقط به مقایسه nlogn نیاز دارند (به عنوان پیچیدگی متوسط برای اولی، به عنوان پیچیدگی در بدترین حالت برای دومی). این حدود 30,000,000 مقایسه برای n = 1,000,000 ایجاد می کند که با 3 میلیون مقایسه در ثانیه فقط 10 ثانیه طول می کشد.
در نتیجه، ارزیابی پیچیدگی ممکن است امکان حذف بسیاری از الگوریتمهای ناکارآمد را قبل از اجرا فراهم کند. این همچنین می تواند برای تنظیم دقیق الگوریتم های پیچیده بدون نیاز به آزمایش همه انواع ممکن استفاده شود. مطالعه پیچیدگی اجازه می دهد تا تلاش برای افزایش کارایی یک پیاده سازی با تعیین پرهزینه ترین مراحل یک الگوریتم پیچیده متمرکز شود.
برای آشنایی کامل با برنامه درسی گواهینامه می توانید جدول زیر را گسترش داده و تجزیه و تحلیل کنید.
برنامه درسی گواهی مبانی نظریه پیچیدگی محاسباتی EITC/IS/CCTF به مواد آموزشی با دسترسی آزاد در فرم ویدیویی ارجاع می دهد. فرآیند یادگیری به یک ساختار گام به گام (برنامه ها -> درس ها -> موضوعات) تقسیم می شود که بخش های برنامه درسی مربوطه را پوشش می دهد. مشاوره نامحدود با کارشناسان حوزه نیز ارائه می شود.
برای جزئیات بیشتر در مورد روش صدور گواهینامه بررسی کنید چگونه کار می کند.
مواد خواندنی برنامه درسی حمایتی اولیه
S. Arora، B. Barak، پیچیدگی محاسباتی: یک رویکرد مدرن
https://theory.cs.princeton.edu/complexity/book.pdf
مواد خواندنی برنامه درسی حمایتی ثانویه
O. Goldreich، مقدمه ای بر نظریه پیچیدگی:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
مطالب خواندنی برنامه درسی حمایتی در مورد ریاضیات گسسته
J. Aspnes، یادداشت هایی در مورد ریاضیات گسسته:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
مطالب خواندنی برنامه درسی حمایتی در مورد نظریه گراف
آر. دیستل، نظریه گراف:
https://diestel-graph-theory.com/
دانلود کامل مطالب آماده سازی خودآموز آفلاین برای برنامه مبانی نظریه پیچیدگی محاسباتی EITC/IS/CCTF در یک فایل PDF
مواد آماده سازی EITC/IS/CCTF – نسخه استاندارد
مواد مقدماتی EITC/IS/CCTF - نسخه توسعه یافته با سوالات بررسی