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 –
