8
1-§. Kirish. Hisoblash modellari, algoritmlar va ularning
murakkabligi
Algoritm tushunchasi. Avvalo
algoritm tushunchasi IX asrda
yashab ijod etgan buyuk bobokalonimiz Muhammad al-Xorazmiy nomi
bilan uzviy bogʻliqligini tushuntirish lozim.
Algoritm soʻzi al-
Xorazmiyning arifmetikaga bagʻishlangan asarining
dastlabki betidagi
“Dixit Algoritmi” (“dediki al-Xorazmiy” ning lotincha ifodasi) degan
jumlalardan kelib chiqqan. Shundan soʻng al-Xorazmiyning sanoq
sistemasini takomillashtirishga qoʻshgan hissasi, uning asarlari algoritm
tushunchasining kiritilishiga sabab boʻlganligi ta‘kidlab oʻtiladi.
Algoritm nima degan savolga, u asosiy
tushuncha sifatida qabul
qilinganligidan, uning faqat tavsifi beriladi, ya‘ni biror maqsadga
erishishga
yoki
qandaydir
masalani
yechishga
qaratilgan
koʻrsatmalarning (buyruqlarning) aniq,
tushunarli, chekli hamda toʻliq
tizimi tushuniladi.
Algoritm tushunchasi aniq shaklda 20-asr boshlarida D. Gilbert, K.
Gyodel, S. Klin, A. Chyorch, E. Post, A. Tyuring, N. Viner, A. A.
Markov singari olimlarning asarlari tufayli shakllandi.
Eng qadimiy raqamli algoritmlardan biri Yevklid algoritmi
(miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta
umumiy boʻluvchisini topish. Algoritmlarning
zamonaviy nazariyasi
nemis matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular
oʻzlarining rasmiy, izchil aksiomalar tizimi doirasida yechib
boʻlmaydigan muammolar mavjudligini koʻrsatdi.
Algoritmlar nazariyasi boʻyicha birinchi fundamental ishlar 1936-
yilda paydo boʻlgan. Tyuring mashinasi, Post va Chyorch tomonidan
-
hisobi taklif etiladi. Ushbu mashinalar algoritmning formallashtirilgan
rasmiylashtirilishi edi.
Algoritmni bajarayotgan kishi – ijrochi,
asosiy algoritmni
aniqlashtiruvchi algoritm –
yordamchi algoritm ekanligini ham
ta‘kidlab oʻtish joiz. Umuman, algoritmning
qanday maqsadga
moʻljallanganligidan qat‘i nazar uni muvaffaqiyat bilan bajarish
mumkinligini aytib oʻtish lozimdir.
9
Algoritmning bir nechta ta‘rifi mavjud. Ulardan ayrimlarini keltirib
oʻtamiz:
– ―
Algoritm - bu belgilaydigan cheklangan qoidalar toʻplami,
muayyan vazifalar toʻplamini hal qilish boʻyicha amallar ketma-ketligi
va beshta muhim xossaga ega: aniqlik, tushunarlilik,
kiritish, chiqarish,
samaradorlik‖. (D. E. Knut).
– ―
Algoritm - bu qat‘iy belgilangan qoidalar asosida bajariladigan
har
qanday hisoblash tizimidir, bu ma‘lum bir qator bosqichlardan
soʻng, aniq qoʻyilgan masalani hal qilishga olib keladi" (A.
Kolmogorov).
– ―
Algoritm - bu har xil boshlangʻich ma‘lumotlardan kerakli
natijaga oʻtadigan hisoblash jarayonini belgilaydigan aniq ketma-ketlik"
(A. Markov).
1950-yillarda algoritm nazariyasiga oʻz
hissalarini Kolmogorov va
Markov asarlari qoʻshgan. 1960-1970 yillarda algoritm nazariyasida
quyidagi tadqiqot yoʻnalishlari shakllandi:
