|
Toshkent axborot texnologiyalari universiteti algoritmlarni loyihalash fanidan
|
| bet | 2/6 | | Sana | 21.05.2024 | | Hajmi | 0,61 Mb. | | #246996 |
Bog'liq Ajrat va hukmronlik qilAjrat bosqichi. Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi.
Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.
Shu sababli, bo’lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab qolish mumkin: ajrat, hukmronlik qil, birlashtir. Oddiy, bittagina qadamdan iborat “bo’lib tashla va hukmronlik qil” algoritmi qanday ishlashini ko’raylik(1-rasm):
1-rasm. Bir qadamdan iborat “ajrat va hukmronlik qil” algoritmining ishlash printsipi.
Agar biz qadamlar sonini oshiradigan bo’lsak, paradigma tasviri quyidagicha ko’rinish oladi.
Agar biz qadamlar sonini oshiradigan bo’lsak, paradigma tasviri quyidagicha ko’rinish oladi
2- rasm. Ko’p qadamdan iborat “ajrat va hukmronlik qil” algoritmining ishlash
Ko'pincha muammoning optimal echimini topish uchun "bo'l va zabt et" paradigmasi qo'llaniladi. Uning asosiy g‘oyasi berilgan masalani ikki yoki undan ortiq o‘xshash, lekin soddaroq kichik masalalarga ajratish, ularni navbatma-navbat yechish va berilgan masalani yechish uchun ularning yechimlarini tuzishdan iborat. Etarli soddalik muammolari to'g'ridan-to'g'ri hal qilinadi. Masalan, n ta natural sondan iborat berilgan roʻyxatni saralash uchun uni har biri taxminan n/2 sondan iborat ikkita roʻyxatga ajrating, ularning har birini navbatma-navbat tartiblang va berilgan roʻyxatning tartiblangan versiyasini olish uchun ikkala natijani ham mos ravishda qoʻying (qarang. rasm). Ushbu yondashuv birlashma tartiblash algoritmi sifatida tanilgan.
Ba'zan "bo'l va zabt et" nomi har bir muammoni faqat bitta kichik muammoga qisqartiradigan algoritmlarga nisbatan qo'llaniladi, masalan, tartiblangan ro'yxatdagi yozuvni topish uchun ikkilik qidiruv algoritmi (yoki raqamli hisoblashda uning analogi, ildiz uchun bisektsiya algoritmi) topish. Bu algoritmlarni umumiy bo'lish va zabt etish algoritmlariga qaraganda samaraliroq amalga oshirish mumkin; xususan, agar ular quyruq rekursiyasidan foydalansa, ular oddiy halqalarga aylantirilishi mumkin. Biroq, bu keng ta'rif ostida, rekursiya yoki tsikllardan foydalanadigan har bir algoritm "bo'l va zabt et" algoritmi sifatida qaralishi mumkin.
Shu sababli, ba'zi mualliflar "bo'l va zabt et" nomini faqat har bir muammo ikki yoki undan ortiq kichik muammolarni keltirib chiqarishi mumkin bo'lgan hollarda ishlatish kerak deb hisoblashadi.Yagona kichik muammoli sinf uchun uning oʻrniga kamaytirish va zabt etish nomi taklif qilingan.
Bo‘l va zabt etishning muhim qo‘llanilishi optimallashtirishdir,[misol kerak] bunda qidiruv maydoni har bir qadamda doimiy omilga qisqartirilsa (“kesilgan”), umumiy algoritm kesish bosqichi bilan bir xil asimptotik murakkablikka ega bo‘ladi. kesish omiliga qarab doimiy (geometrik qatorni yig'ish orqali); bu olxo'ri va qidirish deb nomlanadi.
Ushbu algoritmlarning dastlabki misollari, birinchi navbatda, qisqartiriladi va g'alaba qozonadi - asl muammo ketma-ket bitta kichik muammolarga bo'linadi va haqiqatan ham iterativ tarzda hal qilinishi mumkin.
Ikkilik qidiruv, kichik muammolar asl hajmining taxminan yarmiga teng bo'lgan kamaytirish va zabt etish algoritmi uzoq tarixga ega. Kompyuterlardagi algoritmning aniq tavsifi 1946 yilda Jon Mauchlining maqolasida paydo bo'lgan bo'lsa-da, qidiruvni osonlashtirish uchun elementlarning saralangan ro'yxatidan foydalanish g'oyasi hech bo'lmaganda miloddan avvalgi 200-yillarda Bobiliyaga borib taqaladi.Yana bir qadimiy kamayish va zabt etish algoritmi bu Evklid algoritmi boʻlib, ikki sonning eng katta umumiy boʻluvchisini raqamlarni kichikroq va kichikroq ekvivalent kichik muammolarga qisqartirish orqali hisoblash uchun moʻljallangan boʻlib, u miloddan avvalgi bir necha asrlarga toʻgʻri keladi.
Koʻp kichik muammolarga ega boʻlgan boʻlish va zabt etish algoritmining dastlabki namunasi Gaussning 1805 yilda hozirda Kuley-Tukey tez Furye oʻzgarishi (FFT) algoritmi deb ataladigan taʼrifi boʻlsa-da, lekin u uning amallar sonini miqdoriy jihatdan tahlil qilmagan va FFT. bir asrdan ko'proq vaqt o'tgach, ular qayta kashf qilinmaguncha keng tarqalmagan.
Kompyuterlar uchun maxsus ishlab chiqilgan va to'g'ri tahlil qilingan dastlabki ikkita kichik muammoli D&C algoritmi 1945 yilda Jon fon Neyman tomonidan ixtiro qilingan birlashma tartiblash algoritmidir.
Yana bir diqqatga sazovor misol, 1960-yilda Anatolii A. Karatsuba tomonidan ixtiro qilingan algoritmdir, u ikki n-raqamli sonni koʻpaytira oladi.
Dastlab kompyuterlarni o'z ichiga olmagan bo'lish va zabt etish algoritmining yana bir misoli sifatida Donald Knuth pochta bo'limi odatda pochtani yo'naltirishda foydalanadigan usulni beradi: harflar turli geografik hududlar uchun alohida sumkalarga saralanadi, bu sumkalarning har biri o'zi saralanadi. kichikroq kichik mintaqalar uchun partiyalarga va ular yetkazib berilgunga qadar davom etadi.[5] Bu 1929-yildayoq perfokartalarni saralash mashinalari uchun tasvirlangan radiks turi bilan bog'liq.
“Bo‘l va zabt et” kontseptual jihatdan qiyin muammolarni hal qilish uchun kuchli vositadir: buning uchun faqat muammoni kichik muammolarga ajratish, ahamiyatsiz holatlarni hal qilish va kichik muammolarni asl muammoga birlashtirish kerak bo'ladi. Xuddi shunday, pasaytirish va zabt etish muammoni faqat bitta kichikroq muammoga qisqartirishni talab qiladi, masalan, klassik Xanoy minorasi jumboq, bu balandlik minorasining harakatlanishini kamaytiradi.
Bo‘l va zabt et paradigmasi ko‘pincha samarali algoritmlarni topishda yordam beradi. Bu, masalan, Karatsubaning tez ko'paytirish usuli, tezkor saralash va birlashtirish algoritmlari, matritsalarni ko'paytirish uchun Strassen algoritmi va tez Furye o'zgarishlarining kaliti edi.
Ushbu misollarning barchasida D&C yondashuvi yechimning asimptotik narxini yaxshilashga olib keldi. Misol uchun, agar (a) asosiy holatlar doimiy chegaralangan o'lchamga ega bo'lsa, masalani bo'lish va qisman echimlarni birlashtirish ishi muammoning o'lchamiga proportsionaldir.
Ajra va zabt et algoritmlari tabiiy ravishda xotira keshlaridan samarali foydalanishga intiladi. Sababi shundaki, kichik muammo yetarli darajada kichik bo'lsa, u va uning barcha kichik muammolari, qoida tariqasida, sekinroq asosiy xotiraga kirmasdan, keshda hal qilinishi mumkin. Keshni shu tarzda ishlatish uchun mo'ljallangan algoritm kesh-oblivious deb ataladi, chunki u aniq parametr sifatida kesh hajmini o'z ichiga olmaydi.[9] Bundan tashqari, D&C algoritmlari muhim algoritmlar (masalan, saralash, FFTlar va matritsalarni ko'paytirish) optimal keshni unutmaydigan algoritmlar bo'lishi uchun ishlab chiqilishi mumkin - ular kesh hajmidan qat'i nazar, keshdan asimptotik ma'noda optimal tarzda foydalanadilar. Bundan farqli o'laroq, keshdan foydalanishning an'anaviy yondashuvi, masalan, loop Nest optimallashtirishda bo'lgani kabi, blokirovka qilinadi, bunda muammo aniq o'lchamdagi bo'laklarga bo'linadi - bu ham keshdan optimal tarzda foydalanishi mumkin, lekin faqat algoritm o'ziga xos xususiyatga sozlanganda. ma'lum bir mashinaning kesh o'lchamlari.
Xuddi shu afzallik NUMA yoki virtual xotira kabi boshqa ierarxik saqlash tizimlarida, shuningdek keshning ko'p darajalarida mavjud: kichik muammo etarlicha kichik bo'lsa, uni ierarxiyaning ma'lum bir darajasida hal qilish mumkin. yuqori (sekinroq) darajalarga kirish.
{\displaystyle O(n\log _{p}n)}.
|
| |
