Va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari univesiteti

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI

VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI

TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVESITETI

DASTURIY INJINIRINGI FAKULTETI

Algoritmlarni loyihalash fanidan


Oraliq nazorat ishi

34-VARIANT

CAL003-L4- guruh talabasi

Bajardi: Madaminov Dostonbek

Tekshirdi: Yusupova Zaynab

Qoraqalpog`iston-2020
34-VARIANT.

1. 
   Xoffman kodi
   
2. 
   Resurslarni almashish va qulflash.
   
3. 
   NP bilan bog`liq muammolarni xal qilish yo’llari
   

JAVOBLAR:

1.Algoritm standart matnda o'rnatilgan 256 belgidan iborat. Ba'zi bir belgilar o'rtacha takrorlash davriga qaraganda ko'proq, boshqalari esa kamroq kamroq paydo bo'lishiga asoslanadi. Shuning uchun, agar siz umumiy simvollarni yozish uchun uzunligi 8 dan kam bo'lgan bitlarning qisqa ketma-ketliklaridan foydalansangiz va noyob belgilarni yozish uchun uzun bo'lganlar bo'lsa, fayllarning umumiy hajmi kamayadi.

Xoffman uzunligi entropiyasiga juda yaqin bo'lgan faylni olish uchun qaysi kod bilan kodlanishi kerakligini aniqlash uchun (masalan, ma'lumotlarning to'yinganligi) algoritmni taklif qildi. Aytaylik, bizda boshlang'ich matnda mavjud bo'lgan barcha belgilar ro'yxati va undagi har bir belgi paydo bo'lishi soni ma'lum. Keling, ularni varaqning o'ng qirrasi bo'ylab kelajakdagi grafikaning katakchalari shaklida vertikal ravishda yozamiz (1a-rasm). Matnda eng kam takrorlash bilan ikkita belgini tanlang (agar uchta yoki undan ko'p belgilar bir xil qiymatga ega bo'lsa, ularning ikkalasini tanlang). Grafikning yangi uchiga chapdan chapga chiziq torting va unda har birlashtirilgan belgilarning har birining takrorlanish chastotalari yig'indisiga teng bo'lgan qiymatni yozing (1b-rasm). Shu vaqtdan boshlab biz ikkita kombinatsiyalangan tugunlarning eng past takrorlanish chastotalarini qidirishda e'tiborga olmaymiz (buning uchun biz bu ikki uchdagi raqamlarni o'chirib tashlaymiz), lekin yangi uchni, paydo bo'lish chastotasi ikkita ulangan uchlarning paydo bo'lish chastotalari yig'indisiga teng bo'lgan to'laqonli hujayra sifatida ko'rib chiqamiz. Bir xil verteksga raqam bilan kelgunimizcha biz vertikallarni birlashtirish harakatlarini takrorlaymiz (1c va 1d-rasmlar). Tekshirish uchun: unda kodlangan faylning uzunligi yozilishi aniq. Endi grafikning har bir verteksidan boshlab, 0 va 1 bitlari o'zboshimchalik bilan - masalan, har bir yuqori qirrada 0, va har bir pastki chetida - 1. Endi har bir aniq harfning kodini aniqlash uchun siz shunchaki daraxtning yuqori qismidan unga o'tish kerak. nol va marshrut bo'ylab bo'lganlar. 1-rasm uchun "A" harfi "100", "B" harfi "0", "K" harfi "101" kodini, "O" harfi "11" kodini oladi.

1-rasm(a,b,c,d)

Ma'lumotni kodlash nazariyasida Hoffman kodi prefiks ekanligi, ya'ni har qanday belgi kodi boshqa har qanday belgi kodining boshlanishi emasligi ko'rsatilgan. Buni bizning misolimiz bilan tekshiring. Va shundan kelib chiqadiki, Hoffman kodi qabul qiluvchi tomonidan noyob tarzda tiklanadi, hatto har bir uzatilayotgan belgining kod uzunligi xabar qilinmasa ham. Qabul qiluvchiga faqat Hoffman daraxti ixcham shaklda yuboriladi, so'ngra belgilar kodlarini kiritish ketma-ketligi u mustaqil ravishda hech qanday qo'shimcha ma'lumotsiz dekodlanadi. Masalan, "01001101000" -ni olayotganda birinchi navbatda "B" harfini ajratadi: "0-1001101000", keyin yana daraxtning tepasidan boshlab - "A" "0-100-1101000", keyin barcha yozuv "0-100- 11-0-100-0. "" Baobab ".

2.Dasturning aniqlanmaganligi Dasturning yakuniy natijasini oldindan aytib bo'lmaydi

Dasturning noto'g'ri ishlashi, algoritmning noto'g'ri ishlashi, favqulodda vaziyatlarning paydo bo'lishi.