|
Qidiruv algoritmlari
Reja:
1.Qidiruv;
2.Ketma-ket qidiruv algoritmi;
3.Algoritm tahlili.
4.Xulosa.Foydalanilgan adabiyotlar
Ro‘yxatdan zarur axborotni qidirish - nazariy dasturlashning fundamental masalalaridan biri hisoblanadi. Qidiruv algoritmini tahlil qilishda, qidirilayotgan axborot kompyuterda ma‘lumotlar massivi ko‘rinishida joylashgan deb faraz qilamiz. Yozuvlar yoki ro‘yxat elementlari massivda ketma-ket joylashadi va ular o‘rtasida bo‘shliq yo‘q. Ro‘yxatdagi yozuvlar 1 dan N gacha tartiblangan bo‘ladi. Aslida yozuvlar maydonlardan tashkil topgan bo‘ladi, bizni kalit deb ataluvchi maydonlardan bittasining qiymati qiziqtiradi. Ro‘yxatlar kalit maydonlari qiymati bo‘yicha tartiblangan yoki tartiblanmagan bo‘lishi mumkin. Aniq qiymatni qidirish masalasi biror elementni tanlash masalasi bilan bog‘liq. Aytaylik, bizga kattaligi bo‘yicha beshinchi element, oxiridan yettinchi yoki o‘rta qiymatli element kerak.
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:
Chiziqli algoritmlar
Har qanday murakkab algoritmni ham uch asosiy struktura yordamida tasvirlash mumkin. Bular ketma-ketlik, ayri va takrorlash strukturalaridir. Ushbu strukturalar asosida chiziqli, tarmoqlanuvchi va takrorlanuvchi hisoblash jarayonlarining algoritmlarini tuzish mumkin. Umuman olganda, algoritmlarni shartli ravishda quyidagi turlarga ajratish mumkin:
chiziqli algoritmlar;
tarmoqlanuvchi algoritmlar;
takrorlanuvchi algoritmlar;
ichma-ich joylashgan takrorlanuvchi algoritmlar;
rekurrent algoritmlar;
takrorlanishlar soni oldindan no’malum algoritmlar; - ketma-ket yaqinlashuvchi algoritmlar.
Chiziqli algoritmlar blok–sxemasining umumiy tuzilishi
Faqat ketma-ket bajariladigan amallardan tashkil topgan algoritmlarga - chiziqli algoritmlar deyiladi. Bunday algoritmni ifodalash uchun ketma-ketlik strukturasi ishlatiladi. Strukturada bajariladigan amal mos keluvchi shakl bilan ko‘rsatiladi. Chiziqli algoritmlar blok-sxemasining umumiy tuzilishi rasmda keltirilgan.
Uchburchak tomonlarining uzunligi bilan berilgan. Uchburchakka ichki r va tashqi R chizilgan aylanalar radiuslarini hisoblang.
Ichki chizilgan aylana radiusi r = (a+b+c)/2S, tashqi chizilgan aylana
4S radiusi R= formulalar orqali hisoblanadi. Bu yerda S - uchburchakning yuzi, a, abc
b, c – uchburchak tomonlarining uzunliklari. Masala echimining blok-sxemasi
keltirilgan.
Uchburchakka ichki va tashqi chizilgan aylanalar radiuslarini hisoblash bloksxemasi
. Quyida keltirilgan munosabatni hisoblash algoritmini ko‘rib chiqaylik. Jarayon amallarni ketma-ket bajarilishidan iborat.
z x= 2 + sin(x + y) ,
bu yerda x = cos ( a – b ), y = ln ( a2 - x2 ), a = 0.7, b = 2.1.
Bunda:
a, b - aniq qiymatga ega bo‘lgan boshlang‘ich ma’lumotlar; x, y - oraliq ma’lumotlar; z - natija.
Masalani yechish jarayoni chiziqli hisoblanadi, chunki boshlang‘ich ma’lumotlar kiritilgach, munosabatlarning qiymati dasturda joylashgan tartibda hisoblanadi, ya’ni dastlab x, so‘ng - y qiymati va nihoyat z natija hisoblanadi.
Mazkur jarayonning blok-sxemasi keltirilgan.
Hisoblash blok-sxemasi
6. Tarmoqlanuvchi algoritmlar
Agar hisoblash jarayoni biror-bir berilgan shartning bajarilishiga qarab turli tarmoqlar bo‘yicha davom ettirilsa va hisoblash jarayonida har bir tarmoq faqat bir marta bajarilsa, bunday hisoblash jarayonlari tarmoqlanuvchi algoritmlar deyiladi. Tarmoqlanuvchi algoritmlarni tasvirlash uchun “ayri” tuzilmasi ishlatiladi. Tarmoqlanuvchi tuzilmasi berilgan shartning bajarilishiga qarab ko‘rsatilgan tarmoqdan faqat bittasining bajarilishi ta’minlanadi.
. Tarmoqlanishning umumiy ko‘rinishiBerilgan R-shart romb figurasi ichida tasvirlanadi. Agar shart bajarilsa, "ha" tarmoq bo‘yicha A-amal, aks holda (shart bajarilmasa) "yo‘q" tarmoq bo‘yicha V-amal bajariladi.
Tarmoqlanuvchi algoritmga misol sifatida quyidagi sodda masala keltiriladi:
x2 , agar x ≥ 0 у=
2x, aks holda.
Natijaviy qiymat y berilgan x ning qiytmatiga bog‘liq holda bo‘ladi: agar x≥0 shart rost bo‘lsa, tarmoq bo‘yicha y = x2 munosabatning qiymati, aks holda, y = 2*x munosabatning qiymati hisoblanadi. Bu masala bajarilishining so‘z bilan ifodalangan algoritmi quyidagicha:
agar ( x ≥ 0 ) shart bajarilsa, u holda u=x2, aks holda u=2*x.
Masala echimining blok-sxemasi rasmda keltirilgan.
Interval ko‘rinishidagi funksiya qiymatini hisoblash blok-sxemasi
Ko‘pgina masalalarni yechishda, shart asosida tarmoqlanuvchi algoritmning ikki tarmog‘idan biri, ya’ni «rost» yoki «yolg‘on»ning bajarilishi etarli bo‘ladi. Bu holat tarmoqlanuvchi algoritmning xususiy holi sifatida qisqartirilgan strukturasi deb atash mumkin. Qisqartirilgan struktura blok-sxemasi quyidagi ko‘rinishga ega
. Berilgan x, y, z sonlar ichidan eng kattasini topish blok-sxemasi
Ushbu masalani yechish algoritmining yana bir usulini ko‘rib chiqamiz.
kiritish (x, y, z);
p = x;
agar (p < y ) bo‘lsa, u holda p= y; 4) agar (p < z ) bo‘lsa, u holda p= z; 5) muhrlash (r).
Bu algoritmga mos blok-sxema rasmda tasvirlangan.
Bu usulga asosan, avvalo sonlar ichida birinchisi eng kattasi deb faraz qilinadi, ya’ni p = x. So‘ngra har bir qadamda navbatdagi son – r ning qiymati bilan solishtiriladi va shart bajarilsa, u eng kattasi deb qabul qilinadi. Bu algoritmning afzalligi shundaki, uning asosida uchta va undan ko‘p sonlar ichidan eng kattasini (kichigini) topishning qulay imkoniyati mavjud.
. Hisoblash blok-sxemasi
. Quyidagi ifoda bilan berilgan munosabatni hisoblang [2, 52 b.].
b − x, agar x > 0,
Y = x + a, agar x < 0,
a + b, aks holda .
Bu misol natija x ning qiymatiga bog‘liq shart bilan berilgan va masala quyidagicha so‘zlar orqali ifodalangan algoritm asosida aniqlanadi: agar x > 0 bo‘lsa, u holda u = b - x bo‘ladi, aks holda; agar x < 0 bo‘lsa, u holda u = x + a, aks holda u = a+ b.
Avvalo, birinchi shart tekshiriladi va agar u bajarilsa, y = b - x amal
x + a, agar x < 0, bajariladi, aks holda Y munosabat hisoblanadi.
a + b, aks holda .
Bu fikrlar quyidagi blok-sxemada o‘z aksini topgan.
Hisoblash blok-sxemasi
Binar qidiruv( Binary Search )
Aytaylik bizga tartiblangan n ta elementdan iborat arr[] massiv berilgan bo'lsin, va berilgan x ni arr[] ichidan qidirish funksiyasini tuzish sharti qo'yilsin.
Bu holatda eng oson yo'l sifatida chiziqli qidiruvni misol keltirish mumkin. Ammo bu usulning vaqt davomiyligi O(n) ni tashkil qiladi. Xuddi shu vazifa uchun biz binar qidir algoritmini ishlatsak bo'ladi.
Binar qidiruv
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1)
Eng yomon ko'rsatkichi(vaqt): O(log n)
O'rtacha ko'rsatkichi(vaqt): O( log n)
Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi, ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki massivning elementlari qolmaguncha.
Masalan:
Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
1. x ni o'rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.
Quyida Binar qidiruvning rekursiya orqali amalga oshiramiz.
// C++ tilida rekursiyali Binar Qidiruv
#include
// Rekursiyali qidiruv funksiyasi. U massivdan
// x qaysi o'rinda turganini qaytaradi,
// yoki -1
int binarqidiruv(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// Agar element x ga teng bo'lsa
// o'zi qaytadi
if (arr[mid] == x)
return mid;
// Agar element x dan katta bo'lsa,
// u faqat chap qismni oladi
if (arr[mid] > x)
return binarqidiruv(arr, l, mid-1, x);
// Yoki u faqat o'ng qismni oladi
return binarqidiruv(arr, mid+1, r, x);
}
// Bu yerga yetib keladi, qachonki
// x soni massiv ichidan topilmasa
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
//massiv ni elementlar sonini topib olayabmiz
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int natija = binarqidiruv(arr, 0, n-1, x);
(natija == -1)? printf("X soni massivni ichidan topilmadi.")
: printf("X soni massivning %d - elementi.",
natija);
return 0;
}
Dastur ishlaganda " X soni massivning 3 - elementi." degan yozuvni qaytaradi. Sababi massiv elementlari 0 dan boshlanadi.
Binar qidiruvning yana bir ko'rinishi Interative (ingliz tilida ) orqali ko'rsatamiz.
// C++ tilida interative binar qidiruv
#include
// Interative binar qidiruv funksiyasi. U massivdan
// x qaysi o'rinda turganini qaytaradi,
// yoki -1
int binarqidiruv(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
// X o'rtadagi elementga tengmi yo'qmi tekshiramiz
if (arr[m] == x)
return m;
// Agar x katta bo'lsa, chapni hisobga olmaymiz
if (arr[m] < x)
l = m + 1;
// Aks holda o'ng tarafni hisobga olmaymiz
else
r = m - 1;
}
// Dastur bu yerga qachonki x element topilmaganda yetib keladi.
return -1;
}
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
// Elementlar sonini n ga o'zlashtirayabmiz
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int natija = binarqidiruv(arr, 0, n-1, x);
(natija == -1)? printf("X soni massiv ichida topilmadi.")
: printf("X soni massivning %d o'rnida.", natija);
return 0;
}Xesh-funksiya (inglizcha hash funksiyasi - “qiyma go‘shtga aylantirish”, “mash” [1]) yoki konvolyutsiya funksiyasi ixtiyoriy uzunlikdagi kirish ma’lumotlari qatorini belgilangan uzunlikdagi chiqish bit qatoriga aylantiruvchi funksiyadir. , ma'lum bir algoritm tomonidan amalga oshiriladi. Xesh-funksiya tomonidan amalga oshiriladigan transformatsiyaga xesh deyiladi. Asl ma'lumotlar kirish massivi, "kalit" yoki "xabar" deb ataladi. Transformatsiya natijasi "xesh", "xesh-kod", "xesh summasi", "xabar xulosasi" deb nomlanadi.
Xesh funktsiyalari quyidagi hollarda qo'llaniladi:
assotsiativ massivlarni qurishda;
ma'lumotlar to'plamlari ketma-ketligida dublikatlarni qidirishda;
ma'lumotlar to'plamlari uchun noyob identifikatorlarni qurishda;
ma'lumotlarni saqlash va (yoki) uzatishda yuzaga keladigan xatolarni (tasodifan yoki qasddan kiritilgan) keyinchalik aniqlash uchun ma'lumotlardan (signallardan) nazorat summalarini hisoblashda;
xavfsizlik tizimlarida parollarni xesh-kod ko'rinishida saqlashda (xesh-kod yordamida parolni tiklash uchun ishlatiladigan xesh funktsiyasiga teskari funktsiya talab qilinadi);
elektron imzoni ishlab chiqishda (amalda, ko'pincha xabarning o'zi emas, balki uning "xesh tasviri" imzolanadi);
va boshq.
Umumiy holatda (Dirichlet printsipiga ko'ra) xesh-kod va dastlabki ma'lumotlar o'rtasida birma-bir yozishmalar mavjud emas. Xesh funksiyasi tomonidan qaytarilgan qiymatlar kirish massividagi qiymatlardan kamroq farqlanadi. Xesh funksiyasi bir nechta kirish ma'lumotlar massivlarini bir xil xulosalarga aylantiradigan holat "to'qnashuv" deb ataladi. To'qnashuvlar ehtimoli xesh funktsiyalarining sifatini baholash uchun ishlatiladi.
Turli xil xususiyatlarga ega ko'plab xesh algoritmlari mavjud. Misol xususiyatlari:
bit chuqurligi;
hisoblash murakkabligi;
kriptografik kuch.
U yoki bu xesh-funktsiyani tanlash hal qilinayotgan muammoning o'ziga xos xususiyatlari bilan belgilanadi. Xesh funktsiyasining eng oddiy misoli - bu
|
