Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

1.4. Riyazi induksiya ilə alqoritmlərin qurulması
Rekursiv funksiyalar nəzəriyyəsindən məlumdur ki, bir sıra cəmləri hesablayan zaman rekursiv düsturlardan başqa birbaşa düsturlardan da istfadə oluna bilir. Birbaşa düsturların əsaslandırılması riyazi induksiya üsulu ilə yerinə yetirilir[3,4]. Riyazi induksiya üsulu nəinki riyazi alqoritmlərin, həmçinin məntiqi alqoritmlərin qurulmasında da istfadə olunur. Bu üsul o zaman istfadə olunur ki, alqoritmin qurulması hansısa bir kəmiyyətin natural qiymətlər alması ilə əlaqədar olsun: n=1,2,3,…. və s.
Bəzi hallarda n kəmiyyətinin kifayət qədər böyük qiymətləri üçün müəyyən bir tezis doğru olsa da, bu tezisi ümumiyyətlə doğru hesab etmək olmaz. Tezisin doğruluğunu riyazi induksiya üsulu ilə isbat etmək lazımdır.
Məsələn: a(n)=n²-n+41 funksiyasına baxaq.

n	1	2	3	...	40
a(n)	41	43	47	...	1601

Göründüyü kimi, a(n) funksiyasının xeyli sayda başlanğıc arqumentləri üçün funksiya yalnız sadə ədədlər alsa da, belə qənaətə gəlmək olmaz ki, bu funksiya ümumiyyətlə həmişə sadə qiymətlər alır. n=41 olduqda funksiya 41-in kvadratına bərabər olur ki, bu da mürəkkəb ədəddir.

İnduksiya haqqında teorem: Tutaq ki,
1)T(n)-hər hansı bir tezisin n nöqtəsində doğru olub-olmadığını ifadə edən bul funsiyasıdır, tezis doğrudursa T(n)=1, yalandırsa T(n)=0; n=1,2,3,…;
2) N natural ədədi var ki, T(n₀)=1;
3) əgər qiymətlərində T(n)=1 olarsa T(n+1)=1.
Onda bu tezis - dan böyük bütün natural ədədlər çoxluğunda doğrudur, yəni natural ədədi üçün T(n)=1.
İsbatı: Əksini fərz edək: elə böyük k natural ədədi mövcuddur ki, T(k)=0 bərabərliyi doğrudur, yəni k nöqtəsində tezis doğru deyil. Buradan alınır ki, k-1 nöqtəsində də tezis doğru deyil: T(k-1)=0, çünki belə olmasaydı, T(k)=1 olardı. Bu qayda ilə məntiqi əlaqə zənciri qursaq, aşağıdakı nəticələri alarıq: T(k-2)=0,…,T(n₀)=0. Lakin sonuncu nəticə teoremin şərtlərinə ziddir. Deməli, fərziyyəmiz doğru deyil, yəni induksiya haqqında teorem doğrudur.
Məntiqi alqoritmlərin qurulmasında riyazi induksiya üsulundan istfadəyə aid misala baxaq[3,10,20]. Hanoy qülləsi haqqında məsələni şəkil 1.15 əsasında şərh etməyə çalışaq. Bu məsələnin qoyuluşu belədir. Hər hansı müstəviyə bərkidilmiş 3 çubuqdan birincisinə 3 fərqli disk keçirilib, belə ki, bunlar ölçülərinin azalması ardıcıllığı ilə düzülmüşdür. Məqsəd disklərin bu cür düzülüşünü 3-cü çubuqda qurmaqdan ibarətdir. Bu məqsədə çatmaq üçün hər dəfə yalnız bir diskin yerini başqa bir çubuğa köçürməklə dəyişmək olar. Bu zaman heç bir halda hər hansı diskin üstündə özündən böyük disk olmamalıdır. 2-ci çubuq məqsədə çatmaq üçün yardımçı rolunu oynayır. Hanoy qülləsi haqqında məsələnin qoyuluşunda çubuqların sayının 3-ə bərabər götürülməsi təsadüfi deyil. İş burasındadır ki, çubuqların sayı daha çox olsaydı, bu məsələnin həlli sadələşərdi və məsələyə maraq azalardı. Disklərin sayı 3-ə bərabər olduqda disklər əvəzinə 1 (kiçik disk), 2 (orta disk), 3(böyük disk) ədədlərindən istifadə etməklə məsələnin matris şəklində modelini qurub araşdırma aparmaq olar.


Şək.1.15. Üç diskdən ibarət hanoy qülləsi haqqında məsələnin qoyuluşu

1
2
3

		1
		2
		3