Algoritmlarni loyihalashtirish fanidan

Algoritmlarni loyihalashtirish fanidan

2-	laboratoriya ishi

LABORATORIYA mavzusi	2. Ma’lumotlarni qidirish algoritmlarining tartibli statistikasi.
Quyida keltirilgan topshiriqlarning natijalarini belgilangan muddatga qadar (keyingi laboratoriya darsiga qadar) tizimiga joylashtirishingiz talab etiladi. Laboratoriya ishlarini keltirilgan namuna asosida bajarishingiz so`raladi.

Ish tartibi:

• 
  Labaratoriya ishini nazariy ma’lumotlarini o`rganish;
  
• 
  Berilgan topshiriqni algoritmini ishlab chiqish;
  
• 
  Ixtiyoriy dasturlash muhitida dasturni yaratish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hujatlashtirib tizimga yuklash.
  

Ishdan maqsad

Ushbu laboratoriya ishining maqsadi talabalar qidirishning qanday usullari va algoritmlari mavjudligini, ularning samaradorliklarini baholashni o`rganishlari kerak. Shu asosda qidirish usullarini qiyosiy tahlil qilishlari va ularga oid dasturlar tuzishni o`zlashtirishlari kerak.

Nazariy qism

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 iborat. Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi.

Ma’lumotlarni qidirish algoritmlari bu – to’plam ma’lumotlar orasidan ma’lum bir kalit so’zga mos keluvchi elementlarni qidirshga aytiladi. Hozirgi davrda qidiruv algoritmlarisiz ishaydigan IT tizimlar deyarli mavjud emas.

Ma’lumotlarni qidirish algoritimlari odatda ikki toifaga bo’linadi bular quyidagilar:

1. 
   Tarkibiy qidiruv: Bunda ro'yxat yoki qator ketma-ket o'tkaziladi va har bir element tekshiriladi. Masalan chiziqli qidiruv.
   

Chiziqli qidiruv – bunda berilgan kalit chiziqli ketma ketlikda to’plam elementlari orasidan qidirib chiqiladi. Bu algoritm ancha sodda lekin sekin hisoblanadi.

2. 
   Intervalli qidirish: Ushbu algoritmlar maxsus ajratilgan ma'lumotlar tuzilmalarida qidirish uchun mo'ljallangan. Ushbu turdagi qidiruv algoritmlari Linear Search-ga qaraganda ancha samaralidir, chunki ular qayta-qayta qidiruv tuzilmasi markaziga yo’naladi va qidiruv maydonini ikkiga bo’ladi. Masalan: Ikkilik qidiruv.
   

Ikkilik qidiruv algoritmi – Bu algoritm asosan to’plamni ikkiga bo’lishlar orqali qidirishdan iborat. Yani unda bo’linishlar toki kalit so’z topilmagunicha davom etadi.

Yuqoridagilardan tashqari qidiruv algoritmlarini quyidagi turlari mavjud:

• 
  Jump Search.
  
• 
  Interpolatsiya qidiruvi.
  
• 
  Eksponensial qidiruv.
  
• 
  Sublist qidiruv. Va h-k.
  

Misol tariqasida Ikkilik qidiruvni rekursiv shaklda Java dasturlash tilida ifoda qiladigan bo’lsey quyidagi ko’rinishga ega bo’ladi:

class BinarySearch {

int binarySearch(int arr[], int l, int r, int x)

{

if (r >= l) {

int mid = l + (r - l) / 2;

if (arr[mid] == x)

return mid;

if (arr[mid] > x)

return binarySearch(arr, l, mid - 1, x);

//

return binarySearch(arr, mid + 1, r, x);

}

//

return -1;

}
//

public static void main(String args[])

{

BinarySearch ob = new BinarySearch();

int arr[] = { 2, 3, 4, 10, 40 };

int n = arr.length;

int x = 10;

int result = ob.binarySearch(arr, 0, n - 1, x);

if (result == -1)

System.out.println("Element topilmadi");

else

System.out.println("Element indeksi - " + result);

}

}

Ixtiyoriy ma’lumot (yoki tuzilma 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 yagona bo’lishi mumkin. Bunday noyob kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali ham qidiruvni amalga oshirish mumkin. Ma’lumotlar kalitini bir joyga yig’ish (boshqa jadvalga) yoki yozuv sifatida ifodalab bitta maydonga kalitlarni yozish mumkin. Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya’ni yozuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi. Kalitni berilgan argument bilan mosligini aniqlovchi algoritmga berilgan argument bo’yicha qidiruv deb ataladi. Qidiruv algoritmi vazifasi kerakli ma’lumotni jadvaldan topish yoki yo’qligini aniqlashdan iboratdir. Agar kerakli ma’lumot yo’q bo’lsa, u holda ikkita ishni amalga oshirish mumkin:

1. Ma’lumot yo’qligini indikatsiya qilish (belgilash)

2. Jadvalga ma’lumotni qo’yish.

Faraz qilaylik, k – kalitlar massivi. Har bir k(i) uchun r(i) – ma’lumot mavjud. Key – qidiruv argumenti. Unga rec - informatsion yozuv mos qo’yiladi. Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvning bir necha turlari mavjud.

Ketma-ket qidiruv algoritmi

Mazkur ko’rinishdagi qidiruv agar ma’lumotlar tartibsiz yoki ular tuzilishi noaniq bo’lganda qo’llaniladi. Bunda ma’lumotlar butun jadval bo’yicha operativ xotirada kichik adresdan boshlab, to katta adresgacha ketma-ket qarab chiqiladi.

Massivda ketma-ket qidiruv (search o’zgaruvchi topilgan element tartib raqamini saqlaydi).

Ketma-ket qidiruv algoritmi C++ tilida quyidagicha bo’ladi:

int qidiruv(int key)

{ for (int i=0;i

if (k[i]==key) { search = i;return search;}

search = -1;

return search;

}}

Ushbu qidiruv usullarini o’rganish jarayonida biz tuzilmaning shakliga qarab biror kalitga mos elementni qidirishning optimal usulini qo’llashni o;rganishimiz va qidiruv usullarining samaradorligini taqqoslashni o’rganishimiz mumkin.Kompyuterda ma’lumotlarni qidirish asosiy amallardan biri hisoblanadi.Qidirishdan asosiy maqsad berilgan argument bo’yicha massiv ma’lumotlari ichidan mazkur argumentga mos ma’lumotlarni topish yoki bunday ma’lumot yo’qligini aniqlashdan iborat. Ixtiyoriy ma’lumot (yoki tuzilma 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 yagona bo’lishi mumkin. Bunday noyob kalitga boshlang’ich (birinchi) kalit deyiladi. Ikkinchi kalit bir jadvalda takrorlansada u orqali ham qidiruvni amalga oshirish mumkin.

Transpozitsiya usuli

Ushbu usulda topilgan element ro’yhatda bitta oldingi element bilan o’rin almashtiriladi. Agarda mazkur elementga ko’p murojaat qilinsa, bittadan oldinga surilib borib natijada ro’yhat boshiga kelib qoladi. Ushbu usulning afzalligi shundaki, tuzilmada ko’p murojaat qilinadigan elementlar ro’yhat boshiga bitta qadam bilan intiladi.

Ushbu usulning qulayligi u nafaqat ro’yhatda, balki tartiblanmagan massivda ham samarali ishlaydi (sababi faqatgina ikkita yonma-yon turgan element o’rin almashtiriladi). Bu usulda uchta ko’rsatkichdan foydalanamiz

p – ishchi ko’rsatkich

q – yordamchi ko’rsatkich, p dan bitta qadam orqada bo’ladi

s – yordamchi ko’rsatkich, p dan ikkita qadam orqada bo’ladi

Biz tomonimizdan topilgan uchinchi element ro’yhat boshiga bir qadam suriladi (ya’ni ikkinchi bo’lib qoladi). Birinchi element ko’rsatkichi uchinchi elementga joylashtiriladi, ikkinchi element ko’rsatkichi to’rtinchi, shunday qilib uchinchi element ikkinchi joyga joylashib qoladi. Agar mazkur elementga yana bir bor murojaat qilinsa, u holda u ro’yhat boshida bo’lib qoladi.

node *s=NULL;

node *q=NULL;

node *p=table;

while (p != NULL){

if (key == p->k){ //transponerlaymiz

if( q ==NULL){//o‘rinlashtirish shart emas

search=p;

exit(0); }

q->nxt=p->nxt;

p->nxt=q;

if (s == NULL) table = p;

else s->nxt = p;

search=p; exit(0);

}

s=q;

q=p;

p=p->nxt; }

search=NULL;

exit(0);

Labaratoriya ishi topshiriqlari

Topshiriq 1. Qidiruv masalalarini algoritmi va dasturini yozing

1-variyant. Ketma-ket qidiruv usulidan foydalanib, A massiv eng kichik elementini toping.

2-variyant. A massiv berilgan, A massivdagi elementlar orasidan 30 dan katta elemeni toping.

3-variyant. Ketma-ket qidiruv usulidan foydalanib, A massiv elementlari orasidan 3(3,6,9, …) ga karralilarini ekranga chiqaring.

4-variyant. Ketma-ket qidiruv usulidan foydalanib moduli 20 dan katta va 50 dan kichik elementlarni toping.

5-variyant. Ketma-ket qidiruv usulidan foydalanib, A massiv elementlari orasidan 4(4,8,…) ga karralilarini ekranga chiqaring.

6-variyant. Ketma-ket qidiruv usulidan foydalanib 50 dan katta sonlarni ekranga chiqaring.

7-variyant. Ketma-ket qidiruv usulidan foydalanib, A massivda elementlarni va taqqoslashlar sonini toping.

8-variant. Binar qidiruvdan foydalanib elementlami tasodifiy ravishda toping.

9-variant. Mashina raqamlari ro’yxati bcrilgan: 145, 368. 876, 945, 511, 387, 230. Binar qidiruvdan foydalanib berilgan raqamli mashina qaysi joyda turganini toping.

10-variant. Ro’yxatda har ikkinchi elementni qidiring va taqqoslashair sonini aniqlang.

11-variant. Qo’shni elementlari ayirmasi juft va 3 ga bo’linadigan elementni toping. Agar bunday element mavjud bo’lmasa - shunga mos ma’lumot chiqaring.

12-variant. Berilgan massiv elementlari ichidan eng katta elementni topilsin.

13-variant. Berilgan massiv elementlari ichidan eng kichik elementi topilsin.

14-variant. 11 ga butun bo’linuvchi eng katta sonni toping (agar bunday sonlar ko’p bo’lsa, u holda ularning eng kattasini toping; agar bunday son mavjud bo’lmasa - shunga mos ma’lumot chiqaring).

15-variant. 11 ga butun bo’linuvchi eng katta sonni toping (agar bunday sonlar ko’p bo’lsa, u holda ularning eng kichigini toping; agar bunday son mavjud bo’lmasa - shunga mos ma’lumot chiqaring).

16-variant. Qo’shni elementlari ayirmasi 72 dan kichik bo'lgan elementni toping. Agar bunday elementlar ko’p bo’lsa, u holda ularning eng kattasini toping; agar bunday element mavjud bo’lmasa shunga mos ma’lumot chiqaring.

17-variant. Qo’shni elementlari bo’linmasi juft son bo’lgan elementni toping. Agar bunday elementlar ko’p bo’lsa, u holda ularning eng kattasi yoki eng kichigini toping; agar bunday element mavjud bo’lmasa - shunga mos ma’lumot chiqaring.

18-variant. Kerakli elementdan keyingi elementlarning o’rtacha kvadratik qiymati 10 dan kichik bo’lgan elementni toping. Agar bunday elementlar ko’p bo’lsa, u holda ularning eng kattasini toping; agar bunday element mavjud bo’lmasa- shunga mos ma’lumot chiqaring.