Algoritmlarni loyihalashtirish fanidan

Algoritmlarni loyihalashtirish fanidan

1-	laboratoriya ishi

LABORATORIYA mavzusi	1. Ma’lumotlarni saralash algoritmlarini 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 saralash va qidirishning qanday usullari va algoritmlari mavjudligini, ularning samaradorliklarini baholashni o`rganishlari kerak. Shu asosda saralash va qidirish usullarini qiyosiy tahlil qilishlari va ularga oid dasturlar tuzishni o`zlashtirishlari kerak.

Nazariy qism

Ma’lumotlarni kompyuterda qayta ishlashda elementning informatsion maydoni va uning mashina xotirasida joylashishini bilish zarur. Shu maqsadda ma’lumotlarni saralash amalga oshiriladi. Demak, saralash – bu ma’lumotlarni kalitlari bo`yicha doimiy ko`rinishda mashina xotirasida joylashtirishdan iborat. Bu yerda doimiylik ma’lumotlarni massivda kalitlari bo`yicha o`sish tartibida berilishi tushuniladi.

Ma’lumotlarga qayta ishlov berilayotganda ma’lumotning informatsion maydonini hamda uning mashinada joylashishini (adresini) bilish zarur.

Saralashning ikkita turi mavjud:

1. 
   ichki saralash bu operativ xotiradagi saralash;
   
2. 
   tashqi saralash – tashqi xotirada saralash.
   

Agar saralanayotgan yozuvlar xotirada katta hajmni egallasa, u holda ularni almashtirishlar katta sarf (vaqt va xotira ma`nosida) talab qiladi. Ushbu sarfni kamaytirish maqsadida, saralash kalitlar adresi jadvalida amalga oshiriladi. Bunda faqatgina ma’lumot ko`rsatkichlari almashtirilib, massiv o`z joyida qoladi. Bu usul adreslar jadvalini saralash usuli deyiladi.

Saralanayotganda bir xil kalitlar uchrashi mumkin, bu holda saralangandan keyin bir xil kalitlilar boshlang`ich tartibda qanday joylashgan bo`lsa, shu tartibda qoldirilishi maqsadga muvofiq bo`ladi (Bir xil kalitlilar o`zlariga nisbatan). Bunday usulga turg`un saralash deyiladi.

Saralash samaradorligini bir necha mezonlar bo`yicha baholash mumkin:

• 
  saralashga ketgan vaqt;
  
• 
  saralash uchun talab qilingan operativ xotira;
  
• 
  dasturni ishlab chiqishga ketgan vaqt.
  

Birinchi mezonni qarab chiqaylik. Saralash bajarilganda taqqoslashlar yoki almashtirishlar sonini hisoblash mumkin.

Faraz qilaylik, N = 0,01n2 + 10n – taqqoslashlar soni. Agar n < 1000 bo`lsa, u holda ikkinchi qo`shiluvchi katta, aks holda ya`ni, n > 1000 bo`lsa, birinchi qo`shiluvchi katta bo`ladi. Demak, kichkina n larda taqqoslashlar soni n ga teng bo`ladi, katta n larda esa n2 ga teng bo`ladi.

Saralashning quyidagicha usullari bor:

• 
  qat’iy (to`g`ridan-to`g`ri) usullar;
  
• 
  yaxshilangan usullar.
  

Saralash jarayoni qanday kechadi? Saralash jarayoni taqqoslashga asoslangan jarayon hisoblanadi. Bu jarayonni his qilish uchun miyamizdagi tezlik bilan kechayotgan jarayonlarni birma-bir tahlil qilib chiqamiz(buning uchun saralanmagan sonlar ketma-ketligini olamiz)

Sonlar berilishi: 23, 54, 3, 22, 1, 45;

1. 
   Eng kattasini oxiriga o`tkazamiz: 23, 3, 22, 1, 45, 54;(54 soni har bir son bilan solishtirilib eng katta ekani aniqlandi, 45 esa o`z o`rnida turibdi)
   
2. 
   Shu tartibni davom ettiramiz: 3, 22, 1, 23, 45, 54;(23 undan keyinda turuvchi eng katta son)
   
3. 
   Yuqoridagi amalni yana davom ettiramiz: 3, 1, 22, 23, 45, 54;(22 esa davomchi)
   
4. 
   Oxirgi marta almashtirishimiz quyidagi natijani beradi: 1, 3, 22, 23, 45, 54;(1 eng kichigi)
   

Misol uchun ASCII chalkash berilgan harflar saralanganda quyidagi ko’rinishda bo’ladi:



Yuqoridagi jarayonni o’ylash orqali biz saralash algoritmini tuzib oldik. Demak saralash algoritmlari bu – taqqoslash va o’rin almashtirishlarni tartibli ko’rinishi ekan.

Tanlash orqali saralash algoritmi.

Mazkur usul quyidagi tamoyillarga asoslangan:

1. Eng kichik kalitga ega element tanlanadi.

2. Ushbu element birinchi element bilan o'rin almashadi.

3. Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.

Misol:
arr[] = 64 25 12 22 11

//Eng kichik element massivni boshiga o’tkaziladi.
11 25 12 22 64
//Huddi shu ketma-ketlikda jarayon massiv oxirgi elementigacha davom etadi
11 12 25 22 64
11 12 22 25 64
11 12 22 25 64

Algoritm samaradorligi:

• 
  Taqqoslashlar soni
  
• 
  Massiv tartiblanganda o'rinlashtirishlar soni
  
• 
  Massiv teskari tartiblanganda o'rinlashtirishlar soni
  

Ushbu usul bo'yicha saralash bajarilsa, eng yomon holda taqqoslashlar va o'rinlashtirishlar soni tartibi n2 bo'ladi.

Ushbu algoritmning blok sxemasi quyidagi ko’rinishga ega:


“Bubble sort” eng ko`p vaqt talab qiluvchi saralash algoritmi hisoblanadi. Chunki unda n ta element uchun takrorlanishlar soni n*n ga teng. Bu, n kichik son bo`lsa unchalik sezilmaydi. Sababi, hozirgi zamonaviy kompyuterlar uchun bu takrorlanish soni qiyinchilik tug`dirmaydi. Ammo butun boshli ma`lumotlar bazasidagi ma`lumotlarni saralash talab etilsachi? Albatta vaqtdan yutqazamiz. Ammo, bu algoritm saralash algoritmlarini tushunib olish uchun ilk qadam hisoblanadi. Endi esa, bu algoritmlani kodga o`giramiz:

1-usul funksiyalar yordamida yoziladi.

public class BubbleSort {

public static void bubble_srt(int massiv[]) {// funksiyamizga saralash uchun saralanmagan bir o`lchamli massiv kiritiladi

int n = massiv.length;

int k;

for (int m = n; m >= 0; m--) {

for (int i = 0; i < n - 1; i++) {

k = i + 1;

if (massiv[i] > massiv[k]) {

almashtirish(i, k, massiv);//almashtirish uchun alohida funksiya

}

}

chiqarish(massiv);//chop etish uchun alohida funksiya

}

}

private static void almashtirish(int i, int j, int[] massiv) {

int temp;

temp = massiv[i];

massiv[i] = massiv[j];

massiv[j] = temp;

}

private static void chiqarish(int[] input) {

for (int i = 0; i < input.length; i++) {

System.out.print(input[i] + ", ");

}

System.out.println("\n");

}

public static void main(String[] args) {

int[] saralanmagan = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };

bubble_srt(saralanmagan);

}

}

2-usul esa faqat main funksiyaning ichida yozishga asoslangan.

Source code

public class BubbleSort {

  public static void main(String[] args) {

int[] massiv = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };

int n = massiv.length;

int k;

for (int m = n; m >= 0; m--) {

for (int i = 0; i < n - 1; i++) {

k = i + 1;

if (massiv[i] > massiv[k]) {

int temp;

temp = massiv[i];

massiv[i] = massiv[k];

massiv[k] = temp;

  }

}

for (int i = 0; i < massiv.length; i++) {

System.out.print(massiv[i] + ", ");

}

System.out.println("\n");

  }

  }

 }

Chiqariluvchi natijamiz esa:

2, 4, 6, 9, 12, 23, 0, 1, 34, // 1-qadam.

2, 4, 6, 9, 12, 0, 1, 23, 34, //2-qadam.

2, 4, 6, 9, 0, 1, 12, 23, 34,//3-qadam.

2, 4, 6, 0, 1, 9, 12, 23, 34,//4-qadam.

2, 4, 0, 1, 6, 9, 12, 23, 34,//5-qadam.

2, 0, 1, 4, 6, 9, 12, 23, 34,//6-qadam.

0, 1, 2, 4, 6, 9, 12, 23, 34, //7-qadam.

0, 1, 2, 4, 6, 9, 12, 23, 34, //8-qadam.

0, 1, 2, 4, 6, 9, 12, 23, 34,//9-qadam.

0, 1, 2, 4, 6, 9, 12, 23, 34, // saralangan holdagi massiv.


Labaratoriya ishi topshiriqlari

Topshiriq 1. Saralash masalalarini algoritmi va dasturini yozing

1. 
   Mashina egalarining ismlari bo`yicha alifbo tartibida joylashtirilsin va mos ravishda ularning mashinalari haqidagi ma’lumotlar chiqarilsin.
   
2. 
   Avtomobillarni ta`mirlash tartibi ishlab chiqilsin. Bu yerda ta`mir tugashi sanasi qaysi avtomobil uchun ertaroq bo`lsa, shunga birinchi navbatda xizmat ko`rsatiladi.
   
3. 
   Oldingi ta`mir qilinganlar soni 2 ga teng bo`lgan mashinalar raqamlari bo`yicha kamayish tartibida joylashtirilsin.
   
4. 
   Oldin ta`mir qilinmagan mashinalarni ta`mirdan chiqish sanasi bo`yicha o`sish tartibida joylashtiring.
   
5. 
   "Mersedes" markali mashina egalarini alifbo bo`yicha teskari tartibda joylashtiring.
   
6. 
   Boshqalaridan oldinroq ta`mirlanadigan mashinalarni ularning markasi bo`yicha alifbo tartibida joylashtiring (ta`mir tugatilishi sanasi 31.12.2019 dan erta).
   
7. 
   "Nexia" markasidagi mashinalarni raqamlari bo`yicha o`sish tartibida joylashtiring.
   
8. 
   O`tgan yildan beri ta`mirlanmagan mashinalarni ularning egalari ismlari bo`yicha alifbo tartibida joylashtiring.
   
9. 
   Keyingi oyda ta`mirlanishi lozim bo`lgan mashinalarni oxirgi marta ta`mirlanganlik sanasi bo`yicha o`sish tartibida keltiring.
   
10. 
    "Mersedes" markasidagi mashinalarni raqamlari bo`yicha kamayish tartibida joylashtiring.
    
11. 
    Talabalar familiyalarini alifbo tartibida joylashtiring.
    
12. 
    Talabalarni yoshi bo`yicha o`sish tartibida joylashtiring.
    
13. 
    Talabalarni umumiy bali bo`yicha o`sish tartibida joylashtiring.
    
14. 
    Talabalarni umumiy bali bo`yicha kamayish tartibida joylashtiring.
    

Topshiriq 2. Quyidagi nazariy savollarga javob bering

1. 
   Algoritm ta`rifini ayting
   
2. 
   Algoritmning xossalarini ayting
   
3. 
   Algoritmning to`liq qurish bosqichlarini sanab bering
   
4. 
   Algoritmik yechib bo`lmaydigan masalalarga misol keltiring