Kompyuter injiniringi” fakulteti “axborot ta’lim texnologiyalari” kafedrasi «taqsimlangan algoritmlar va tizimlar»

O’ZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

“KOMPYUTER INJINIRINGI” FAKULTETI

“AXBOROT TA’LIM TEXNOLOGIYALARI” KAFEDRASI


«TAQSIMLANGAN ALGORITMLAR VA TIZIMLAR » fanidan

1­ - AMALIY ISH


\


Bajardi: Rustam Abduqahorov
Tekshirdi: Xusanov K..
Guruh: 401-19

SAMARQAND – 2023
Mavzu: Taqsimlangan tizimlarda qidiruv algoritmlari


Nazariy qism:


Qidiruv - bu kompyuter xotirasida ma‘lumotlarni qayta ishlash jarayonida qo‘llaniladigan asosiy amallardan biri hisoblanadi. Bu amalning mazmuni shundan iboratki, berilgan argument bo‘yicha massiv elementlari orasidan shu argumentga mos ma‘lumotni (elementni) aniqlashdan iborat.
Ixtiyoriy ma‘lumot (yoki tuzilma) elementi qandaydir belgisi bilan boshqasidan farq qiladi. Ushbu belgi kalit deyiladi. Kalit takrorlanmas bo‘lishi mumkin, ya‘ni tuzimadagi mavjud bitta element uchun aynan shu kalit qo‘llaniladi. Bunday kalit birlamchi deb ataladi. Elementlarning ma‘lum guruhi uchun takrorlanishi mumkin bo‘lgan kalit ikkilamchi kalit deyiladi, ushbu kalit bo‘yicha ham qidiruv tashkil qilish mumkin. Ma‘lumot elementlarining kalitlari alohida joyda to‘plangan (boshqa jadvalda) bo‘lishi yoki o‘zi alohida yozuvdagi biror bir maydonda saqlanishi mumkin. Bunday ajratib olingan yoki alohida faylda saqlanadigan tashqi kalit deyiladi. Agar kalit yozuvda joylashgan bo‘lsa, u holda ichki kalit deyiladi.
Berilgan argument bo‘yicha qidiruv berilgan argument kaliti bilan aniqlangan algoritm deyiladi. Qidiruv algoritmi ishlashi natijasi ushbu ma‘lumotda joylashishi mumkin yoki u jadvalda mavjud bo‘lmasligi mumkin. Ma‘lumotning mavjud bo‘lmaslik holati ikkita amalda yuz berishi mumkin:

1. 
   berilgan qiymatning yo‘qligini aniqlashda;
   
2. 
   berilgan qiymatni jadvalga qo‘yishda.
   

Masalan, bizga ro‘yxat elementi kaliti sifatida k berilgan bo‘lsin. Har bir k(i) kalitda r(i)-ma‘lumot mavjud. Qidiruv argumenti - Key. Unga yozuv ma‘lumoti rec mos keladi. Jadvalda ma‘lumotlar tuzilmasiga bog‘liq holda qidiruvning bir nechta shakllari farqlanadi.
Bu masalani yechish uchun ikki xil yondoshuv mavjud: ketma-ket qidiruv va
indeksli ketma-ket qidiruv. Ushbu qidiruv algoritmlarini o‘rganib chiqamiz.
Ketma-ket qidiruv algoritmi
Qidiruv algoritmlarida biror aniq elementni mavjud ro‘yxat elementlarini birma-bir qarab chiqish orqali qidirib topish masalasi hal qilinadi. Ketma-ket qidiruv algoritmida ro‘yxatning saralanganligi ahamiyatga ega bo‘lmasa-da, lekin saralangan ro‘yxatda eng yaxshi natijaga erishiladi. Odatda qidiruv kerakli elementning ro‘yxatda bor yoki yo‘qligini shunchaki tekshirish uchun emas, balki shu kalit-qiymatga ega bo‘lgan ma‘lumotni ajratib olish uchun ham qo‘llaniladi. Masalan, kalit-qiymat qidirilayotgan elementning tartib raqami yoki boshqa unikal (yagona) identifikator bo‘lishi mumkin. Kerakli kalit topilgandan so‘ng dastur shu kalitga mos ma‘lumotlarni o‘zgartirishi yoki shunchaki barcha yozuvlarni ajratib chiqarishi mumkin. Har qanday holatda ham qidiruv algoritmi kalitning joylashgan o‘rnini aniqlash masalasini yechish uchun qo‘llaniladi. SHuning uchun ham qidiruv algoritmlari kerakli kalitdan tarkib topgan yozuv indeksini natija sifatida ajratib beradi. Agar kalit-qiymat topilmasa, u holda qidiruv algoritmi massivning yuqori chegarasidan katta bo‘lgan indeks qiymatini qaytaradi. Maqsadga erishish uchun ro‘yxat elementlari 1 dan N gacha bo‘lgan sonlar yordamida raqamlangan bo‘lsin deb faraz qilamiz. Bu holatda qidirilayotgan kalit ro‘yxatda mavjud bo‘lmasa, algoritm 0 qiymatni beradi (1-rasm). Soddalik uchun ajratib olinadigan kalit-qiymatlar ro‘yxatda takrorlanmaydi deb qabul qilinadi.



1-rasm

Ketma-ket qidiruv algoritmi ro‘yxatning birinchi elementidan boshlab oxirgi elementgacha qidirilayotgan elementni topilmaguncha qarab chiqiladi. Bundan kelib chiqadiki, kalit qiymati ro‘yxatda qancha uzoqda turgan bo‘lsa, qidiruv shuncha uzoq davom etadi (vaqtga nisbatan). Bu holatni ketma-ket qidiruv algoritmi tahlilida e‘tiborga olish zarur bo‘ladi.

Binary Search (ya'ni ikkilik qidirish) bir turi yordam orqali biron bir saralangan ro'yxat ichida qidirishni bajaradigan algoritm hisoblanadi. Algoritm bir nechta qadamda bajariladi:

1. 
   Ro'yxatni saralash
   

Algoritm ro'yxatni saralaydi. Binary Search faqatgina saralgan ro'yxatda ishlaydi.

2. 
   Markaziy elementni aniqlash
   

Keyin, ro'yxatning o'rta elementini aniqlaydi. Agar ro'yxatning juft sonli elementlari bo'lsa, markaziy elementni ikki elementdan birini tanlash orqali aniqlaydi.

3. 
   Qidiruvni boshlash
   

Qidiruvni boshlash uchun, algoritm ma'lum bir qiymatni ro'yxatning markaziy elementi bilan solishtiradi. Agar qiymat katta bo'lsa, qidirishni markaziy elementning o'ng yarimiga olib boradi. Aks holda, markaziy elementning chap yarimiga qidiruvni davom ettiradi.

4. 
   Qiymatni topish
   

Keyingi qadamda, qidiruv natijasiga qarab ma'lum bir qiymatni topadi. Agar qiymat ro'yxatda mavjud bo'lsa, indeksni qaytaradi. Aks holda, qiymat yo'qligini bildiruv xabar qaytaradi.

Binary Search algoritmida foydalaniladigan saralash usuli O(log n) vaqtni talab qiladi, shuning uchun bu katta ro'yxatlarda qidiruv uchun juda samarali algoritm hisoblanadi.