Mavzu: Normal va murakkab algoritmlar (4 soat) Reja

4. “Ajrat va hukumron bo’l” va “Qurumsoq algoritmlar”

"Bo'lib tashla va hukmronlik qil" nimani anglatadi
Dasturlashda, bo'lib tashla va hukmronlik qil — bu algoritmik paradigma bo'lib, bu paradigmaning asosiy g'oyasi algoritmik masalalarni bosh masalaga o'xshash kichik qismlarga bo'lib tashlab, ularni rekursiv hal qilishdan iborat.
Bu paradigmada masala qismlarga bo'linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo'lishi va bu bo'linish to'xtashi uchun asos holat bo'lishi kerak (Rekursiya esingizga tushib ketmadimi?). Barcha turdagi bo'lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo'ladi:

1. 
   Bo'lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o'xshash kichikroq masalalarga bo'lib chiqiladi.
   
2. 
   Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi.
   
3. 
   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: bo'lib tashla, hukmronlik qil, birlashtir. Boshida tushunish ozroq qiyin bo'lishi tabiiy, shuning uchun bu paradigma g'oyasini tasvirlab berishga harakat qilamiz.
Oddiy, bittagina qadamdan iborat bo'lib tashla va hukmronlik qil algoritmi qanday ishlashini ko'raylik:

Agar biz qadamlar sonini oshiradigan bo'lsak, paradigma tasviri quyidagicha ko'rinish oladi:

Bo'lib tashla va hukmronlik qil paradigmasi asosiy masalalari

Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:

1. 
   Ikkilik qidirish (Binary Search)
   
2. 
   Merge Sort
   
3. 
   Quick Sort
   
4. 
   Eng yaqin ikki nuqta (Closest two points)
   
5. 
   Strassen ko'paytirishi (Strassen multiplication)
   
6. 
   Karatsuba algoritmi (Karatsuba algorithm)
   
7. 
   Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
   

Bulardan eng asosiylarini keyingi darslarimizda ko'rib chiqamiz
Bo'lib tashla va hukmronlik qil paradigmasi afzalliklari

• 
  qiyin masalalarni osonlik bilan yechishga imkon beradi
  
• 
  bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko'ra tezroq ishlaydi. Masalan: oddiy saralash bo'lgan Bubble Sortning tezligi O(n²) bo'lsa, MergeSortniki O(n*logn)
  
• 
  bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o'zgarishsiz ishlatish mumkin
  
• 
  bunday algoritmlarni qo'llashda xotira keshidan unumli foydalanish mumkin. Chunki masalalar bo'linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o'zida turib yechish mumkin bo'ladi.
  
• 
  haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko'paytirish algoritmlarida)
  

Bo'lib tashla va hukmronlik qil paradigmasi kamchiliklari

• 
  bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va bu narsa ularni ishlashini ma'lum miqdorga sekinlashtiradi. Buning ustiga kichik bir xato yechimni cheksiz takrorlanishga tushirib qo'yishi mumkin.
  
• 
  asos shartni tanlashda yo'l qo'yilgan xato barcha qism masalalarda xatolik va ortiqcha xotira ishlatilishiga olib keladi
  

“Qurumsoq” algoritmi.

Ko'pgina optimallashtirish muammolari uchun dinamik dasturlashdan ko'ra sodda va tezkor algoritmlar mavjud. Ushbu ma'ruzada Qurumsoq algoritmlar yordamida hal qilinishi mumkin bo'lgan muammolarga qaraymiz. Bunday algoritm har bir qadamda oxirgi echim ham maqbul bo'lishiga umid qilib, mahalliy eng maqbul tanlovga aylantiradi. Bu har doim ham shunday emas - lekin ko'pgina vazifalar uchun bunday algoritmlar haqiqatan ham eng maqbulligini ta'minlaydi. Bizning birinchi misolimiz - bu oddiy, ammo unchalik ahamiyatsiz bo'lmagan dasturlarni tanlash. Keyingi, Qurumsoq algoritmlar qaysi vazifalarga mos kelishini muhokama qilamiz.
Qurumsoq algoritm sizga bir qator tanlovlarni amalga oshirish orqali muammoning maqbul echimini topishga imkon beradi. Algoritmdagi har bir qaror nuqtasida hozirgi paytda eng yaxshi ko'rinishga ega bo'lgan tanlov amalga oshiriladi. Ushbu evristik strategiya har doim ham eng maqbul echimni ta'minlamaydi, ammo baribir yechim eng maqbul bo'lishi mumkin. Qurumsoq algoritmlarning rivojlanishi quyida keltirilgan bosqichlarning ketma-ketligi sifatida namoyish etilishi mumkin.
1. Optimallashtirish masalasini, tanlov amalga oshirilgandan so'ng, faqat bitta pastki bandni hal qilish uchun olib keling.
2. Aslida Qurumsoq tanlov orqali olinishi mumkin bo'lgan asl muammoning eng maqbul echimi borligini isbotlang, shunda bunday tanlov har doim haqiqiy bo'ladi. 3. Qurumsoq tanlovdan so'ng subproblemning eng maqbul echimini qilingan Qurumsoq tanlov bilan birlashtirgan va substrulning asl maqbul echimiga olib keladigan subproblema qolganligini ko'rsating.
Yuqorida tavsiflangan jarayon keyingi vazifalarda qo'llaniladi. Eslatma. Har qanday Qurumsoq algoritmning markazida deyarli har doim dinamik dasturlash uslubidagi yanada murakkab echim bo'ladi. Savol Qurumsoq algoritm bizdan oldin optimizatsiya masalasini hal qila olishini qanday aniqlash mumkin? Bu erda umumiy yo'l yo'q, ammo ikkita asosiy komponentni ajratib ko'rsatish mumkin - Qurumsoq tanlov xususiyati va maqbul pastki tuzilma. Agar vazifa bu ikkita xususiyatga ega ekanligini namoyish etish mumkin bo'lsa, unda Qurumsoq algoritmni ishlab chiqish mumkin. Agar ochko'z algoritm ushbu muammoni echishga imkon beradigan bo'lsa, qanday qilib bilasiz? Bu erda umumiy retseptlar mavjud emas, ammo Qurumsoq algoritmlar tomonidan hal qilingan muammolarga xos bo'lgan ikkita xususiyat mavjud. Bu Qurumsoq tanlov printsipi va pastki qismlarga maqbullik xususiyati. Yuqorida aytib o'tilgan Qurumsoq algoritmning asosiy tarkibiy qismlaridan birinchisi Qurumsoq tanlov xususiyatidir: global maqbul echimni mahalliy maqbul (Qurumsoq) tanlov orqali olish mumkin. Boshqacha qilib aytganda, qaysi tanlovni tanlash haqida bahslashib, biz hozirgi vazifada eng yaxshi ko'rinadigan tanlovni qilamiz; vujudga kelgan pastki qismlarning natijalari hisobga olinmaydi. Qurumsoq va dinamik dasturlash o'rtasidagi farqni ko'rib chiqing. Dinamik dasturlashda har bir bosqichda tanlov qilinadi, lekin odatda bu tanlov pastki qismlarning yechimlariga bog'liq. Shuning uchun, dinamik dasturlash usulidan foydalanib, muammolar odatda yuqoriga yo'naltirilgan, ya'ni. avval sodda taglavhalar, so'ngra murakkabroqlari qayta ishlanadi.
Qurumsoq algoritmda hozirgi vaqtda eng yaxshi ko'rinishga ega bo'lgan tanlov amalga oshiriladi, shundan so'ng ushbu tanlov natijasida olingan pastki band hal qilinadi. Qurumsoq algoritmda qilingan tanlov oldingi tanlovlarga bog'liq bo'lishi mumkin, ammo u biron bir tanlovga yoki keyingi qo'shimcha vazifalarning qarorlariga bog'liq bo'lolmaydi. Shunday qilib, subkastrlar ko'tarilish tartibida hal qilinadigan dinamik dasturlardan farqli o'laroq, Qurumsoq strategiya, odatda, Qurumsoq tanlovlar birma-bir amalga oshirilganda, kamayib boruvchi tartibda yuzaga keladi, natijada joriy vazifalarning har bir misoli soddalashtirilgan holatga tushiriladi. Aytishlaricha, Qurumsoqlik bilan tanlangan mulk tamoyili mahalliy optimallashtirilgan (Qurumsoq) tanlovlar ketma-ketligi global miqyosda eng maqbul echimni beradigan bo'lsa, optimallashtirish muammosiga nisbatan qo'llaniladi. Qurumsoq va dinamik dasturlash o'rtasidagi farqni quyidagicha izohlash mumkin: har bir qadamda Qurumsoq algoritm "eng semiz parcha" ni oladi va keyin qolganlari orasidan eng yaxshisini tanlashga harakat qiladi; dinamik dasturlash algoritmi barcha variantlarning oqibatlarini oldindan hisoblash orqali qaror qabul qiladi.
Qurumsoq algoritm maqbul echim berishini qanday isbotlash mumkin? Bu har doim ham ahamiyatsiz emas, lekin odatiy holatda bunday isbot Teorem 1 isbotida ishlatilgan sxemaga amal qiladi. Birinchidan, birinchi bosqichda Qurumsoq tanlov maqbul echimga olib boradigan yo'lni yopib qo'ymasligini isbotlaymiz: har bir echim uchun Qurumsoq tanlovga mos keladigan va undan ham yomon bo'lmagan yana bir bor. birinchi Keyin birinchi bosqichdagi Qurumsoq tanlovdan keyin paydo bo'ladigan pastki qismning boshlang'ichga o'xshashligi va dalil indüksiya bilan yakunlanishi ko'rsatilgan.
Quyi masalalar uchun maqbullik
Boshqacha qilib aytganda, Qurumsoq algoritmlar yordamida hal qilingan muammolar maqbul pastki tuzilish xususiyatiga ega: butun muammoning eng maqbul echimi pastki qismlarga maqbul echimlarni o'z ichiga oladi. (Biz bu xususiyat bilan tanishgan edik, dinamik dasturlash haqida gaplashamiz). Masalan, 1-teorema isbotida, agar A 1-sonli da'voni o'z ichiga olgan maqbul da'volar yig'indisi bo'lsa, A '= A {1} - bu da'volarning kichikroq to'plami S' uchun talablarning optimal to'plamidir, deb da'volarni o'z ichiga oladi. Qurumsoq algoritmda hozirgi vaqtda eng yaxshi ko'rinishga ega bo'lgan tanlov amalga oshiriladi, shundan so'ng ushbu tanlov natijasida olingan pastki band hal qilinadi. Qurumsoq algoritmda qilingan tanlov oldingi tanlovlarga bog'liq bo'lishi mumkin, ammo u biron bir tanlovga yoki keyingi qo'shimcha vazifalarning qarorlariga bog'liq bo'lolmaydi. Shunday qilib, subkastrlar ko'tarilish tartibida hal qilinadigan dinamik dasturlardan farqli o'laroq, Qurumsoq strategiya, odatda, Qurumsoq tanlovlar birma-bir amalga oshirilganda, kamayib boruvchi tartibda yuzaga keladi, natijada joriy vazifalarning har bir misoli soddalashtirilgan holatga tushiriladi. Haffman kodlari (Haffman kodlari) - ma'lumotlarning xususiyatlariga qarab odatda hajmning 20% ​​dan 90% gacha tejaydigan ma'lumotni siqishning keng tarqalgan va juda samarali usuli. Belgilar ketma-ketligini ko'rsatadigan ma'lumotlarni ko'rib chiqing. Qurumsoq Haffman algoritmi muayyan belgilar paydo bo'lish chastotalarini o'z ichiga olgan jadvaldan foydalanadi. Ushbu jadvaldan foydalanib, har bir belgi ikkilik sim shaklida maqbul vakili aniqlanadi. Aytaylik, siz siqmoqchi bo'lgan 100000 ta belgi ma'lumotlari fayli mavjud. Ushbu fayldagi belgilar 1-jadvalda ko'rsatilgan chastota bilan topilgan. Shunday qilib, butun fayl oltita turli xil belgilarni o'z ichiga oladi va masalan, a belgisi unda 45000 marta uchraydi. Bunday ma'lumotlar faylini taqdim etishning ko'plab usullari mavjud. Ikkilik belgilar kodini ishlab chiqish vazifasini ko'rib chiqing, unda har bir belgi noyob ikkilik satr bilan ifodalanadi.
Agar sobit uzunlikdagi kod yoki yagona kod ishlatilsa, oltita belgini ko'rsatish uchun 3 bit kerak bo'ladi: a = 000, b = 001, ..., / = 101. Ushbu usuldan foydalanganda butun faylni kodlash uchun 300000 bit kerak bo'ladi. Yaxshi natijalarga erishish mumkinmi?
1-jadval. Belgilar ketma-ketligini kodlash vazifasi.

O'zgaruvchan uzunlikdagi kod yoki notekis koddan foydalanib, sobit uzunlikdagi kodni ishlatishdan ancha yaxshi natijalarga erishish mumkin. Bunga tez-tez uchraydigan belgilar qisqa kodli so'zlar bilan, kamdan-kam uchraydigan belgilar uzoq belgilar bilan solishtirilganligi sababli erishiladi.

Bunday kod 1-jadvalning oxirgi qatorida keltirilgan. Unda a harfi 1 bitli satr bilan ifodalanadi, f harfi esa 4 bitli satr bilan ifodalanadi 1100. Ushbu koddan foydalanib faylni ko'rsatish uchun sizga kerak bo'ladi (45 • 1 + 13 • 3 + 12 • 3 + 16 • 3 + 9 • 4 + 5 • 4) • 1000 = 224000 bit. Bu qo'shimcha ravishda tovushning 25 foizini tejaydi.
Faqatgina A, B, C, D harflaridan iborat bo'lgan 130 uzunlikdagi chiziqni ko'rib chiqing. Bundan tashqari, har bir belgining chastotasi ma'lum deb hisoblang: ABCD 70 3 20 37 Bizning vazifamiz har bir belgi uchun tegishli kodlangan bo'lishi uchun bit kodni berishdir. chiziq imkon qadar qisqa edi. Kodlash variantlaridan biri: A = 00, B = 01, C = 10, D = 11. Keyin kodda 260 bit bo'ladi. Men A kodli belgi bir bit bilan kodlangan kodlash bilan shug'ullanishni xohlayotganim intuitiv ravishda ravshan (masalan, B qiymati uchga teng bo'lishi mumkin).
B
iroq, turli xil uzunlikdagi bitli ketma-ketlik bilan belgilarni kodlashda dekodlash muammosi paydo bo'lishi mumkin. Ushbu muammoni hal qilishning bir usuli - bu prefiks kodlash. Ushbu kodlash bilan har qanday ikkita belgi uchun birining kodi boshqasining kodi prefiksi emas. Har bir bunday kodlash qirralarida 0 va 1 bo'lgan to'liq bargli (har bir uchida yoki nol yoki ikkita o'g'il) ikkilik daraxti va barglarida kodlangan belgilar bilan ifodalanishi mumkin.