Mustaqil ish Mavzu: Rekursiv algoritmlar va ularning tahlili. Rekursiya doir misollar Bajardi: Urozov G’ Guruh: tt2M21-01 Reja
Download 121 Kb.
|
gayrat
|
Mustaqil ish Mavzu:Rekursiv algoritmlar va ularning tahlili. Rekursiya doir misollar Bajardi: Urozov G’ Guruh: TT2M21-01 Reja: Rekursiv algoritmlarga misollar Rekursiv algoritmlarni tahlil qilish Almashtirish (takrorlash) usuli Matematik induksiya usuli Asosiy usul Quyruqning rekursiyasi va pastadir Dasturlashdagi rekursiya. Algoritmlarni tahlil qilish Rekursiya - bu ob'ektning o'zini taqlid qilish xususiyati. Agar uning qismlari butun ob'ekt bilan bir xil ko'rinadigan bo'lsa, ob'ekt rekursivdir. Rekursiya matematikada va dasturlashda juda keng qo'llaniladi: ma'lumotlar tuzilmalari: grafani (xususan, daraxtlar va ro'yxatlar) bitta tugun va subgraf (kichikroq grafik) to'plami sifatida ko'rish mumkin; mag'lubiyat birinchi belgidan va pastki satrdan iborat (kichikroq satr); dekorativ kabi dizayn naqshlari [1]. Dekorativ ob'ektga boshqa bezak beruvchilar ham kirishi mumkin. Rekursiv naqshlar Makkolm Smit tomonidan batafsil o'rganilib, kitobida umumiy dizayn naqshini - Recursion [2] ni ta'kidlab o'tdi; rekursiv funktsiyalar (algoritmlar) o'zlarini chaqirishadi. Maqola rekursiv algoritmlarning murakkabligini tahlil qilishga bag'ishlangan, kerakli matematik ma'lumotlar berilgan, misollar ko'rib chiqilgan. Bundan tashqari, rekursiyani ilmoq, quyruq rekursiyasi bilan almashtirish imkoniyati tasvirlangan. Rekursiv algoritmlarga misollar Rekursiv algoritm har doim muammoni tarkibiy jihatdan asl masala bilan bir xil, ammo oddiyroq qismlarga ajratadi. Subtaskalarni echish uchun funktsiya rekursiv deb nomlanadi va ularning natijalari qandaydir birlashtiriladi. Muammoning bo'linishi faqat uni darhol hal qilib bo'lmaganda (u juda murakkab) yuzaga keladi. Masalan, massivni qayta ishlash vazifasini ko'pincha uning qismlarini qayta ishlashga kamaytirish mumkin. Qismlarga bo'lish ular elementar bo'lguncha amalga oshiriladi, ya'ni. natijani yanada soddalashtirmasdan olish uchun etarlicha sodda. Massiv elementlarini toppish начало; search(array, begin, end, element) ; выполняет поиск элемента со значением element в массиве array между индексами begin и end если begin > end результат := false; элемент не найден иначе если array[begin] = element результат := true; элемент найден иначе результат := search(array, begin+1, end, element) конец; вернуть результат Algoritm asl massivni ikki qismga ajratadi - birinchi element va boshqa elementlar massivi. Ajratish talab qilinmaydigan ikkita oddiy holat mavjud - barcha elementlar qayta ishlangan yoki birinchi element kerakli. Qidiruv algoritmida massivni boshqa yo'l bilan ajratish mumkin edi (masalan, yarmida), lekin bu samaradorlikka ta'sir qilmaydi. Agar qator tartiblangan bo'lsa, uni ikkiga bo'lish maqsadga muvofiqdir, chunki har bir qadamda qayta ishlangan ma'lumotlar miqdori ikki baravarga kamaytirilishi mumkin. Bir qatorda ikkilik qidiruv
Fibonachchi raqamlarini hisoblash Fibonachchi raqamlari rekursiv ifoda bilan aniqlanadi, ya'ni. shunday qilib elementni hisoblash oldingi elementlardan ifodalangan: F0=0,F1=1,Fn=Fn−1+Fn−2,n>2. начало; fibonacci(number) если number = 0 конец; вернуть 0 если number = 1 конец; вернуть 1 fib_1 := fibonacci(number-1) fib_2 := fibonacci(number-2) результат := fib_1 + fib_2 конец; вернуть результат Tez saralash Har bir qadamda tez saralash algoritmi elementlardan birini (pivot) tanlaydi va unga nisbatan qatorni rekursiv ravishda qayta ishlanadigan ikki qismga ajratadi. Burilishdan kichikroq elementlar bir qismga, qolganlari esa boshqa qismga joylashtiriladi. Saralashni birlashtirish Birlashtirishni saralash algoritmi buyurtma qilingan massivlarni (yoki ro'yxatlarni) tezda birlashtirish qobiliyatiga asoslanadi, natijada natija buyurtma qilinadi. Algoritm asl qatorni tasodifiy ikkiga (odatda yarmida) ajratadi, ularni rekursiv tartibda saralaydi va natijani birlashtiradi. Bo'linish, massivning kattaligi birdan kattaroq bo'lganda sodir bo'ladi, chunki bo'sh qator va bitta element massivi har doim saralanadi. Birlashtirishning har bir bosqichida har ikkala ro'yxatdan birinchi ishlov berilmagan element tanlanadi. Ob'ektlar taqqoslanadi, natijada ularning eng kichigi qo'shiladi va ishlov berilgan deb belgilanadi. Birlashtirish ro'yxatlarning biri bo'sh bo'lguncha sodir bo'ladi. начало; merge(Array1, Size1, Array2, Size2) ; исходные массивы упорядочены ; в результат формируется упорядоченный массив длины Size1+Size2 i := 0, j := 0 вечный_цикл если i >= Size1 дописать элементы от j до Size2 массива Array2 в конец результата выход из цикла если j >= Size2 дописать элементы от i до Size1 массива Array1 в конец результата выход из цикла если Array1[i] < Array2[j] результат[i+j] := Array1[i] i := i + 1 иначе (если Array1[i] >= Array2[j]) результат[i+j] := Array2[j] j := j + 1 конец; вернуть результат Rekursiv algoritmlarni tahlil qilish Tsiklik algoritmlarning murakkabligini tahlil qilishda takrorlanishning murakkabligi va ularning soni eng yomon, eng yaxshi va o'rtacha holatlarda hisoblanadi [4]. Biroq, ushbu yondashuvni rekursiv funktsiyaga tatbiq etish ishlamaydi, chunki natija takrorlanish munosabati bo'ladi. Masalan, massivda elementni topish funktsiyasi uchun: Tsearchn={O(1)O(1)+O(Tsearchn−1)n=0n>0 Takroriy munosabatlar bizga murakkablikni baholashga imkon bermaydi - biz ularni shunchaki taqqoslay olmaymiz, shuning uchun tegishli algoritmlarning samaradorligini taqqoslaymiz. Takrorlanish munosabatini tavsiflovchi formulani olish kerak - buning universal usuli bu almashtirish usuli yordamida formulani tanlash, so'ngra matematik induktsiya usuli bilan formulaning o'zaro bog'liqligini isbotlashdir. Almashtirish (takrorlash) usuli U yangi ifodalarni olish uchun ifodadagi takrorlanadigan qismni ketma-ket almashtirishdan iborat. O'zgartirish umumiy printsipni tushunib, uni takrorlanmaydigan formulada ifodalash mumkin bo'lgunga qadar amalga oshiriladi. Masalan, massivda elementni topish uchun: Tsearchn=O(1)+O(Tsearchn−1)=2×O(1)+O(Tsearchn−2)=3×O(1)+O(Tsearchn−3) Можно предположить, что Tsearchn=Tsearchn−k+k×O(1), но тогда Tsearchn=Tsearch0+n×O(1)=O(n) Biz formulani chiqardik, ammo birinchi qadam taxminni o'z ichiga oladi, ya'ni. formulaning takrorlanadigan ifodaga muvofiqligini isbotlovchi dalil yo'q - matematik induksiya usuli isbot olishga imkon beradi. Matematik induksiya usuli
bir yoki bir nechta maxsus holatlar uchun bayonotni tasdiqlash P0, P1,…; Pn + 1 ning isboti Pn (induktiv gipoteza) va maxsus holatlarning haqiqatidan kelib chiqadi. Qidiruv funktsiyasining murakkabligini baholashda taxminning to'g'riligini isbotlaylik ( Tsearchn=(n+1)×O(1)): Tsearch1=2×O(1) верно из условия (можно подставить в исходную рекуррентную формулу); допустим истинность Tsearchn=(n+1)×O(1); требуется доказать, что Tsearchn+1=((n+1)+1)×O(1)=(n+2)×O(1) подставим n+1 в рекуррентное соотношение: Tsearchn+1=O(1)+Tsearchn; в правой части выражения возможно произвести замену на основании индуктивной гипотезы: Tsearchn+1=O(1)+(n+1)×O(1)=(n+2)×O(1); утверждение доказано. Ko'pincha, bunday dalil juda mashaqqatli jarayondir, ammo almashtirish usuli yordamida naqshni aniqlash yanada qiyinroq. Shu munosabat bilan umumiy usul deb nomlangan usul qo'llaniladi Takrorlanish munosabatlarini hal qilishning umumiy (asosiy) usuli Umumiy usul universal emas; masalan, Fibonachchi raqamlarini hisoblash uchun yuqoridagi algoritmning murakkabligini baholash uchun foydalanib bo'lmaydi. Biroq, bu ikkiga bo'linish va zabt etish usulidan foydalanish uchun amal qiladi. Tn=a⋅T(nb)+fn;a,b=const,a≥1,b>1,fn>0,∀n. Ushbu turdagi tenglamalar, agar asl masala har biri nb elementlarini qayta ishlaydigan kichik topshiriqlarga bo'linadigan bo'lsa olinadi. fn - muammoni qismlarga ajratish va echimlarni birlashtirish operatsiyalarining murakkabligi. Aloqaning shakliga qo'shimcha ravishda, umumiy usul fn funktsiyasiga cheklashlarni keltirib chiqaradi, uchta holatni ajratib turadi: ∃ε>0:fn=O(nlogba—ε)⇒Tn=Θ(nlogba); fn=Θ(nlogba)⇒Tn=Θ(nlogba⋅logn); ∃ε>0,c<1:fn=Ω(nlogba+ε),fnb≤c⋅fn⇒Tn=Θ(fn). Har bir holat bo'yicha bayonotlarning to'g'riligi rasmiy ravishda isbotlandi [6]. Rekursiv algoritmni tahlil qilish muammosi endi asosiy teoremaning holatini aniqlashga qisqartirildi, bu esa takrorlanish munosabatlariga to'g'ri keladi. Ikkilik qidiruv algoritmini tahlil qilish
Tahlilni amalga oshirish uchun almashtirish usuli yoki quyidagi mulohazalardan foydalanish mumkin: har bir rekursiv chaqiruv kirish ma'lumotlarining o'lchamlarini bittaga qisqartiradi, shuning uchun ularning hammasi n (n) bo'ladi, ularning har biri murakkabligi O (1) ). Keyin Tsearchn = n⋅O (1) = O (n). Birlashtirish tartiblash algoritmini tahlil qilish
Ro'yxatni qayta ishlashda bo'linish Θ (n) operatsiyalarni bajarishni talab qilishi mumkin, va massiv uchun bu doimiy vaqt (Θ (1)) vaqtida amalga oshiriladi. Biroq, har qanday holatda ham (n) natijalarga qo'shilish uchun sarflanadi, shuning uchun $ fn = n $. Teoremaning ikkinchi holatidan foydalaniladi: TmergeSortn=Θ(nlogba⋅logn)=Θ(n⋅logn). Tez saralashning murakkabligini tahlil qilish Yaxshiyamki, asl massiv ikki qismga bo'linadi, ularning har biri asl ma'lumotlarning yarmini o'z ichiga oladi. Ajratish uchun n ta operatsiya kerak bo'ladi. Natija tuzishning murakkabligi ishlatiladigan ma'lumotlar tuzilmalariga bog'liq - O (n) massivi uchun, bog'langan ro'yxat uchun O (1). a = 2, b = 2, fn = b, ya'ni algoritmning murakkabligi birlashma saralash bilan bir xil bo'ladi: TquickSortn = O (n⋅logn). Biroq, eng yomon holatda, massivning minimal yoki maksimal elementi doimiy ravishda mos yozuvlar sifatida tanlanadi. Keyin b = 1, demak biz yana asosiy teoremadan foydalana olmaymiz. Ammo, biz bilamizki, bu holda n rekursiv chaqiriqlar amalga oshiriladi, ularning har biri massivni qismlarga bo'linishini amalga oshiradi (O (n)) - bu TquickSortn = O (n2) algoritmining murakkabligini anglatadi. Quicksortni almashtirish bilan tahlil qilishda, shuningdek, eng yaxshi va yomon holatlarni alohida ko'rib chiqish kerak. Quyruq rekursiyasi va pastadir Rekursiv funktsiyalarning murakkabligini tahlil qilish tsikllarni baholashdan ko'ra ancha qiyinroq, lekin ko'chadan afzalroq bo'lishining asosiy sababi funktsiya chaqiruvining yuqori narxidir. Qo'ng'iroqdan keyin boshqaruv boshqa funktsiyaga o'tkaziladi. Boshqarishni o'tkazish uchun protsessor hozirda bajarilayotgan buyruqning sonini saqlaydigan dastur hisoblagichining qiymatini o'zgartirish kifoya - xuddi shu tarzda boshqarish algoritm tarmoqlariga uzatiladi, masalan shartli operator. Biroq, qo'ng'iroq faqat boshqaruvni uzatish emas, chunki chaqirilgan funktsiya o'z hisob-kitoblarini tugatgandan so'ng, boshqaruvni qo'ng'iroq qilingan nuqtaga qaytarishi va u erda qo'ng'iroqdan oldin mavjud bo'lgan mahalliy o'zgaruvchilar qiymatlarini tiklashi kerak. . Ushbu xatti-harakatni amalga oshirish uchun stack (call stack, call stack) ishlatiladi - qaytish uchun buyruq raqami va unga mahalliy o'zgaruvchilar haqida ma'lumotlar joylashtiriladi. Stek cheksiz emas, shuning uchun rekursiv algoritmlar uni to'ldirishi mumkin; har holda, u bilan ishlash uchun juda ko'p vaqt ketishi mumkin. Ba'zi hollarda rekursiv funktsiyani osongina tsikl bilan almashtirish mumkin, masalan, yuqorida muhokama qilingan qidirish va ikkilik qidiruv algoritmlari [4]. Ba'zi hollarda, ko'proq ijodiy yondashuv talab etiladi, lekin ko'pincha bunday almashtirish mumkin. Bundan tashqari, rekursiv chaqiruv funktsiya tomonidan amalga oshirilgan so'nggi operatsiya bo'lgan maxsus rekursiyaning turi mavjud. Shubhasiz, bu holda qo'ng'iroq qilish funktsiyasi natijani hech qanday o'zgartirmaydi, demak uning boshqaruvni qaytarishi mantiqsiz. Ushbu rekursiya quyruq rekursiyasi deb ataladi - kompilyatorlar uni avtomatik ravishda pastadir bilan almashtiradi. Ko'pincha, parametrni to'plash usuli [7] quyruq rekursiyasini amalga oshirishga yordam beradi, bu qo'shimcha argument-akkumulyator funktsiyasini qo'shishdan iborat bo'lib, unda natija to'planadi. Funksiya rekursiv chaqiruvdan oldin akkumulyator hisob-kitoblarini amalga oshiradi. Ushbu texnikadan foydalanishning yaxshi namunasi faktorial funktsiya: factn=n⋅fact(n−1)fact3=3⋅fact2=3⋅(2⋅fact1)=3⋅(2⋅(1⋅fact0))=6factn=factTailn,1factTailn,accumulator=factTail(n−1,accumulator⋅n)factTail3,1=factTail2,3=factTail1,6=factTail0,6=6 Keyinchalik murakkab misol sifatida, Fibonachchi raqamlarini hisoblash funktsiyasini ko'rib chiqing. Asosiy funktsiya iterator va ikkita akkumulyatorning dastlabki qiymatini (avvalgi ikkita Fibonachchi raqami) o'tkazishda to'plash parametri usulidan foydalanadigan yordamchi funktsiyani chaqiradi. начало; fibonacci(number) вернуть fibonacci(number, 1, 1, 0) конец начало; fibonacci(number, iterator, fib1, fib2) если iterator == number вернуть fib1 вернуть fibonacci(number, iterator + 1, fib1 + fib2, fib1) конец Yig'ish parametriga ega funktsiya, agar ko'rsatilgan raqamlar soni hisoblab chiqilgan bo'lsa, to'plangan natijani qaytaradi, aks holda u hisoblagichni ko'paytiradi, yangi Fibonachchi raqamini hisoblab chiqadi va rekursiv qo'ng'iroq qiladi. Optimallashtiruvchi kompilyatorlar funktsiya chaqiruvining natijasi o'zgarmagan holda funktsiya chiqishiga uzatilishini va uning o'rnini tsikl bilan almashtirishi mumkin. Ushbu uslub ayniqsa funktsional va mantiqiy dasturlash tillarida dolzarbdir, chunki dasturchi ularda tsiklik konstruktsiyalarni aniq ishlata olmaydi. Adabiyot Ko'p tarmoqli Qt-server. Iplar havzasi. Dekorativ naqsh [Elektron resurs] - kirish rejimi: https://pro-prof.com/archives/1390. Kirish sanasi: 21.02.2015. Jeyson Makkolm Smitning boshlang'ich dizayn naqshlari: Per. ingliz tilidan - M .: MChJ “I.D. Uilyams ”, 2013. - 304 p. Skiena S. Algoritmlari. Rivojlanish bo'yicha qo'llanma.-2-nashr: trans. inglizcha-SPb .: BHV-Peterburg, 2011.-720p.: kasal. Vasilev V.S. Algoritmlarning murakkabligini tahlil qilish. Misollar [Elektron resurs] - kirish rejimi: https://pro-prof.com/archives/1660. Kirish sanasi: 21.02.2015. A. Aho, J. Xopkroft, J. Ullman, ma'lumotlar tuzilmalari va algoritmlari, M., Uilyams, 2007. Miller, R. Ketma-ket va parallel algoritmlar: Umumiy yondashuv / R. Miller, L. Bokschi; per. ingliz tilidan - M .: BINOM. Bilimlar laboratoriyasi, 2006 y. - 406 p. Sergievskiy G.M. Funktsional va mantiqiy dasturlash: darslik. oliy o'quv yurtlari talabalari uchun qo'llanma. o'rganish. muassasalar / G.M. Sergievskiy, N.G. Volchenkov. - M.: "Akademiya" nashriyot markazi, 2010.- 320s. Algoritmlar va ma'lumotlar tuzilmalari bo'yicha kitoblar: [Elektron resurs] - kirish rejimi: https://pro-prof.com/books-algorithms. Kirish sanasi: 21.02. Download 121 Kb. Do'stlaringiz bilan baham: 
|