Mustaqil ish Ma’lumotlar tuzilmasi va algoritmlar

Mustaqil ish Ma’lumotlar tuzilmasi va algoritmlar

712-21-guruh U.Ermamatova

Mavzu:Xesh jadval va xesh funksiyalar. Qidiruv algoritmlar samaradorligi.

• Xeshlash – bu ma'lum bir turdagi va ixtiyoriy uzunlikdagi kirish ma'lumotlari massivini fiksirlangan uzunlikdagi chiquvchi bitlar qatoriga aylantirish. Bunday akslantirish xesh-funksiya deb ham ataladi. Xesh-funksiya – bu kirish ma’lumotlarini sonlarga aylantiruvchi funksiya bo’lib, bir xil ma’lumotlar to’plami hamma vaqt bir xil natija beradi.
• Xesh funksiyalar – ixtiyoriy uzunlikdagi kirish ma’lumotini chiqishda belgilangan uzunlikdagi xesh qiymatga aylantirib beruvchi bir tomonlama funksiyalarga aytiladi. Xesh funksiyalar kriptografiya va zamonaviy axborot xavfsizligi sohasida ma’lumotlarni to’laligini tekshirishda foydalaniladi.

Hesh-funksiyaga misollar

Xeshlash assotsiativ massivlarni tashkil qilish uchun qo’llaniladi, bunda indekslari sonlar emas, balki ixtiyoriy qiymatlar bo’ladi. Bundan tashqari, xeshlash ko'pincha parollarni saqlash uchun ishlatiladi; Shu bilan birgalikda noyob identifikatorlarni yaratish uchun, masalan, agar fayl o'ziga xos nomni talab qilsa, siz ushbu faylni xeshlash natijasini hisoblab chiqishingiz va natijani faylga nom sifatida ishlatishingiz mumkin

• Kompyuterda ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri hisoblanadi. Uning vazifasi berilgan argument bo’yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topish yoki bunday ma’lumot yo’qligini aniqlashdan iboratIxtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yokituzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit deb ataladi. Kalit noyob bo’lishi, ya’ni mazkur kalitga ega ma’lumot jadvalda yagonabo’lishi mumkin.
• Qidiruv algoritmlarining binary va chiziqli qidiruv usullarini ko’rib chiqamiz:

Aytaylik bizga massiv berilgan: a[]={5,8,1,2,13,7,9,10,11,6}; Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan dastur tuzish sharti qo'yilgan. Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul: Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:

Array = [15,58,96,78,45,96]

• Array = [15,58,96,78,45,96]
• def chiziqli_qidiruv(array, searchvalue):
• for i in range(len(array)):
• if searchvalue == array[i]:
• return i
• return -1
• qid_son = int(input("Qidirilayotgan sonni kiriting: "))
• natija = chiziqli_qidiruv(Array, qid_son)
• if natija >= 0:
• print("qidirilayotgan son ", Array[natija], " ", natija, "- indexda joylashgan")
• else:
• print("qidirilayotgan son ", qid_son, " ushbu massivda mavjud emas.")

Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak. Bu usulda ham funksiyaga 2 ta parametr, birinchisi massiv o'zi keyin esa biz qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha: Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu left va right o'zgaruvchilaridir:

left va right index lari markazidagi elementni topamiz (left + right) / 2

• left va right index lari markazidagi elementni topamiz (left + right) / 2
• topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
• agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
• agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.
• Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur kodi keltirilgan:

def linear_search(arr, target):

• def linear_search(arr, target):
• for i in range(len(arr)):
• if arr[i] == target:
• return i
• return -1
• arr = [15, 58, 96, 78, 45, 96]
• target = 96
• result = linear_search(arr, target)
• if result != -1:
• print(f"Element {target} mavjud.")
• else:
• print(f"Element {target} topilmadi.")

E’TIBORINGIZ UCHUN RAXMAT