HESH JADVALLAR VA ULARNI TASHKIL ETISH

Bosh sahifa

HESH JADVALLAR VA ULARNI TASHKIL ETISH

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

2

Hajmi:

1.0 MB

Ko'chirib olish shartlari

1
O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
RAQAMLI TEXNOLOGIYALAR FAKULTETI
DASTURIY INJINIRING YO`NALISHI
107 -GURUH TALABASI
YO`LDOSHEV DAVRONBEKNING
“ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN
“HESH JADVALLAR VA ULARNI TASHKIL ETISH” MAVZU-
SIDA TAYYORLAGAN
KURS ISHI

Topshirdi: Yo‘ldoshev D
Tekshirdi: Abdusalomova G .

2
Mundari ja
KIRISH ................................ ................................ ................................ ................................ ................................ .. 3
I BOB. HESH JADVALLA RI ASOSLARI ................................ ................................ ................................ ......... 4
1.1.HESH TUSHUNCHASI ................................ ................................ ................................ ........................... 4
1.2. HESH ALGORITMLA RI ................................ ................................ ................................ ...................... 7
II BOB . KOLLIZIYA TUSHUNCH ASI ................................ ................................ ................................ ............ 10
2.1 KOLLIZIYA HAQID A TUSHUNCHA ................................ ................................ ............................... 10
2.2. KOLLIZIYA ANIQL IGI (COLLISION RESOL UTION) ................................ ................................ . 11
2.3 . OCHIQ ADRESLASH ................................ ................................ ................................ .......................... 16
III BOB. AMALIY MASA LALAR ................................ ................................ ................................ .................... 19
3.1.SATRLI FUNKSIYAL AR UCHUN HESH -FUNKSI YASINI QO ’LLASH ................................ ...... 19
3.2. SONLAR UCHUN HE SH -FUNKSIYASI ................................ ................................ ........................... 21
3.3.IKKILIK DARAXTLA RDA IZLASH VA HESH J ADVALLAR ................................ ...................... 22
HESH JADVALNI REALIZ ATSIYA QILISH ................................ ................................ ................................ . 22
XULOSA ................................ ................................ ................................ ................................ .............................. 28
ADABIYOTLAR ................................ ................................ ................................ ................................ ................. 29

$7 1.2. Hesh algoritmlari Hozirda deyarli hech qanday kriptografiya ilovasi xeshlashdan foyda- lanmasdan to'liq emas. Hesh funksiyalari odatda ikkilik alifboda yozilgan ixtiyoriy xabar yoki maʼlumotlar toʻplamini konvolyutsiya deb ataladi gan qatʼiy uzunlikdagi bit birk- masiga “siqish ” uchun moʻljallangan funksiyalardir. Hesh -funksiyalar statistik eksperimentlarni o'tkazishda, mantiqiy qurilmalarni sinovdan o'tkazishda, tezkor qidiruv algoritmlarini yaratishda va ma'lumotlar bazalaridagi yoz uvlarning yaxlitligini tekshirishda turli xil ilovalarga ega. Hesh -funksiyalar uchun asosiy talab - bu argument qiymatlarini tasodifiy tanlash bilan ularning qiymatlarini taqsimlashning bir xilligi. Kriptografik hesh -funksiya - kriptografik jihatdan xavfsiz bo'lgan, ya'ni kriptografik ilovalar uchun xos bo'lgan bir qator talablarni qondiradigan har qanday hesh funksiyasi. Kriptografiyada hesh funksiyalari quyidagi muammo- larni hal qilish uchun ishlatil adi: - uzatish yoki saqlash vaqtida ma'lumotlar yaxlitligini nazorat qilish tizimlarini yaratish; - ma'lumotlar manbasini autentifikatsiya qilish. Hesh funktsiyasi har qanday funktsiyadir h:X -> Y , oson hisoblash mumkin va har qanday xabar uchun shunday M ma'nosi h(M) = H (konvolyutsiya) bel- gilangan bit uzunligiga ega. X- barcha xabarlar to'plami, Y- belgilangan uzunlik- dagi ikkilik vektorlar to'plami. Qoidaga ko'ra, hesh funktsiyalari bir bosqichli qisqarish funktsiyalari aso- sida qurilgan y \u003d f (x 1, x 2) ikkita o'zgaruvchi, bu erda x 1 , x2 va y- ikkilik uzunlik vektorlari m va n mos ravishda va n konvolyutsiya uzunligi va m - xabar blokining uzunligi. Qiymatni olish uchun h(M) xabar avval uzunlikdagi bloklarga bo'linadi m (shu bilan birga, agar xabarning uzunligi ko'p bo'lmasa m keyin oxirgi blok qandaydir maxsus tarzda to'liq bloklarga to'ldiriladi), so'ngra olingan bloklarga M 1 , M 2 ,.., M N konvolyutsiyani hisoblash uchun quyidagi ketma -$ $8 ketlikni qo'llang: H o \u003d v, H i = f(M i ,H i -1), i = 1,.., N, h(M) = H N Bu yerda v- ba'zi doimiy, u ko'pincha initsializatsiya vektori deb ataladi. U chiqadi turli sabablarga ko'ra va maxfiy doimiy yoki tasodifiy ma'lumotlar to'plami bo'lishi mumkin (masalan, sana va vaqtni tanlash). Ushbu yondashuv bi- la n hash funktsiyasining xususiyatlari bir bosqichli qisqarish funktsiyasining xususiyatlari bilan to'liq aniqlanadi. Kriptografik hesh -funktsiyalarning ikkita muhim turi mavjud - kalitli va kalitsiz. Asosiy hesh funksiyalari xabar autentifikatsiya kodlari d eb ataladi. Ular uchun imkoniyat yaratadi qo'shimcha mablag'lar o'zaro ishonchli foydalanuvchi- lar bilan tizimlarda ma'lumotlar manbasining t o'g'riligini va ma'lumotlarning yaxlitligini ta'minlash. Kalitsiz hesh funksiyalari xatolarni aniqlash kodlari deb ataladi. Ular qo'shimcha vositalar (masalan, shifrlash) yordamida ma'lumotlarning yaxlitligini kafolatlash imkonini beradi. Ushbu hesh -funksi yalar ishonchli va ishonchsiz foy- dalanuvchilarga ega tizimlarda ishlatilishi mumkin. Statistik xususiyatlar va talablar haqida Aytganimdek, hesh -funksiyalar uchun asosiy talab argument qiymatlarini tasodifiy tanlash bilan ularning qiymatlarini bir xil taqsimlashdir. Kriptografik hesh -funksiyalar uchun argumentning eng kichik o'zgarishi bilan funktsiyaning qiymati sezilarli darajada o'zgarishi ham muhimdir. Bu ko'chki effekti deb ataladi. H eshlash quyidagi talablarga ega: - ishlab chiqarishning mumkin e masligi; - o'zgartirishning mumkin emasligi. Birinchi talab shuni anglatadiki, xabarni to'g'ri qatlama qiymatiga mos- lashtirish juda qiyin. Ikkinchisi, ma'lum qatlama qiymatiga ega bo'lgan ma'lum bir xabar uchun to'g'ri katlama qiymatiga ega boshqa xabarni moslashtirishning$

1 O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI SAMARQAND DAVLAT UNIVERSITETI RAQAMLI TEXNOLOGIYALAR FAKULTETI DASTURIY INJINIRING YO`NALISHI 107 -GURUH TALABASI YO`LDOSHEV DAVRONBEKNING “ALGORITM VA MA’LUMOTLAR STRUKTURASI” FANIDAN “HESH JADVALLAR VA ULARNI TASHKIL ETISH” MAVZU- SIDA TAYYORLAGAN KURS ISHI Topshirdi: Yo‘ldoshev D Tekshirdi: Abdusalomova G .

2 Mundari ja KIRISH ................................ ................................ ................................ ................................ ................................ .. 3 I BOB. HESH JADVALLA RI ASOSLARI ................................ ................................ ................................ ......... 4 1.1.HESH TUSHUNCHASI ................................ ................................ ................................ ........................... 4 1.2. HESH ALGORITMLA RI ................................ ................................ ................................ ...................... 7 II BOB . KOLLIZIYA TUSHUNCH ASI ................................ ................................ ................................ ............ 10 2.1 KOLLIZIYA HAQID A TUSHUNCHA ................................ ................................ ............................... 10 2.2. KOLLIZIYA ANIQL IGI (COLLISION RESOL UTION) ................................ ................................ . 11 2.3 . OCHIQ ADRESLASH ................................ ................................ ................................ .......................... 16 III BOB. AMALIY MASA LALAR ................................ ................................ ................................ .................... 19 3.1.SATRLI FUNKSIYAL AR UCHUN HESH -FUNKSI YASINI QO ’LLASH ................................ ...... 19 3.2. SONLAR UCHUN HE SH -FUNKSIYASI ................................ ................................ ........................... 21 3.3.IKKILIK DARAXTLA RDA IZLASH VA HESH J ADVALLAR ................................ ...................... 22 HESH JADVALNI REALIZ ATSIYA QILISH ................................ ................................ ................................ . 22 XULOSA ................................ ................................ ................................ ................................ .............................. 28 ADABIYOTLAR ................................ ................................ ................................ ................................ ................. 29

3 Kirish Hozirgi kunda amaliy matematika va kibernetika fanining asosiy yo`nalishlaridan biri – tasvirlarni aniqlash masalasidir. Bu yo`nalishning muhimligi avvalo shu bilan asoslanadiki juda ko`pgina amaliy masalalar mavjudki, ularni to`liq matematik qa’tiylik bilan asoslangan metodlar bilan yechish qiyin yoki yechib bo`lmaydi. Bunday masalalarga, masalan, geologiya, texnika va tibbiyotda uchraydigan diagnost ika va bashorat qilish masalalari misol bo`la oladi. Tasvirlarni aniqlash masalalasi metodlarining bu sohalarda keng tarqalishing sabablarirdan yana biri, ularni tadbiqida bu sohalardagi boshlang`ich ma`lumotlarni yuqori darajada formallash talab qilinmayd i. Tasvirlarni aniqlash nazariyasi optimal yechimni axtarish muammosini diskret analogidir. Bu masalaga nafaqat eng yaxshi yechimni sintezi masalasi, balki boshqa muammoli amaliy masalalar sinfi ham keltiriladi. Hesh jadvali - bu assotsiativ massiv interfeysini amalga oshiruvchi ma'lumotlar tuzilmasi, ya'ni juftlarni saqlashga (kalit, qiymat) va uchta operatsiyani bajarishga imkon beradi: yangi juftlikni qo'shish, qidirish operatsiyasi va juftlikni kalit bilan o'chirish. Hesh jadvallarining ikkita asosiy varianti mavjud: zanjirli va ochiq adreslash. H esh jadvali ba'zi bir ?????? massivini o'z ichiga oladi, ularning elementlari juftliklar (ochiq adreslash bilan hesh jadvali) yoki juftliklar ro'yxati (zanjir bilan hesh jadvali). Hes hlash – bu ixtiyori uzunlikdagi kirish ma'lumotlari majmuasini ma'lum bir algoritm tomonidan bajarilgan, belgilangan o'lchamdagi chiqish massiviga aylantirish jarayoni. Bunday algoritmni amalga oshiruvchi funksiya hesh funktsiya , transformatsiya natijasi x ash yoki xash yig'indisi deyiladi. Hesh funktsiyasi quyidagi xususiyatlarga ega: - bir xil ma'lumotlar bir xil xashni beradi; - "deyarli har doim" turli xil ma'lumotlar boshqacha hesh beradi.

4 I BOB. Hesh jadvallari asoslari 1.1.Hesh tushunchasi Katta hajmdagi ma'lumotlarda ma'lumotlarni izlash jarayoni ko'p vaqt talab etadi, bu esa qidiruv kaliti yordamida sezilarli miqdordagi elementlarni ko'rish va taqqoslash zarurati bilan bog'liq. Ko'rish oynasini mahalliylashtirish orqali qidiruvni qisqartirish mu mkin. Misol uchun, ma'lumotlarni qidirish kaliti bo'yicha tartiblang, ularni biron bir guruh atributiga ko'ra bir -biriga mos kelmaydigan bloklarga bo'ling yoki haqiqiy ma'lumotlarni qidirish jarayonini soddalashtiradigan kod bilan moslang. Heshlash (yoki he shlash , inglizcha hashing ) - ma'lum turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlar massivini belgilangan uzunlikdagi chiqish bit qatoriga aylantirish. Bunda transformatsiyalar ham deyiladi. Hesh funktsiya- lari yoki konvolyutsiya funksiyalari va ularnin g natijalari deyiladi. Hash, hash kodi, hash jadvali yoki hazm qilish xabarlar (inglizcha) xabar dayjesti ). Hesh jadvali - bu ma'lumotlar tuzilishi, bu assotsiativ massiv interfeysini amalga oshiradi, ya'ni kalit -qiymat juftlarini saqlash va uchta amalni bajarish im- konini beradi: yangi juft qo'shish operatsiyasi, qidirish operatsiyasi va kalit bo'yi- cha juftlikni o'chirish operatsiyasi. Hesh -jadval - bu hesh funktsiyasi tomonidan ma'lum tartibda tuzilgan massiv.  funksiya hisoblash uchun oddiy bo'lishi kerak;  funksiya hesh -jadvaldagi kalitlarni iloji boricha bir tekis taqsimlashi kerak;  funktsiya kalit qiymatlar o'rtasidagi hech qanday munosabatni manzil qiymatlari o'rtasidagi munosabatlarga moslashtirmasligi kerak;  funktsiya to'qnashuvlar sonini minimal lashtirishi kerak, ya'ni turli tugmalar bitta hesh qiymatiga to'g'ri keladigan vaziyatlar (bu holda kalitlar deyiladi. si- nonimlar ). Bunda yaxshi hesh funksiyasining birinchi xossasi kompyuterning xususiyatlariga, ikkinchisi esa ma'lumotlar qiymatlariga bog 'liq. Agar barcha ma'lumotlar tasodifiy bo'lsa, hesh funktsiyalari juda oddiy bo'lar edi (kalitning bir necha bitlari kabi). Biroq, amalda tasodifiy ma'lumotlar

Ko'chirib oling, shunda to'liq holda ko'ra olasiz

O'xshashlar

Maktabgacha ta’lim muassasalari va ularni tashkil etish.

Maktabgacha ta’lim tashkilotlari mashg‘ulotlari va ularni innovatsion tashkil etish

Latexda hujjat strukturasini tashkil etish .Matnni formatlash .Jadvallar yaratish ,grafiklar bilan ishlash

Psixologik xizmatni tashkil etish

BOSHQARUV HISOBINI TASHKIL ETISH