10-amaliy ishi. ”Ajrat va hukmronlik qil” prinsipi buyicha ishlaydigan algoritmlarni loyihalash
Yüklə 0,61 Mb. Pdf görüntüsü
|
1 2
10-amaliy| 10-AMALIY ISHI. ”Ajrat va hukmronlik qil” prinsipi buyicha ishlaydigan algoritmlarni loyihalash Paradigma "ajratish va hukmronlik qilish": 1. Kirish ma'lumotlarini kichikroq kichik kichik topshiriqlarga bo'ling. Vazifani bir xil vazifaning kichik nusxalarini ifodalovchi bir nechta kichik topshiriqlarga ajratish. 2. Pastki vazifalarni qayta tiklash usuli bilan hal qiling. Recursive ularning qaror bilan sub-vazifalari ustidan hukmronlik. Subzadalarning o'lchamlari etarlicha kichik bo'lsa, bunday kichik vazifalar to'g'ridan-to'g'ri hal qilinishi mumkin. 3. Boshlang'ich muammoni hal qilishda kichik vazifalar echimlarini birlashtirish. Bir muammoni hal qilishda kichik vazifalar echimlarini birlashtirish. Misol uchun, MergeSort algoritmida (birlashma bilan tartiblash) "ajratish" bosqichi kirish satrini chap va o'ng yarmiga ajratadi, "qaror qabul qilish" bosqichi chap va o'ng pastki qatlamlarni ajratish uchun ikkita rekursiv chaqiruvdan foydalanadi va "birlashtirish" bosqichi birlashma muntazamligi bilan amalga oshiriladi. MergeSort algoritmida va boshqa ko'plab algoritmlarda bu so'nggi qadam eng ixtirochilikni talab qiladi. Bundan tashqari, birinchi bosqichda (Quicksort) yoki rekursiv chaqiruvlarning spetsifikatsiyasida ixtiro qilish kerak bo'lgan "ajratish va boshqarish" kabi algoritmlar mavjud. 2.Integer ko'paytirish vazifasi Tamsayı ko'paytirish vazifasida kirish ma'lumotlari ikkita n-son raqamlari bo'lib, ularni x va y bilan belgilaymiz.raqamlarning soni (uzunligi) x va y har qanday ijobiy tamsayı bo'lishi mumkin. Misol uchun, kriptografik ilovalar juda katta sonlar bilan manipulyatsiya qilinadi. Tamsayı ko'paytirish vazifasida kerakli chiqish x × y mahsulotining natijasidir. Kirish: ikki n-raqamli salbiy bo'lmagan butun son, x va y. Chiqish: mahsulot x × y. Biz aniq hisoblash muammosini aniqladik, endi uni hal qiladigan algoritmni tasvirlab beramiz - boshlang'ich maktabda o'rganilgan algoritm. Ushbu algoritmning ishlashini "ibtidoiy operatsiyalar" soni bilan baholaymiz, u har bir kirish raqamidagi n belgilarining soni sifatida ishlaydi. Keling, ibtidoiy operatsiyani quyidagilardan biri sifatida tasavvur qilaylik: ikkita bitta raqamli (n=1 ) raqamlarni qo'shish; ikki bitta raqamli raqamlarni ko'paytirish yoki raqamning boshiga yoki oxiriga nol qo'shish. Xotirani yangilash uchun x=5678ni y= 1234 (bu erda n = 4) bilan ustunga ko'paytirishning aniq misolini ko'rib chiqing. Shakl. 1. Ustunda tamsayı ko'paytirish algoritmi Birinchidan, algoritm birinchi raqamning "qisman mahsuloti" ni va ikkinchi raqamning oxirgi raqamini hisoblab chiqadi: 5678 * 4 = 22 712. Ushbu qisman ishni hisoblash birinchi raqamning har bir sonini 4 bilan ko'paytirishga, natijaning eng kichik toifasini qayd etishga, yuqori toifani (keyingi bosqichga"o'tkazish") va keyingi ko'paytirishda ushbu "o'tkazmalar" (agar mavjud bo'lsa) qo'shilishi bilan kamayadi. Keyingi qisman ishni hisoblashda (5678 * 3 = 17 034) biz natijani chap tomonga siljitib (aslida oxirida "0" qo'shib) xuddi shunday qilamiz. Va shuning uchun qolgan ikkita qisman ish uchun. Yakuniy qadam barcha qisman ishlarni to'ldirishdir. Shunday qilib, hech qachon noto'g'ri javob bo'lmaydi va algoritm o'chirilmaydi. Operatsiyalar sonini tahlil qilish. Ilgari ustunga ko'paytirish tartibini bajarish uchun zarur bo'lgan ibtidoiy operatsiyalar sonini muhokama qilmadilar. Bizning misolimizda, birinchi qisman mahsulotni hisoblash uchun 4, 5, 6, 7, 8 raqamlarining har birini ko'paytirdik. Ular to'rtta ibtidoiy operatsiya. Bundan tashqari, biz bir nechta qo'shimchalarni o'tkazdik. Umuman olganda, qisman ishni hisoblash ko'paytirishni (bir belgi bilan bir marta ko'paytirish) va n qo'shimchalaridan ko'p bo'lmagan (bir belgidan ko'p bo'lmagan) sabab bo'ladi. Hammasi bo'lib 2n ibtidoiy operatsiyalaridan ko'p emas. Birinchi qisman ish boshqalardan farq qilmaydi va ularning har biri 2n dan ortiq operatsiyalarni talab qilmaydi. N qisman asarlar mavjud bo'lgani uchun-ikkinchi raqamning har bir belgisi uchun - ularning barchasini hisoblash n 2 2n=2n^2 ibtidoiy operatsiyalaridan ko'proq narsani talab qiladi. Yakuniy javobni hisoblash uchun biz hali ham barcha qisman ishlarni birlashtirishimiz kerak, ammo buning uchun teng miqdordagi operatsiyalar talab etiladi (boshqa 2n^2 dan oshmasligi kerak). Xulosa: Ushbu algoritmning qanday ishlashi haqida gapirganda, asl multiplikatorlar uzoq va uzoqlashib borayotganligi sababli, amalga oshirilgan operatsiyalar hajmi kvadratik ravishda o'sib borayotganini ko'rib turibmiz. Agar siz dastlabki omillarning uzunligini ikki barobarga oshirsangiz, kerakli operatsiyalar hajmi 4 marta sakrab chiqadi. Ularning uzunligini 4 marta oshiring va u 16 marta sakrab chiqadi va hokazo. Eng yaxshi erishish mumkinmi? Biz ushbu amaliyotni noyob yoki kamida ikkita raqamni ko'paytirishning eng yaxshi usuli sifatida qabul qilishimiz mumkin. Agar biz jiddiy algoritm dizaynerlari bo'lishni istasak, unda bu uyatchanlikni engib o'tish kerak bo'ladi. Aho, Xopkroft va Ulman algoritmlari bo'yicha klassik kitob, algoritmlarni ishlab chiqish uchun bir qator usullarni qayta ko'rib chiqqandan so'ng, quyidagilarni aytadi: "Algoritmlarni yaxshi ishlab chiquvchi uchun, ehtimol, eng muhim printsip shartnomani bekor qilishdir". "Men sizlarga barcha azizlar uchun so'rayman, avval oddiy narsani o'rganing, keyin esa murakkab" Epiktetga o'ting. (Qamchi. Dasturlash san'ati 1 jild): Har doim o'zingizga savol bering: yaxshiroq erishish mumkinmi? Hisoblash vazifasini aniq yoki to'g'ridan-to'g'ri hal qilishda bu masala ayniqsa muhimdir. Ilgari, siz ustunga oddiy klassik ko'paytirish algoritmini yaratishdan ko'ra, yechim yo'lini yaxshiroq qurish mumkinmi, deb hayron bo'lmaysiz. Bu savolni berish va unga javob berish vaqti keldi. Karatsubaning Ko'payishi Algoritmlarni ishlab chiqish hayratlanarli darajada ko'p qirrali sohadir. Albatta, uchinchi sinfda o'qiganingizdan tashqari, ikkita tamsayı ko'paytirishning boshqa qiziqarli usullari mavjud. Ushbu bo'limda Karatsubaning ko'payishi deb ataladigan usullardan biri tasvirlangan. 1960da Andrey Kolmogorov kibernetikaning matematik muammolariga bag'ishlangan seminar o'tkazdi. Seminarda ko'rib chiqilayotgan vazifalardan biri ikki n-bit tamsayılarning ko'payishi edi. O'sha paytda ko'paytirish asosiy ma'lum usuli algoritmik amalga oshirish O(n^2)elementar operatsiyalar (qo'shimchalarning yoki bir-bit soni ko'payish) talab "ustunga" ko'paytirish edi. Kolmogorov "ustunga" ko'paytirish har qanday ko'paytirish usuli ish vaqti qiymati maqsadida n^2 kam bo'lmagan ma'noda ikki raqamlarni ko'paytirish uchun optimal algoritm deb faraz ilgari surdi. "N ^ 2 gipotezasi" ning ishonchliligi shuni ko'rsatdiki, "ustunga" ko'paytirish usuli kamida to'rt ming yil davomida ma'lum bo'lgan va agar tezroq ko'paytirish usuli bo'lsa, u allaqachon topilgan bo'lishi mumkin. Biroq, bir hafta o'tgach, 23 yoshli Anatoliy Karatsuba u(n^log3) ish vaqtini baholash bilan ikki n- raqamli sonlarni ko'paytirishning yangi usulini taklif qildi va shu bilan "n^2 farazini" Karatsuba usuli ikkilik qidiruv, tezkor tartiblash va boshqalar kabi algoritmlar bilan bir qatorda "bo'linish va hukmronlik" tipidagi algoritmlarga ishora qiladi. Muayyan misol Karatsubaning ko'payishini his qilish uchun, avvalgi misolimizdan x=5678 va y=1234 bilan yana foydalanaylik. Ushbu yangi algoritm sizga juda sirli ko'rinishi kerak, bu esa quyonni shlyapadan olib chiqish markaziga o'xshaydi. Karatsubaning ko'payishi va nima uchun ishlayotganligi haqida aniq tushuntirishni ko'rib chiqing. Endi asosiy narsa-bu misolda baholash uchun, hisoblash muammolarni hal qilish uchun turli xil variantlar bir ajoyib tasavvur qator bor, xususan integer ko'paytirish. Birinchidan, a va b kabi raqamlarning birinchi va ikkinchi yarmini alohida- alohida ko'rib chiqamiz. Bizning misolimiz uchun biz a=56,b=78 ni olamiz, xuddi shu tarzda y bilan harakat qilamiz, bu erda c va d navbati bilan y sonining birinchi va ikkinchi yarmini, ya'ni C = 12 va d= 34 (shakl.2). Keyin biz faqat ikkita raqamli a,b,C,d raqamlarini o'z ichiga olgan operatsiyalar ketma-ketligini bajaramiz va nihoyat sehrli tarzda barcha elementlarni birlashtiramiz. Bunday belgilarda x va y raqamlari mahsuloti qayta yozilishi mumkin х × у = (𝑎𝑅 + 𝑏) ∙ (𝑐𝑅 + 𝑑) = Yüklə 0,61 Mb. Dostları ilə paylaş:
|
1 2