Rekursiv funksiyalar

Информация о документе

Цена	10000UZS
Размер	29.6KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	docx
Раздел	Курсовые работы
Предмет	Педагогика

Rekursiv funksiyalar

Купить

Kirish
Matematikaning muhim elementi berilgan masalani yechish algoritmining
mavjudligi yoki yo‘qligini isbotlashdir.
Bunday dalil bizga algoritmik yechim mavjudmi degan savolga aniq javob
berishga imkon beradi va shu bilan bizni agar u mavjud bo'lmasa, uni topishga bo'lgan
samarasiz urinishlardan qutqaradi.
Har qanday boshlang'ich sharoitda to'g'ri natijaga olib keladigan chekli
harakatlar ketma-ketligi bo'lmasa, muammoni algoritmik ravishda hal qilib bo'lmaydi.
Algoritm tushunchasini aniqlashda bir qancha yondashuvlar mavjud. Ulardan
biri samarali hisoblanuvchi funksiya tushunchasini oydinlashtirish bilan bog‘liq. U
matematiklar A. Cherc, K. Handel va S. Kleene tomonidan ishlab chiqilgan. Natijada,
qat'iy matematik ta'rifga ega bo'lgan qisman rekursiv funktsiyalar sinfi olingan.

1. Kurs ishining maqsad va vazifalari
Ushbu kurs ishi: masalaning algoritmik yechilmasligini aniqlash;
funksiyalarning superpozitsiyasi, rekursiv funksiyalar tushunchalari; ibtidoiy
rekursiya sxemasi; minimallashtirish operatsiyasi.
Kurs ishining maqsadi algoritmik hisoblanuvchi funksiya va rekursiv funksiya
tushunchalarini tushuntirishdan iborat.
Kurs ishining maqsadlari:
. algoritmik masala ta'rifini tushuntirish, algoritmik hal qilmaslik;
. funksiyalarning superpozitsiyasi tushunchasini ochib berish;
. funksiyalarning hisoblash imkoniyatini aniqlashda qisman rekursiv va
umumiy rekursiv funksiyalarning rolini oydinlashtirish; ibtidoiy rekursiya sxemasini
tahlil qilish.

2. Algoritmik hal qilmaslik
algoritm muammosi rekursiya superpozitsiyasi
Algoritmlarni hal qilmaslik algoritmlardan foydalanishga imkon beruvchi
yaxshi qo'yilgan masalalarning ayrim sinflarining eng muhim xususiyatidir. Gap
shundaki, ushbu sinflarning har birining muammolari, qoida tariqasida, ushbu sinfni
birlashtiradigan umumiy, universal echim algoritmiga ega emas. Shartlar va
talablarning to'liq bir xilligiga qaramasdan, bu erda, paradoksal ravishda, yechim
usulining bir xilligi printsipial jihatdan mumkin emas. A. n. Bu ma'lum bir sinfning
ayrim individual muammolarini hal qilib bo'lmaydi degani emas - ularning ba'zilari
o'zlarining echimlariga ega bo'lishi mumkin. Ammo, umuman olganda, bu sinfdagi
muammolarning umumiy universal yechim algoritmi ham, sinfni to'liq kichik
sinflarga bo'lish uchun tarmoqli algoritmi ham mavjud emas, ularning har biriga
o'ziga xos algoritm qo'llanilishi mumkin.
Algoritmik jihatdan hal qilib bo'lmaydigan muammo, masalan, tanib olish
muammosi: o'zboshimchalik bilan tanlangan algoritmik turdagi harakatlar dasturi
(nafaqat kompyuter, balki algoritmik turdagi odam tomonidan amalga oshiriladi) o'z
ishini tugatadi (to'xtatadi) yoki "muzlatadi". cheksiz halqa; dastur ekvivalentligi
muammosi (bu ekvivalentlikni o'rnatish uchun universal algoritm mavjud emas);
ikkita matematik ifodaning bir xilligi masalasi; mavjud mashinalardan berilgan
mashinani yig'ish mumkinmi yoki yo'qligini tan olish muammosi; topologiya,
guruhlar nazariyasi va boshqa sohalarga oid ko'plab boshqa muammolar kabi.

$3. Funksiyalarning superpozitsiyasi f1, ..., fm funksiyalarning superpozitsiyasi bu funksiyalarni bir-biriga almashtirish va o‘zgaruvchilar nomini o‘zgartirish orqali olingan f funksiyadir. Ikkita displey bo'lsin <http://moodle.herzen.spb.ru/filter/tex/displaytex.php? texexp=f : X_f \rightarrow Y_f> va <http://moodle.herzen.spb.ru/filter / tex/displaytex.php?texexp=g : X_g \rightarrow Y_g> va <http://moodle.herzen.spb.ru/filter/tex/displaytex.php?texexp= f (X_f) \cap X_g> bo'sh bo'lmagan to'plam. Keyin <http://moodle.herzen.spb.ru/filter/tex/displaytex.php?texexp=g> va <http://moodle.herzen.spb.ru/filter/ funktsiyalarining super pozitsiyasi yoki tarkibi. tex/displaytex .php?texexp=f>funktsiya <http://moodle.herzen.spb.ru/filter/tex/displaytex.php?texexp= g \circ f : X_f \ rightarrow Y_g> tomonidan belgilanadi, hamma uchun <http://moodle.herzen.spb.ru/filter/tex/displaytex.php?texexp= g \circ f(x) = g(f(x))> tengligi <http://moodle. herzen.spb.ru/filter /tex/displaytex.php?texexp=x \in X_f>. Superpozitsiyani aniqlash sohasi <http://moodle.herzen.spb.ru/filter/tex/displaytex.php?texexp=\mathbb{D}_h = \left \ { x \in X_f \mid f to'plamidir. (x) \ X_g ichida \o'ng \}>. Funktsiya <http://moodle.herzen.spb.ru/filter/tex/displaytex.php?texexp=g> tashqi deb ataladi va <http://moodle.herzen.spb.ru/filter/tex/displaytex .php ? texexp=f>-superpozitsiya uchun ichki funksiya <http://moodle.herzen.spb.ru/filter/tex/displaytex.php?texexp=g\circ f>. "Oddiyroq"larning tarkibi sifatida taqdim etilgan funktsiyalar murakkab funktsiyalar deb ataladi. Superpozitsiyadan foydalanishga misollar: tenglamalar tizimini almashtirish yo'li bilan yechish; funktsiyaning hosilasini topish; ko'rsatilgan o'zgaruvchilarning qiymatlarini unga almashtirish orqali algebraik ifodaning qiymatini topish.$

3. Rekursiv funksiyalar
Rekursiya - bu funktsiyani aniqlash usuli bo'lib, unda ixtiyoriy argument
qiymatlari uchun belgilangan funktsiyaning qiymatlari ma'lum tarzda kichikroq
argument qiymatlari uchun belgilangan funktsiyaning qiymatlari orqali ifodalanadi.
.1 Primitiv rekursiv funksiya
Primitiv rekursiv funksiya tushunchasining ta'rifi induktivdir. U asosiy ibtidoiy
rekursiv funksiyalar sinfini va mavjudlari asosida yangi ibtidoiy rekursiv
funksiyalarni qurish imkonini beruvchi ikkita operatorni (superpozitsiya va ibtidoiy
rekursiya) belgilashdan iborat.
Asosiy ibtidoiy rekursiv funktsiyalarga quyidagi uch turdagi funktsiyalar kiradi:
Null funksiyasi argumentsiz funksiya bo lib, u har doim ʻ
<https://ru.wikipedia.org/wiki/0_(%D1%87%D0%B8%D1%81%D0%BB
%D0%BE)> qaytaradi .
Har qanday natural songa bevosita keyingi natural songa mos keladigan bitta
o zgaruvchining ketma-ketlik funksiyasi.
ʻ
Funktsiyalar , bu erda , n o'zgaruvchilardan, istalgan tartiblangan to'plamga
solishtirish natural sonlar soni ushbu to'plamdan.
Almashtirish va ibtidoiy rekursiya operatorlari quyidagicha aniqlanadi:
Superpozitsiya operatori (ba'zan almashtirish operatori). m o‘zgaruvchili
funksiya bo‘lsin va har biri o‘zgaruvchiga ega bo‘lgan tartiblangan funksiyalar
to‘plami bo‘lsin. Keyin funksiyalarning funksiyaga superpozitsiyasi natijasi har
qanday tartiblangan to‘plamga moslashuvchi o‘zgaruvchilar funksiyasi natural sonlar
soni.
Primitiv rekursiya operatori. Mayli n o‘zgaruvchining funksiyasi va -
funktsiyadan o'zgaruvchilar. Keyin bir juft funksiyaga ibtidoiy rekursiya operatorini
qo'llash natijasi bo'ladi Va funksiya deb ataladi dan shaklning o'zgaruvchisi;
.
Ushbu ta'rifda o'zgaruvchini iteratsiya hisoblagichi sifatida tushunish mumkin, -
bilan boshlanadigan o'zgaruvchilar funktsiyalarining ma'lum ketma-ketligini hosil
qiluvchi iterativ jarayonning boshida boshlang'ich funktsiya sifatida va - kirish
o'zgaruvchilari, iteratsiya qadam raqami, funksiya sifatida qabul qiluvchi operator
sifatida Berilgan takrorlash bosqichida va keyingi iteratsiya bosqichida funktsiyani

qaytarish.
Ibtidoiy rekursiv funktsiyalar to'plami barcha asosiy funktsiyalarni o'z ichiga
olgan va belgilangan almashtirish va ibtidoiy rekursiya operatorlari ostida yopilgan
minimal to'plamdir.
Imperativ dasturlash shartlarida ibtidoiy rekursiv funksiyalar faqat arifmetik
amallardan foydalanadigan dastur bloklariga, shuningdek shartli operator va arifmetik
sikl operatoriga (sikl boshida takrorlanishlar soni ma'lum bo'lgan sikl operatori) mos
keladi. Agar dasturchi takrorlashlar soni oldindan noma'lum bo'lgan va printsipial
jihatdan cheksiz bo'lishi mumkin bo'lgan while sikl operatoridan foydalanishni
boshlasa, u qisman rekursiv funksiyalar sinfiga o'tadi.
Primitiv rekursiv bo'lgan bir qancha taniqli arifmetik funktsiyalarni ko'rsatamiz.
Ikki natural sonni qo‘shish funksiyasini () funksiyalarga ibtidoiy rekursiya
operatorini qo‘llash orqali olingan ikkita o‘zgaruvchining ibtidoiy rekursiv funksiyasi
sifatida ko‘rish mumkin. va , ikkinchisi asosiy funktsiyani almashtirish orqali olinadi
asosiy funktsiyaga:
;
;
.
Ikki natural sonni ko‘paytirishni ikkita o‘zgaruvchining ibtidoiy rekursiv
funksiyasi deb hisoblash mumkin, bu funksiyalarga ibtidoiy rekursiya operatorini
qo‘llash orqali olinadi. va , ikkinchisi asosiy funktsiyalarni almashtirish orqali olinadi
Va qo'shish funktsiyasiga:
;
;
.
Ikki natural sonning () nosimmetrik farqi (farqning mutlaq qiymati) quyidagi
almashtirishlar va ibtidoiy rekursiyalarni qo‘llash orqali olingan ikkita
o‘zgaruvchining ibtidoiy rekursiv funksiyasi sifatida qaralishi mumkin:
;
;
;
;
;
.2 Umumiy rekursiv funksiyalar

Funktsiya odatda rekursiv bo'ladi, agar u qandaydir turdagi tenglamalar qatori
bilan aniqlansa.
Qiyinchilik shundan kelib chiqadiki, tenglamalarning bunday tanlovini ko'rib
chiqish odatda bizni bu tenglamalar har qanday funktsiyani "aniqlashi"ga
ishontirmaydi. “Funksiya” deganda biz odatda “har bir qiymatga (yoki n ta
o‘zgaruvchidan iborat funksiyaga ega bo‘lsak, n ta qiymatlar to‘plamiga) natijaviy
qiymatni belgilaydigan qoidani nazarda tutamiz. Ammo umuman olganda,
tenglamalar tizimi har doim ham ma'lum bir qiymatni bermaydi.
Bu. Ba'zi nuqtalar uchun (yoki hatto hamma uchun) funktsiyaning qiymati
aniqlanmagan bo'lsa, bu mutlaqo maqbul holat - bu nuqtalarda funktsiyaning o'zi
aniqlanmagan deb hisoblanadi. Bu hodisa juda xarakterlidir. Shuning uchun,
tenglamalar tizimi haqiqatda umumiy rekursiv funktsiyani aniqlaydi, deb taxmin
qilishda doimo ehtiyot bo'lish kerak. Biz odatda bu fikrning qo'shimcha isbotini talab
qilamiz, masalan, argumentning har bir qiymati uchun baholash bitta qiymat bilan
tugaydigan induktiv dalil shaklida.
Natijada, biz odatda qisman rekursiv funksiya haqida gapiramiz. Qisman
rekursiv funktsiya (yoki qisqasi, qisman funksiya) F(x) haqida gapirganda, x ning
ba'zi (yoki hatto biron bir!) qiymati uchun aniqlangan qiymat bo'lmasligi
mumkinligini tushunamiz. Agar F(x) x ning barcha qiymatlari uchun aniqlangan
bo'lsa, biz uni umumiy rekursiv funktsiya yoki qisqasi, umumiy funktsiya deb
ataymiz. Albatta, har qanday umumiy rekursiv funksiya ham qisman rekursiv
hisoblanishi mumkin.
Demak, umumiy holatda rekursiv tenglamalarning ixtiyoriy tizimi qisman
rekursiv funktsiyani belgilaydi.
Cherkov tezisi: algoritmik (yoki mashina) hisoblanuvchi qisman sonli
funktsiyalar sinfi barcha qisman rekursiv funktsiyalar sinfiga to'g'ri keladi.
Boshqacha qilib aytganda, umumiy ma'noda hisoblanishi mumkin bo'lgan
arifmetik funktsiya mohiyatan rekursiv funktsiyadir. Javob. umumiy ma'noda

hisoblanishi mumkin bo'lgan qisman arifmetik funktsiya qisman rekursiv
funktsiyaning mohiyatidir. Bu qat'iy ta'rif emas, bu tezis darajasidagi xulosa
(tasdiqlangan emas, lekin rad etilgan bayonot emas).
.3 Kengaytirilgan Kleene asosi. Farqning qisman rekursivligi
Qisman arifmetik f funksiya, agar uni eng oddiy O, S, Umn funksiyalardan
cheklangan miqdordagi almashtirish, ibtidoiy rekursiya va minimallashtirish amallari
orqali olish mumkin bo‘lsa, qisman rekursiv deyiladi.
Shunday qilib, qisman rekursiv funktsiyani hisoblashning elementar sxemasi
ko'rinishida aniqlash uchun yangi operatsiyani kiritish orqali ilgari kiritilgan Kleene
asosini kengaytirish kerak: minimallashtirish operatsiyasi.
Minimallashtirish operatori tushunchasi bilan tanishamiz.
Qisman arifmetik funksiyalar to‘plamiga (PAF) tegishli f(x1,….xn) funksiya
bo‘lsin. Uni hisoblash uchun qandaydir mexanizm bo'lsin va funksiya qiymati noaniq
bo'ladi, agar bu mexanizm hech qanday aniq natija bermasdan, cheksiz ishlaydi.
f funktsiyaning birinchi n-1 argumentlari uchun x1,......,xn-1 qiymatlarini
aniqlaymiz va tenglamani ko'rib chiqamiz: f(x1,......,xn-1, y)=xn. (1).
Ushbu tenglamaning y (tabiiy) yechimini topish uchun yuqoridagi “mexanizm”
yordamida f(x1,...,xn-1,a)=xn qiymatlarini ketma-ket hisoblab chiqamiz, y=0,1, 2,...
f(x1,...xn-1,a)=xn ni oladigan a ning eng kichik qiymati my(f(x1,...,xn-1,y)= bilan
belgilanadi. xn). (2)
Ta'riflangan (2) ifodani topish jarayoni quyidagi hollarda cheksiz davom etadi:
f(x1,.....,xn-1,y) qiymati aniqlanmagan;
y=0,1,...,a-1 uchun f(x1,.....,xn-1,y) qiymatlari aniqlangan, lekin xn dan farq
qiladi va f(x1) qiymati ,....., xn-1,a) - aniqlanmagan
f(x1,.....,xn-1,y) qiymatlari barcha y=0,1,2,... uchun aniqlanadi va xn dan farq
qiladi.

Bu barcha holatlarda (2) ifoda qiymati aniqlanmagan hisoblanadi. Boshqa
hollarda tasvirlangan jarayon uzilib, (1) tenglamaning eng kichik y=a yechimini
beradi.
Masalan, f(x,y)=xy farq funksiyasi uchun m belgisining ko’rsatilgan ma’nosiga
muvofiq barcha x,y uchun bizda: y=mz(y+z=x) (3)
Aksincha, my(y(y-(x+1))=0) (4) ifoda qiymati.
noaniq, chunki 0i(0-(x+1)) atamasining qiymati allaqachon noaniq. Shu bilan
birga, y(y-(x+1))=0 tenglama y=x+1 yechimga ega, lekin u (4) ifoda qiymatiga mos
kelmaydi. Bu misol f(x1,.....,xn-1,y) qismli funksiyalar uchun (2) ifodasi, to'g'ri
aytganda, (1) tenglamaning eng kichik yechimi emasligini ko'rsatadi. Agar
f(x1,.....,xn-1,y) funksiya hamma joyda aniqlangan bo‘lsa va (1) tenglama
yechimlarga ega bo‘lsa, (2) (1) ning eng kichik yechimi bo‘ladi.
Bu minimallashtirish operatori ostida faqat hamma joyda belgilangan
funktsiyalardan foydalanishning tabiiy istagini keltirib chiqaradi. Funktsiya hamma
joyda aniqlanganligiga ishonch hosil qilishning eng yaxshi usuli bu aniq ibtidoiy
rekursiv funktsiyalardan (yoki ibtidoiy rekursivligi ilgari isbotlangan yoki ular
ko'rsatilganidan kelib chiqadigan funktsiyalardan) foydalanishdir . Bunday holda,
f(x1,.....,xn) qiymatlari uchta usuldan faqat birida aniqlanmaydi, ya'ni f(x1,.....,xn-
qiymatlari bo'lsa. 1,y) barcha y= 0,1,2,... uchun aniqlanadi va xn dan farq qiladi.
Buning uchun mavjud funktsiyani shunday o'zgartirish kerak (alohidalarni ko'chirish,
ikkala qismni ko'paytirish va hokazolar orqali) tenglikning har ikki tomonida ibtidoiy
rekursiv (shuning uchun hamma joyda aniqlangan) ifodalar mavjud. Umuman
olganda, minimallashtirish operatori ostida biz ma'lum bir rekursiv tenglamani
olamiz, uning qismlari o'zgaruvchilarga (x1,....., xn-1, xn, y) bog'liq bo'lib, u "true"
yoki "false" qiymatini oladi. ” ketma-ket tanlangan parametr qiymatlari uchun y.
Agar qisman f funktsiyani O, S, Umn eng oddiy funksiyalaridan chekli sonli
almashtirish, ibtidoiy rekursiya va minimallashtirish amallari orqali olish mumkin
bo'lsa, qisman rekursiv deyiladi.

Rekursiv funktsiyalarga tegishli quyidagi xususiyatlar bevosita ushbu asosiy
ta'rifdan kelib chiqadi.
y funksiyalar tizimiga nisbatan ibtidoiy rekursiv bo'lgan har bir qisman
funksiya y ga nisbatan ham qisman rekursivdir. Xususan, barcha ibtidoiy rekursiv
funksiyalar qisman rekursivdir.
Qisman rekursiv funksiyalar sinfi ibtidoiy rekursiv funksiyalar sinfiga
qaraganda kengroqdir, chunki barcha ibtidoiy rekursiv funksiyalar hamma joyda
aniqlanadi, qisman rekursiv funksiyalar orasida hamma joyda aniqlanmagan
funksiyalar ham bor, masalan, hech qayerda aniqlanmagan funksiya (x) = mz (x + 1 +
z = 0) .
y tizimiga nisbatan qisman rekursiv bo‘lgan funksiyalar ustida bajariladigan
almashtirish, ibtidoiy rekursiya va minimallashtirish amallari natijasida y ga nisbatan
yana qisman rekursiv bo‘lgan funksiyalar paydo bo‘ladi.

3.4 Gödel raqamlash va qisman rekursiv funktsiyalarni samarali sanab o'tish
Negadir biz 1(x), f2(x), …fn(x), …, barcha qisman rekursiv funksiyalarning
tartiblangan ketma-ketligiga (ro yxati) ega bo lishni xohlaymiz.ʻ ʻ
shunday qilib, bu haqda samarali belgilangan operatsiyalar tilida gapirish
mumkin. Ob'ektlar to'plamini ma'lum bir diskret ketma-ketlikda joylashtirish ob'ektlar
to'plamini sanab o'tish deyiladi. Bizning maqsadlarimiz uchun qisman rekursiv
funktsiyalarni sanab o'tish samarali bo'lishi muhim, ya'ni. Shunday qilib, biz
ro'yxatning n-funktsiyasini topishning samarali usuliga egamiz yoki hech
bo'lmaganda uning ta'rifini topamiz. Garchi bu g'alati tuyulishi mumkin bo'lsa-da,
ro'yxatga olish mavjudligini bilish kifoya - biz uning xususiyatlari haqida hech
qanday ma'lumotni bilishimiz shart emas! Shuning uchun, batafsil dalil o'rniga, uning
imkoniyati foydasiga ishonchli dalil keltirish kifoya, ya'ni. Agar kerak bo'lsa, biz uni
qurishimiz mumkin.
Nima uchun biz hali ham qisman rekursiv funktsiyalarning samarali ro'yxati
mavjud deb taxmin qilishimiz mumkin? Oxir-oqibat, ular fantastik darajada boy,
g'alati va tartibsiz ob'ektlar to'plamini tashkil qiladi, chunki to'plam barcha mumkin
bo'lgan rekursiv ta'riflarga javob beradigan ob'ektlarni o'z ichiga oladi.
Darhaqiqat, yaqinroq tekshirilganda, har bir qisman rekursiv funktsiyaning
ta'rifi chekli tenglamalar to'plamidan iborat ekanligi ayon bo'ladi, ularning har biri
nol, identifikatsiya, implikatsiya, ibtidoiy rekursiya, superpozitsiya va eng kichik son
uchun chekli sonli belgilarni o'z ichiga oladi. chekli sonli vergul va qavslar bilan
birlashtiriladi. Ularning joylashuvi uchun aniq qoidalar muhim emas; muhimi
shundaki, har qanday bunday vaziyatda kompozitsion ob'ektlarning qandaydir cheksiz
leksikografik tartibini kiritish har doim mumkin. Garchi bu holat murakkabroq
ko'rinsa-da, uni yanada soddalashtirishning bir yo'li bor. Haqiqatan ham, qisman
rekursiv funktsiyalarning ko'pchiligi (aniqrog'i ta'riflar) hisoblash jarayonining
haqiqiy yakunini aniqlamaganligi sababli, ta'riflarni sanab o'tishda barcha belgilar

ketma-ketligi to'g'ri ekanligidan juda xavotirlanishga hojat yo'q. Darhaqiqat, biz
ta'riflar uchun zarur bo'lgan har qanday (va barcha) belgilar ketma-ketligini ishlab
chiqaradigan ba'zi protseduralarni ko'rib chiqishimiz mumkin. Faqat bitta texnik
muammo bor - belgilangan alifboda qolish; va u talab qilinishi mumkin bo'lgan
cheksiz miqdordagi o'zgaruvchilar va funksiya nomlarini, aytaylik, ikkilik kodlash
yordamida hal qilinadi. Keyin oddiy raqamlarni tartiblash sxemasi n-chi tavsifni
to'g'ri talqin qilish usuli mavjud bo'lsa, samarali sanab o'tadi.
Kompozit ob'ektlarning cheksiz leksikografik tartibini Gödel algoritmi
yordamida osongina sanab o'tish mumkin. Bundan tashqari, Kleen teoremasidan kelib
chiqadiki, qisman rekursiv funktsiyalar operator atamasi sifatida ifodalanishi mumkin,
ya'ni. faqat bir nechta funksiya belgilaridan foydalanadigan qisman rekursiya sxemasi
shaklida: uchta funksiya uchun O, S, Umn va uchta amal: almashtirish indekslari
bilan S, ibtidoiy rekursiya uchun R va minimallashtirish uchun. Ushbu faktni hisobga
olgan holda, n-chi tavsifni to'g'ri talqin qilish masalasi olib tashlanadi: agar biz
tenglamalar tizimini emas, balki qisman ibtidoiy rekursiyalar sxemalarini operator
atamalar shaklida kodlasak, unda bunday talqin avtomatik bo'ladi.
Keling, Gödel raqamlash asosida samarali sanab o'tishning isbotini yarataylik.
Buning uchun siz Gödel raqamlashdan foydalangan holda barcha elementlar uchun
kod raqamlarini kiritishingiz kerak.
Keling, bir qator tub sonlarni olaylik: 2, 3, 5, 7,... Keyingi protsedura Gödel
raqamlashiga o'xshaydi, masalan, Markov algoritmlari. Bu. Biz ibtidoiy rekursiv
tavsifning Gödel raqamini oldik. Gödel raqamlari tabiiy sonlar orasida samarali tan
olinadi;
Ba'zi fn{x funksiyalarini hatto x ning kamida bitta qiymati uchun ham aniqlab
bo'lmaydi. Fi(x) va fj(x) kabi indekslari har xil bo lgan ba zi funksiyalar bir xilʻ ʼ
bo lishi mumkin: barcha x uchun fi(x) = fj(x). Darhaqiqat, ba'zi funktsiyalar butunlay
ʻ
boshqa ta'riflarga mos keladigan ro'yxatda cheksiz ravishda paydo bo'lishi mumkin.
Biz amin bo'lgan yagona narsa shundaki, agar funktsiya qisman rekursiv bo'lsa, u

holda ro'yxatda kamida bitta indeks mavjud.
Hech bir joyda aniqlanmagan funksiya va bir nuqtada aniqlangan funksiyaning
qisman rekursivligi.
1) Hech qaysi joyda aniqlanmagan funksiya 1 ) (   x x f .
Rekursiv tenglama tuzamiz:
)0 1 ( ) (      x z x f 
Minimallashtirish operatsiyasining natijasi hatto x=0 nuqtasi uchun ham
aniqlanmagan.
2) Bir nuqtada aniqlangan funksiya,
x x f ) ( .
Rekursiv tenglama tuzamiz:
)0 ( ) (     x z x f 
Minimallashtirish operatsiyasining natijasi faqat x ning boshqa qiymatlari
uchun x=0 uchun aniqlanadi, hisoblash (kerakli qiymat z ni tanlash) hech qachon
tugallanmaydi.

Xulosa
Ushbu kurs ishi: masalaning algoritmik yechilmasligini aniqlash;
funksiyalarning superpozitsiyasi, rekursiv funksiyalar tushunchalari; ibtidoiy
rekursiya sxemasi; minimallashtirish operatsiyasi.
Kurs ishining maqsadi algoritmik hisoblanuvchi funksiya va rekursiv funksiya
tushunchalarini tushuntirishdan iborat.
Kurs ishining vazifalari quyidagilardan iborat: algoritmik muammoning ta'rifini
tushuntirish, algoritmik hal qilmaslik; funksiyalarning superpozitsiyasi
tushunchalarini ochib berish; funksiyalarning hisoblash imkoniyatini aniqlashda
qisman rekursiv va umumiy rekursiv funksiyalarning rolini oydinlashtirish; ibtidoiy
rekursiya sxemasini tahlil qilish.
Kurs ishi davomida quyidagi mavzular bo‘yicha bilimlar o‘rganildi va
mustahkamlandi: algoritmik hisoblanuvchi funksiya, rekursiv funksiya tushunchalari.
Ushbu mavzu bo'yicha asosiy tushunchalar ko'rib chiqildi:
algoritmik muammo
algoritmik noaniqlik
funksiyalarning superpozitsiyasi
ibtidoiy rekursiya
qisman rekursiv va umumiy rekursiv funksiyalar.
Taqdim etilgan ishda tushunchalarni tahlil qilish amalga oshirildi: masalani
yechish algoritmi, algoritmik hal qilinmaslik, funktsiyalarning superpozitsiyasi,
rekursiv funktsiya.
Ushbu kurs ishi bo'yicha topshiriqda belgilangan barcha vazifalar to'liq
bajarildi.
Xulosa:
Berilgan masalani yechish algoritmining mavjudligi yoki yo‘qligini isbotlash
matematik mantiqning muhim elementi hisoblanadi, chunki u algoritmik yechim

mavjudligi yoki yo‘qligi haqidagi savolga aniq javob berishga imkon beradi.
Har qanday boshlang'ich sharoitda to'g'ri natijaga olib keladigan chekli
harakatlar ketma-ketligi bo'lmasa, muammoni algoritmik ravishda hal qilib bo'lmaydi.
Buni isbotlash usullaridan biri funksiya qisman rekursiv funksiyalar sinfiga
tegishli ekanligini aniqlashdir.

Foydalanilgan adabiyotlar ro'yxati
1. Kleene S. Matematik mantiq. - M.: Mir, 1980 yil.
2. Karri Xaskell B. Matematik mantiq asoslari. - M.: Mir, 1969 yil
. Karpov V.G., Moshchenskiy V.A. Matematik mantiq va diskret matematika. -
Minsk: “Eng baland. maktab", 1977 yil
. Vereshchagin N.K., Uspenskiy V.A., Plisko V.E. Matematik mantiqga kirish
kursi: darslik - FIZMATLIT, 2007 y
. Ershov Yu.L., Palyutin E.A. Matematik mantiq - FIZMATLIT, 2011 yil
. Zaitseva E.V., Gurova L.M. Matematik mantiq va algoritmlar nazariyasi:
Darslik - Moskva davlat nashriyoti

Rekursiv funksiyalar

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish

Информация о документе

Продавец

Rekursiv funksiyalar

Похожие документы