Hisoblash modellari, algoritmlar va ularning murakkabligi Algoritm tushunchasi. Avvalo algoritm

1.2. Hisoblash modellari
Hisoblash nazariyasi va hisoblash murakkabligi nazariyasi hisoblash modelini nafaqat hisoblash uchun foydalaniladigan qabul qilinadigan
13
amallar toʻplamining ta‘rifi, balki ularni qoʻllashning nisbiy xarajatlari
sifatida ham koʻrib chiqadi. Kerakli hisoblash manbalarini - ijro etish
vaqtini, xotira hajmini, shuningdek algoritmlarning cheklanishlarini yoki
kompyuterni xarakterlash mumkin - faqat ma‘lum bir hisoblash modeli
tanlangan taqdirda.
Modelga asoslangan muhandislikda hisoblash modeli va uning
tanlovi, agar uning alohida qismlarining xatti-harakatlari ma‘lum boʻlsa,
umuman tizim qanday ishlaydi degan savolga javob beradi.
Hisoblash murakkabligining asimptotik bahosida hisoblash modeli
ma‘lum narx bilan qabul qilinadigan primitiv amallar orqali aniqlanadi.
Ma‘lum amallar toʻplamiga va ularning hisoblash murakkabligiga
qarab bir qator hisoblash modellari ma‘lum. Ular quyidagi keng
toifalarga boʻlinadi: algoritm hisoblashning murakkabligini yuqori
chegarasini olish uchun foydalaniladigan abstrakt mashinalar va
algoritmik masalalar uchun hisoblash murakkabligining pastki
chegarasini olish uchun ishlatiladigan qaror modellari.
Tyuring tezisi. Chyorch tezisi. Algoritm tushunchasini
aniqlashga yondashishlar. Algoritm tushunchasini aniqlash boʻyicha
yondashishlarni uch asosiy yoʻnalishga boʻlish mumkin.
Birinchi yoʻnalish effektiv hisoblanuvchi funksiya tushunchasini
aniqlash bilan bogʻliq. Bu yoʻnalish boʻyicha A.Chyorch, K.Gyodel,
S.Klini1 tadqiqot ishlarini olib borishgan.
1932-1935-yillar davomida A.Chyorch va S.Klini tomonidan
oʻrganilgan va ―-aniqlanuvchi funksiyalar‖ deb atalgan, toʻgʻri
aniqlangan hisoblanuvchi nazariy-sonli funksiyalar sinfining ―-
aniqlanuvchi funksiyalar‖ sinfi bizning intuitiv tasavvurimiz boʻyicha
hisoblanuvchi deb qaraladigan hamma funksiyalarni qamrab olishi
mumkin degan fikr tugʻilganligi 1935-yilda e‘lon qilindi. Bu kutilmagan
natija edi.
J.Erbranning2 bir gʻoyasi asosida 1934-yilda K.Gyodel tomonidan
aniqlangan va ―umumrekursiv funksiyalar‖ deb atalgan boshqa