Primitiv rekursiya operatorlari Rekursiv funktsiyalar
Download 25.4 Kb.
|
R.Aziza diskret
|
Primitiv rekursiya operatorlari Rekursiv funktsiyalar Rekursiya - bu argumentlarning ixtiyoriy qiymatlari uchun belgilangan funktsiyaning qiymatlari argumentlarning kichikroq qiymatlari uchun belgilangan funktsiya qiymatlari orqali ma'lum tarzda ifodalanadigan funktsiyani aniqlash usuli. Primitiv rekursiv funksiya Ibtidoiy rekursiv funksiyaning ta'rifi induktivdir. Bu asosiy ibtidoiy rekursiv funktsiyalar sinfini va mavjud bo'lganlar asosida yangi ibtidoiy rekursiv funktsiyalarni yaratishga imkon beradigan ikkita operatorni (superpozitsiya va ibtidoiy rekursiya) belgilashdan iborat. Asosiy ibtidoiy rekursiv funktsiyalar quyidagi uch turdagi funktsiyalarni o'z ichiga oladi: Null funktsiyasi - bu argumentlarsiz, har doim qaytadigan funksiya 0 . Bir o'zgaruvchining vorisi vazifasi, u istalgan natural sonni darhol keyingi natural songa beradi. Funksiyalar, bu erda, n o'zgaruvchida, har qanday tartiblangan natural sonlar to'plamini ushbu to'plamdan raqamga tayinlash. O'zgarish va ibtidoiy rekursiya operatorlari quyidagicha tasniflanadi: Superpozitsiya operatori (ba'zan almashtirish operatori). M o'zgaruvchining funktsiyasi bo'lsin va har bir o'zgaruvchining funktsiyalarining tartiblangan to'plami bo'lsin. Keyin funktsiyalarning funktsiyaga superpozitsiyasining natijasi o'zgaruvchilar funktsiyasi bo'lib, u har qanday tartiblangan natural sonlar sonini belgilaydi. Primitiv rekursiya operatori. N o'zgaruvchining funktsiyasi bo'lsin va o'zgaruvchilar funktsiyasi bo'lsin. Keyin ibtidoiy rekursiya operatorini bir juft funktsiyaga qo'llash natijasi shakl o'zgaruvchisining funktsiyasi deb ataladi; Bu ta'rifda o'zgaruvchini takrorlash hisoblagichi, ya'ni takrorlanadigan jarayonning boshida boshlang'ich funktsiya sifatida, o'zgaruvchilar funktsiyalarining ma'lum bir ketma -ketligini ishlab chiqaruvchi sifatida, va - sonini oluvchi operator sifatida tushunish mumkin. kirish sifatida iteratsiya bosqichi, berilgan iteratsiya bosqichidagi funksiya va iteratsiyaning keyingi bosqichida funktsiyani qaytaradi. Ibtidoiy rekursiv funktsiyalar to'plami - bu barcha asosiy funktsiyalarni o'z ichiga olgan va belgilangan almashtirish va ibtidoiy rekursiya operatorlari ostida yopilgan minimal to'plam. Imperativ dasturlash nuqtai nazaridan, ibtidoiy rekursiv funktsiyalar faqat arifmetik operatsiyalar qo'llaniladigan dastur bloklariga, shuningdek shartli operator va arifmetik pastadir operatoriga (tsikl boshida takrorlanishlar soni ma'lum bo'lgan loop operatoriga) mos keladi. ). Agar dasturchi takrorlanishlar soni oldindan ma'lum bo'lmagan va asosan cheksiz bo'lishi mumkin bo'lgan while loop operatoridan foydalanishni boshlasa, u qisman rekursiv funktsiyalar sinfiga o'tadi. Keling, ibtidoiy rekursiv bo'lgan bir qator taniqli arifmetik funktsiyalarni ko'rsataylik. Ikkita natural sonni qo'shish funktsiyasini ikkita o'zgaruvchining ibtidoiy rekursiv funktsiyasi deb hisoblash mumkin, bu funktsiyalarga ibtidoiy rekursiya operatorini qo'llash natijasida olingan, ikkinchisi esa asosiy funktsiyani asosiyga almashtirish orqali olinadi. funktsiya: Ikkita natural sonni ko'paytirishni ikkita o'zgaruvchining ibtidoiy rekursiv funktsiyasi deb hisoblash mumkin, bu ibtidoiy rekursiya operatorini funktsiyalarga qo'llash natijasida olingan, ikkinchisi esa asosiy funktsiyalarni almashtirish va qo'shish funktsiyasiga ega bo'lish: Ikki natural son () ning nosimmetrik farqini (farqning mutlaq qiymati) ikkita o'zgaruvchining ibtidoiy rekursiv funktsiyasi deb hisoblash mumkin, bu quyidagi almashtirishlar va ibtidoiy rekursiyalarni qo'llash orqali olingan: Keling, funktsiyalarning superpozitsiyasi (yoki qoplamasi) kontseptsiyasi bilan tanishib chiqaylik, u berilgan funktsiyani argumenti o'rniga boshqa argumentdan funktsiyani almashtirishdan iborat. Masalan, funktsiyalarning superpozitsiyasi funktsiyani beradi, shunga o'xshash funktsiyalar olinadi Umuman olganda, biz funktsiyani ma'lum bir mintaqada, funktsiyani esa mintaqada va uning qiymatlarini hammasini o'z ichiga olamiz deb o'ylaymiz, keyin z o'zgaruvchisi, ular aytganidek, y orqali va o'zi funktsiyadir. Berilgan ma'lumot uchun birinchi navbatda unga mos keladigan narsani toping (Y dan Y qiymatining belgisi bilan tavsiflangan qoidaga muvofiq, keyin esa mos keladigan y qiymatini o'rnating (qoida bo'yicha, uning qiymati belgi bilan tavsiflanadi va tanlangan x ga mos deb hisoblanadi. Funktsiya yoki murakkab funktsiyadan kelib chiqadigan funktsiya funktsiyalarning superpozitsiyasi natijasidir Funktsiya qiymatlari funktsiya aniqlangan Y mintaqasidan tashqariga chiqmaydi degan taxmin juda muhim: agar u o'tkazib yuborilgan bo'lsa, bema'ni bo'lib chiqishi mumkin. Masalan, biz faqat x qiymatlarini hisobga olamiz deb faraz qilsak, aks holda bu ibora mantiqiy bo'lmaydi. Bu erda funktsiyani kompleks sifatida tavsiflash funksiyaning z ning x ga bog'liqligi bilan emas, balki bu bog'liqlikni aniqlash usuli bilan bog'liqligini ta'kidlashni foydali deb bilamiz. Masalan, So'ngra y uchun ruxsat bering Bu erda funksiya murakkab funksiya shaklida berilgan bo'lib chiqdi. Endi funktsiyalarning superpozitsiyasi kontseptsiyasi to'liq aniqlanganidan so'ng, biz tahlilda o'rganiladigan funktsiyalar sinflarining eng oddiylarini aniq tavsiflay olamiz: bular, birinchi navbatda, yuqorida sanab o'tilgan elementar funktsiyalar, so'ngra ulardan olingan funktsiyalar. ular to'rtta arifmetik operatsiyalar va superpozitsiyalar yordamida ketma -ket cheklangan marta ishlatilgan. Ular cheklangan shaklda boshlang'ichlar bilan ifodalanishi aytiladi; ba'zida ularning hammasini elementar deb ham atashadi. Keyinchalik, yanada murakkab analitik apparatni (cheksiz ketma -ketliklar, integrallar) o'zlashtirgan holda, biz tahlilda ham muhim rol o'ynaydigan, lekin elementar funktsiyalar sinfidan tashqariga chiqadigan boshqa funktsiyalar bilan tanishamiz. Ilmiy hamjamiyatda bu mavzu bo'yicha keng tarqalgan hazil bor, "chiziqsizlik" ni "filsiz" bilan taqqoslashadi-"fil" dan boshqa barcha jonzotlar "fil bo'lmaganlar" dir. O'xshashlik shundaki, bizni o'rab turgan dunyodagi ko'pgina tizimlar va hodisalar chiziqli emas, bir nechta istisnolar. Shunga qaramay, maktabda bizga "chiziqli" fikrlashni o'rgatishadi, bu juda yomon, chunki biz koinotning chiziqli bo'lmaganligini, uning jismoniy, biologik, psixologik yoki ijtimoiy jihatlarini idrok etishga tayyorligimiz nuqtai nazaridan. Chiziqsizlik o'z -o'zidan atrofdagi dunyoni bilishning asosiy qiyinchiliklaridan birini to'playdi, chunki oqibatlari, ularning umumiy massasi, sabablarga mutanosib emas, o'zaro ta'sir qilishda ikkita sabab qo'shimchali emas, ya'ni oqibatlari ko'proq oddiy superpozitsiyadan ko'ra murakkabroq, sabablar vazifalari. Ya'ni, bir vaqtning o'zida ta'sir qiladigan ikkita sababning mavjudligi va ta'siridan kelib chiqadigan natija, har bir sabab alohida, boshqa sabab bo'lmasa, olingan natijalar yig'indisi emas. Ta'rif 9. X ning ba'zi oralig'ida Z qiymatlar to'plamiga ega rf (x) funktsiyasi aniqlanadi va Z to'plamda y = f (z) funktsiyasi aniqlanadi, u holda y funktsiyasi murakkab funktsiyadir. x (yoki funksiyaning superpozitsiyasi), va z o'zgaruvchisi - murakkab funktsiyaning oraliq o'zgaruvchisi. Nazoratni boshqaruvning uchta klassik funktsiyalari - buxgalteriya hisobi, nazorat va tahlil (retrospektiv) ning superpozitsiyasi sifatida qarash mumkin. Boshqaruvning yaxlit funktsiyasi sifatida nazorat qilish nafaqat echimni tayyorlashga, balki tegishli boshqaruv vositalaridan foydalangan holda uning bajarilishini nazorat qilishni ham ta'minlaydi. Ma'lumki / 50 /, har qanday vaqtinchalik funktsiyani turli davrlar, amplitudalar va fazalar bilan oddiy harmonik funktsiyalarning superpozitsiyasi (to'plami) sifatida ko'rsatish mumkin. Umuman olganda, P (t) = f (t), Vaqtinchalik yoki impulsli javob eksperimental tarzda aniqlanadi. Qachonki ular superpozitsiya usulida ishlatilsa, kirish harakatining tanlangan modeli avval elementar "vaqtning funktsiyalari" ga kengaytiriladi, so'ngra ularga berilgan javoblar umumlashtiriladi. Oxirgi operatsiyani ba'zan konvulsiya, ifodalardagi integrallar (24) ) .. (29) - konvolyutsiyali integrallar, sodda integrandli tanlanadi. Bu teorema shartli ekstremum muammosini shartsiz ekstremum muammosining superpozitsiyasiga kamaytiradi. Haqiqatan ham, biz R (g) funktsiyasini aniqlaymiz. Superpozitsiya ((> (f (x)), bu erda y (y)-bitta o'zgaruvchining kamaymaydigan qavariq funktsiyasi, f (x)-qavariq funktsiya, qavariq funktsiya. Misol 3.29. Fig. 3.25-rasmda XA va X tez-tez aniqlovchiga mos keladigan holat uchun superpozitsiya va cho'zish siljishi bilan olingan ikkita natija ko'rsatilgan. Ko'rinib turibdiki, a'zolar orasida superpozitsiya ko'pincha uchraydigan qadriyatlarni ajratadi. Qirqish va cho'zish holatida biz natijani tez-tez qiymatiga ega bo'lgan yangi kvantning paydo bo'lishi sifatida talqin qilishimiz mumkin, agar xohlasak, uni taxmin qilish mumkin, masalan, tez-tez. Shuni ko'rsatingki, qat'iy ravishda ortib borayotgan funktsiyani va ba'zi bir afzalliklar aloqasini ifodalovchi yordamchi funktsiyani superpozitsiyasi ham ushbu afzallikni ifodalovchi yordamchi funktsiyadir. Quyidagi funktsiyalardan qaysi biri bunday o'zgarish bo'lishi mumkin Birinchisi (2)-bu qoidaning yozilishidan boshqa narsa emas, unga ko'ra monotonik ravishda kamaymaydigan mutlaq uzluksiz funktsiyalar oilasiga mansub har bir F (x) funktsiya bitta va bitta uzluksiz w (j) funktsiyasi bilan bog'liq. . Bu qoida chiziqli, ya'ni. superpozitsiya printsipi uning uchun to'g'ri Dalil. Agar F xaritasi uzluksiz bo'lsa, M0 funktsiyasi uzluksiz funktsiyalarning superpozitsiyasi sifatida uzluksizdir. Bayonotning ikkinchi qismini isbotlash uchun funktsiyani ko'rib chiqing Murakkab e funktsiyalari (superpozitsiya) Funktsional transformatsiyalar usuli evristik yondashuvni qo'llashni ham o'z ichiga oladi. Masalan, B va C operatorlari sifatida logarifmik transformatsiyalardan foydalanish aniqlanadigan modellarni tuzish uchun axborot mezonlariga va axborot nazariyasida kuchli vositadan foydalanishga olib keladi. V operatori funktsiyaga ko'paytirish operatorlarining superpozitsiyasi bo'lsin, (.) Va K0 () funktsiyasi bo'yicha siljish, operator S - operator Bu erda, umumiy ma'noda, (1) - (3) bir qator variatsion muammolarni echish natijalari taqdim etiladi. Ular 1962-1963 yillarda, usulning texnologiyasi endigina shakllana boshlagan va sinovdan o'tkazilayotganda, ketma-ket chiziqlanish (19-21) usuli bilan hal qilingan. Shuning uchun biz faqat ba'zi tafsilotlar haqida to'xtalamiz. Birinchidan, shuni ta'kidlaymizki, C va C2 funktsiyalari yordamchi funktsiyalarning superpozitsiyasi bo'lgan jadvalda ko'rsatilgan funktsiyalarni o'z ichiga olgan ancha murakkab ifodalar bilan aniqlangan. Shuning uchun, konjugat tizimini echishda ph = -fx jadvalda ko'rsatilgan funktsiyalar yordamida. Odatda, bunday jadvallar mustaqil argument oralig'idagi tugunlar to'plamining oz sonli qiymatlarini o'z ichiga oladi va ular orasidagi funktsiya chiziqli interpolyatsiyalanadi, chunki aniqroq interpolatsiya usullaridan foydalanish oqlanmagan. jadval qiymatlarining o'zi (qoida tariqasida jadvallar eksperimental xarakterdagi funktsional bog'liqliklarni ko'rsatadi). Biroq, bizning maqsadlarimiz uchun bizga f (x, u) funktsiyalarini ajratish kerak, shuning uchun biz jadvalda berilgan funktsiyani bajarish uchun silliq usullarni afzal ko'rishimiz kerak (masalan, spline yordamida). Endi (YES va (q chastotali miqdor o'lchagichlarining ba'zi qiymatlariga mos keladigan ixtiyoriy funktsiyalar bo'lsin. 3.23-rasmda bu funktsiyalarga mos keladigan ikkita bir kamarli egri chiziqlar ko'rsatilgan. Ularning superpozitsiyasi natijasi-kesilgan chiziq bilan ko'rsatilgan ikki kamarli egri chiziq). Uning ma'nosi nima, agar, masalan, (YES kamdan -kam hollarda va (q - ko'pincha, F -ni aniqlashning ushbu usulining afzalligi shundaki, monotonik transformatsiyalarda a'zolik funktsiyasining shakli keskin o'zgarmaydi. Uning bir xilligi yoki monotonligi saqlanib qoladi va yangi funktsiya shaklidan (2.16) o'tish trapezoidal shaklga ega, keyin chiziqli superpozitsiya (2.15) ham trapezoidal noaniq sondir (bu hisoblashning hisoblash qoidasi yordamida osonlikcha isbotlanadi). Va a'zolik funktsiyalari bilan bajariladigan operatsiyalarni ularning tepaliklari bilan kamaytirish mumkin. Agar biz (2.16) trapezoidal sonni (ab a2, az, a4) deb belgilasak, bu erda trapetsiya tepaliklarining abssissalariga mos keladi. 2 funktsiya bo'lsin: : A → B va g: D → F G funksiyaning D sohasi f (DB) funktsiyasining qiymatlar diapazoniga tegishli bo'lsin. Keyin yangi funktsiyani aniqlash mumkin - superpozitsiya (kompozitsiya, murakkab funksiya) f va g funktsiyalari: z= g( (x)). Misollar. f (x) = x 2, g (x) = e x. f: R → R, g: R → R . (g (x)) = e 2x, g ( (x)) =. Ta'rif
Tarkibi xususiyatlari
Agar F= id X bu identifikatsiya xaritasi X, ya'ni . Agar G= id Y bu identifikatsiya xaritasi Y, ya'ni . Qo'shimcha xususiyatlarHisoblanadigan va sanab bo'lmaydigan to'plamlar. Ikkita cheklangan to'plam teng miqdordagi elementlardan iborat, agar bu to'plamlar o'rtasida yakka yozishmalar o'rnatilsa. Cheklangan to'plam elementlarining soni - bu to'plamning kardinalligi. Cheksiz to'plam uchun siz butun to'plam va uning qismi o'rtasida birma-bir yozishmalar o'rnatishingiz mumkin. Cheksiz to'plamlarning eng soddasi - N. Ta'rif. A va B to'plamlar chaqiriladi ekvivalent(AB), agar ular o'rtasida birma-bir yozishmalar o'rnatilishi mumkin bo'lsa. Agar ikkita cheklangan to'plam teng bo'lsa, ular bir xil miqdordagi elementlardan iborat. Agar A va B ekvivalent to'plamlari o'zboshimchalik bilan bo'lsa, unda ular A va B bir xil deyishadi kuch... (kuch = ekvivalent). Cheklangan to
Download 25.4 Kb. Do'stlaringiz bilan baham: 
|