Javoblar 86. Хасис алгоритм қачон қўлланилади?

86.Хасис алгоритм қачон қўлланилади?

87.“Бўлиб ташла ва ҳукмронлик қил” алгоритмининг босқичларини айтинг.

88.Қандай саралаш алгоритмларини биласиз?

89.Саралаш алгоритмлари самарадорлигини қандай баҳолаш мумкин?

92. Quicksort алгоритмини тушунтиринг.
JAVOBLAR

86.Хасис алгоритм қачон қўлланилади?
Agar ochko'z algoritm ushbu muammoni echishga imkon beradigan bo'lsa, qanday qilib bilasiz? Bu erda umumiy retseptlar mavjud emas, ammo hasis algoritmlar tomonidan hal qilingan muammolarga xos bo'lgan ikkita xususiyat mavjud. Bu hasis tanlov printsipi va pastki qismlarga maqbullik xususiyati.

Hasis tamoyil

Aytishlaricha, hasislik bilan tanlangan mulk tamoyili mahalliy optimallashtirilgan (hasis) tanlovlar ketma-ketligi global miqyosda eng maqbul echimni beradigan bo'lsa, optimallashtirish muammosiga nisbatan qo'llaniladi. Hasis va dinamik dasturlash o'rtasidagi farqni quyidagicha izohlash mumkin: har bir qadamda hasis 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.

Hasis 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 hasis tanlov maqbul echimga olib boradigan yo'lni yopib qo'ymasligini isbotlaymiz: har bir echim uchun hasis tanlovga mos keladigan va undan ham yomon bo'lmagan yana bir bor. birinchi Keyin birinchi bosqichdagi hasis 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, hasis 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. ³ f1.

Xaffman kodlari

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. Hasis 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).

Biroq, 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.

Optimal daraxt

Bizning vazifamiz barglari ramzlar bilan belgilangan va daraxtning narxini minimallashtiradigan, deb belgilangan aniq, binar daraxtni topishdir.

(daraxtdagi i-chi belgi chuqurligi). Biz daraxtning ichki uchining chastotasini o'g'illarining chastotalari yig'indisi sifatida aniqlaymiz. Ushbu ta'rif bilan daraxtning har bir uchining chastotasi shunchaki kodlash yoki dekodlash paytida ushbu uchga kirishlar soni ekanligini ko'rish mumkin. Daraxtning narxi, ildizdan tashqari, daraxtning barcha uchlari chastotalarining yig'indisiga teng bo'ladi. Ikkala noyob belgilar eng maqbul daraxtning eng pastki qismida osib qo'yilishi aniq. NUO, f1, f2 - bu minimal chastotalar. F1 va ... fn, aka-uka va opa-singillar bo'lgan f1, ... fn chastotalar uchun maqbul daraxtning qiymati yig'indiga (f1 + f2) va chastotalar uchun eng maqbul daraxt narxiga (f1 + f2), ... fn.