Algoritmik hal qilmaslik Rekursiv funksiyalar - Информатика и ИТ - Курсовые работы

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

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

Algoritmik hal qilmaslik Rekursiv funksiyalar

Купить

Algoritmik hal qilmaslik Rekursiv funksiyalar
Reja
Kirish
I BOB Algoritmik hal qilmaslik
1.1. Algoritm tushunchasi
1.2. Funksiyalarning superpozitsiyasi
II BOB. Rekursiv funksiyalar
2.1 Primitiv rekursiv funksiya
2.2 Umumiy rekursiv funksiyalar
2.3 Kengaytirilgan xanjar asosi. Farqning qisman rekursivligi
2.4 Go’del raqamlash va qisman rekursiv funktsiyalarni samarali sanab o'tish
Xulosa
Foydalanilgan adabiyotlar ro'yxati

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.
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.

I BOB 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.
1.2. Algoritm tushunchasi
Algoritm — ma lum bir turga oid masalalarni yechishda ishlatiladiganʼ
amallarning muayyan tartibda bajarilishi haqidagi aniq qoida
(dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. O rta
ʻ
asrlarda sanoqning o nli tizimi bo yicha to rt arifmetik amal bajariladigan qoidani
ʻ ʻ ʻ
algoritm deb atashgan. "Bu qoidalarni matematikaga IX asrda al-
Xorazmiy kiritgan. Yevropada bunday qoidalar uning tugilgan yurtiga nisbatan
lotinchalashtirilgan (Algoritmus yoki Algorithmus shaklida „algorizm“ deyilgan),
keyinchalik „algoritm“ga aylangan". Fanda „Yevklid algoritmi“, „G iyosiddin
ʻ

Koshiy algoritmi“, „Laure algoritmi“, „Markov algoritmi“ deb ataluvchi
algoritmlar ma lum. Algoritm tushunchasi tobora kengayib borib, kibernetikaningʼ
nazariy va mantiqiy asosi hisoblangan algoritmlar nazariyasi paydo
bo ldi.
ʻ O zbekistonda ʻ bir necha ilmiy tadqiqot muassasalari va hisoblash
markazlarida algoritmdan foydalanish sohasida samarali ishlar olib borilmoqda.
Masalan, O zbekiston Fanlar Akademiyasi
ʻ „Kibernetika“ ilmiy ishlab chiqarish
birlashmasida, O zbekistondagi barcha universitetlarda, Toshkent davlat texnika
ʻ
universitetida, O zbekiston Respublikasi Makroiqtisod va statistika vazirligi
ʻ
qoshidagi Hisoblash markazi va boshqa muassasalarda olib borilayotgan ishlar
bunga misol bo la oladi
ʻ [1]
.
 Xususiyatlari
 Aniqlik ( deterministik ) — har bir vaqtda algoritmning keyingi qadami
uning mazkur holati bilan to liq aniqlanadi.
ʻ
 Tushunarlilik — algoritm faqat uni bajaruvchisi uchun tushunarli
buyruqlardan iborat bo lishi shart.
ʻ
 Yakunlanishi — algoritm albatta chekli qadamdan so ng yakunlashishi
ʻ
lozim.
 Turlari
 Chiziqli algoritm — barcha ko rsatmalari hech qanday shartsiz, faqat
ʻ
ketma-ket bajariladigan jarayonlar.
 Tarmoqlanuvchi algoritm — hisoblash jarayoni qandaydir berilgan
shartning bajarilishiga qarab turli tarmoqlar bo yicha davom ettiriladigan
ʻ
va hisoblash jarayonida har bir tarmoq faqat bir marta bajariladigan
jarayonlar.
 Takrorlanuvchi algoritm — biron bir shart tekshirilishi yoki
qandaydir parametrning har xil qiymatlari asosida algoritmda
takrorlanish yuz beradigan jarayonlar.
 Aralash (kombinatsiyalashgan) algoritm — tarkibida bir necha turdagi
algoritmlar qatnashgan algoritmdir.

1.2. Funksiyalarning superpozitsiyasi
Superpozitsiya prinsipi — bu bir nechta mustaqil ta sirlarning aniq ta siri har birʼ ʼ
ta sirning alohida ta siri natijasida yuzaga keladigan ta sirlarning yig indisi degan
ʼ ʼ ʼ ʻ
taxmindir. Chiziqli tenglamalar bilan tavsiflangan tizimlar yoki maydonlar uchun
amal qiladi. Bu klassik fizikaning ko plab bo limlarida muhim ahamiyatga ega:
ʻ ʻ
mexanikada, tebranishlar va to lqinlar nazariyasi, fizik maydonlar nazariyasi.
ʻ
Matnni konkretlashtirish ma lum bir sohaga nisbatan mumkin. Masalan,
ʼ
mexanikada, eng oddiy formulasida, superpozitsiya printsipi o qiydi:
ʻ
 bir nechta tashqi kuchlarning zarrachaga ta siri natijasi bu kuchlar
ʼ
ta sirining vektor yig indisi;
ʼ ʻ
 har qanday murakkab harakatni ikki yoki undan ortiq oddiyga bo lish
ʻ
mumkin.
Elektrostatikada superpozitsiyaning eng mashhur prinsipi: ma lum bir nuqtada
ʼ
zaryadlar tizimi tomonidan vujudga keltirilgan elektrostatik maydonning kuchi,
alohida zaryadlarning tashkil etgan maydon kuchlarining vektor yig indisidir
ʻ .
Superpozitsiya prinsipi boshqa formulalarni olishi mumkin, jumladan:
 ko p zarrachali tizimdagi barcha zarralarning o zaro ta sir qilish
ʻ ʻ ʼ
energiyasi shunchaki zarralarning barcha mumkin bo lgan juftlari
ʻ
orasidagi juftlik o zaro ta sirlari
ʻ ʼ energiyalarining
yig indisidir
ʻ — tizimda ko p zarrachalarning o zaro ta siri yo q; ʻ ʻ ʼ ʻ
 ko p zarrali tizimning harakatini tavsiflovchi tenglamalar zarrachalar
ʻ
soni bo yicha
ʻ chiziqli .
Ko rib chiqilayotgan fizika sohasidagi fundamental nazariyaning chiziqliligi unda
ʻ
superpozitsiya prinsipining paydo bo lishiga sabab bo ladi.
ʻ ʻ
Elektrodinamikada superpozitsiya prinsipi

Superpozitsiya printsipi to g ridan-to g ri ko rib chiqilayotgan nazariyadan kelibʻ ʻ ʻ ʻ ʻ
chiqadigan natijadir va umuman nazariyaga apriori kiritilgan postulat emas.
Masalan, elektrostatikada superpozitsiya printsipi vakuumdagi Maksvell
tenglamalari chiziqli bo lishining natijasidir. Bundan kelib chiqadiki, zaryadlar
ʻ
tizimining elektrostatik o zaro ta sirining potentsial energiyasini har bir zaryad
ʻ ʼ
juftining potensial energiyasini hisoblash orqali osongina hisoblash mumkin.
Maksvell tenglamalarining chiziqliligining yana bir natijasi yorug lik
ʻ nurlarining
tarqalmasligi va umuman bir-biri bilan hech qanday tarzda o zaro ta sir
ʻ ʼ
qilmasligidir. Ushbu qonunni taxminiy ravishda optikada superpozitsiya
prinsipi deb atash mumkin.
Shunday qilib, superpozitsiyaning elektrodinamik printsipi tabiatning o zgarmas
ʻ
qonuni emas, balki faqat Maksvell tenglamalarining, ya ni klassik
ʼ
elektrodinamika tenglamalarining chiziqliligining natijasidir. Shuning uchun, biz
klassik elektrodinamikaning qo llanilishi chegarasidan tashqariga chiqsak,
ʻ
superpozitsiya printsipining buzilishini kutish juda oqilona.
Superpozitsiyaning elektrodinamik prinsipini buzish misollari
Agar elektrodinamika vakuumda emas, balki ba zi muhitda ko rib chiqilsa,
ʼ ʻ
superpozitsiya printsipi buzilishi mumkin. Misol uchun, agar muhitning
qutblanishi yoki magnitlanishi qo llaniladigan maydonga nochiziqli bog liq bo lsa,
ʻ ʻ ʻ
bu Maksvell tenglamalarida chiziqli bo lmagan tuzatishlarga olib keladi. Buning
ʻ
to g ridan-to g ri natijasi, bunday
ʻ ʻ ʻ ʻ chiziqli bo lmagan muhitda ʻ superpozitsion
prinsipining buzilishidir.
Ba zi hollarda, bu chiziqli bo lmaganlar kichikdir va superpozitsiya printsipi
ʼ ʻ
ma lum darajada yaqinlashish bilan bajarilishi mumkin. Boshqa hollarda,
ʼ
superpozitsiya printsipining buzilishi katta va tubdan yangi hodisalarga olib kelishi
mumkin. Shunday qilib, masalan, chiziqli bo lmagan muhitda tarqaladigan ikkita
ʻ
yorug lik nurlari bir-birining traektoriyasini o zgartirishi mumkin. Bundan
ʻ ʻ
tashqari, chiziqli bo lmagan muhitdagi bitta yorug lik nuri ham o z-o zidan ta sir
ʻ ʻ ʻ ʻ ʼ

qilishi va xususiyatlarini o zgartirishi mumkin. Ushbu turdagi ko plab effektlarʻ ʻ
chiziqli bo lmagan optikada o rganiladi.
ʻ ʻ
Kvant hodisalari hisobga olinganda vakuumda superpozitsiya tamoyili ham
buziladi. Kvant elektrodinamikasida foton bir muncha
vaqt elektronga — pozitron juftiga aylanishi mumkin, u allaqachon boshqa
fotonlar bilan o zaro ta sir qilishi mumkin. Samarali ravishda, bu fotonlarning bir-
ʻ ʼ
biri bilan o zaro ta sir qilishiga olib keladi. Ushbu turdagi jarayonlar (tarqoq
ʻ ʼ
yorug lik va
ʻ nochiziqli elektrodinamikaning boshqa jarayonlari) tajribada
kuzatildi.
Nochiziqli nazariyalarda superpozitsiya prinsipining yo qligi
ʻ
Klassik elektrodinamika tenglamalarining chiziqli bo lishi qoidadan ko ra
ʻ ʻ
istisnodir. Zamonaviy fizikaning ko pgina fundamental nazariyalari chiziqli emas.
ʻ
Masalan, kuchli o zaro ta sirlarning
ʻ ʼ asosiy nazariyasi bo lgan kvant ʻ
xromodinamikasi Yang-Mills nazariyasining o zgarishi bo lib, qurilishda chiziqli
ʻ ʻ
bo lmagan. Bu Yang-Mills tenglamalarining klassik (kvantlanmagan) yechimlarida
ʻ
ham superpozitsiya printsipining kuchli buzilishiga olib keladi.
Chiziqli bo lmagan nazariyaning yana bir mashhur misoli
ʻ umumiy nisbiylik
nazariyasidir . Bundan tashqari, superpozitsiya tamoyilini bajarmaydi. Misol
uchun, Quyoshning tortishish maydoni nafaqat Yer va Oyga, balki Yer va Oy
o rtasidagi tortishishning o zaro ta siriga ham ta sir qiladi. Quyoshning tortishish
ʻ ʻ ʼ ʼ
maydoni ta siridan tashqari, Yer va Oy o rtasidagi tortishish o zaro ta siri
ʼ ʻ ʻ ʼ
kuzatilganidan farq qiladi. Biroq, zaif tortishish maydonlarida chiziqli
bo lmaganlikning ta siri zaif va kundalik muammolar uchun taxminiy
ʻ ʼ
superpozitsiya prinsipi yuqori aniqlik bilan amalga oshiriladi.
Va nihoyat, atomlar va molekulalarning o zaro ta siri haqida gap ketganda,
ʻ ʼ
superpozitsiya printsipi bajarilmaydi. Buni quyidagicha tushuntirish mumkin.
Umumiy elektron buluti bilan bog langan ikkita atomni ko rib chiqing. Keling,
ʻ ʻ
xuddi shu uchinchi atomni keltiraylik. U go yo atomlarni bog laydigan elektron
ʻ ʻ

bulutining bir qismini tortib oladi va buning natijasida asl atomlar orasidagi
bog lanish energiyasi o zgaradi.ʻ ʻ
Atomlarning o zaro ta sirida superpozitsiya prinsipining buzilishi ko p jihatdan
ʻ ʼ ʻ
moddalar va materiallarning fizik-kimyoviy xususiyatlarining hayratlanarli xilma-
xilligiga olib keladi, bu molekulyar dinamikaning umumiy tamoyillaridan bashorat
qilish juda qiyin.
Elektrotexnikada superpozitsiya prinsipi
Chiziqli elektr zanjirining har bir tarmog idagi elektr toki, kontaktlarning
ʻ
zanglashiga olib keladigan EYK manbalarining har biri tomonidan alohida-alohida
kelib chiqadigan toklarning algebraik yig indisiga teng.
ʻ
Avtomatik boshqarish nazariyasida superpozitsiya prinsipi
Avtomatlashtirishda superpozitsiya prinsipi chiziqli dinamik tizimlarni tahlil qilish
muammolarini hal qilish uchun zarurdir. Superpozitsiya printsipi va vaqtinchalik
yoki impuls xususiyatlarini bilish asosida chiziqli dinamik tizimning ixtiyoriy
harakatga javobini olish mumkin.
Fizik amalga oshirish mumkin bo lgan har qanday ta sir bosqichli ta sirlar
ʻ ʼ ʼ
yig indisi bilan almashtirilishi mumkin. Keyin tizimning reaktsiyasini individual
ʻ
qadam harakatlariga reaktsiyalar yig indisi sifatida ko rsatish mumkin.
ʻ ʻ
Matematik o zgartirishlar natijasida chiziqli tizim dinamikasining matematik
ʻ
modeli ikkita funktsiyaning konvolyutsion integrali ko rinishida olinadi.
ʻ
Konvolyutsiya integrallari ko rinishidagi matematik model ma lum vaqtinchalik
ʻ ʼ
yoki impulsli javob yordamida dinamik tizimning berilgan kirish harakatiga
javobini hisoblash imkonini beradi. Bu zaruriy o tish jarayonini ifodalaydi.
ʻ
Agar alohida bog lanishlarning faqat o tkinchi xarakteristikalari berilgan bo lsa, u
ʻ ʻ ʻ
holda integral Laplas va Furye o zgarishlari yordamida chiziqli tizimlarni sintez va
ʻ
tahlil qilish masalalarining samaraliroq va nisbatan sodda yechimini olish mumkin.
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.
Funksiyalarning superpozitsiyasi
Superpozitsiya prinsipi — bu bir nechta mustaqil ta sirlarning aniq ta siri har birʼ ʼ
ta sirning alohida ta siri natijasida yuzaga keladigan ta sirlarning yig indisi degan
ʼ ʼ ʼ ʻ
taxmindir. Chiziqli tenglamalar bilan tavsiflangan tizimlar yoki maydonlar uchun
amal qiladi. Bu klassik fizikaning ko plab bo limlarida muhim ahamiyatga ega:
ʻ ʻ
mexanikada, tebranishlar va to lqinlar nazariyasi, fizik maydonlar nazariyasi.
ʻ
Matnni konkretlashtirish ma lum bir sohaga nisbatan mumkin. Masalan,
ʼ
mexanikada, eng oddiy formulasida, superpozitsiya printsipi o qiydi:
ʻ
 bir nechta tashqi kuchlarning zarrachaga ta siri natijasi bu kuchlar
ʼ
ta sirining vektor yig indisi;
ʼ ʻ
 har qanday murakkab harakatni ikki yoki undan ortiq oddiyga bo lish
ʻ
mumkin.
Elektrostatikada superpozitsiyaning eng mashhur prinsipi: ma lum bir nuqtada
ʼ
zaryadlar tizimi tomonidan vujudga keltirilgan elektrostatik maydonning kuchi,
alohida zaryadlarning tashkil etgan maydon kuchlarining vektor yig indisidir
ʻ .
Superpozitsiya prinsipi boshqa formulalarni olishi mumkin, jumladan:
 ko p zarrachali tizimdagi barcha zarralarning o zaro ta sir qilish
ʻ ʻ ʼ
energiyasi shunchaki zarralarning barcha mumkin bo lgan juftlari
ʻ
orasidagi juftlik o zaro ta sirlari
ʻ ʼ energiyalarining
yig indisidir
ʻ — tizimda ko p zarrachalarning o zaro ta siri yo q; ʻ ʻ ʼ ʻ
 ko p zarrali tizimning harakatini tavsiflovchi tenglamalar zarrachalar
ʻ
soni bo yicha
ʻ chiziqli .
Ko rib chiqilayotgan fizika sohasidagi fundamental nazariyaning chiziqliligi unda
ʻ
superpozitsiya prinsipining paydo bo lishiga sabab bo ladi.
ʻ ʻ
Elektrodinamikada superpozitsiya prinsipi

Superpozitsiya printsipi to g ridan-to g ri ko rib chiqilayotgan nazariyadan kelibʻ ʻ ʻ ʻ ʻ
chiqadigan natijadir va umuman nazariyaga apriori kiritilgan postulat emas.
Masalan, elektrostatikada superpozitsiya printsipi vakuumdagi Maksvell
tenglamalari chiziqli bo lishining natijasidir. Bundan kelib chiqadiki, zaryadlar
ʻ
tizimining elektrostatik o zaro ta sirining potentsial energiyasini har bir zaryad
ʻ ʼ
juftining potensial energiyasini hisoblash orqali osongina hisoblash mumkin.
Maksvell tenglamalarining chiziqliligining yana bir natijasi yorug lik
ʻ nurlarining
tarqalmasligi va umuman bir-biri bilan hech qanday tarzda o zaro ta sir
ʻ ʼ
qilmasligidir. Ushbu qonunni taxminiy ravishda optikada superpozitsiya
prinsipi deb atash mumkin.
Shunday qilib, superpozitsiyaning elektrodinamik printsipi tabiatning o zgarmas
ʻ
qonuni emas, balki faqat Maksvell tenglamalarining, ya ni klassik
ʼ
elektrodinamika tenglamalarining chiziqliligining natijasidir. Shuning uchun, biz
klassik elektrodinamikaning qo llanilishi chegarasidan tashqariga chiqsak,
ʻ
superpozitsiya printsipining buzilishini kutish juda oqilona.
Superpozitsiyaning elektrodinamik prinsipini buzish misollari
Agar elektrodinamika vakuumda emas, balki ba zi muhitda ko rib chiqilsa,
ʼ ʻ
superpozitsiya printsipi buzilishi mumkin. Misol uchun, agar muhitning
qutblanishi yoki magnitlanishi qo llaniladigan maydonga nochiziqli bog liq bo lsa,
ʻ ʻ ʻ
bu Maksvell tenglamalarida chiziqli bo lmagan tuzatishlarga olib keladi. Buning
ʻ
to g ridan-to g ri natijasi, bunday
ʻ ʻ ʻ ʻ chiziqli bo lmagan muhitda ʻ superpozitsion
prinsipining buzilishidir.
Ba zi hollarda, bu chiziqli bo lmaganlar kichikdir va superpozitsiya printsipi
ʼ ʻ
ma lum darajada yaqinlashish bilan bajarilishi mumkin. Boshqa hollarda,
ʼ
superpozitsiya printsipining buzilishi katta va tubdan yangi hodisalarga olib kelishi
mumkin. Shunday qilib, masalan, chiziqli bo lmagan muhitda tarqaladigan ikkita
ʻ
yorug lik nurlari bir-birining traektoriyasini o zgartirishi mumkin. Bundan
ʻ ʻ
tashqari, chiziqli bo lmagan muhitdagi bitta yorug lik nuri ham o z-o zidan ta sir
ʻ ʻ ʻ ʻ ʼ

qilishi va xususiyatlarini o zgartirishi mumkin. Ushbu turdagi ko plab effektlarʻ ʻ
chiziqli bo lmagan optikada o rganiladi.
ʻ ʻ
Kvant hodisalari hisobga olinganda vakuumda superpozitsiya tamoyili ham
buziladi. Kvant elektrodinamikasida foton bir muncha
vaqt elektronga — pozitron juftiga aylanishi mumkin, u allaqachon boshqa
fotonlar bilan o zaro ta sir qilishi mumkin. Samarali ravishda, bu fotonlarning bir-
ʻ ʼ
biri bilan o zaro ta sir qilishiga olib keladi. Ushbu turdagi jarayonlar (tarqoq
ʻ ʼ
yorug lik va
ʻ nochiziqli elektrodinamikaning boshqa jarayonlari) tajribada
kuzatildi.
Nochiziqli nazariyalarda superpozitsiya prinsipining yo qligi
ʻ
Klassik elektrodinamika tenglamalarining chiziqli bo lishi qoidadan ko ra
ʻ ʻ
istisnodir. Zamonaviy fizikaning ko pgina fundamental nazariyalari chiziqli emas.
ʻ
Masalan, kuchli o zaro ta sirlarning
ʻ ʼ asosiy nazariyasi bo lgan kvant ʻ
xromodinamikasi Yang-Mills nazariyasining o zgarishi bo lib, qurilishda chiziqli
ʻ ʻ
bo lmagan. Bu Yang-Mills tenglamalarining klassik (kvantlanmagan) yechimlarida
ʻ
ham superpozitsiya printsipining kuchli buzilishiga olib keladi.
Chiziqli bo lmagan nazariyaning yana bir mashhur misoli
ʻ umumiy nisbiylik
nazariyasidir . Bundan tashqari, superpozitsiya tamoyilini bajarmaydi. Misol
uchun, Quyoshning tortishish maydoni nafaqat Yer va Oyga, balki Yer va Oy
o rtasidagi tortishishning o zaro ta siriga ham ta sir qiladi. Quyoshning tortishish
ʻ ʻ ʼ ʼ
maydoni ta siridan tashqari, Yer va Oy o rtasidagi tortishish o zaro ta siri
ʼ ʻ ʻ ʼ
kuzatilganidan farq qiladi. Biroq, zaif tortishish maydonlarida chiziqli
bo lmaganlikning ta siri zaif va kundalik muammolar uchun taxminiy
ʻ ʼ
superpozitsiya prinsipi yuqori aniqlik bilan amalga oshiriladi.
Va nihoyat, atomlar va molekulalarning o zaro ta siri haqida gap ketganda,
ʻ ʼ
superpozitsiya printsipi bajarilmaydi. Buni quyidagicha tushuntirish mumkin.
Umumiy elektron buluti bilan bog langan ikkita atomni ko rib chiqing. Keling,
ʻ ʻ
xuddi shu uchinchi atomni keltiraylik. U go yo atomlarni bog laydigan elektron
ʻ ʻ

bulutining bir qismini tortib oladi va buning natijasida asl atomlar orasidagi
bog lanish energiyasi o zgaradi.ʻ ʻ
Atomlarning o zaro ta sirida superpozitsiya prinsipining buzilishi ko p jihatdan
ʻ ʼ ʻ
moddalar va materiallarning fizik-kimyoviy xususiyatlarining hayratlanarli xilma-
xilligiga olib keladi, bu molekulyar dinamikaning umumiy tamoyillaridan bashorat
qilish juda qiyin.
Elektrotexnikada superpozitsiya prinsipi
Chiziqli elektr zanjirining har bir tarmog idagi elektr toki, kontaktlarning
ʻ
zanglashiga olib keladigan EYK manbalarining har biri tomonidan alohida-alohida
kelib chiqadigan toklarning algebraik yig indisiga teng.
ʻ
Avtomatik boshqarish nazariyasida superpozitsiya prinsipi
Avtomatlashtirishda superpozitsiya prinsipi chiziqli dinamik tizimlarni tahlil qilish
muammolarini hal qilish uchun zarurdir. Superpozitsiya printsipi va vaqtinchalik
yoki impuls xususiyatlarini bilish asosida chiziqli dinamik tizimning ixtiyoriy
harakatga javobini olish mumkin.
Fizik amalga oshirish mumkin bo lgan har qanday ta sir bosqichli ta sirlar
ʻ ʼ ʼ
yig indisi bilan almashtirilishi mumkin. Keyin tizimning reaktsiyasini individual
ʻ
qadam harakatlariga reaktsiyalar yig indisi sifatida ko rsatish mumkin.
ʻ ʻ
Matematik o zgartirishlar natijasida chiziqli tizim dinamikasining matematik
ʻ
modeli ikkita funktsiyaning konvolyutsion integrali ko rinishida olinadi.
ʻ
Konvolyutsiya integrallari ko rinishidagi matematik model ma lum vaqtinchalik
ʻ ʼ
yoki impulsli javob yordamida dinamik tizimning berilgan kirish harakatiga
javobini hisoblash imkonini beradi. Bu zaruriy o tish jarayonini ifodalaydi.
ʻ
Agar alohida bog lanishlarning faqat o tkinchi xarakteristikalari berilgan bo lsa, u
ʻ ʻ ʻ
holda integral Laplas va Furye o zgarishlari yordamida chiziqli tizimlarni sintez va
ʻ
tahlil qilish masalalarining samaraliroq va nisbatan sodda yechimini olish mumkin.

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.
f1, ..., fm funksiyalarning superpozitsiyasi bu funksiyalarni bir-biriga almashtirish
va o‘zgaruvchilar nomini o‘zgartirish orqali olingan f funksiyadir.
va , va bo'sh bo'lmagan to'plam bo'lsin . U
holda funksiyalarning superpozitsiyasi yoki tarkibi har biri
uchun tenglik bilan aniqlangan funksiyadir .
Superpozitsiyani aniqlash sohasi to'plamdir
.
Funktsiya superpozitsiya uchun tashqi va ichki funksiya deb ataladi .
"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.

II BOB. Rekursiv funksiyalar
2.1 Primitiv rekursiv funksiya
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.
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 funksiya har doim 0 ni qaytaradigan argumentsiz funksiyadir .
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‘zgaruvchining
funksiyasi va har bir o‘zgaruvchining 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 - funktsiyasi
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 qarash mumkin. va , ikkinchisi asosiy
funktsiyani almashtirish orqali olinadi asosiy funktsiyaga :
;
;
.
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:
;
;
.
nosimmetrik ayirmasi (farqning mutlaq qiymati) quyidagi
almashtirishlar va ibtidoiy rekursiyalarni qo‘llash orqali olingan ikkita
o‘zgaruvchining ibtidoiy rekursiv funksiyasi sifatida qaralishi mumkin:
;

;
;
;
;
2.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).
2.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).
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. Funksiya hamma
joyda aniqlanganligiga ishonch hosil qilishning eng yaxshi usuli bu aniq ibtidoiy
rekursiv funksiyalardan (yoki ibtidoiy rekursivligi ilgari isbotlangan yoki ular
aniqlanganidan kelib chiqadigan funksiyalardan) 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.
2.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
qisman rekursiv funktsiyalar operator atamasi sifatida ifodalanishi mumkinligi,
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 .
Rekursiv tenglama tuzamiz:
Minimallashtirish operatsiyasining natijasi hatto x=0 nuqtasi uchun ham
aniqlanmagan.
2) Bir nuqtada aniqlangan funksiya, .
Rekursiv tenglama tuzamiz:
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 masala
- 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'yxatidan
1. Kleene S. Matematik mantiq. - M.: Mir, 1980 yil.
2. Karri Xaskell B. Matematik mantiq asoslari. – M.: Mir, 1969 yil
3. Karpov V.G., Moshchenskiy V.A. Matematik mantiq va diskret
matematika. - Minsk: "Eng baland". maktab", 1977 yil
4. Vereshchagin N.K., Uspenskiy V.A., Plisko V.E. Matematik mantiqga
kirish kursi: darslik – FIZMATLIT, 2007
5. Ershov Yu.L., Palyutin E.A. Matematik mantiq – FIZMATLIT, 2011
6. Zaitseva E.V., Gurova L.M. Matematik mantiq va algoritmlar
nazariyasi: Darslik - Moskva davlat nashriyoti
E'lon qilingan. ru

Algoritmik hal qilmaslik Rekursiv funksiyalar

Купить

Похожие документы
3d-max dasturida obektlarni yaratish
Algoritm va ma’lumotlar strukturasi
3D-MAX dasturi haqida
3D Studio MAX dasturiga kirish. 3D Studio MAX dasturi haqida tushuncha
Adobe photoshop dasturida tasvirlarda ishlov berish,taqdimot yaratish