Hesablama mürəkkəbliyi nəzəriyyəsi

Hesablama mürəkkəbliyi nəzəriyyəsi () — kompüter elmlərinin bir sahəsi olub, müxtəlif problemlərin həllində istifadə olunan resursların miqdarını (məsələn, vaxt və yaddaş) ölçür və təsnif edir. Bu nəzəriyyə, müxtəlif problemlərin hansı resurslar daxilində həll oluna biləcəyini və hansı problemlərin həlli üçün çox resurs tələb olunduğunu müəyyən etməyə çalışır. Hesablama mürəkkəbliyi nəzəriyyəsi həm də riyazi çətinliklərin və resurs məhdudiyyətlərinin təhlili ilə kompüterlərin həll edə biləcəyi problemlər dairəsini genişləndirir.See 

 Əsas mövzuları 
 Mürəkkəblik sinifləri 
Mürəkkəblik sinifləri müxtəlif məsələlərin həllində istifadə olunan resurs miqdarına görə təsnif olunur. Ən məşhur mürəkkəblik sinifləri aşağıdakılardır:
 P (Polinomial vaxt): Bu sinifdəki məsələlər polinomial vaxt çərçivəsində həll edilə bilər. Bu, məsələlərin həllinin praktik olduğunu göstərir. Məsələn, sıralama alqoritmlərinin çoxu P sinifinə aiddir.
 NP (): Bu sinifdəki məsələlərin həllini yoxlamaq polinomial vaxtda mümkündür, lakin həllini tapmaq eyni dərəcədə asan olmaya bilər. NP məsələlərinə nümunə olaraq "satışmen problemi" () verilə bilər.Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2007) Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Boston/San Francisco/New York (page 368)
 NP-tam (): Bu sinif NP sinifində olan və eyni zamanda bütün digər NP məsələlərini də polinomial vaxtda çözə bilən məsələləri əhatə edir. Əgər bir NP-tam məsələ P sinifinə aid edilə bilsə, onda bütün NP məsələləri də P-də həll edilə bilər.
 NP-çətin (NP-hard): NP-çətin məsələlər NP sinifinə aid olmaya bilər, lakin digər NP məsələlərindən daha az resursla həll edilə bilməz. Bu məsələlər daha genişdir və optimallaşdırma problemlərini də əhatə edir.

 P və NP Problemi 
P və NP problemi, mürəkkəblik nəzəriyyəsinin ən mühüm açıq suallarından biridir. Problem, P sinifində olan məsələlərin NP sinifində olan bütün məsələlərə bərabər olub-olmadığını öyrənməyə çalışır. Başqa sözlə, "Hər polinomial vaxtda yoxlanıla bilən məsələ polinomial vaxtda həll oluna bilərmi?" sualı ilə bağlıdır. Bu suala cavab verilərsə, hesablama nəzəriyyəsində böyük bir irəliləyiş olar.

 Mürəkkəbliyin sərhədləri və Asimptotik Notasiyalar 
Mürəkkəblik nəzəriyyəsində problemlərin resurs tələbatını dəyərləndirmək üçün O-Böyük Notasiyası () və digər asimptotik notasiya üsulları istifadə edilir. Bu, məsələlərin həllində tələb olunan vaxt və yaddaşın nisbətini təsvir edir və alqoritmin "sürətini" ifadə edir.

Məsələn:
O(n): Həll üçün tələb olunan resursların miqdarı giriş məlumatlarının sayı ilə xətti əlaqədədir.
O(n^2): Tələb olunan resurslar giriş məlumatlarının kvadratı ilə əlaqədədir.

 Mürəkkəblik nəzəriyyəsinin tətbiqləri  
Mürəkkəblik nəzəriyyəsi praktiki olaraq bir çox sahədə əhəmiyyətlidir:
Kriptoqrafiya: Çətin həlli olan NP məsələləri (məsələn, böyük ədədlərin sadə ədədlərə bölünməsi) kriptoqrafiya sistemlərinin etibarlılığı üçün əsas yaradır.
Optimizasiya: NP-çətin məsələlər, böyük həcmli verilənləri analiz edərkən effektiv həll yolları tapmağa kömək edir.
Maşın öyrənmə və süni intellekt: Maşın öyrənmə modellərinin mürəkkəbliyini təhlil etməyə imkan verir və bu modellərin təlimində istifadə olunan resursları optimallaşdırır.
 Hesablama modelleri və mürəkkəblik teoremləri  
Hesablama nəzəriyyəsi müxtəlif modellərlə təchiz edilmişdir və bu modellərdə resurs tələbləri və onların effektivliyi arasında əlaqələr tədqiq edilir. Türinq maşını hesablama modellərinin ən geniş istifadə olunanıdır və mürəkkəblik siniflərini də onun əsasında müəyyənləşdirir.Wolfram MathWorld: Number Field Sieve 

Mürəkkəblik nəzəriyyəsi kompüter elmlərinin nəzəri əsasını təşkil edir və bu nəzəriyyə ilə alqoritmlərin daha da effektiv şəkildə inkişaf etdirilməsi, məsələlərin həllində lazım olan resursların optimallaşdırılması üçün geniş imkanlar yaradır.Boaz Barak's course on Computational Complexity  Lecture 2 

 İstinadlar 

 Dərsliklər 









Kateqoriya:Hesablama tədqiqat sahələri