Hesablama nəzəriyyəsi

Hesablama nəzəriyyəsi () — 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. (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 ).) 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.

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

 Əsas bölmələri 
 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.  
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ı.
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.
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.  
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.
Alqoritm və mürəkkəblik sinifləri  
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.

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.

 İstinadlar 

 Ədəbiyyat 
 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






  Reprinted in .

 Xarici keçidlər 

 Association for Symbolic Logic homepage
 Computability in Europe homepage 
 Webpage on Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes
 German language lecture notes on inductive inference

Kateqoriya:İnformatika