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:
1) Algoritmlarning klassik nazariyasi
(rasmiy tillar nuqtai
nazaridan
masalalarni
shakllantirish,
yechuvchanlik
muammosi
tushunchasi, murakkablik sinflarini kiritish, P = NP (?) masalasini
shakllantirish, NP-ning toʻliq masalalarini sinfi va uni oʻrganish);
2) Algoritmlarni asimptotik tahlil qilish nazariyasi
(algoritmning
murakkabligi
tushunchasi,
algoritmlarni
baholash
kriteriyalari,
asimptotik baholarni olish usullari, xususan, rekursiv algoritmlar uchun,
murakkablikni yoki bajarilish vaqtini asimptotik tahlil qilish);
3)
