EITC/IS/CCTF د کمپیوټري پیچلتیا تیوري اساسات د کمپیوټر ساینس د بنسټونو نظري اړخونو په اړه د اروپا د معلوماتي ټیکنالوژۍ تصدیق برنامه ده کوم چې د کلاسیک غیر متناسب عامه کلیدي کریپټوګرافي اساس هم دی چې په پراخه کچه په انټرنیټ کې کارول کیږي.
د EITC/IS/CCTF د کمپیوټري پیچلتیا تیوري اساساتو نصاب د کمپیوټر ساینس او کمپیوټري ماډلونو په اساساتو باندې تیوريکي پوهه پوښي چې د اساسی مفاهیمو لکه تعییناتي او غیر متمرکز محدود دولتي ماشینونه، منظمې ژبې، د شرایطو وړیا ګرامر او د ژبې تیوري، اتومات تیوري، تورینګ. ماشینونه، د ستونزو پریکړه کول، تکرار، منطق او د الګوریتمیک پیچلتیا په لاندې جوړښت کې د بنسټیزو امنیتي غوښتنلیکونو لپاره، د دې EITC تصدیق لپاره د یوې مرجع په توګه د جامع ویډیو ډیډاکټیک مینځپانګې شامل دي.
د الګوریتم کمپیوټري پیچلتیا د دې کار کولو لپاره د اړتیا وړ سرچینو مقدار دی. د وخت او حافظې سرچینو ته ځانګړې پاملرنه کیږي. د ستونزې پیچلتیا د حل کولو لپاره د غوره الګوریتم پیچلتیا په توګه تعریف شوې. د الګوریتم تحلیل په واضح ډول د الګوریتمونو د پیچلتیا مطالعه ده، پداسې حال کې چې د کمپیوټري پیچلتیا تیوري د غوره پیژندل شوي الګوریتمونو سره د ستونزو حل کولو پیچلتیا مطالعه ده. دواړه ډومینونه یو له بل سره تړلي دي ځکه چې د الګوریتم پیچلتیا تل د ستونزې په پیچلتیا کې لوړ خنډ دی چې دا حل کوي. سربیره پردې، دا په مکرر ډول اړینه ده چې د یو ځانګړي الګوریتم پیچلتیا د ستونزې پیچلتیا سره پرتله کړئ کله چې د اغیزمن الګوریتم رامینځته کولو پرمهال حل شي. په ډیری حاالتو کې، د ستونزې د ستونزې په اړه یوازینی معلومات شتون لري چې دا د خورا اغیزمن پیژندل شوي تخنیکونو پیچلتیا څخه کم دي. د پایلې په توګه، د الګوریتم تحلیل او پیچلتیا تیورۍ تر منځ خورا ډیر تکرار شتون لري.
د پیچلتیا تیوري نه یوازې د کمپیوټر ساینس د اساس په توګه د کمپیوټري ماډلونو بنسټونو کې مهم رول لوبوي بلکې د کلاسیک غیر متناسب کریپټوګرافي (د عامه کلیدي کریپټوګرافي په نوم یادیږي) چې په عصري شبکو کې په پراخه کچه خپریږي ، په ځانګړي توګه په انټرنیټ کې. د عامه کلیدي کوډ کول د ځینې غیر متناسب ریاضيکي ستونزو د کمپیوټري مشکل پراساس دي لکه د مثال په توګه د لوی شمیر فکتورونو په اصلي فکتورونو کې (دا عملیات د پیچلتیا تیوري طبقه بندي کې یوه سخته ستونزه ده، ځکه چې د حل کولو لپاره اغیزمن کلاسیک الګوریتمونه ندي پیژندل شوي. دا د سرچینې اندازه کولو سره په پولی نومیالي توګه د ستونزې د اندازې د اندازې د زیاتوالي پر ځای په چټکۍ سره، کوم چې د اصلي لوی شمیر د ورکولو لپاره پیژندل شوي اصلي فکتورونو ته د ضرب کولو خورا ساده ریورس عملیات سره مخالف دی). د عامه کیلي کریپټوګرافي په جوړښت کې د دې غیر متناسب کارول (د عامه کیلي ترمینځ د کمپیوټري غیر متناسب اړیکې په ټاکلو سره ، دا په اسانۍ سره د شخصي کیلي څخه محاسبه کیدی شي ، پداسې حال کې چې خصوصي کیلي په اسانۍ سره د عامه کیلي څخه کمپیوټر نشي کیدی ، یو څوک کولی شي په عامه توګه عامه کیلي اعلان کړئ او د مخابراتو نورو اړخونو ته وړتیا ورکړئ چې دا د ډیټا غیر متناسب کوډ کولو لپاره وکاروي ، کوم چې بیا یوازې د جوړه شوي خصوصي کیلي سره ډیکرپټ کیدی شي ، په کمپیوټري ډول دریمې ډلې ته شتون نلري ، پدې توګه اړیکه خوندي کوي).
د کمپیوټري پیچلتیا تیوري په عمده توګه د کمپیوټر ساینس او د الګوریتمیک مخکښانو په لاسته راوړنو کې رامینځته شوې، لکه الان تورینګ، چې کار یې د نازي آلمان د اینګما سیفر ماتولو لپاره مهم و، کوم چې د دویمې نړیوالې جګړې په ګټلو کې د متحدینو په برخه کې ژور رول لوبولی و. د پټو معلوماتو د افشا کولو لپاره د کریپټوګرافیک سیسټمونو سرغړونې او د کوډ شوي اړیکو مینځپانګې ته لاسرسی ترلاسه کولو لپاره د کریپټوګرافیکي تحلیلونو هدف د ډیټا تحلیل کولو کمپیوټري پروسې رامینځته کول او اتومات کول دي (په عمده ډول کوډ شوي ارتباط) ، معمولا د ستراتیژیک نظامي اهمیت څخه. دا د کریپټو تحلیل هم و چې د لومړي عصري کمپیوټرونو پراختیا یې کتله (کوم چې په پیل کې د کوډ ماتولو ستراتیژیک هدف لپاره پلي شوي وو). د برتانیې کولسوس (د لومړي عصري بریښنایی او پروګرام کمپیوټر په توګه ګڼل کیږي) مخکې د پولنډ "بم" لخوا جوړ شوی و، یو بریښنایی کمپیوټري وسیله چې د ماریان ریجیوسکي لخوا ډیزاین شوې ترڅو د اینګما سیفرونو ماتولو کې مرسته وکړي، او د پولنډ استخباراتو لخوا لوی بریتانیا ته وسپارل شو. په ۱۹۳۹ کال کې د جرمني له خوا د پولنډ تر یرغل وروسته نیول شوی د آلمان د اینیګما د کوډ کولو ماشین نیول شوی دی. د دې وسیلې پر بنسټ الان تورینګ خپل ډیر پرمختللی سیال جوړ کړ چې په بریالیتوب سره د آلمان کوډ شوي ارتباطات مات کړي، چې وروسته په عصري کمپیوټرونو کې جوړ شو.
ځکه چې د الګوریتم چلولو لپاره د سرچینو مقدار د ان پټ د اندازې سره توپیر لري، پیچلتیا معمولا د فنکشن 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 ماشینونو په څیر ورته ده ، سره له دې چې د دې انډول ترلاسه کولو لپاره په حافظه کې ډیټا څنګه ذخیره کیږي د پام وړ پاملرنې ته اړتیا وي.
د کمپیوټینګ په غیر متمرکز ماډل کې د محاسبې په ځینو مرحلو کې مختلف انتخابونه کیدی شي ، لکه د غیر متمرکز ټورینګ ماشینونه. د پیچلتیا په تیوري کې، ټول ممکنه اختیارونه په ورته وخت کې په پام کې نیول کیږي، او د غیر متمرکز وخت پیچلتیا هغه وخت ته اړتیا لري کله چې غوره انتخابونه تل ترسره کیږي. د دې لپاره چې په بل ډول یې واچوئ ، محاسبه په ورته وخت کې په ورته ډول ډیری ( ورته) پروسیسرونو باندې ترسره کیږي لکه څنګه چې اړتیا وي ، او د غیر ټاکلي محاسبې وخت هغه وخت دی چې د لومړي پروسیسر لخوا د محاسبې بشپړولو لپاره اخیستل کیږي. دا موازي په کوانټم کمپیوټینګ کې د سپرپوز شوي انټینګل حالتونو په کارولو سره کارول کیدی شي کله چې ځانګړي کوانټم الګوریتمونه چلوي ، لکه د مثال په توګه د شور د کوچني انټیجرونو فکتور کول.
حتی که د محاسبې دا ډول ماډل اوس مهال د عملي کیدو وړ نه وي، دا نظري اهمیت لري، په ځانګړې توګه د P = NP ستونزې سره تړاو لري، کوم چې پوښتنه کوي چې آیا د پیچلتیا ټولګي د "پولینومیال وخت" او "غیر ټاکلي پولی نومي وخت" په کارولو سره تولید شوي. حدود یو شان دي. په یو تعییناتي کمپیوټر کې، د NP-الګوریتم انډول کول "قطعي وخت" ته اړتیا لري. که چیرې یو کار په غیر متقابل سیسټم کې په پولینومیل وخت کې حل شي ، دا د NP مشکل طبقې پورې اړه لري. که یوه مسله په NP کې وي او د کومې بلې NP ستونزې څخه اسانه نه وي ، نو دا NP بشپړ ویل کیږي. د Knapsack ستونزه، د سفر پلورونکي ستونزه، او د بولین د رضایت ستونزه ټول د NP - بشپړ ترکیبي ستونزې دي. تر ټولو مشهور الګوریتم د دې ټولو ستونزو لپاره د پام وړ پیچلتیا لري. که چیرې د دې مسلو څخه کوم یو په ټاکلي ماشین کې په پولینومیل وخت کې حل شي، نو د NP ټولې ستونزې په پولینومیل وخت کې هم حل کیدی شي، او P = NP به تاسیس شي. تر 2017 پورې، دا په پراخه کچه انګیرل کیږي چې P NP، د دې معنی لري چې د NP ستونزې خورا خراب حالتونه په بنسټیز ډول حل کول ستونزمن دي، د بیلګې په توګه، د هرې ممکنه مودې (لسیزو) څخه ډیر وخت نیسي چې په زړه پورې معلوماتي اوږدوالی لري.
موازي او توزیع شوي کمپیوټري
موازي او توزیع شوي کمپیوټري په ډیری پروسیسرونو کې د پروسس ویشل شامل دي چې ټول په ورته وخت کې کار کوي. د مختلفو موډلونو ترمنځ بنسټیز توپیر د پروسیسرونو ترمنځ د معلوماتو لیږلو طریقه ده. د پروسیسرونو ترمنځ د ډیټا لیږد معمولا په موازي کمپیوټري کې خورا ګړندی وي ، پداسې حال کې چې په توزیع شوي کمپیوټر کې د پروسیسرونو ترمینځ د ډیټا لیږد په شبکه کې ترسره کیږي او پدې توګه د پام وړ ورو وي.
د N پروسیسرونو محاسبه لږترلږه د N لخوا د هغه وخت برخه اخلي چې دا یو واحد پروسیسر اخلي. په واقعیت کې، ځکه چې ځینې فرعي ټاسکونه موازي نه شي کیدی او ځینې پروسیسرونه ممکن د بل پروسیسر څخه پایلې ته انتظار ته اړتیا ولري، دا په نظرياتي توګه مثالی حد به هیڅکله ترلاسه نشي.
د پیچلتیا کلیدي مسله پدې توګه د الګوریتم رامینځته کول دي ترڅو د پروسیسرونو شمیر لخوا د کمپیوټري وخت محصول د امکان تر حده نږدې وي چې په یو واحد پروسیسر کې ورته محاسبه ترسره کولو لپاره اړین وي.
د کوانټم محاسبه
کوانټم کمپیوټر یو کمپیوټر دی چې د کوانټم میخانیک پر بنسټ د محاسبې ماډل لري. د کلیسا – ټورینګ مقاله د کوانټم کمپیوټرونو لپاره ریښتیا ده ، پدې معنی چې هره مسله چې د کوانټم کمپیوټر حل کولی شي د تورینګ ماشین لخوا هم حل کیدی شي. په هرصورت، ځینې دندې ممکن په تیوریکي توګه د کلاسیک کمپیوټر په ځای د کوانټم کمپیوټر په کارولو سره حل شي چې د پام وړ ټیټ لنډمهاله پیچلتیا سره. د اوس لپاره، دا په کلکه نظري ده، ځکه چې هیڅوک نه پوهیږي چې څنګه د عملي کوانټم کمپیوټر رامینځته کړي.
د کوانټم پیچلتیا تیوري د مختلف ډوله مسلو څیړلو لپاره رامینځته شوې چې د کوانټم کمپیوټرونو لخوا حل کیدی شي. دا د پوسټ کوانټم کریپټوګرافي کې کارول کیږي ، کوم چې د کریپټوګرافیک پروتوکولونو رامینځته کولو پروسه ده چې د کوانټم کمپیوټر بریدونو پروړاندې مقاومت لري.
د ستونزې پیچلتیا (ټیټ حدود)
د الګوریتمونو پیچلتیاوې چې ممکن ستونزه حل کړي، په شمول د ناڅرګند تخنیکونو په شمول، د ستونزې پیچلتیا ده. د پایلې په توګه، د ستونزې پیچلتیا د هر الګوریتم پیچلتیا سره مساوي ده چې دا حل کوي.
د پایلې په توګه، هر ډول پیچلتیا چې په لوی O نوټیشن کې ورکړل شوي د الګوریتم او ورسره تړلې ستونزې دواړه پیچلتیا څرګندوي.
له بلې خوا، د مسلې په پیچلتیا کې د غیر معمولي ټیټ حدونو ترلاسه کول ډیری وختونه ستونزمن وي، او د دې کولو لپاره لږې ستراتیژۍ شتون لري.
د ډیری مسلو د حل کولو لپاره، ټول داخل شوي معلومات باید ولوستل شي، کوم چې د معلوماتو شدت سره متناسب وخت نیسي. د پایلې په توګه، دا ډول ستونزې لږترلږه خطي پیچلتیا لري، یا په لوی اومیګا نوټیشن کې، د Ω (n) پیچلتیا.
ځینې ستونزې، لکه د کمپیوټر الجبرا او کمپیوټري الجبریک جیومیټري کې، خورا لوی حلونه لري. ځکه چې محصول باید لیکل شي، پیچلتیا د محصول اعظمي اندازې لخوا محدوده ده.
د ترتیب کولو الګوریتم لپاره اړین پرتله کولو شمیره د Ω (nlogn) غیر خطي ټیټ حد لري. د پایلې په توګه، د غوره ترتیب کولو الګوریتم خورا اغیزمن دي ځکه چې د دوی پیچلتیا O (nlogn) ده. حقیقت دا دی چې ن شتون لري! د شیانو د تنظیم کولو لارې د دې ټیټ حد ته رسوي. ځکه چې هر پرتله کول د n دا ټولګه تقسیموي! امرونه په دوه برخو ویشئ، د ټولو امرونو د توپیر لپاره د N پرتله کولو شمیر باید 2N > n! وي، د سټرلینګ فارمول لخوا د O(nlogn) معنی لري.
د یوې ستونزې بلې ستونزې ته کمول د پیچلتیا کمولو محدودیتونو ترلاسه کولو لپاره یوه عامه تګلاره ده.
د الګوریتم پراختیا
د الګوریتم پیچلتیا ارزونه د ډیزاین پروسې یو مهم عنصر دی ځکه چې دا د هغه فعالیت په اړه ګټور معلومات چمتو کوي چې تمه کیدی شي.
دا یو پرله پسې غلط فهمۍ دی چې د مور د قانون په پایله کې، کوم چې د عصري کمپیوټر ځواک د پراخې ودې وړاندوینه کوي، د الګوریتم پیچلتیا ارزونه به لږ اړونده شي. دا غلط دی ځکه چې د بریښنا زیاتوالی د ډیرو ډیټا (لوی ډاټا) پروسس کولو ته اجازه ورکوي. د مثال په توګه، هر الګوریتم باید د یوې ثانیې څخه لږ وخت کې ښه کار وکړي کله چې د الفبا په ترتیب سره د څو سلګونو ننوتلو لیست ترتیب کړي، لکه د کتاب کتابتون. له بلې خوا، د یو ملیون ننوتلو لپاره (د مثال په توګه، د لوی ښار د تلیفون شمیرې)، لومړني الګوریتمونه چې د O(n2) پرتله کولو ته اړتیا لري باید یو ټریلیون پرتله کړي، چې د 10 په سرعت کې به درې ساعته وخت ونیسي. په هره ثانیه کې ملیونونه پرتله کول. Quicksort او ضم کولو ترتیب، له بلې خوا، یوازې د nlogn پرتله کولو ته اړتیا لري (د پخوانیو لپاره د اوسط قضیې پیچلتیا په توګه، د وروستي لپاره د بدترین قضیې پیچلتیا په توګه). دا د n = 30,000,000 لپاره شاوخوا 1,000,000 پرتله کوي، کوم چې په هره ثانیه کې د 3 ملیون پرتله کولو لپاره یوازې 10 ثانیې وخت نیسي.
د پایلې په توګه، د پیچلتیا ارزونه ممکن د پلي کولو دمخه د ډیری غیر موثر الګوریتمونو له مینځه وړو لپاره اجازه ورکړي. دا د پیچلو الګوریتمونو ښه کولو لپاره هم کارول کیدی شي پرته لدې چې ټول احتمالي ډولونه ازموي. د پیچلتیا مطالعه اجازه ورکوي چې د پیچلي الګوریتم خورا قیمتي مرحلو په ټاکلو سره د پلي کولو موثریت زیاتولو لپاره هڅې تمرکز وکړي.
د تصدیق کولو نصاب سره په تفصیل سره د ځان پیژندلو لپاره تاسو کولی شئ لاندې جدول پراخه او تحلیل کړئ.
د EITC/IS/CCTF د کمپیوټري پیچلتیا تیوري بنسټیز تصدیق نصاب په ویډیو کې د خلاص لاسرسي درسي موادو ته اشاره کوي. د زده کړې پروسه په مرحله وار جوړښت ویشل شوې ده (پروګرامونه -> درسونه -> موضوعات) چې د نصاب اړوند برخې پوښي. د ډومین متخصصینو سره لامحدود مشوره هم چمتو کیږي.
د تصدیق پروسې په اړه د جزیاتو لپاره چیک کړئ څنګه کار کوي.
د لومړني ملاتړي نصاب لوستلو توکي
ایس ارورا، بی بارک، کمپیوټری پیچلتیا: یو عصري طریقه
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 فایل کې ډاونلوډ کړئ