Kamalov abrorbekning

Everistik algoritmlar

Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:

1. U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.
2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.
Odatda yahshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlaydigan va barcha test topshiriqlariga javob beradigan algoritmni tuzdik, lekin uning to’g’riligini isbotlab bilmaymiz. Shunday isbot berilmaguncha, algoritm evristik deb tushuniladi.
10. Har qanday matematik nazariya u yoki bu matematik jumlaning rost yoki yolg’onligini o’rganadi.
Ta’rif: Rost yoki yolg’onligi bir qiymatli aniqlangan darak gapga jumla (mulohaza) deyiladi.
Ta’rifga ko’ra “0<1”, “2*5=10”, “7 – juft son”, “1 – tub son” gaplar mulohaza bo’lib, ulardan birinchisi va ikkinchisi rost, uchinchisi va to’rtinchisi yolg’on mulohazalardir.
Mulohazalar nazariyasining boshlang’ich ob’yektlari sodda (oddiy) mulohazalardan iborat. Sodda mulohazalar lotin alifbosining katta harflari A, B, C, …. yoki kichik harflari a, b, c,.... orqali belgilanadi. Mulohazalarning rost yoki yolg’onligi ularning mazmuniga qarab aniqlanadi. Rost mulohazalarning qiymati 1, yolg’onligi mulohazalarning qiymati 0 orqali belgilanadi. Mulohaza bir vaqtning o’zida ham rost, ham yolg’on bo’la olmaydi.
Matematikada har bir teorema mulohaza hisoblanadi.
Sodda mulohazalardan bog’lovchi yoki bog’lovchi so’zlar orqali murakkab mulohazalar hosil qilinadi.
“emas”, “va”, “yoki”, “... kelib chiqadi”, “zarur va yetarli” kabi bog’lovchi so’zlarga bittadan mantiqiy amal mos keladi.
Mulohazalar ustida bajariladigan inkor, kon’yuksiya, dizyunksiya, implikatsiya, ekvivalensiya amallari mavjud.

1. Inkor amali.
Ta’rif: p mulohazaning inkori deb p rost bo’lganda yolg’on, p yolg’on bo’lganda rost bo’ladigan mulohazaga aytiladi.
Inkor amaliga “emas” bog’lovchisi mos keladi.
p mulohazaning inkorini yoki ┐p ko’rinishlarda belgilanadi. Masalan, p: “5-juft son” bo’lsa, u holda ┐p: “5-juft son emas” bo’ladi. Bu yerda p mulohaza yolg’on bo’lib, ┐p mulohaza rost bo’ladi.
p mulohazaning inkorining inkori yana p mulohazaning o’zi, ya’ni ┐(┐p)= ┐┐p= p bo’ladi. Buni ikki karrali inkor deb yuritiladi. Inkor amaliga quyidagi rostlik jadvali mos keladi: