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

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: