Daraxtlarni Prufer usulida kodlash. Daraxtlarni ularning kodi bo‘yicha yasash
Download 0.65 Mb. Pdf ko'rish
|
diskret1mi
- Bu sahifa navigatsiya:
- Topshirdi
|
O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI Kompyuter injiniringi FAKULTETI Algoritmlash va matematik modellashtirish kafedrasi “Diskret tuzilmalar” fani MUSTAQIL ISH № 1 Mavzu: Daraxtlarni Prufer usulida kodlash. Daraxtlarni ularning kodi bo‘yicha yasash. Topshirdi: 030-20 guruh talabasi Tojimov Alisher Toshkent – 2021-y Reja 1.Kirish 2.Daraxt va unga ekvivalent tushunchalar 3.Daraxtlarni Prufer usulida kodlash 4.Daraxtlarni ularning kodi bo’yicha yasash 5.Foydalanilgan adabiyotlar 1948 yilda, Klod Shannon nashr etilgan "Muloqotning matematik nazariyasi", Iyul va Oktyabr sonlarida ikki qismdan iborat maqola Bell tizimi texnik jurnali . Ushbu ish kodlashni qanday qilib yaxshiroq kodlash masalasiga qaratilgan ma `lumot jo'natuvchi uzatishni xohlaydi. Ushbu fundamental ishda u tomonidan ishlab chiqilgan ehtimollar nazariyasidagi vositalardan foydalanilgan Norbert Viner, ular o'sha paytda aloqa nazariyasiga tatbiq etilish bosqichlarida bo'lgan. Shannon ishlab chiqdi axborot entropiyasi maydonini ixtiro qilgan holda xabardagi noaniqlik o'lchovi sifatida axborot nazariyasi. The ikkilik Golay kodi 1949 yilda ishlab chiqilgan. Bu har 24 bitli so'zda uchta xatolikni tuzatishga va to'rtinchisini aniqlashga qodir bo'lgan xatolarni tuzatuvchi kod. Richard Xamming g'olib bo'ldi Turing mukofoti 1968 yilda ishlaganligi uchun Bell laboratoriyalari raqamli usullarda, avtomatik kodlash tizimlarida va xatolarni aniqlash va xatolarni tuzatish kodlarida. U sifatida tanilgan tushunchalarni ixtiro qildi Hamming kodlari, Hamming windows, Hamming raqamlariva Hamming masofasi. 1972 yilda, Nosir Ahmed taklif qildi diskret kosinus o'zgarishi (DCT), u T. Natarajan bilan ishlab chiqqan va K. R. Rao 1973 yilda. [2] DCT eng keng qo'llaniladigan hisoblanadi yo'qotishlarni siqish algoritmi, kabi multimedia formatlari uchun asos JPEG, MPEG va MP3. Daraxt tushunchasiga boshqacha ham ta'rif berish mumkin. Umuman olganda, G(m,n)-gvaf uchun daraxtlar haqidagi asosiy teorema, deb ataluvchi quyidagi teorema o'rinlidir. 1-teorema. Uchlari soni m va qirralari soni n bo 'Igan G graf uchun quyidagi tasdiqlar ekvivalentdir: • G daraxtdir; • G asiklikdir va n=m—l; • G bog'lamlidir va n=m—\; Induksion o'tish: G daraxt uchun k>2 vam=k bo'lganda, 2) tasdiq o'rinli bo'lsin deb faraz qilamiz. Endi uchlari soni m=k+l va qirralari soni n bo'lgan daraxtni qaray-miz. Bu daraxtning ixtiyoriy qirrasini (vp v2) bilan belgilab, undan bu qirrani olib tashlasak, Vj uchdan v2 uchgacha marshruti (aniqrog'i, zanjiri) mavjud bo'lma-gan grafni hosil qilamiz , chunki agar hosil bo'lgan grafda bunday zanjir bor bo'lsa edi, u holda G daraxtda sikl topilar edi. Bunday bo'lishi esa mumkin emas. Hosil bo'lgan graf ikkita GlvaG2bog'lamli komponentalardan iborat bo'lib, bu komponentalarning har biri daraxtdir. Yana shuni ham e'tiborga olish kerakki , GlvaG2 daraxtlarning har biridagi uchlar soni к dan oshmaydi. Matematik induksiya usuliga ko'ra, bu daraxtlarning har birida qirralar soni uning uchlari sonidan bitta kam bo'lishini ta'kidlaymiz, ya'ni Gxgraf (m, «)-graf bo'lsa, quyidagi tengliklar o'rinlidir: n=nx+n2+\, k+l=ml+m2va. n=m — \ (/=1,2). Bu tengliklardan n=nl+n2+l=m]— l+m2—1+1= (mx+m2)—l= (k+l)—l Endi daraxtlar haqidagi asosiy teoremaning 2) tasdig'idan uning 3) tasdig'i kelib chiqishini isbotlaymiz. G graf asiklik, ya'ni u siklga ega bo'lmagan graf van=m— 1 bo'lsin. G grafning bog'lamli bo'lishini isbotlash kerak. Agar G graf bog'lamli bo'lmasa, u holda uni har bir bog'lamli komponentasi sik- lsiz graf G. (ya'ni daraxt) bo'lgan qandaydir к.kta (k>l) graflar dizyunktiv birlash- masi sifatida ^=U^ tenglik /=] bilan ifodalash mumkin. Har bir i=l,kuchun G.tgraf daraxt bo'lgani uchun, yuqorida isbotlangan tasdiqqa ko'ra, agar unda mj ta uch va «.ta qirra bo'lsa, u holda G. asiklikdir va n=m—1 tenglik Agar qandaydir ikki uch bittadan ko'p, masalan, ikkita turli oddiy zanjir vosita- sida tutashtirilishi imkoniyati bo'lsa, u holda bu uchlarning biridan zanjirlarning biron-tasi bo'ylab harakatlanib ikkinchi uchga , keyin bu uchdan ikkinchi zanjir bo'ylab harakatlanib dastlabki uchga qaytish imkoniyati bor bo'lar edi. Ya'ni qaralayotgan graf da sikl topilar edi Download 0.65 Mb. Do'stlaringiz bilan baham: 
|