Muhammad al-Xorazmiy nomidagi Toshkent Axborot
Download 0.74 Mb. Pdf ko'rish
|
MTA
- Bu sahifa navigatsiya:
- Ma`lumotlar tuzilmasi va algoritmlash fanidan Mustaqil ish №1 Mavzu: Eng oddiy qatorlarni qayta ishlash algoritmlari
- Tekshirdi:Ganixodjayeva Dilfuza
- Determinantlik sifati
- To`g`ridan-to`g`ri qo`shish usuli bilan saralash algoritmi
- To`g`ridan-to`g`ri almashtirish usuli
- Ketma-ket qidiruv algoritm
- Teng bo`lish orqali qidiruv (ikkilik qidiruv) algoritmi
- Foydalanilgan adabiyotlar ro`yxati: 1.
Muhammad al-Xorazmiy nomidagi Toshkent Axborot
Mustaqil ish №1
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
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;
Algoritmni EHM(Elektron Hisoblash Mashinalari) yoki inson tomonidan bajarilishi mumkinligi shubxasiz bo’lgan ayrim-ayrim sodda bosqichlarga bo’lish mumkinligi.
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.
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
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
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).
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 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.
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).
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.
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:
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.
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 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.
for(int i=0;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; 7
6 8 2 Qidirilayotgan son: 2;
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
2. Darslar davomida foydalanilgan adabiyotlar. 3.
www.ziyonet.uz
4. www.cplusplus.com
Download 0.74 Mb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling