Hesablama Murekkebliyi Nezeriyyesi - Wikipedia - Ureyim.az

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:^[4]

1. 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.
2. NP (ing. Nondeterministic Polynomial Time): 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" (ing. travelling salesman problem) verilə bilər.^[5]
3. NP-tam (ing. NP-complete): 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.
4. 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.^[6]

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.^[7]

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ı (ing. Big O Notation) 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ə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.^[8]
• 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.^[9]

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.^[10]

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.^[11]

• Arora, Sanjeev; Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Downey, Rod; Fellows, Michael, Parameterized complexity, Monographs in Computer Science, Berlin, New York: Springer-Verlag, 1999, ISBN 9780387948836
• Du, Ding-Zhu; Ko, Ker-I, Theory of Computational Complexity, John Wiley & Sons, 2000, ISBN 978-0-471-34506-0
• Goldreich, Oded, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008
• van Leeuwen, Jan, redaktorHandbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, 1990, ISBN 978-0-444-88071-0
• Khalil, Hatem; Ulery, Dana, A review of current studies on complexity of algorithms for partial differential equations // Proceedings of the annual conference on - ACM 76, 1976, 197–201, doi:10.1145/800191.805573, ISBN 9781450374897
• Papadimitriou, Christos, Computational Complexity (1st), Addison Wesley, 1994, ISBN 978-0-201-53082-7
• Sipser, Michael, Introduction to the Theory of Computation (2nd), USA: Thomson Course Technology, 2006, ISBN 978-0-534-95097-2