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

Vikipediya, azad ensiklopediya
Naviqasiyaya keç Axtarışa keç

Hesablama mürəkkəbliyi nəzəriyyəsi (ing. Computational Complexity Theory) — 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.[1] 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.[2] 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.[3]

Əsas mövzuları

[redaktə | mənbəni redaktə et]

Mürəkkəblik sinifləri

[redaktə | mənbəni redaktə et]

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

[redaktə | mənbəni redaktə et]

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əbliyin sərhədləri və Asimptotik Notasiyalar

[redaktə | mənbəni redaktə et]

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əsinin tətbiqləri

[redaktə | mənbəni redaktə et]

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]
Türinq maşını illüstrasiya

Hesablama modelleri və mürəkkəblik teoremləri

[redaktə | mənbəni redaktə et]

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]

İstinadlar

[redaktə | mənbəni redaktə et]
  1. ↑ Zobel, Justin. Writing for Computer Science. Springer. 2015. səh. 132. ISBN 978-1-44716639-9.
  2. ↑ "P vs NP Problem | Clay Mathematics Institute". www.claymath.org (ingilis). July 6, 2018 tarixində orijinalından arxivləşdirilib. İstifadə tarixi: July 6, 2018.
  3. ↑ See Arora, Barak, 2009, Chapter 1: The computational model and why it doesn't matter
  4. ↑ Berger, Bonnie A.; Leighton, T, "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete", Journal of Computational Biology, 5 (1), 1998: 27–40, CiteSeerX 10.1.1.139.5547, doi:10.1089/cmb.1998.5.27, PMID 9541869.
  5. ↑ 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)
  6. ↑ Jaffe, Arthur M., "The Millennium Grand Challenge in Mathematics" (PDF), Notices of the AMS, 53 (6), 2006, 2006-06-12 tarixində arxivləşdirilib (PDF), İstifadə tarixi: 2006-10-18.
  7. ↑ Schöning, Uwe, "Graph Isomorphism is in the Low Hierarchy", Journal of Computer and System Sciences, 37 (3), 1988: 312–323, doi:10.1016/0022-0000(88)90010-4
  8. ↑ Arvind, Vikraman; Kurur, Piyush P., "Graph isomorphism is in SPP", Information and Computation, 204 (5), 2006: 835–852, doi:10.1016/j.ic.2006.02.002.
  9. ↑ Fortnow, Lance. "Computational Complexity Blog: Factoring". weblog.fortnow.com. 2002-09-13.
  10. ↑ Wolfram MathWorld: Number Field Sieve
  11. ↑ Boaz Barak's course on Computational Complexity Lecture 2

Dərsliklər

[redaktə | mənbəni redaktə et]
Mənbə — "https://az.wikipedia.org/w/index.php?title=Hesablama_mürəkkəbliyi_nəzəriyyəsi&oldid=7828624"