Muhammad al-Xorazmiy nomidagi Toshkent Axborot


Download 0.74 Mb.
Pdf ko'rish
Sana26.11.2020
Hajmi0.74 Mb.
#152679
Bog'liq
MTA


Muhammad al-Xorazmiy nomidagi Toshkent Axborot

 

Texnologiyalari Universiteti 



 

 

 



 

 

 



 

 

Ma`lumotlar tuzilmasi va algoritmlash fanidan 



Mustaqil ish №1 

 

Mavzu: Eng oddiy qatorlarni qayta ishlash algoritmlari



 

 

 

 

 

 

Bajardi:  Sultonov Isfandiyor 

Guruh:  218-19 

Tekshirdi:Ganixodjayeva Dilfuza 

 

 



 

 

 



 

Toshkent 2020 yil 

Mavzu: Eng oddiy qatorlarni qayta ishlash algoritmlari

 

Reja: 


I.  Algoritm  nima. 

II.  Qayta ishlash algoritmlari: 

1. Saralash algoritmlari 

2. Qidiruv algoritmlari 

III.  Xulosa  

IV.  Foydalanilgan adabiyotlar ro`yxati 

 

I. 

Algoritm – berilgan natijaga erishish uchun qilinishi kerak boʻlgan aniq koʻrsatmalar 

ketma-ketligi. Algoritm keng maʼnoda faqat kompyuterga oid atama boʻlmay, balki unda 

berilgan koʻrsatmalarni bajara oluvchi har qanday narsaga oiddir. Algoritm maʼlum bir turga 

oid masalalarni yechishda ish-latiladigan amallarning muayyan tar-tibda bajarilishi haqidagi 

aniq qoida. Kibernetika va mat.ning asosiy tushunchalaridan biri. O‘rta asrlarda sanoqning 

o‘nli tizimi bo‘yicha to‘rt arifmetik amal bajariladigan qoidani A. deb atashgan. "Bu 

qoidalarni mat.ga 9-asrda al-Xorazmiy kiritgan. Yevro-pada bunday qoidalar uning tugilgan 

yurtiga nisbatan lotinchalashtirilgan , keyinchalik "algoritm"ga aylangan" . Fanda "Yevklid 

algoritmi", "G‘iyosiddin Koshiy algoritmi", "Laure algoritmi", "Markov algoritmi" deb 

ataluvchi A.lar maʼlum. A. tushunchasi tobora kengayib borib, kibernetikaning nazariy va 

mantiqiy asosi hisoblangan A.lar nazariyasi paydo bo‘ldi. Oʻzbekiston Respublikasi da bir 

necha ilmiy tadqiqot muassasalari va hisoblash mar-kazlarida A.dan foydalanish sohasida 

samarali ishlar olib borilmoqda. Mas, O‘zbekiston Fanlar Akademiyasi "Kibernetika" ilmiy 

ishlab chiqarish birlashmasida, O‘zbekistondagi bar-cha universitetlarda, Toshkent davlat 

texnika untida, Oʻzbekiston Respublikasi Makroiqgisod va statistika vazirligi qoshidagi 

Hisoblash markazi va boshqa muassasalarda olib borilayotgan ishlar bunga misol bo‘la oladi. 

Algoritm so’zi Al – Xorazmiy nomining lotincha tal

affuzidan kelib chiqqan bo’lib.

 

Muxammad Muso Al-Xorazmiyning X asrda yaratilgan qo’llanmasida keltirilgan o’nlik sanoq 



sistemasida  arifmetik  amallarni  bajarish  qoidalari  soddaligi  tufayli  yevropada  ham  o’nlik 

sanoq  sistemasi  qo’llanishiga  turtki  bo’ldi.  Bu  qoidalar  tarjimasida  xar  bir  qoida  “Al-



Xorazmiy aytadiki” deb boshlangan va bora-bora talaffuz tufayli algoritm tarzida ifodalanib 

kelgan. 


  

Hozirgi paytda algoritm sifatida biror masalani ishlash yoki biror ishni bajarish uchun 

qilinishi kerak bo’lgan tartiblangan chekli sondagi aniq bir qiymatli ko’rsatmalar ketma-

ketligi tushiniladi. Algoritm tushunchasi keng ma’noda tahlil qilish mumkin.Masalan, biror 

manzildan boshqa manzilga borish uchun shahar transportidan foydalanib qanday borish 


mumkin, degan savolga biz ma’lum algoritm tavsiya qilishimiz mumkin. Pazandalik 

kitobida, masalan, palovni pishirish qoidasi keltiriladi. Bu ham o’ziga xos algoritm 

hisoblashlar ishlanadigan masala algoritmini biz hisoblash algoritmi deymiz. 

Biz asosan hisoblash algoritmlari haqida so’z yuritamiz. Algoritmlarga xos bo’lgan 

belgi va talablarni sanab o’tamiz. Har qanday algoritm quyidagi asosiy xususiyatlarga ega 

bo’lishi kerak: 



Determinantlik sifati 

Berilgan boshlangich qiymatlarda bir qiymatli javob olinishi; 



Ommaviylik sifati 

Ma’lum turdagi masalalar uchun turli boshlangich qiymatlarda yechim olish mumkin 

bo’lishi;  

Diskretlilik sifati 

Algoritmni EHM(Elektron Hisoblash Mashinalari) yoki inson tomonidan bajarilishi 

mumkinligi shubxasiz bo’lgan ayrim-ayrim sodda bosqichlarga bo’lish mumkinligi. 

Natijaviylik sifati 

Har qanday boshlangich qiymatlarda ham javobning mavjudligi, bunda «bu holda 

yechim yo’q» singari axborot ham algoritmning ishlash natijasi deb qabul 

qilinadi;Keltirilgan sifatlardan kelib chiqqan xolda algoritmni ifodalash va bajarish qoidalari 

xaqida so’z yuritish mumkin. Amaliyotda algoritmni ifodalashning uchta asosiy usullari 

fodalaniladi. Bular matnli ko’rinishi, sxematik(grafik) ko’rinishi, biror algoritmik tildagi 

(dasturiy) ifodasi. 

II.

1.

 

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`sishi  tartibida berilishi tushuniladi.  

Ma`lumotlarga  qayta  ishlov  berilayotganda  ma`lumotning  informatsion  

maydonini hamda uning mashinada joylashishini (adresini) bilish zarur.  

Saralashning ikkita turi mavjud: ichki va tashqi:  

-  ichki saralash bu operativ xotiradagi saralash;  

-  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,01

𝑛

2

  +  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 


𝑛

2

 ga teng bo`ladi.  



Saralashda taqqoslashlar soni quyidagi oraliqlarda bo„ladi:  

O (nlogn)    dan O(

𝑛

2

)gacha; O(n) – ideal holatda.  



Saralashning quyidagicha usullari bor:  

- qat`iy (to`g`ridan-to`g`ri) usullar;  

-  yaxshilangan usullar.  

Qatiy usullarning afzalliklarini ko„rib chiqaylik:  

1.  Bilamizki,  dasturlarning  o`zlari  ham  xotirada  joy  egallaydi.  To`g`ridan-  

To`g`ri saralash usullarining dasturlari qisqa bo`lib, ular tushunishga oson.   

2. To`g`ridan-to`g`ri saralash usullari orqali saralash tamoyillarining asosiy  

xususiyatlarini tushuntirish qulay.  

3.  Murakkablashtirilgan  usullarda  uncha  ko`p  amallarni  bajarish  talab   

qilinmasada,  ushbu  amallarning  o„zlari  ham  ancha  murakkabdir.  Garchi  yetarlicha  katta  n 

larda ulardan foydalanish tavsiya etilmasada, kichik n larda mazkur usullar tezroq ishlaydi.  

Shu  joyni  o`zida  qat`iy  usullarni  ishlash  tamoyillariga  ko`ra  3  ta  toifaga  



Bo`lish mumkin:  

1. To`g`ridan-to`g`ri qo`shish usuli (by insertion);   

2. To`g`ridan-to`g`ri tanlash usuli (by selection);   

3. To`g`ridan-to`g`ri almashtirish usuli (by exchange).  

 

To`g`ridan-to`g`ri qo`shish usuli bilan saralash algoritmi 

  

Bunday usul karta o`yinida keng qo`llaniladi. Elementlar (kartalar) hayolan  



“tayyor”  a(1),...,a(i-1)  va  boshlang`ich  ketma-ketliklarga  bo„linadi.  Har  bir qadamda  (i=2  

dan  boshlanib,  har  bir  qadamda  bir  birlikka  oshirib  boriladi) boshlang`ich ketma-ketlikdan 

i-chi element ajratib olinib tayyor ketma-ketlikning kerakli joyiga qo`yiladi.  

To`g`ridan-to`g`ri qo`shish orqali saralash algoritmi quyidagicha bo„ladi:  

                 for (int i=1;i

                  x=a[i];  

                  x ni a[0]...a[i] oraliqning mos joyiga qo‘shish  

                 }  

Kerakli joyni qidirish jarayonini quyidagi tartibda olib borish qulay bo`ladi.             

2-elementdan  boshlab  har  bir  elementni  qarab  chiqamiz,  ya`ni  har  bir  element o„zidan 

oldin  turgan  element  bilan  solishtiriladi. Agar  qaralayotgan  element  kichik  bo`lsa,   oldinda  

turgan  element  bilan  o`rin  almashadi  va  yana  o`zidan  oldinda turgan  element  bilan  

solishtiriladi,  jarayon  shu  kabi  davom  etadi.  Bu  jarayon quyidagi shartlarning birortasi 

bajarilganda to`xtatiladi:  

1. x elementi oldida uning kalitidan kichik kalitli a(j) elementi chiqqanda.  

2. x elementi oldida element qolmaganda.  

for (int i=1;i

      int j=i;  

      while(a[j]

            int t=a[j-1];  

            a[j-1]=a[j];  

            a[j]=t;  

            j=j-1;  

      }  

 }  

 


 

 

 

Tanlash orqali saralash algoritmi 

Mazkur usul quyidagi tamoyillarga asoslangan:  

1. Eng kichik kalitga ega element tanlanadi.  

2. Ushbu element a0  birinchi element bilan o„rin almashinadi.  

3.  Keyin  mazkur  jarayon  qolgan  n-1,  n-2  elementlar  bilan  takrorlanib,  to  

bitta eng “katta” element qolguncha davom ettiriladi.  

for(int i=0;i

for(int j=i+1;j

      if (a[i] > a[j]){  

         int k = a[j];  

          a[j]= a[i];  

          a[i]= k;  

          }       


 

To`g`ridan-to`g`ri almashtirish usuli 

 


2.

 

Ma’lumotlarni qayta ishlashda qidiruv asosiy amallardan biri bo‘lib, uning vazifasi 



berilgan argument (kalit) bo‘yicha ma’lumotlar bazasi ichidan mazkur argumentga mos 

ma’lumotlarni topish yoki yo‘qligini aniqlashdan iborat. 

 Agar kerakli ma’lumot yo‘q bo‘lsa, u holda ikkita ishni amalga oshirish mumkin: 

  ma’lumot yo‘qligini belgilash; 

  jadvalga ma’lumotni qo‘yish. 

  Ixtiyoriy ma’lumotlar majmuasi jadval yoki fayl deb ataladi. Ixtiyoriy ma’lumot (yoki 

tuzilma elementi) boshqa ma’lumotdan biror bir belgisi orqali farq qiladi. Mazkur belgi kalit 

deb ataladi.  

  Kalit ikki hil bo‘lishi mumkin: 

  birlamchi(takrorlanmaydi, noyob); 

  ikkilamchi(takrorlanadi). 

Ta’rif. 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. 

    Qidiruvning maqsadi - quyidagi jarayonlarning birini bajarilishidan iborat: 

  topilgan yozuvni o‘qish; 

  qidirilayotgan yozuv topilmasa, uni jadvalga qo‘yish; 

  topilgan yozuvni o‘chirish. 

     


    Faraz qilaylik, k – kalitlar massivi bo‘lsin. Har bir k(i) uchun r(i) – ma’lumot mavjud. 

Key – qidiruv argumenti.  

    Jadvaldagi ma’lumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud. 

Ketma-ket qidiruv algoritm 

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;  

}}  

Massivda  ketma-ket  qidiruv  algoritmi  samaradorligini  bajarilgan taqqoslashlar  soni  

M  bilan  aniqlash  mumkin.  Mmin  =  1,  Mmax  =  n.  Agar ma`lumotlar massiv 

yacheykasida bir xil ehtimollik bilan taqsimlangan bo‟lsa,  u  

holda Mo`rt 

≈ (n + 1)/2 bo‟ladi.

 

Agar  kerakli  element  jadvalda  yo`q  bo`lib,  uni  



jadvalga  qo‟shish  lozim  

bo`lsa, u holda yuqorida keltirilgan algoritmdagi oxirgi ikkita operator quyidagicha  

almashtiriladi.  

n=n+1;  

k[n-1]:=key;  

r[n-1]:=rec;  

search:=n-1;  

return search;  

Agar ma`lumotlar jadvali bir bog`lamli ro`yhat ko`rinishida berilgan bo`lsa u holda 

ketma-ket qidiruv ro`yhatda amalga oshiriladi.

 

 



Chiziqli  bir  bog‟lamli  ro`yhatdan  key  kalitga  mos  elementni  ketma-ket qidiruv usuli 

yordamida izlab topish dasturi.  



Node *q=NULL;  

Node *p=lst;  

while (p !=NULL){   

      if (p->k == key){  

          search = p;  

          return search;  

          }  

  q = p;  

  p = p->nxt;  

}  

Node *s=new Node;;  

s->k=key;  

s->r=rec;  

s->nxt= NULL;  

if (q == NULL){ s->nxt=lst; lst = s; }  

               else q->nxt = s;  

search= s;  

return search;  

Ro`yhatli  tuzilmaning  afzalligi  shundan  iboratki,  ro`yhatga  elementni Qo`shish yoki 

o`chirish  tez  amalga  oshadi,  bunda  qo`shish  yoki  o`chirish  element  soniga    bog`liq  

bo`lmaydi,    massivda    esa    elementni    qo`shish    yoki    o`chirish    o`rta  hisobda    barcha  

elementlarning    yarmini    siljitishni    talab    qiladi.    Ro`yhatda  qidiruvning  samaradorligi 

taxminan massivniki bilan bir xil bo`ladi. 



Teng bo`lish orqali qidiruv (ikkilik qidiruv) algoritmi 

Faraz qilaylik,  o`sish tartibida tartiblangan sonlar massivi berilgan bo`lsin. Ushbu usulning 

asosiy g`oyasi shundan iboratki, tasodifiy qandaydir AM element olinadi va u X qidiruv 

argumenti bilan taqqoslanadi. Agar AM=X bo`lsa, u holda qidiruv yakunlanadi; agar AM 



qidiruvdan    chiqarib    yuboriladi.    Xuddi  shuningdek,    agar    AM    >X    bo`lsa,    u    holda  

indekslari  M  dan  katta  bo`lgan  barcha elementlar kelgusi qidiruvdan chiqarib yuboriladi. 

M  ixtiyoriy  tanlanganda  ham  taklif  qilinayotgan  algoritm  korrekt  ishlaydi. Shu  sababali  

M  ni  shunday  tanlash  lozimki,  tadqiq  qilinayotgan  algoritm samaraliroq  natija  bersin,  

ya`ni    uni    shunday    tanlaylikki,    iloji    boricha    kelgusi  jarayonlarda    ishtirok    etuvchi  

elementlar  soni  kam  bo`lsin.  Agar  biz  o‟rtacha elementni, ya`ni massiv o`rtasini tanlasak 

yechim  mukammal  bo`ladi.  Misol  uchun  butun  sonlardan  iborat,  o`sish  bo‟yicha 

tartiblangan massivdan ikkilik qidiruv usuli yordamida key kalitga mos elementni izlash 

dasturini ko`rib chiqamiz.   

   

Dastur kodi  

#include  

using namespace std;  

int main(){  

    int n;cout<<"n=";cin>>n;  

    int k[n];  


    for(int i=0;i>k[i];  

    int key, search;  

    cout<<"qidirilayotgan elementni kiriting=";cin>>key;  

int low = 0;  

int hi = n-1; int j=0;  

while (low <= hi){  

    int mid = (low + hi) / 2;j++;  

    if (key == k[mid]){  

        search = mid;  

        cout<<"qidirilayotgan  element  "<

"<

        system("pause");  

        exit(0);  

    }  

    if (key < k[mid])   

             hi = mid - 1;  

      else low = mid + 1;  

    }  

    search=-1;  

    cout<

topilmadi\n";  

system("pause");  

}       

Dastur natijasi  

n=5; 







Qidirilayotgan son: 2; 

 

 

Xulosa. 

Ma`lumotlarni  kompyuterda  qayta  ishlashda  elementning  informatsion maydoni  va  

uning    mashina    xotirasida    joylashishini    bilish    zarur  hisoblanadi.  Shu    maqsadda 

ma`lumotlarni  saralash  amalga  oshiriladi. Hamda 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. Budan tashqari ma`lmotlarni o`zgartirish, ularni 

o`cherish kabi amallarning barchasi   ma`lumotlar ustidan qayta ishlash amallari hisoblanar 

ekan. 


Foydalanilgan adabiyotlar ro`yxati: 

1. 

“MA`LUMOTLAR TUZILMASI VA ALGORITMLAR” fanidan laboratoriya ishlarini 

bajarish  bo`yicha USLUBIY KO`RSATMA 

 

Akbaraliyev  B.B. va Yusupova Z.Dj.   

2. Darslar davomida foydalanilgan adabiyotlar. 

3. 


www.ziyonet.uz

 

4. 



www.cplusplus.com

 

 



 

 

Download 0.74 Mb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling