Hesablama nəzəriyyəsi

Hesablama nəzəriyyəsi (ing. Computational Theory) — riyaziyyat və kompüter elmlərinin bir sahəsidir və hesablama anlayışının əsaslarını, hesablama cihazlarının (məsələn, Türinq maşınları) nəzəri modelini, hesablama prosesinin gücünü və məhdudiyyətlərini öyrənir.[1] Bu nəzəriyyə, hansı problemlərin həll oluna biləcəyini və hansıların mümkün olmadığını müəyyən edir və hesablama mürəkkəbliyi kimi mövzuları əhatə edir.[2]

Hesablama nəzəriyyəsinin əsas bölmələri mövcuddur.[3]

Əsas bölmələri

[redaktə | mənbəni redaktə et]
  1. Formal dillər və avtomatlar nəzəriyyəsi
    • Formal dillər, riyazi olaraq dilin sintaksisini və semantikasını müəyyən edən nəzəri modelləri araşdırır. Bu sahə, dilin hansı qaydalara əsasən formalaşdığını təhlil edir.[4]
    • Avtomatlar nəzəriyyəsi isə sadə hesablama modellərindən başlayaraq, daha mürəkkəb modellər yaratmağa imkan verən avtomatları tədqiq edir. Məsələn, sonlu avtomatlar, yığın avtomatları və Türinq maşınları.
  2. Türinq maşınları və hesablana bilmə nəzəriyyəsi
    • Alan Türinqin təklif etdiyi Türinq maşını, hesablama nəzəriyyəsində universal hesablama modelidir. Bu model hesablana bilən funksiyaları müəyyən edir və bir məsələnin həll oluna bilib-bilməyəcəyini təhlil edir.
  3. Hesablama mürəkkəbliyi nəzəriyyəsi
    • Bu nəzəriyyə hansı problemlərin nə dərəcədə resurslarla (vaxt və yaddaş) həll olunacağını müəyyənləşdirir.[5]
    • Məsələn, P (polinomial vaxtda həll olunan məsələlər) və NP (teyidi polinomial vaxtda edilə bilən məsələlər) sinifləri arasındakı fərqi öyrənir. NP-həlli çətin və ya həlli mümkün olmayan məsələlər də bu sahəyə daxildir.
  4. Alqoritm və mürəkkəblik sinifləri [6]
    • Hesablama nəzəriyyəsində mürəkkəblik sinifləri (məsələn, P, NP, NP-tam, NP-mürəkkəb və s.) müxtəlif problemlərin həll mürəkkəbliyinə görə təsnif olunur.[7]

Hesablama nəzəriyyəsi kompüter elmlərinin nəzəri əsaslarını təşkil edir və real həyatda alqoritmlərin, kriptoqrafiyanın və maşın öyrənmənin inkişafında mühüm rol oynayır.

  1. Gödel, Kurt. [Gödel (1946)] // Feferman, Solomon; və b. (redaktorlar ). Kurt Gödel Publications 1938–1974 Volume II. II. New York, USA: Oxford University Press. 1990. 144ff. ISBN 978-0-19-514721-6. To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function f is called computable in S if there is in S a computable term representing f. (NB. This volume also includes the 1946 paper by Kurt Gödel (with commentary by Charles Parsons at pp. 144ff.). This 1990 edition has the cited footnote added by Gödel on p. 150 (which had also been added to Gödel's reprint in Şablon:Citeref).)
  2. Soare, Robert Irving. "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. 2011-12-22. 2022-06-30 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2017-08-23.
  3. Friedman, Harvey. "Renaming recursion theory". FOM email list. 1998-08-28. 2022-03-01 tarixində arxivləşdirilib. İstifadə tarixi: 2006-01-09.
  4. Radó, Tibor. "On non-computable functions". Bell System Technical Journal. 41 (3). May 1962: 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.
  5. Kleene, Stephen Cole. Introduction to Metamathematics. North-Holland. 1952. 300, 376. ISBN 0-7204-2103-9.
  6. Simpson, Stephen George. "What is computability theory?". FOM email list. 1998-08-24. 2021-12-18 tarixində arxivləşdirilib. İstifadə tarixi: 2006-01-09.
  7. Fortnow, Lance Jeremy. "Is it Recursive, Computable or Decidable?". 2004-02-15. 2022-08-07 tarixində arxivləşdirilib. İstifadə tarixi: 2018-03-22.
Bakalavr səviyyəli mətnlər
Təkmilləşdirilmiş mətnlər
Sorğu sənədləri və kolleksiyalar
Tədqiqat sənədləri və kolleksiyalar

Xarici keçidlər

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