Tayanch iboralar

Algoritmning determinatsiyalanuvchanligi (aniqlanuvchanligi). Boshlang‘ich holat-dan farq qiluvchi boshqa holatda aniqlangan miqdorlar sistemasi ilgarigi holatlarda hosil qilingan miqdorlar sistemasi orqali bir qiymatli aniqlanadi.

Algoritm qadamlarining elementarligi. Ilgarigi miqdorlar sistemasidan keyingisini hosil qilish qonuni sodda qadamlardan iborat bo‘lishi kerak.

Algoritmning ommaviyligi. Boshlang‘ich miqdorlar sistemasini ayrim potensial cheksiz to‘plamdan tanlash mumkin.

Algoritmning natijaviyligi. Miqdorlarni topish jarayoni chekli bo‘lishi va natijani (masalaning yechimini) berishi kerak.

Matematik amallar asosiy rolni o‘ynaydigan algoritmlar sonli algoritmlar deb yuritiladi. Bundan tashqari, mantiqiy algoritmlar ham mavjud. Mantiqiy algoritmlardan biri quyidagi misoldagi o‘yinda ifodalangan.

2- misol. Ikki kishi (boshlovchi va uning raqibi) ishtirok etayotgan o‘yinda har bir o‘yinchi navbat bilan 15ta predmetdan yo bitta, yo ikkita, yoki uchta predmetni oladi. Kim oxirgi predmetni olsa, o‘sha kishi o‘yinda g‘olib hisoblanadi. Boshlovchi o‘yinda g‘alaba qozonishi uchun bu o‘yinda qanday strategiyani qo‘llash kerakligini aniqlaymiz. Boshlovchiga bu o‘yinda yutuq ta’minlaydigan strategiyani mantiqiy algoritm sifatida 1- jadval shaklida ifodalash mumkin.

Haqiqatan ham, boshlovchi bunday strategiya natijasida 3+(4-n)+(4-p)=15-(n+m+p) predmet, raqib esa n+m+p predmet oladi, ya’ni ikkalasi birgalikda 15ta predmet olishadi. Oxirgi predmetni albatta boshlovchi olganligi tufayli, u o‘yinda yutuqqa erishadi.

Rekursiv va rekursiv sanaluvchi to‘plamlar

Biror alfavit berilgan bo‘lsin. Bu alfavitdagi hamma so‘zlar to‘plamini S bilan va S to‘plamning qism to‘plamini M bilan belgilaymiz.

1-ta’rif. Agar x so‘zning M to‘plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo‘lsa, u holda M rekursiv to‘plam deb ataladi.

2- ta’rif. Agar M to‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo‘lsa, u holda M effektiv rekursiv sanaluvchi to‘plam deb ataladi.