logo
  1. Bosh sahifa
  2. Referatlar
  3. Umumiy
  4. ALGORITM VA MA’LUMOTLAR STRUKTURASI

ALGORITM VA MA’LUMOTLAR STRUKTURASI

Yuklangan vaqt:

08.08.2023

Ko'chirishlar soni:

0

Hajmi:

425.681640625 KB
Ko'chirib olish
ALGORITM VA MA’LUMOTLAR STRUKTURASI fanidan yozgan Tekshirdi:_____________________________ MUSTAQIL ISHI 1-mustaqil ish Mavzu: Ma’lumotlar tuzilmasi,tuzilmalar ustida bajariladigan amallar. Dasturlash texnologiyalari. Reja: 1.Ma’lumotlar tuzilmasi 2. Ma’lumotlar tuzilmalari ustida quyidagi amallarni bajarish mumkin: Ma’lumotlar tuzilmasi bu xotirada tashkil etiladigan elementlar yig’indisi bo’lib, ular ustida dastur yordamida amallar bajariladi. Ma’lumotlar tuzilmasi – bu bironta toifaga tegishli bo’lgan va o’zaro ma’lum munosabatga ega bo’lgan elementlar to’plamiga aytiladi. Ma’lumot – bironta qiymat yoki qiymatlar to’plami hisoblanadi.Misol uchun bu bironta eksperiment natijalari, yoki talabalarning imtixon ballari bo’lishi mumkin. Ma’lumotlar tuzilmasi elementi – bu qiymatlar to’plamining bir bo’lagi hisoblanadi. Tuzilma elementi – qiymatlar jamlanmasi bo’lib, misol uchun talabalarning ismi, sharifi, yoshi har bir fandan olgan bahosi va x.k. larni keltirish mumkin. Elementlar 2 taga bo’linishi mumkin:  Element sifatida ma’lumotlar guruhi olib qaraladi. Bunda e;lementlar yana qism bo’lak;arga bo’linishi mumkin. Masalan, ota-onalar maydoni talabalarning ota va onalari xaqida ma’lumot saqlaydigan alohida maydonlardan tashkil topadi.  Elementar, ya’ni bo’linmas, bunda element qism bo’laklarga ajratilmaydi. Ob’ekt – bu xususiyatlar va attributlariga ega bo’lgan va bu xususiyatlarga qiymat qabul qilishi mumkin bo’lgan tuzilma hisoblanadi. Masalan, talaba bu ob’ekt deb qaralishi mumkin tuzilma. Maydon – bu ob’ektlarning attributlari yoki xususiyatlarini ifodalovchi tushuncha bo’lib, sonli yoki son bo’lmagan qiymatlarni o’zlashtirishi mumkin. Yozuv – bu bironta ob’ektga tegishli turli toifadagi maydonlar to’plamidir. Fayl - bu bir-biriga bog’liq bo’lgan yozuvlar to’plamidir. Masalan, barcha talabalar xaqidagi yozuvlarni o’z ichiga olishi mumkin, Kalit – bu yozuvdagi maydon bo’lib, aynan shu yozuvni boshqa yozuvlardan ajratib turishga xizmat qiladi , uning qiymati boshqa yozuvlarda takrorlanmas hisoblanadi. Ba’zida bittadan ko’p maydonlar qiymatlari elementlararo betakror bo’lishi mumkin va bunga karrali kalit deyiladi. Ko’pincha asosiy kalit hisoblanadigan bitta maydon ma’lumoti ishlatiladi va u boshlang’ich kalit deyiladi, qolganlari esa alternativ kalit deyiladi. Ba’zida esa yozuvlaning yagona qiymatlatli kalit maydonni yo’qligi sababli kalit sifatida bir nechta maydonlar olinadi va ularga tarkibli kalit deyiladi. Eng yomon holatda, ba’zan shunaqa bo’lishi mumkinki, bironta maydon kalit bo’la olmasa, xar bit elementga qo’shimcha, qiymati yagona bo’lgan kalit maydon kiritiladi. Ma’lumotlar tuzilmasi Ma’lumotlar turli yo’lar asosida tashkil etilishi mumkin, mantiqiy yoki matematik modelni tashkil etilishi ma’lumotlar tuzilmasi deyiladi. Konkret bir ma’lumotlar tuzilmasini tanlash quyidagilarga bog’liq:  Real voqe’likda elementlararo munosabatni yaqqol ifodalay olishi kerak;  U shunday soda tuzilishi kerakki, zarur bo’lganda ustida samarali amal bajarish mumkin bo’lsin. Ma’lumotlar tuzilmasini o’rganish quyidagilardan iborat:  Tuzilmani mantiqiy ifodalash;  Tuzilmani fiizik amalga oshirish ;  Tuzilmani sifatiy taxlili, ya’ni elementlarni saqlash uchun qancha xotira xajmi sarflanishini aniqlash (xotira sarfi) va qayta ishlashga ketadigan vaqtni (vaqt sarfi) xisoblash nazarda tutiladi. Ma’lumotlar tuzilmalari ustida quyidagi amallarni bajarish mumkin: 1. Ko’rikdan o’tkazish (traversing) - tuzilma elementlariga 1 martadan murojaat qilish amali. 2. Kiritish – tuzilmaga yangi element kiritish amali. 3. O’chirish – tuzlmadan bironta elementni o’chirish amali. Bunda element shunday o’chirilishi kerakki, qolgan elementlar stabil holatda bo’lishi kerak, ya’ni ayrim tuzilmalarda nosozlik sezilishi kerak emas. 4. Qidirish – tuzilmadan bironta elementni joylashgan o’rnini aniqlash amali. 5. Saralash – elementlarni ma’lum bir tartibda joylashtirish amali. 6. Birlashtirish (merging) – ikkita tuzilmani birlashtirish amali. Ma’lumotlar tuzilmasi (MT) – informatsion ob’ektning umumiy xossasi bo‘lib, mazkur xossa bilan biror bir dastur o‘zaro aloqador bo‘ladi. Ushbu umumiy xossa quyidagilar orqali tavsiflanadi: 1) mazkur tuzilmaning mumkin (qabul qilishi mumkin) bo‘lgan qiymatlari to‘plami; 2) mumkin bo‘lgan amallar (operatsiyalar) majmuasi; 3) tashkil etilganlik tasnifi. 2-mustaqil ish Mavzu: Algoritmlarni murakkablik darajalasining tahlili, murak-kablik darajasini baholash usullari. Reja: 1 Algoritmning asosiy xossalari 2 Algoritmlarning murakkabligi . 3 Murakkablikni baholash 4 Algoritmlar murakkabligining o sish tartibiʻ 1-ta’rif. Algoritm - bu ma’lum bir tilda berilgan, mumkin bo lgan dastlabki ʻ ma’lumotlar sinfi uchun masalani hal qilish uchun mumkin bo lgan elementar amallarning ʻ cheklangan ketma-ketligi. Algoritmning asosiy xossalari haqida quyidagilarni ta’kidlash mumkin: 1-xossa . Diskretlilik, ya’ni algoritmni chekli sondagi oddiy ko rsatmalar ketma- ʻ ketligi shaklida ifodalash mumkin. 2-xossa. Tushunarlilik, ya’ni ijrochiga tavsiya etilayotgan ko rsatmalar uning uchun ʻ tushunarli bo lishi shart, aks holda ijrochi oddiy amalni ham bajara olmay qolishi mumkin. ʻ Har bir ijrochining bajara olishi mumkin bo lgan ko rsatmalar tizimi mavjud. ʻ ʻ 3-xossa. Aniqlik, ya’ni ijrochiga berilayotgan ko rsatmalar aniq mazmunda bo lishi ʻ ʻ lozim hamda faqat algoritmda ko rsatilgan tartibda bajarilishi shart. ʻ 4-xossa . Ommaviylik, ya’ni har bir algoritm mazmuniga ko ra bir turdagi ʻ masalalarning barchasi uchun yaroqli bo lishi lozim ʻ . Masalan, ikki oddiy kasr umumiy maxrajini topish algoritmi har qanday kasrlar umumiy maxrajini topish uchun ishlatiladi. 5-xossa. Natijaviylik, ya’ni har bir algoritm chekli sondagi qadamlardan so ng ʻ albatta natija berishi lozim . Bu xossalar mohiyatini o rganish va konkret algoritmlar uchun qarab chiqish ʻ talabalarning xossalar mazmunini bilib olishlariga yordam beradi. Algoritmlar berilishi va ifodalanishiga qarab: chiziqli, tarmoqlanuvchi va takrorlanuvchi turlarga bo linadi. ʻ Algoritmlarning murakkabligi . Hisoblash muammolari cheklangan xotira resurslaridan foydalangan holda oqilona vaqt ichida yechilishi kerak. Bu algoritmning vaqt va fazoviy murakkabligi tushunchasiga olib keladi. Qoida tariqasida, algoritm turli vaqtlarni bajarishi mumkin bo lgan turli xil amallarni o z ichiga oladi. Algoritmlarni baholash uchun ʻ ʻ ko pgina mezonlar mavjud. Odatda kirituvchi berilganlarni ko payishida masalani yechish ʻ ʻ uchun kerak bo ladigan vaqt va xotira hajmlarini o sish tartibini aniqlash muammosi ʻ ʻ qo yiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini aniqlovchi ʻ qandaydir sonni bog lash zarur. Bunday son masalaning kattaligi deb qabul qilinadi. ʻ Masalan, ikkita matritsani ko paytirish masalasining o lchami bo lib, matritsalar kattaligig ʻ ʻ ʻ xizmat qilishi mumkin. Graflar haqidagi masalada o lcham sifatida graf ʻ uchlarining soni bo lishi mumkin. ʻ Algoritm sarflanayotgan vaqt masalaning o lchami funksiyasi sifatida ʻ algoritmni vaqt bo yicha qiyinligi deb nomlanadi. Bunday funksiyaga masalaning kattaligi ʻ oshganda limit ostidagi o zgarish asimptotik qiyinlik deb aytiladi. ʻ Murakkablikni baholash . Algoritmlarning murakkabligi odatda bajarilish vaqti yoki ishlatilgan xotira bo yicha baholanadi. Ikkala holatda ham, murakkablik kiritilgan ʻ ma’lumotlarning hajmiga bog liq: 100 ta elementdan iborat massivi xuddi shunga ʻ o xshash 1000 ta elementdan iborat massivga qaraganda tezroq qayta ishlanadi. Shu bilan ʻ birga, aniq vaqt bilan bir necha kishi qiziqadi: bu protsessorgabog liq, ma’lumotlar turi, ʻ dasturlash tili va boshqa ko plab parametrlarga ham bog liq. Faqatgina ʻ ʻ asimptotik murakkablik muhim, ya’ni kirish ma’lumotlarining kattaligi cheksizlikka intilayotgandagi murakkablik. Masalan, ba’zi bir algoritmga kirish ma’lumotlarining n ta elementlarini qayta ishlash uchun 4n 3 + 7n ta shartli amallarni bajarish kerak. n ning ortishi bilan ishning umumiy davomiyligi n ning kubi uni 4 ga ko paytirgandan yoki 7n ni qo shgandan ko ra ʻ ʻ ʻ ko proq ta’sir qiladi. Ushbu algoritmning vaqt murakkabligi O(n ʻ 3 ), ya’ni u kubik bilan kiritilgan ma’lumotlarning hajmiga bog liq bo ladi. Bosh harf ʻ ʻ O dan foydalanish matematikadan kelib chiqadi, bu yerda ushbu belgi funksiyalarning asimptotik harakatlarini taqqoslash uchun ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki egallagan xotira miqdori), kiritilgan ma’lumotlarning hajmiga qarab, f(n) ga ko paytiriladigan ba’zi konstantalardan tezroq emasligini anglatadi. ʻ O (n) - chiziqli murakkablik. Bunday murakkablik, masalan, saralanmagan massivdagi eng katta elementni topish algoritmiga ega. Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n elementlaridan o tishimiz kerak bo ladi. ʻ ʻ O (log n) - logaritmik murakkablik . Eng oddiy misol - ikkilik qidirish. Agar massiv saralangan bo lsa, uni ʻ yarmiga bo lish orqali ma’lum bir qiymatga ega ekanligini tekshirishimiz mumkin. O rta ʻ ʻ elementni tekshirib ko ramiz, agar u kattaroq bo lsa, unda massivning ikkinchi yarmini ʻ ʻ tashlab yuboramiz. Agar kichikroq bo lsa, unda aksincha - biz dastlabki yarmini ʻ tashlaymiz va shu tarzda ikkiga bo linishni davom ettiramiz, natijada (logn) elementlarini ʻ tekshiramiz. O (n 2 ) - kvadratik murakkablik. Bunday murakkablik, masalan, element qo shilishi natijasida yangi saralash algoritmiga ega. Kanonik dasturda ʻ bu ikkita ichki sikldan iborat: biri butun massivni bosib o tish, ikkinchisi esa allaqachon ʻ ajratilgan qismdan keyingi element uchun joy topish. Shunday qilib, amallar soni n*n, ya’ni n 2 kabi massiv o lchamiga bog liq bo ladi. ʻ ʻ ʻ Murakkablikning boshqa ko rinishlari ʻ ham mavjud, ammo ularning barchasi bir xil prinsipga asoslanadi. Algoritmning ishlash vaqti umuman kiritilgan ma’lumotlarning hajmiga bog liq emasligi ham sodir bo ladi. Bu ʻ ʻ holda murakkablik O(1) bilan belgilanadi. Masalan, massivning uchinchi elementi qiymatini aniqlash uchun elementlarni eslab qolishingiz yoki ular orqali bir necha bor o tishingiz shart emas. Siz har doimma’lumotlarni kiritish oqimidagi uchinchi elementni ʻ kutishingiz kerak va bu esa siz uchun natija bo ladi, bu har qanday ma’lumot uchun ʻ hisoblash uchun bir xil vaqtni oladi. Baholash muhim bo lgan taqdirda xotiradan xuddi ʻ shu tarzda amalga oshiriladi. Biroq, algoritmlar kirish ma’lumotlarining hajmi boshqalarga nisbatan kattalashganda sezilarli darajada ko proq xotiradan foydalanishi mumkin, ammo ʻ ular tezroq ishlaydi va aksincha. Bu hozirgi sharoit va talablar asosida muammolarni hal qilishning eng yaxshi usullarini tanlashga yordam beradi. Algoritmlar murakkabligining o sish tartibi ʻ Murakkablikning o sish tartibi ʻ (yoki aksiomatik murakkablik) katta kirish hajmi uchun algoritmning murakkablik funksiyasining taxminiy xatti-harakatini tavsiflaydi. Bundan kelib chiqadiki, vaqt murakkabligini baholashda elementar amallarni ko rib chiqishning ʻ hojati yo q, algoritm qadamlarini ko rib chiqish kifoya. ʻ ʻ Algoritm qadami – bu ketma-ket joylashtirilgan elementar amallar to plami, uning ʻ bajarilish vaqti kirish qadamiga bog liq emas, ya’ni yuqoridan qandaydir doimiy bilan ʻ chegaralangan. Asimptotik baholashning ko rinishlari. ʻ F(n)>0 murakkabligini, bir xil tartibdagi g(n)>0 funksiyasini, kirish n>0 o lchamini ko rib chiqaylik. Agar f(n) = O (g(n)) va n> n ʻ ʻ 0 uchun c>0, n 0 > 0 konstantalar mavjud bo lsa, u holda 0 <f(n)<c*g(n). ʻ Bu holda g(n) funksiyasi f(n) uchun asimptotik-aniq baho hisoblanadi. Agar f(n) algoritmning murakkablik funksiyasi bo lsa, unda murakkablik tartibi f(n) uchun - O(g(n)) ʻ deb belgilanadi. Ushbu ibora doimiy koeffitsiyentgacha g(n) dan tez o smaydigan ʻ funksiyalar sinfini belgilaydi. Misollardan namunalar: 1-Misol. Kiritilgan 2 ta qiymat (k,l; k<l) oralig’idagi sonlar kvadratlari yig’indisi o’rtachasini hisoblash dasturini tuzing #include <iostream> using namespace std; int main() { int k,l; cout<<”boshlang’ich qiymatni kiriting=”; cin>>k; cout<<”oxirgi qiymatni kiriting=”; cin>>l; int p=0; for(int i=k;i<=l;i++) p+=i*i; p/=k-l+1; c out<<”k va l qiymatlar oralig’idagi sonlar kvadratlari yig’indisi o’rtachasi=”<<p; system(“pause”);} 2-Misol. M natural soni mukammal deyiladi, agar uning bo’luvchilari yig’indisi (1 ham kiradi va M ning o’zidan tashqari) M ga teng bo’lsa. Kiritilgan sonning mukammalligini aniqlang. #include <iostream> #include <cmath> using namespace std; int main() { int x, sum=0; cout<<"son kiriting: "; cin>>x; for(int i=1; i<x;i++) { if(x%i==0) sum+=i; } if(x==sum) {cout<<"bu mukammal son"<<endl;} else {cout<<" bu mukammal y son emas"<<endl;} } 3-Misol. Alifbo xarflarini chiqaring va kiritilgan so’zning xarflarini o’sish tartibida saralang. #include <stdio.h> #include <iostream> using namespace std; int main(void) { for(char c='a';c<='z';c++) cout<<c<<(char)(c-32)<<" "; char s[34]; cout<<endl<<"so'z kiriting "; cin>>s; for(int i=0;i<strlen(s)-1;i++) for(int j=i+1;j<strlen(s);j++) if(s[i]>s[j]) swap(s[i],s[j]); cout<<s; return 0; } 4-misol. Ikki son berilgan. Ularning musbat ekanligini tekshiring. #include <iostream> #include <cmath> using namespace std; int main() { bool x; int a,b; cin>>a>>b; x=a>0&&b>0; cout<<x; return 0; } 5-misol. Kiritilgan belgining nimaligini aniqlovchi programma tuzilsin. Agar belgi raqam bo’lsa –“digit”, lotincha harf bo’lsa-“lotin” yozuvi chiqarilsin. Boshqa holatlarda nol chiqarilsin. #include <iostream> #include <ctype.h> using namespase std; int main() {char a; bool x,y; cin>>a; x=isdigit(a); y=isalpha(a); if (x==true) cout<<”digit”; if (y==true) cout<<”lotin”; else cout<<0; return 0;} 3-mustaqil ish Mavzu: Ma’lumotlar tuzilmasida satrli va belgili turlarni dasturlashtirish Reja: 1 Satrlarni e’lon qilish 2 Satr uzunligini aniqlash 3 Satrlarni nusxalash C++ dasturlash tilida bir nechta turlardan foydalanish va ular ustida amallar bajarish mimkin, dasturlash muhitida boshqa turlar kabi belgili turlar ham mavjud. C++ dasturlash tilida belgili turlar char turiga mansub bo‘lgan yagona elementli tur hisoblanadi. C++ dasturlash tilida satrlar uchun alohida maxsus turlar ham mavjud, lekin satrlarni belgilar massivi sifatida ishlatish ham mumkin. Ta’rif: Alohida nom bilan saqlanuvchi bir nechta belgilardan tashkil topgan belgilar majmuasi satr deyiladi. Satrlarni belgilar massivi sifatida qarab ular ustida amallar bajarish mumkin. C++ dasturlash tilida satrlar nol(‘\0’) terminatori bilan tugaydi. Nol terminatori bilan tugaydigan satrlar ASCIIZ –satrlari deyiladi. Satrlardan foydalanish va ular ustida amallar bajarish uchun albatta oldin ularni e’lon qilish kerak. Satr turiga mansub bo‘lgan o‘zgaruvchilarni char xizmatchi so‘zi orqali e’lon qilinadi. Satrlarni e’lon qilish uchun quyidagi dasturlarga etibor bering. #include <iostream.h> #include <string.h> using namespace std; int main() { char s[10]; // s satrli o‘zgaruvchini e’lon qilish return 0; } Yuqoridagi dastur tarkibida s[10] satr o‘zgaruvchisi 9 ta elementga va bitta nol terminatoriga mo‘ljallangan. Satrlarni boshlang’ich qiymatlarini berish jarayonida uning elementlar sonini berish shart emas. Agar satrlarni elementlar soni berilmasa dastur avtomatik ravishda uning elementlar soniga boshlang’ich qiymatdagi elementlar sonidan bitta ortiq qilib ta’minlaydi, chunki oxiriga bitta nol terminatorini hisobga oladi. Doim satrlarni kiritishda uning elementlar soni e’lon qilinganidan oshib ketmasligi kerak aks holda faqat e’lon qilingan elementlar soniga teng elementlarni saqlab qolinib qolganlari olinmaydi. Satrlarni kiritish jarayonida >> oqim bo‘yicha kiritishdan foydalanmasdan getline() funksiyasidan foydalanish maqsadga muvofiq bo‘ladi. Agar oqim bo‘yicha kiritishdan foydalanilsa unda probellar inkor qilinib satrni ikkinchi qismlari qabul qilinmaydi. getline(s,n) funksiyasi ikkita parametrni o‘z ichiga oladi, birinchisi s satr o‘zgaruvchisi ikkinchisi n satr elementlar soni. Getline funksiyasi satr elementlaridan ortiq qiymatlarni ham kiritish imkoniyatini yaratadi, natijada satr elementlari ortadi. Yuqoridagi dastur tarkibidagi s satrli o‘zgaruvchi faqat 9 ta elementni qbul qiladi, agar 9 tadan ortiq bo‘lsa natija qaytarmaydi. Satr uzunligini aniqlash Satrlar ustida amallar bajarish vaqtida albatta satrlarning uzunligi kerak bo‘ladi. Satr uzunligini aniqlash uchun string.h kutubhonasiga murojat qilish kerak aksariyat satr uchun ishlatiladigan funksiyalarni string.h kutubhonasiga murojat qilib ishlatishimiz mumkin. Satr uzunligini aniqlashni ikki hil usuli mavjud. -satr tarkibidagi mavjud elementlar sonini nol terminatorisiz aniqlash; -satr tarkibidagi elementlarga ajratilgan sonini nol terminatori bilan aniqlash; Satr tarkibidagi mavjud elementlar sonini nol terminatorisiz aniqlash funksiyasining umumiy ko‘rinishi quyidagicha bo‘ladi. strlen(<satrli o‘zgaruvchi>); Strlen funksiyasi o‘z tarkibiga satrli o‘zgaruvchi yoki satr uzini qabul qilishi mumkin. Masalan strlen (“absd”) bo‘lsa uning natijasi 4 ga teng bo‘ladi. Satr tarkibidagi elementlarga ajratilgan sonini nol terminatori bilan aniqlash uchun sizeof(s) funksiyasidan foydaliniladi. Sizeof(s) funksiyasi s satr uchun ajratilgan elementlar sonini aniqlaydi, s satrni 10 ta elementga moslab e’lon qilib lekin 5 ta element kiritilsa ham sizeof funksiyasi 10 qiymatni qaytaradi. Satr tarkibidagi elementlarga ajratilgan sonini nol terminatori bilan aniqlash funksiyasining umumiy ko‘rinishi quyidagicha bo‘ladi. sizeof(<satrli o‘zgaruvchi>); Sizeof funksiyasi o‘z tarkibiga satrli o‘zgaruvchi yoki satr uzini qabul qilishi mumkin. Masalan strlen (“absd”) bo‘lsa uning natijasi 5 ga teng bo‘ladi. Satrlarni ixtiyoriy elementiga murojat qilish uchun doimo bitta kam qilib buyruq berish kerak chunki satrlar belgili massiv bo‘lganligi uchun boshlang’ich element nolinchi o‘rindan boshlanadi. Satrlarni nusxalash C++ dasturlash tilida satrlarni bir biriga nusxalashni bir qancha usullari mavjud. Satrlarni nusxalash uchun strcpy() funksiyasidan foydalanish mumkin, strcpy() funksiyasining umumiy ko‘rinishi quyidagicha bo‘ladi. strcpy(satr1, satr2); strcpy(satr1, satr2) funksiyasi satr2 dagi elementlarni to‘laligicha satr1 ga nusxalaydi. Satr1 ni elementlar soni doimo satr2 elementlar sonidan katta bo‘lishi kerak. Satrlarni nusxalash uchun strncpy() funksiyasidan foydalanish mumkin, strncpy() funksiyasining umumiy ko‘rinishi quyidagicha bo‘ladi. strncpy(satr1, satr2,n); strncpy(satr1, satr2,n) funksiyasi satr2 dagi elementlarni n tasini satr1 ni boshiga nusxalaydi. Strncpy() funksiyasini strcpy() funksiyasidan farqi satr2 ni nta elementini satr1 ni boshiga nusxalaydi. Satrlarni ulash Bir nechta satrlarni ulash natijasida yangi satrlarni hosil qilish mumkin. C++ dasturlash tili tarkibida satrlarni bir biriga ulashni bir nechta usullari mavjud, satrlarni bir biriga ulab yangi satrlar hosil qilinadi. C++ dasturlash tilida strcat() funksiyasi yordamida satrlarni bir biriga ulash imkoniyati mavjud, strcat() funksiyasining umumiy ko‘rinishi quyidagicha ko‘rinishda bo‘ladi. strcat(satr1, satr2); C++ dasturlash tilida strcat(satr1, satr2) funksiyasi satr2 ni satr1ni oxiriga ulaydi. C++ dasturlash tilida strncat() funksiyasi yordamida satrlarni bir biriga faqat n ta elementini ulash imkoniyati mavjud, strncat() funksiyasining umumiy ko‘rinishi quyidagicha ko‘rinishda bo‘ladi. strncat(satr1, satr2,n); C++ dasturlash tilida strncat(satr1, satr2, n) funksiyasi satr2 ni n ta boshlang’ich elementlarini satr1ni oxiriga ulaydi. Misollardan namunalar: 1-Misol: Berilgan satrni ekranga chiqaring #include <iostream.h> #include <string.h> using namespace std; int main() { char s[10]; cin.getline(s,10); cout<<s; return 0; } 2- Misol: Berilgan satr tarkibidagi elementlar sonini aniqlang. #include <iostream.h> #include <string.h> using namespace std; int main() { char s[10]; cin.getline(s,10); x=sizeof(s); cout<<x; return 0; } 3- Misol: Berilgan s satr elementlarini p satrga nusxalang. #include <iostream.h> #include <string.h> using namespace std; int main() { char s[100]; cin.getline(s,10); char p[10]; strcpy(p,s); cout<<p; return 0; } 4-Misol: Berilgan s satrni teskari tartiblang. #include <iostream.h> #include <string.h> using namespace std; int main() { char s[100]; cin.getline(s,10); cout<<strrev(s); return 0; } 5-Misol: Berilgan s satrdan p belgini qidiring. #include <iostream.h> #include <string.h> using namespace std; int main() { char s[100]; cin.getline(s,10); char p; cin>>p; cout<<strchr(s,p); return 0; } 4-mustaqil ish Mavzu: Dinamik xotiradan foydalanish, dinamik xotirani ishlatishda ko’rsatkich turlari Reja: 1 Ko‘rsatkich o‘zgaruvchilar 2. Funksiyaga ko‘rsatkich 3 void ko‘rsatkichlar 4 Ko‘rsatkichlar ustida bajariladigan amallar C++ dasturlash tilida tuzilgan dastur tarkibidagi o‘zgaruvchilar dastur komplyatsiya qilingandan keyin kompyuter xotirasiga borib joylashadi. Komplyator dastur matnini kompyuter xotirasiga joylashtirgandan so‘ng uning tarkibidagi o‘zgaruvchilar adresini obeykt kod sifatida qabul qilib oladi. C++ dasturlash tilida tuzilgan dastur tarkibidagi o‘zgaruvchilar, o‘zgarmaslar va funksiyalar adreslarini kompyuter xotirasiga alohida saqlash va ular ustida amallar bajarish mumkin. Ta’rif: Qiymatlari adres bo‘lgan o‘zgaruvchilar ko‘rsatkich o‘zgaruvchilar deb ataladi. Ko‘rsatkichlar uch xil turda bo‘ladi: -Funksiyaga ko‘rsatkich; -Obyektga o‘zgaruvchiga ko‘rsatkich; -Void ko‘rsatkich. Ko‘rsatkichlar, albatta, birorta turga bog’langan bo‘ladi, ya’ni u ko‘rsatgan adresda ma’lum bir qiymat joylashishi mumkin va bu qiymat kompyuter xotirasidan qancha joy egallashi oldindan ma’lum bo‘lishi kerak. Funksiyaga ko‘rsatkich Funksiyaga ko‘rsatkich programma joylashgan xotiradagi funksiya kodini boshlang’ich adresini ko‘rsatadi, ya’ni funksiya chaqirilganda boshqaruv ayni shu adresga uzatiladi. Bunda funksiya nomi bo‘yicha emas, balki funksiyaga ko‘rsatuvchi o‘zgaruvchi orqali chaqiriladi. Funksiyani boshqa funksiyaga argument sifatida uzatish ham funksiya ko‘rsatkichi orqali bajariladi. C++ dasturlash tilida funksiya ko‘rsatkichining yozilishi quyidagicha. <tur> (*<nom>)(<parametrlar ro‘yxati>); Bu yerda *<nom> funksiya ko‘rsatkich o‘zgaruvchisi nomi. Obyektga o‘zgaruvchiga ko‘rsatkich C++ dasturlash tilida o‘zgaruvchiga ko‘rsatkich e’lon qilish, bunda kompyuter xotirasiga o‘zgaruvchining adresi yoziladi. C++ tilida o‘zgaruvchi va o‘zgarmas qiymatlarga ko‘rsatkich e’lon qilish bir xil bo‘ladi. C++ dasturlash tilida o‘zgaruvchi ko‘rsatkichining yozilishi quyidagicha: <tur> *<nom>; C++ dasturlash tilida o‘zgaruvchiga ko‘rsatkich e’lon qilishni quyidagi dastur orqali aniqlaymiz: #include <iostream.h> using namespace std; int main() { int *a, *b; float *i, *y; return 0; } Yuqoridagi dasturda a va b butun ko ‘ rsatkichlar , i va y haqiqiy ko ‘ rsatkichlar keltirilgan . void ko‘rsatkichlar void ko‘rsatkichlar obyekt turi oldindan aniq bo‘lmagan holatlarda ishlatiladi. Void ko‘rsatkichini afzalliklari unga har qanday turdagi ko‘rsatkich qiymatini yuklash mumkin. C++ dasturlash tilida void ko‘rsatkichining yozilishi quyidagicha: void *<nom>; void ko‘rsatkichi sifatida e’lon qilingan ko‘rsatkichga boshqa turdagi o‘zgaruvchilarni taminlash imkoniyati mavjud bo‘ladi. Ko‘rsatkichlarga boshlang’ich qiymat berish C++ dasturlash tili tarkibidagi ko‘rsatkichlarga boshlang’ich qiymatlarni berish uchun, albatta, biror o‘zgaruvchi orqali qabul qilish maqsadga muvofiq bo‘ladi. Ko‘rsatkichlarga boshlang’ich qiymatlarni = belgisi yoki qavs ichiga olib berilish mumkin. Ko‘rsatkichlarni boshlang’ich qiymatlarini berish uchun quyidagi dasturga e’tibor bering: #include <iostream.h> using namespace std; int main() { int x=10, k=9; int *y=&x; int *t(&k); return 0; } Yuqoridagi dasturga e ’ tibor qaratsak , x va k butun sonlar qiymatlari bilan aniqlangan . * y va * t ko ‘ rsatkichlarga boshlang ’ ich qiymat sifatida x va k ni qiymatlari berilgan . Ko ‘ rsatkichlar ustida bajariladigan amallar C ++ dasturlash tilida ko ‘ rsatkichlar ustida bajariladigan amallar quyidagilarni tashkil etadi : - obyektga vositali murojat qilish amali ; - qiymat berish amali ; -ko‘rsatgichga o‘zgarmas qiymatni qo‘shish amali; -ayirish amali; -inkrement va decrement amali; -solishtirish amali. C++ dasturlash tilida ko‘rsatkichlar ustida faqatgina yuqorida keltirilgan amallardan foydalanish maqsadga muvofiq bo‘ladi. Adres olish amali C++ dasturlash tilida biror bir o‘zgaruvchini uning sinonimi bilan almashtirib unga murojat qilish imkoniyati mavjud. Biror bir o‘zgaruvchining boshqa o‘zgaruvchiga adresini olish mumkin va unga murojat qilish uchun keyingi adres bo‘yicha murojat qilinadi. C++ dasturlash tilida adres olish amalining umumiy ko‘rinishi quyidagicha bo‘ladi: <tur> &<nom>; #include <iostream.h> using namespace std; int main() { int x=12; int &a=x; a=(a+2)/2; cout<<”a=”<<a; return 0; } Misollardan namunalar: 1-Misol: C++ dasturlash tilida ikki sonning yig’indisini hisoblash uchun fuksiya yarating va unga murojat qilishni tasvirlang #include <iostream.h> int yig(int a, int b); using namespace std; int main() { int x,y,z; cin>>x>>y; z=yig(x,y); cout<<z; return 0; } int yig(int a, int b) { int t; t=a+b; return t; } 2-Misol: n! faktorialni hisoblash jarayonini funksiya yordamida tasvirlash #include <iostream.h> using namespace std; int main() { int x; cin>>x; int fak(int n); cout<<fak(x); return 0; } int fak(int n) { int p=1; for(int i=1;i<=n;i++) p=p*i; return p; } 3- Misol: Sonning natural bo‘luvchilar sonini aniqlash uchun bo’luvchi(x) funksiyasini yarating. #include <iostream.h> using namespace std; int main() { int x; cin>>x; int buluvchi(int x); cout<<buluvchi(x); return 0; } int buluvchi(int n) { int p; for(int i=1;i<=n;i++) if(n%i==0) p++; return p; } 4-misol. x, y, x+y qiymatlar uchun eng katta umumiy bo luvchilari (EKUB) topilsin‟ . #include <iostream> using namespace std; int evklid(int m,int n) //ma lumotlar qiymatlar bo yicha uzatiladi ‟ ‟ { while (m!=n) if (m>n) m=m-n; else n=n-m; return (m); } int main () { int x,y,ekub; cin>>x>>y; ekub=evklid(evklid(x,y),x+y); cout<<“EKUB="<<ekub<<"\n";} 5-Misol . N ta butun sonni so raydigan va bu sonlar tarkibidagi barcha raqamlarini ʻ teskari tartibda, vergul bilan ajratilgan holda matnli faylga yozadigan dastur tuzilsin #include <iostream> #include <fstream> using namespace std; ofstream f; void kiritish(int n) //ma lumotlar ‟ qiymat bo yicha uzatiladi ‟ { int k; while (n!=0) { k=n%10; f<<k; n=n/10; if (n!=0) f<<","; } f<<endl; } int main () { int x,i,n; f.open("a.txt",ios::out); cin>>n; for (i=1;i<=n;i++) { cin>>x; kiritish(x); } f.close(); } 5-mustaqil ish Mavzu: Murakkab turlarni algoritmlashtirish va dasturlash. Vektorlar va massiv ma’lumotlarini algoritmlashtirish Reja: 1. Bir o‘lchovli massivlar 2. Rand funksiyasi 3. Ikki o‘lchovli massivlar Massivlar holatiga ko‘ra ikki turga bo‘linadi. - Bir o‘lchovli massivlar; - Ikki o‘lchovli massivlar; Bir o‘lchovli massivlar ma’lumotlarni bir satrli ko‘rinishda saqlansa, ikki o‘lchovli massivlar esa ma’lumotlarni satrlar satri ko‘rinishida saqlaydi. Bir o‘lchovli massivlar Odatda massivlar zarurat, katta hajmdagi tartiblangan, lekin chekli elementlarga oid masalalarni hal etishda yuzaga keladi. Dastur ishlatilishi davomida massivlar aniq nomga ega bo‘lishi va uning elementlari ma’lum bir turda bo‘lishi kerak. Bir o‘lchovli massivlar kompyuter xotirasiga quyidagi shaklda saqlanadi. o‘zgaruvchi qiymatlar Yuqoridagi holat bo‘yicha massivlar kompyuter xotirasiga saqlanadi, bunda massivning ixtiyoriy elementiga murojat qilish uchun uning indeks nomeri bo‘yicha murojat qilinadi. Bir o‘lchovli massivlarni C++ dasturlash tilida bir nechta usullarda e’lon qilish mumkin. Bir o‘lchovli massivlarni boshlang’ich qiymatlari berilmasdan C++ dasturlash tilida quyidagicha e’lon qilinadi. <tur> <massiv o‘zgaruvchisi>[<element soni>]; Massivni C++ dasturlash tilida e’lon qilish uchun, albatta, elementlar soni yoki massiv elementlarining boshlang’ich qiymatlari berilishi kerak. C++ dasturlash tilida bir o‘lchovli massivni e’lon qilish. #include <iostream.h> int main() { int a[10]; //butun turli 10ta elementli massiv double b[10]; //haqiqiy turli 10ta elementli massiv return 0; } Massivni umumiy ko‘rinishida birinchi o‘zgaruvchi turi, massiv o‘zgaruvchisi va massiv elementlari soni yoziladi. Massiv elementlari soni, albatta, butun sondan iborat bo‘lishi kerak, chunki elementlar soni, albatta, butun bo’lishi kerak. Massiv elementlari soni biror bir ifoda yoki yagona o‘zgaruvchi bo‘lishi mumkin, bitta o‘zgaruvchi orqali massivning umumiy indekslarini ifodalash mumkin. Massiv elementlarini tashkil qilish va massiv elementlari ustida amallar bajarishni quyidagi masala orqali qaraymiz. Massiv elementlarini tartib nomeri doimo 0 dan boshlanadi. C++ dasturlash tilida massiv elementlari boshlang’ich qiymatlari berilgan holatlarda e’lon qilish quyidagicha. <tur> <massiv o‘zgaruvchisi>[<element soni>]={boshlang’ich qiymatlar}; Bunda massiv elementlari oldindan berilgan holatlarda ishlatilishi mumkin. Rand funksiyasi a a[1] a[2] a[3] a[4] a[5] Massiv elementlarini ixtiyoriy tasodifiy sonlar bilan to‘ldirish uchun C++ dasturlash tilida imkoniyat yaratilgan. Agar massiv elementlarini tasodifiy sonlar bilan to‘ldirish kerak bo‘lsa, tasodifiy sonlar bilan ishlash funksiyasiga murojat qilish kerak. C++ dasturlash tilida tasodifiy sonlarni hosil qilish rand() funksiyasining umumiy ko‘rinishi quyidagicha bo‘ladi. Rand(); rand() funksiyasining vazifasi biror bir o‘zgaruvchiga yoki massiv elementlariga tasodifiy sonni o‘zlashtirish uchun xizmat qiladi. Rand() funksiyasi foydalanuvchi tomonidan dastur tarkibiga massiv elementlarini kiritishdan ozod qiladi. Ikki o‘lchovli massivlar C++ dasturlash tilida ba’zi hollarda bir nechta o‘lchamlari va turi bir xil bo‘lgan bir o‘lchovli massivlardan foydalanishga to‘g’ri keladi. Bir nechta bir o‘lchovli massivlarni birlashtirish natijasida ikki o‘lchovli massivlarni hosil qilish mumkin. Ikki o‘lchovli massivlarni tarkibida ma’lumotlar satrlarning satri ko‘rinishida tasvirlanadi. Ikki o‘lchovli massivlarning tarkibi ham bir o‘lchovli massivlar kabi tartiblangan bir turga mansub bo‘lishi kerak. Ikki o‘lchovli massivlarga matematikadagi matritsalar misol bo‘lishi mumkin. Ikki o‘lchovli massivlar tarkibidagi elementlar xuddi matritsani elementlari kabi tasvirlanadi. Ta’rif: Bir turga mansub bo‘lgan yagona nom bilan saqlangan matritsa ko‘rinishdagi tartiblangan ma’lumotlar majmuasi ikki o‘lchovli massivlar deyiladi. Ikki o‘lchovli massivning barcha elementlari aniq turga mansub bo‘ladi va uning elementlari bir nechta satrlar ko‘rinishda bo‘ladi. Ikki o‘lchovli massivlar quyidagi shaklda bo‘ladi.( a 11 a 12 … a 1 n a 21 a 22 … a 2 n . . . a n 1 a n 2 … a nn ) Yuqoridagi shakldan ko‘rinib turibdiki ikki o‘lchovli massiv bir o‘lchovli massivlarning bir nechtasi yoki matritsa ko‘rinishida tasvirlanar ekan. Ikki o‘lchovli massivlarning kompyuter xotirasiga har bir satr uchun alohida tartib nomer bilan saqlanadi. Ikki o‘lchovli massivlarning har bir elementiga o’zining indeksi bo‘yicha murojat qilinadi. Ikki o‘lchovli massivlarni C++ dasturlash tilida e’lon qilish va uning umumiy ko‘rinishi quyidagicha. <tur> <massivO‘zgaruvchisi>[<element1 soni>][<element2 soni>]; Quyidagi ikki o‘lchovli massiv berilgan bo‘lsin. a = ( 1 2 3 4 5 6 7 8 9 ) a(3,3) massivning elementlariga C++ dasturlash tilida murojat qilish quyidagicha ko‘rinishda bo‘ladi. a[1][1]=1, a[2][1]=2, a[3][1]=3, a[1][2]=4, a[2][2]=5, a[3] [2]=6, a[1][3]=7, a[2][3]=8, a[3][3]=9. C++ dasturlash tilida ikki o‘lchovli massivlarning elementlarini boshlang’ich qiymatlarini quyidagi tartibda berilishi mumkin. #include <iostream.h> int main() { int a[][]={{1,2,3}{4,5,6}{7,8,9}}; return 0; } Misollardan namunalar: 1-Misol: 10 ta elementdan tashkil topgan massiv elementlarini hosil qilib, elementlarini ikkiga ko‘paytirib ekranga chiqaring. #include <iostream.h> using namespace std; int main() { int a[10]; for(int i=0;i<=9;i++) cin>>a[i]; for(int i=0;i<=9;i++) cout<<a[i]*2<<” ”; return 0; } 2-Misol: Butun sonlardan iborat a[8] massiv berilgan uning juft elementlarini 2ga ko‘paytirib toq elementlarini 3 ga ko‘paytirib ekranga chiqaring. #include <iostream.h> using namespace std; int main() { int a[8]; for(int i=0;i<=7;i++) cin>>a[i]; for(int i=0;i<=7;i++) if(a[i]%2==0) {cout<<a[i]*2<<” ”;} else cout<<a[i]*3<<” ”; return 0; } 3-Misol: n natural son va n ta elementdan tashkil topgan massiv berilgan uning eng katta elementini aniqlang. #include <iostream.h> using namespace std; int main() { int a[10]; for(int i=0;i<=9;i++) cin>>a[i]; int max=a[0]; for(int i=0;i<=9;i++) if(a[i]>max) max=a[i]; cout<<max; return 0; } 4-Misol: A(n) massiv elementlarini tasodifiy sonlar yordamida hosil qilib uning juft elementlarini ikkiga ko‘paytirib ekranga chiqaring #include <iostream.h> using namespace std; int main() { int a[10]; for(int i=0;i<=9;i++) a[i]=rand(); for(int i=0;i<=9;i++) if(a[i]%2==0) cout<<a[i]*2<<” “; return 0; } 5-Misol: A(2,3) massiv berilgan uning elementlarini ikkiga ko‘paytirib ekranga chiqaring #include <iostream.h> int main() { int a[3][2]; for(int i=0;i<=2;i++) for(int j=0;j<=1;j++) cin>>a[j][i]; for(int i=0;i<=2;i++) { for(int j=0;j<=1;j++) cout<<2*a[j][i]<<” ”; cout<<”\n”; } return 0; } 6-mustaqil ish Mavzu: Struktura turi, Strukturalarni dasturlash va algoritmlashtirish Reja: 1. Struktura turlari 2. Stek ma’lumotlar strukturasi 3. Navbat C++ dasturlash tili tarkibida bir nechta turlarni birlashtirib bitta tur asosida ma’lumotlar bazasini yaratish va ularni qayta ishlash imkoniyati keng yaratilgan. Bir nechta turlarni birlashtirish natijasida strukturalar hosil qilib C++ dasturlash tili tarkibida tashkilotlarga tegishli bo‘lgan bir nechta masalalarni hal etish imkoniyati mavjud. Ta’rif: C++ dasturlash tilida bir yoki bir nechta turlarni jamlanmasini birlashtirish struktura deb nomlanadi. Strukturalarni ba’zi hollarda yozuvlar ham deb ataladi, strukturalar tarkibidagi turlarning har biri maydon deb nomlanadi. Ta’rif: Ob’yektning bitta xususiyatini uzida saqlaydigan parameter maydon deb nomlanadi. Talaba haqida ma’lumotlar strukturasi hosil qilinishda quyidagi maydonlar bo‘lishi mumkin: Talabani familyasi, ismi, otasining ismi, tug’ilgan vaqti, telefoni, manzili va hakoza. Strukturalar maydonlardan tashkil topgan ekan, struktura tarkibidagi har bir maydon strukturani bitta parametrini o‘zida saqlaydi. Struktura maydoni uchun xotira hajmi , mayon uzunligiga teng bo‘ladi. Struktura maydoni qiymatlari ifodalarda ishlatilishi mumkin. C++ dasturlash tilida strukturalarni e’lon qilishda struct xizmatchi so‘zidan foydalaniladi. Struktura e’lon qilingandan so‘ng dastur tarkibida o‘zgaruvchilarni struktura nomi bilan e’lon qilinadi. C++ dasturlash tilida strukturalarni tasvirlashning umumiy ko‘rinishi quyidagicha ko‘rinishda bo‘ladi: struct <struktura nomi> { <tur1> <maydon 1>; <tur2> <maydon 2>; _ _ _ _ _ _ _ <tur n> <maydon n>; }; Strukturalarni tasvirlashda struct xizmatchi so‘zidan keyin struktura nomi va fegurali qavsda uning maydonlari kiritilishi shart. Structura nomi masala mohiyatiga qarab tanlansa, maqsadga muvofiq. Masalan, talabalar haqida ma’lumotlar bazasida struktura nomini talaba yoki supermarket mahsulotlari narxlari bazasida esa narx deb nomlash mumkin. Strukturalar tarkibidagi maydonlarni e’lon qilish xuddi oddiy o‘zgaruvchilarni e’lon qilishdek bajariladi va oxiri blok yopilishidan so‘ng, albatta, nuqtali vergul qo‘yilishi shart. Yuqoridagi masalada talaba haqida ma’lumotlar strukturasini hosil qilishda struktura nomiga talaba deb nomlandi va uning maydonlari familyasi(fam), ismi(ism), telefoni(tel), reytingi(reyting), tug’ilgan yili(tugy) ko’rinishlarida tasvirlandi. Maydonlarni e’lon qilishda dastur tarkibida qanday maqsadlarda foydalanishi e’tiborga olinishi kerak. Agar dastur tarkibida maydonlar ustida hisob ishlari olib borilmasa, uning turini char yoki string turi ko‘rinishida e’lon qi Stek – Stack inglizchadan uyum, g aram, dasta, bog lam deganʻ ʻ ma’noni anglatadi. Stek - bu LIFO (last in – first out; oxirgi kelgan – birinchi ketadi) prinsipi bo yicha ʻ ishlaydigan ma’lumotlar strukturasi. Stekda massivdagi kabi indekslar mavjud emas, demak ma’lum bir elementga murojaat qila olmaysiz. Buning sababi, stek bog langan ro yxatlar asosida tuzilgan. Bu shuni ʻ ʻ anglatadiki, har bir element (oxirgisidan tashqari qolgan elementlar NULL-ga ishora qiladi, oddiy so zlar bilan aytganda, hech narsaga ishora qilmasa NULL bo ladi) keyingi ʻ ʻ elementga ko rsatgichga ega. Ammo ko rsatgich bo lmagan element mavjud - birinchisi ʻ ʻ ʻ (yoki uni bosh element deb ham atashadi). Stek ma’lumotlar strukturasi Shu o rinda savol paydo bo lishi mumkin? Nima uchun massivlarni ishlatish mumkin ʻ ʻ bo lganda stekni ishlatamiz. Sababi stek to plamining asosiy kuchi elementlarni qo shish ʻ ʻ ʻ va olib tashlashdan iborat ekanligida. Ushbu amallar doimiy vaqt ichida amalga oshiriladi (bu yaxshi plyus). Ba’zi dasturchilar massivda stek qilishadi. Stekdan foydalanishning bu usuli haqida biroz keyinroq gaplashamiz. C ++ tilida stekni realizatsiya qilish. Dastur boshida stek shablonidan foydalanish uchun < stack > kutubxonasini yoqishimiz kerak. Stek yaratish uchun biz quyidagi sxema bilan ishlashimiz kerak: stack <ma’lumot_turi> <nom>; Yangi satrda stack kalit so zini yozishimiz kerak. ʻ <ma’lumotlar turi> - bu yerda stekda saqlanadigan ma’lumotlar turini yozishimiz kerak. <nom> - bu stek nomi. Navbat Navbat. Navbat - bu FIFO (First In - First Out - "birinchi kelgan – birinchi ketadi") prinsipi bo yicha qurilgan ma’lumotlar strukturasi. ʻ Navbatda, agar siz avval kiritilgan elementni qo shsangiz, u birinchi bo lib chiqadi. Agar 4 ʻ ʻ ta element qo shsangiz, birinchi qo shilgan element birinchi bo lib chiqadi. ʻ ʻ ʻ Navbat ma’lumotlar strukturasi Rasmda 7 ta raqam mavjud: 2, 4, 7, 1, 4, 9, 10. Agar ularni ajratib olishimiz kerak bo lsa, ʻ biz ularni rasmdagi kabi tartibda chiqaramiz! Masalan, 4-raqamni ajratib olish uchun avval 2-raqamga, so ngra 4-raqamga xizmat ʻ ko rsatishimiz kerak. ʻ Stekda peek() funksiyasi mavjud bo lsa-da (bu elementga indeks bo yicha kirishga imkon ʻ ʻ beradi), navbat shablonidagi ma’lum bir elementga murojaat qilish mumkin emas. Agar siz navbatning barcha elementlariga kirishingiz kerak bo lsa, unda siz navbatni ʻ massiv orqali amalga oshirishingiz mumkin Misollardan namunalar: 1-Misol: Talabalar(familyasi, ismi, telefoni, reytingi, tug’ilgan yili) haqida ma’lumotlarga asosan c++ dasturlash tilida struktura hosil qiling. #include <iostream.h> using namespace std; struct talaba { char[20] fam; //familyani saqlovchi maydon char[20] ism; //ismni saqlovchi maydon char[20] tel; //telefonni saqlovchi maydon int reyting; //reyting balini saqlovchi maydon int tugy; //tug’ilgan vaqtini saqlovchi maydon }; int main() { return 0; } 2-Misol: #include <iostream> using namespace std; struct MT { char Univernomi[10]; int Tbsoni; int Kafedrasoni; }; int main(void) { struct MT p; cout<<"Universitet nomini kiriting"; cin.get(p.Univernomi,10); cout<<"Talabalar soni"; cin>>p.Tbsoni; p.Kafedrasoni = 30; cout << "Talabalar soni: " << p.Tbsoni << endl; cout << "Kafedralar soni: " << p.Kafedrasoni << endl; cout<<"Universitet nomi:"<<p.Univernomi; return 0;} 3-Misol: #include <iostream> using namespace std; struct Person { char name[50]; int age; float salary; }; int main() { Person p1; cout << "Enter Full name: "; cin.get(p1.name, 50); cout << "Enter age: "; cin >> p1.age; cout << "Enter salary: "; cin >> p1.salary; cout << "\nDisplaying Information." << endl; cout << "Name: " << p1.name << endl; cout <<"Age: " << p1.age << endl; cout << "Salary: " << p1.salary; return 0; } 4-Misol: #include <iostream> using namespace std; struct Person { char fakultet[50]; char yonalish[50]; int guruh; int ID; }; int main() { Person p1; cout << "Fakultetingiz: "; cin.get(p1.fakultet, 50); cout << "Yo'nalishingiz: "; cin >> p1.yonalish; cout << "Guruhingiz: "; cin >> p1.guruh; cout<<"Id ingiz:"; cin>> p1.ID; cout << "\nDisplaying Information." << endl; cout << "fakultet: " << p1.fakultet << endl; cout <<"yunalish: " << p1.yonalish<< endl; cout << "guruh: " << p1.guruh; cout<<"Id:"<<p1.ID; return 0; } 5-Misol: Stekning juft o’rinda turgan elementlari o’chirilsin. *- coding: utf-8 -*- """ Created on Sat May 14 10:32:29 2022 @author: admin """ class Steck: """Steck degan malimot turi""" def init(self): self.steck=[] def Push(self,data): """Ruyhatga elimentlar qushish""" # self.data=data self.steck.append(data) return f"Malimot qushildi" def isEmpty(self): """Element bush emasligini tekshirish""" return len(self.steck)==0 def Pop(self): """Ruyhatdan eliment sug'irib olish""" if self.isEmpty(): return f"Malimot bosh" else: self.steck.pop() def Peek(self): """Eng yuqoridagi qiymat elimentini kurish""" if self.isEmpty(): return f"Tuplam ichida eliment yuq" else: return self.steck[-1] def malimot(self): """toq urinda turgan malimotlardi chiqarish""" return self.steck[1:10:2] # def uchirish(self): # """Juft urinda turgan malimotlardi uchirish.""" # # if m%2==0: # for n in self.steck: # n%2==0 # return self.steck.pop() steck=Steck() print(steck.Push(2)) print(steck.Push(23)) print(steck.Push(42)) print(steck.Peek()) print(steck.malimot()) 7-mustaqil ish Mavzu: Tartiblash va saralash masalalarini algoritmlashtirish. Ma’lumotlarni tartibga solish turlari. Ma’lumotlar tuzilmasini saralash usullari. Reja: 1. Qo’yish tartiblash usuli (Insertion Sort) 2. Sheyker tartiblash usuli 3. Shell tartiblash usuli Tartiblash – bu berilgan obyektlar to plamini muayyan tartibda qayta tartibga solishʻ jarayoni. Saralashning maqsadi elementlarni topishni osonlashtirishdir. Saralash algoritmi – bu ro yxatdagi elementlarni saralash algoritmi. Agar ro yxat ʻ ʻ elementida bir nechta maydon bo lsa, saralash amalga oshiriladigan maydon ʻ saralash kaliti deb ataladi. Amalda raqam ko pincha kalit sifatida ishlatiladi va ba’zi ma’lumotlar ʻ algoritm ishlashiga hech qanday ta’sir ko rsatmaydigan qolgan maydonlarda saqlanadi. ʻ 1. Qo’yish tartiblash usuli (Insertion Sort) Qo’yish tartiblash usuli (Insertion Sort) – bu sodda tartiblash algoritmi. Algo-ritmning har bir qadamida massiv elementlaridan biri olinadi, qo’yish uchun joyi aniqlanadi va qo’yiladi. Ta'kidlash kerakki, 1 ta elementdan iborat massiv tartiblangan hisoblanadi. Algoritmning so’zli tavsifi murakkab ifodalanadi, lekin amalga oshirish juda ham sodda. Har biri kishi, faoliyati davomida saralash algoritmidan foydalanadi. Masalan, kupyuralarni tartiblashda, 100 so’mlik kupyurani olib, 10, 50 va 500 so’mlik kupyuralar ketma-ket kelgan bo’lsin. Bunda faqat 50 dan 500 so’mlik kupyurani orasiga 100 so’mlik kupyurani qo’yamiz. Amalga oshirish .Amalga oshirishni davom ettirishdan oldin, kirish ma'lumot-larining formatini aniqlaymiz - masalan, bu butun (int) qiymatlar massivi bo'lsin. Massiv elementlarini nomerlash 0 dan boshlanadi va n-1 bilan tugaydi. Algoritmni C++ tilida amalga oshirish misolida qarab chiqamiz. Algoritmning asosiy sikl 0-elementdan emas, balki 1-elementdan boshlanadi, chunki 1- elementgacha bo'lgan element tartiblangan ketma-ketlik bo'ladi (bitta elementdan iborat massiv tartiblangan hisoblanadi) va bu elementga nisbatan 0 nomerli bilan biz boshqasini kiritamiz. Aslida kod: for(int i=1;i<n;i++) for(int j=i;j>0 && x[j-1]>x[j];j--) // toki j>0 va elementlarda j-1 > j swap(x[j-1],x[j]); // massivning j va j-1 elementlari almashtiriladi Tartiblashni amalga oshirish juda oddiy, faqat 3 qatordan iborat. swap funksiyasi x[j-1] va x[j] elementlarini almashtiradi. Ichma-ich sikl elementni qo’yish uchun joyni aniqlaydi. Algoritm tahlili Qo’yish tartiblash usuli n2 murakkablik tartibiga ega, taqqoslashlar soni n*(n-1)/2 formulasi bo'yicha hisoblanadi. Bunga quyidagi kod bilan ishonch xosil qilish mumkin: void Sort(int* arr,int n){ int counter=0; for(int i=1;i<n;i++){ for(int j=i; j>0 && arr[j-1]>arr[j];j--){ counter++; int tmp=arr[j-1]; arr[j-1]=arr[j]; arr[j]=tmp; } } cout<<counter<<endl; } Samaradorlik Agar massivning qismi tartiblangan va massiv elementlar soni ko‘p bo‘lmasa, ushbu tartiblash eng samarali hisoblanadi. Agar elementlar 10 dan ko’p bo'lmasa, ushbu algoritm eng yaxshi hisoblanadi. 2. Sheyker tartiblash usuli Pufakchali tartiblash usuli ma'lum darajada yaxshilanishi va uning vaqt xarak-teristikasini yaxshilashi mumkin. Masalan, tartiblashning bitta o'ziga xos xususi-yatini ko'rish mumkin: massiv oxiridagi o’z o’rnida joylashmagan element bir o'tishda o'z joyiga joylashadi va massiv boshida joylashgan element esa o'z joyiga joylashishi juda sekin amalga oshiriladi. Barcha qarab chiqishlarni bir yo'nalishda olib borish shart emas. Buning o'rniga, har bir keyingi qarab chiqishni teskari yo'nalishda amalga oshirilishi va tartiblanmagan qismning quyi va yuqori chegaralarini belgilash mumkin, ya’ni qarab chiqishning massivning oxirigacha emas, balki oldingi qarab chiqilgandagi oxirgi almashtirishgacha tartiblash maqsadga muvofiq bo’ladi. Bunday holda, o'z joyidan uzoqda bo'lgan elementlar tezda tegishli joyga o'tadi. Quyida massivlarning tartiblashning Sheyker tartiblash usuli deb nomlangan pufakchali tartiblashning takomillashtirilgan versiyasi keltirilgan: left = 1 // tartiblanmagan qismning chap chegarasi right = N // tartiblanmagan qismning o’ng chegarasi tartib = false // true, agar massiv tartiblangan bo’lsa toki emas tartib tartib = true i = left //Massivning boshidan oxirigacha o’tish: toki i < right agar A[i] > A[i + 1] u holda almashtir (А, i, i+1) tartib = false hal bo’ldi // (agar) i = i + 1 sikl oxiri // >=1 element o’ngdan o’zining joyiga qo’yildi right = right – 1 agar emas tartib u holda tartib = true i = right toki i > left agar A[i] < A[i – 1] u holda almashtir (A, i, i–1) tartib = false hal bo’ldi i = i – 1 sikl oxiri hal bo’ldi // (agar) // >= 1 element chapdan o’zining joyiga qo’yildi left = left + 1 sikl oxiri // emas tartib Dasturi : void shaker_sort (struct KeyData A [], int N) { int left = 0, right = N-1; int sorted = 0; while (!sorted && left < right) { int i; sorted = 1; for (i = left; i < right; ++i) { if (A[i+1] < A[i]) { struct KeyData x = A[i+1]; A[i+1] = A[i]; A[i] = x; sorted = 0; } } right -= 1; if (!sorted) for (i = left+1; i<=right; i++) { if (A[i-1] > A[i]) { struct KeyData x = A [i-1]; A[i-1] = A[i]; A[i] = x; } } left += 1; } // while } // shaker sort 3. Shell tartiblash usuli Bu tartiblash usuli 1959 yilda D. Shell tomonidan taklif qilgan. U xotiradan minimal foydalanadi va tartiblashda yuqori tezligini ko'rsatadi. Shell usuli qo'-shish usuliga o'xshash elementlarni taqqoslash va almashtirishlardan foydala-nadi, ammo taqqoslanadigan elementlarning tartibi butunlay boshqacha tar-tibda bo’ladi. Shell tartiblash usulining g’oyasi bir-biridan ma'lum step qadam masofada joylashgan elementlarni tartiblashdan iboratdir. Keyin tartiblash step kichik qiymatlarida takrorlanadi va Shell tartiblash jarayoni step = 1 bo’lganga tugaydi Tartiblash step qadamini tanlash masalasi muhokamasi davom etmoqda. Shell quyidagi ketma-ketlikni taklif qildi: N/2, N/4, N/8 ..., bu erda N - massivdagi tartiblanadigan elementlar soni. Shell tartiblash N uzunlikdagi ketma-ketlikni tartiblash uchun log2N ga yaqin o'tishni talab qiladi Misollardan namunalar 1-Misol: Butun sonlardan iborat navbatning juft elementlarini o’chirish dasturini keltiramiz. #include <iostream> using namespace std; int a[10],R=0,n;//bu yerda n navbatga kiritilishi kerak bo'lgan elementlar soni. int kiritish(int s){ a[R]=s; R++; } int chiqarish(){ int t=a[0]; for(int i=0;i<R-1;i++) a[i]=a[i+1]; R--; return t; } bool isEmpty(){ if(R==0) return true; else return false; } bool isFull(){ if(R>=10)return true;else return false; } int print(){ int i; while(i<R){ int k=chiqarish();i++; cout<<k<<" "; kiritish(k);} } int main(){ int n,s; cout<<"n=";cin>>n; for(int i=0;i<n;i++){ if(!isFull()){cin>>s; kiritish(s);} else{cout<<"navbat to'ldi"; n=i;break;} } cout<<"\nnavbat elementlari: "; print(); for(int i=0;i<n;i++){ s=chiqarish(); if(s%2! =0)kiritish(s); } cout<<"\nnatijaviy navbat elementlari: "; print(); system("PAUSE"); } Dasturning bajarilishi natijasi: n=5 6 7 9 8 11 navbat elementlari: 6 7 9 8 11 natijaviy navbat elementlari: 7 9 11 2-Misol: Dastur kodi #include <iostream> using namespace std; int a[10],R=0,n;//bu yerda n stekka kiritilishi kerak bo'lgan elementlar soni. int kiritish(int s){ a[R]=s; R++; } int chiqarish(){ R--; return a[R]; } bool isEmpty(){ if(R==0) return true; else return false; } bool isFull(){ if(R>=10) return true;else return false; } int print(){ int i=0,c[n]; while(!isEmpty()){ c[i]=chiqarish(); cout<<c[i]<<" ";i++;} for(int j=i-1;j>=0;j--) kiritish(c[j]); } int main(){ int n,s; cout<<"n=";cin>>n; for(int i=0;i<n;i++){ if(!isFull()){ cin>>s; kiritish(s);} else{cout<<"stek to'ldi"; n=i;break;} } cout<<"\nstek elementlari: "; print(); int b[n],k=0; for(int i=0;i<n;i++){ s=chiqarish(); if(s%2!=0) b[k++]=s; } for(int i=k-1;i>=0;i--) kiritish(b[i]); cout<<"\nnatijaviy stek elementlari: "; print(); system("PAUSE"); } Dasturning bajarilishi natijasi: n =5 6 7 9 8 11 stek elementlari: 11 8 9 7 6 natijaviy stek elementlari: 11 9 7 3-Misol: Dastur kodi #include <cstdlib> #include <iostream> using namespace std; int a[10],n,R=0; bool isEmpty(){ if(R==0) return true; else return false; } bool isFull(){ if(R>=10) return true; else return false; } int kirit_left(int s){ if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;} for(int i=R;i>0;i--) a[i]=a[i-1]; a[0]=s;R++; cout<<"\nnatijaviy stek elementlari: "; print(); system("PAUSE"); } Dasturning bajarilishi natijasi: n =5 6 7 9 8 11 stek elementlari: 11 8 9 7 6 natijaviy stek elementlari: 11 9 7 3-Misol: Dastur kodi #include <cstdlib> #include <iostream> using namespace std; int a[10],n,R=0; bool isEmpty(){ if(R==0) return true; else return false;} bool isFull(){ if(R>=10) return true; else return false; } int kirit_left(int s){ if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;} for(int i=R;i>0;i--) a[i]=a[i-1]; a[0]=s;R++; } int olish_left(){ if(isEmpty()){cout<<"\ndek bo'sh";return EXIT_SUCCESS;} int t=a[0]; for(int i=0;i<R-1;i++) a[i]=a[i+1]; R--; return t; } int kirit_right(int s){ if(isFull()){cout<<"\ndek to'ldi";n=R;return EXIT_SUCCESS;} a[R]=s;R++; } int olish_right(){ if(isEmpty()){cout<<"\ndek bo'sh";return EXIT_SUCCESS;} R--; return a[R]; } int print(){ cout<<endl<<"dek ele-tlari="; for(int i=0;i<R;i++)cout<<a[i]<<" "; cout<<endl; } int main(int argc, char *argv[]) { int n,s;cout<<"n="; cin>>n; for(int i=0;i<n;i++){ if(!isFull()){ cout<<"kirit=";cin>>s; if(i>=n/2) kirit_right(s); else kirit_left(s);} else {cout<<"dek to'ldi\n";break;} } print(); int b[n/2],k=0,c[n/2],p=0; while(!isEmpty()){ int q=olish_left(); if(q%2==0) b[k++]=q; if(isEmpty()) break; int p=olish_right(); if(p%2==0) b[k+ +]=p; } int i=0; while(i<k){ kirit_right(b[i]); i++; } print(); system("PAUSE"); return EXIT_SUCCESS; } Dastur natijasi n=8 8-mustaqil ish Mavzu: Qidiruv algoritmlari. Axborot izlashning asosiy tamoyillari. K е tma-k е t izlash. Izlashning t е zlashtiririlgan usullari. Reja: 1. Axborot izlashning asosiy tamoyillari 2. Ketma-ket izlash 3. Ikkilangan daraxt bo’yicha izlash 1.Axborot izlashning asosiy tamoyillari Kompyuter yordamida axborotga ishlov berishning istalgan jarayonida har qanday hisoblash ishlarini bajarishda bir necha marta mashina xotirasidagi zarur ma’lumotlarni izlash masalasini hal qilishga to‘g‘ri keladi. Bunda, odatda, ma’lumotlarning imkon qadar tez topilishi talab etiladi. Izlash ishlari AAT foydalanuvchilari yoki ilovalardan tushadigan so‘rovlarga javoban olib boriladi. Birinchi holda so‘rov ochiq xolda shakllantiriladi va uni amalga oshirish uchun izlash algoritmi ishlab chiqiladi va tegishli dasturlar yoziladi. Ilovalardan tushadigan so‘rovlar ochiq shaklda shakllantirilmaydi, lekin har qanday dasturni bajarishda izlash operatsiyalari amalga oshiriladi. Masalan, o‘zgaruvchiga uning nomi bilan har qanday qilingan murojaatlarda operatsion tizim bu o‘zgaruvchining joriy qiymati saqlanayotgan xotira uyasini izlashga kirishadi. Axborot massividan aynan izlanayotgan axborot joy olgan yozuvni izlab topish uchun uni qandaydir yo‘l bilan «tanish» zarur. Buning ustiga ushbu yozuv so‘rovni qoniqtiradimi-yo‘qmi, buni aniqlash kerak. Agar berish mezonlari bilan belgilanadigan shartlar bajarilsa, yozuv so‘rovni qoniqtiradi deb xisoblanadi. Axborot izlashning asosiy vazifasi - yozuv ichidagi ma’lumotlarning belgilangan berish mezonlariga mosligi to‘g‘risidagi masalani xal qilishdan iborat. AAT ga tushadigan so‘rov muayyan tarzda shakllantiriladi. Bunda izlash argumenti shakllantiriladi. So‘rovning turiga ko‘ra izlash argumenti turli shakl va murakkablik darajasiga ega bo‘lishi mumkin. Eng oddiy xolda, ya’ni muayyan belgilarga ega bo‘lgan ob’ekt to‘g‘risidagi yozuvni topish kerak bo‘lganida shu belgining o‘zi izlash argumenti bo‘ladi. Bunday izlash, odatda, bir aspektli, ya’ni bitta belgisi bo‘yicha izlash deyiladi. Izlash argumenti ob’ektning muayyan, shu jumladan asosiy bo‘lmagan belgilari ro‘yxatidan iborat bo‘lishi mumkin, u xolda ko‘p aspektli deb ataladi. Izlash argumenti belgilar va mantiqiy operatsiyalar (kon’yunksiya, diz’yunksiya, inversiya va boshqalar) dan iborat bo‘lgan bul algebrasi formulasi yoki ko‘plik nazariyasi, yoki bu belgilar ustidagi nazariyko‘plik operatsiyalari (birlashtirish, kesib o‘tish va xokazo) dan iborat bo‘lishi mumkin. Bunday agrument bo‘yicha izlashda yozuv maydoni qiymatlari ustida tegishli operatsiyalar bajariladi. Bu izlash bosqichining o‘zidayoq yozuvning axborot mazmunini muayyan darajada baxolash imkonini beradi. Izlashning bunday turidan ilmiytexnika yoki boshqa matnli axborotga ishlov beradigan avtomatlashtirilgan tizimlarda foydalaniladi. Bunday tizimlarda izlashda u yoki bu belgilari bo‘yicha topilgan xujjatning mazmunini va uning so‘rov mazmuniga moslik darajasini baxolash muximdir. Har qanday xolda ham izlash argumentining istalgan shaklida axborot izlash jarayoni formal jarayon bo‘lib, muayyan simvollarni qiyoslash yoki ular ustida qandaydir operatsiyalarni bajarishdan iboratdir. Bu jarayon izlanayotgan axborot tabiatiga bog‘liq bo‘lmaydi. Izlash jarayonining formalligi izlash uchun xam kompyuterdan, xam turli mexanizatsiyalashgan tizimlardan, xatto dastaki qurilmalardan xam foydalanish imkoniyatini beradi. Izlash sifati, uning samaradorligi tizimni ishlab chiqish bosqichida aniqlanadi va so‘rovning mazmuni va ma’nosi izlash argumentida, xujjatning mazmuni esa yozuv maydoni mazmunida qanchalik aniq va to‘liq aks ettirilganiga bog‘liq bo‘ladi. Axborot izlashning quyidagi turlari mavjud: Mosligi bo‘yicha izlash. Izlash argumenti bir yoki bir nechta belgilar (yozuv maydonlari) nomi va ularning qiymatlaridan iborat bo‘ladi. Izlash jarayonida axborot massividan nomlangan maydonlarning qiymatlari ko‘rsatilgan yozuvlar ajratiladi. Bu xolda bevosita mos tushish ma’lumotni chiqarib berish mezoni xisoblanadi. Bunday izlash natijasida muayyan belgilarning aniq qiymatlariga ega bo‘lgan ob’ektlar to‘g‘risida ma’lumotlar olinadi. Interval bo‘yicha izlash. Izlash argumenti bir yoki bir necha belgilar nomidan va bu belgilar qiymatlarining o‘zgarish chegarasidan iborat bo‘ladi. Izlash jarayonida axborot massividan tegishli maydonlarining qiymati belgilangan chegaralarda yotadigan ko‘plab yozuvlar ajratib olinadi. Bu erda belgilangan intervalga tegishli ma’lumotlarni chiqarib berish mezoni xisoblanadi. Izlash natijasida foydalanuvchini qiziqtirgan belgilar qiymati ko‘rsatilgan diapazon chegarasidan chiqmaydigan ob’ektlar to‘g‘risidagi ma’lumotlar olinadi. Ifodalar bo‘yicha izlash. Izlash argumenti arifmetik yoki nazariy-ko‘plik ifodasi yoki bul algebrasi formulasidan iborat bo‘ladi. Belgilarning nomi operanda xisoblanadi. Izlash jarayonida massivning barcha yozuvlari tegishli maydonlaridagi mavjud narsalar ustida zarur operatsiyalar bajariladi: yoki izlash argumenti bilan belgilangan ifodaning qiymati hisoblab chiqiladi, yoki nazariy-ko‘plik operatsiyalari bajariladi, yoki ifodaning xaqiqiyligi aniqlanadi. Bunday izlashda foydalaniladigan chiqarib berish mezonlari mantiqiy mezonlar deb ataladi. Ancha murakkab bo‘lgan so‘rovlar, odatda, shunday shaklga keltiriladiki, bunda yuqorida sanab o‘tilgan izlash turlaridan biri bilan ularni amalga oshirish mumkin bo‘lsin. Axborot izlash protsedurasi ko‘pincha izlash mantiqi va izlash strategiyasi nuqtai nazaridan qaraladi. Izlash mantiqi izlash topshiriqlarining so‘zlar bilan berilgan mazmuniy bayonini belgilab beradi, izlash argumenti turini aniqlaydi, topilgan axborotning so‘rovga mosligini baxolash mezonlarini belgilaydi. Izlash mantiqi kompyuterning xotira qurilmasida axborot massivlarini tashkil etishning o‘ziga xos xususiyatlari, kompyuterning turi va konfiguratsiyasi, hisoblash tizimining matematik ta’minoti kabilarga bog‘liq bo‘lmaydi. Aynan izlash mantiqi izlash samaradorligi - to‘liqligi va aniqligini baholashni belgilaydi. Izlash strategiyasi — bu izlash mantiqini muayyan tizim sharoitida amalga oshirishdir. Izlash strategiyasini ishlab chiqishda saqlanayotgan axborot harakteri, axborot massivlari hajmi va XQ (xotira qurilmasi) turi baholanadi; kompyuter xotirasidan ma’lumotlarni izlashning ma’lum bo‘lgan bitta usuli tanlanadi yoki o‘ziga xos usuli ishlab chiqiladi; so‘rovlar va javoblar shakllarini xisobga olgan xolda izlash algoritmi belgilanadi. Izlash strategiyasini ishlab chiqishda axborot massivlarini tashkil etish usuli, ya’ni ma’lumotlarni tashkil etish uchun foydalanilgan strukturalar turi albatta xisobga olinadi. Axborotni izlash tezligi strategik masalalarni savodli va oqilona hal qilishga bog‘liq bo‘ladi. Ushbu mavzuda ko‘rib chiqiladigan barcha material dasturiy izlashga taalluqli bo‘lib, muayyan algoritmlar bo‘yicha tuzilgan dasturlar yordamida amalga oshiriladi. Uning davomiyligi axborot massivi, ma’lumotlar tuzilishi, foydalanish usuli, algoritmlar va dasturlar sifatiga bog‘liq bo‘ladi. Assotsiativ xotirlash qurilmalariga ega bo‘lgan kompyuterlarda izlash operatsiyalari apparat vositalari bilan amalga oshiriladi. Apparat (sxema) vositasida izlash tezligi bo‘yicha har qanday dasturiy usuldan ustun turadi, buning ustiga apparat vositasida izlash vaqti yuqorida sanab o‘tilgan omillarning birortasiga xam bog‘liq bo‘lmaydi. Undan foydalanish xozirgi vaqtda ishlatilayotgan kompyuterlarda katta xajmdagi assotsiativ xotira qurilmalari yo‘qligi sababli cheklangandir. Katta assotsiativ xotiraga ega bo‘lgan kompyuterlarni ishlab chiqish va joriy etish ma’lumotlarning jismoniy tuzilishini jiddiy o‘zgartirishlarga va axborotga avtomatlashgan ishlov berish tizimlari ish unumining ancha ortishiga olib keladi. 2. Ketma-ket izlash Izlashning ketma-ket usulini ketma-ket saralash usuli deb xam atashadi. Bu eng universal, eng oddiy va eng uzok davom etadigan izlash usulidir. Ketma-ket izlashdan axborot massivlarining har qanday tashkil etilishida, ma’lum otlarning turli tuzilishida, turli izlash argumentlarida foydalanish mumkin. Izlash jarayonida massivning har bir yozuviga ketma- ket murojaat etiladi va bunda ushbu yozuv chiqarib berish mezonlarini qoniqtirishi aniqlanadi. Mosligi bo‘yicha bir aspektli izlashda tartibga solinmagan axborot massivida yozuvlar kaliti xamda izlash argumentlarini solishtirish massivning barcha N yozuvlari ko‘rib chiqilmaguncha davom ettiriladi. Izlanayotgan kalitli yozuvlar foydalanuvchiga taqdim etiladi yoki yana qayta ishlash uchun amaliy dasturlarga uzatiladi. 2. Ketma-ket izlash Masalan, yozuvlar kaliti qiymatlari ortib borishi bo‘yicha tartibga solingan massivda joriy yozuv kalitining qiymati izlash argumenti qiymatidan ortib ketishi bilan izlashni darhol to‘xtatish mumkin. Interval bo‘yicha bir aspektli izlashda xam tartibga solingan massivda izlashni barcha massiv ko‘rib chiqilgunga qadar to‘xtatish mumkin. N yozuvdan iborat massivda tadrijiy izlash uchun o‘rtacha (N + 1)/2 solishtirish (suratdagi bir N juft bo‘lmaganda paydo bo‘ladi) talab etiladi. Eng yomon xolda, izlanayotgan yozuv massivning eng oxirida bo‘lsa yoki umuman u erda bo‘lmasa, N solishtirish talab etiladi. Ketma-ket izlash — tartibga solinmagan strukturalanmagan massivlarda ma’lumotlarni izlashning yagona variantidir. Lekin, shuni yodda tutish kerakki, axborot massivlari xajmi juda katta bo‘lgan xollarda izlash shunchalik uzoq davom etadiki, u butunlay foydasiz xam bo‘lib qolishi mumkin. Aniqroq aytganda, bunday xolda izlash usuli emas, axborot massivini tashkil etish foydasiz bo‘ladi. Katta xajmdagi axborot yoki tartibga solingan, yoki, eng yaxshisi, strukturalangan bo‘lishi zarur. Tartibga solinmagan massivlarda axborot izlash jarayoni birmuncha tezlashtirilishi mumkin. Har qanday izlash algoritmi massiv tugashini tekshirish blokiga ega bo‘ladi. Odatda, har safar navbatdagi yozuvga murojaat qilishdan oldin bunday tekshirish amalga oshiriladi. Lekin massiv tugashini har bir solishtirish vaqtida tekshirib o‘tirmaslik mumkin. Buning uchun massiv oxiriga kaliti izlanayotgan axborot kalitiga teng bo‘lgan soxta (N + 1) yozuvi kiritiladi. Bunda massivning oxiri faqat izlash argumenti joriy yozuv kaliti qiymati bilan mos kelgan xolda tekshiriladi. Agar bu yozuv massiv ichida bo‘lsa, izlash muvaffaqiyatli tugallanadi va zarur yozuv topilgan xisoblanadi. Agar bu yozuv (N + 1) bo‘lsa, demak, izlash muvaffaqiyatsiz bo‘ladi, ya’ni kerakli yozuv massivda yo‘q bo‘ladi. Agar massiv uchun umumiy ma’lumotnoma tashkil etilgan bo‘lsa, tartibga solinmagan massivda tadrijiy izlash ancha kam vaqt talab etadi. Ma’lumotnoma xajmi asosiy massiv hajmidan kam bo‘lganligi uchun unda axborot izlash tezrok bo‘ladi. Ketma-ket tartibga solingan axborot massivlarida izlashni ancha tezlashtirish mumkin. Izlashning tezlashtirilgan usullariga ikkilangan va blokli izlash usullarini kiritish mumkin. Ikkilangan izlash, boshqacha aytganda, binar yoki dixotomik izlash eng tezkor usullardan biridir. Yozuvlar kalitining qiymati oshib borishi bo‘yicha tartibga solingan massiv o‘rtasida joylashgan yozuvga birinchi murojaat qilinadi (1-rasm). Yozuv kaliti (K) izlash argumenti (A) bilan solishtirilgandan so‘ng bunday keyin massivning qaysi qismiga murojaat qilish kerakligi aniqlanadi. Agar yozuv kaliti qiymati izlash argumenti qiymatidan katta bo‘lsa, keyingi murojaat massivning birinchi qismi o‘rtasida joylashgan yozuvga qilinadi. Aks holda, massivning ikkinchi qismi o‘rtasida joylashgan yozuvga murojaat qilinadi. Ushbu protsedura massivning 1/4, 1/8, 1/16 va xokazo qismlarida, izlanayotgan yozuv topilgunga qadar yoki izlash olib borilayotgan interval bo‘sh bo‘lgunga qadar olib boriladi. Usulning kamchiligi shundan iboratki, har ikki murojaat o‘rtasida muayyan manzil yoki keyingi o‘qiladigan yozuv nomeri uchun hisoblashlar olib borish zarur. 3.Ikkilangan daraxt bo’yicha izlash Axborot izlashning ko‘rib chiqilgan eng tezkor usullaridan biri binar izlash xisoblanadi. Lekin bu usul faqat ba’zi bir cheklashlar bilan qo‘llaniladi: undan faqat uzunligi qaydlangan tartibga solingan yozuv massivlarida ma’lumotlar ketma-ket taqdim etiladigan xollarda foydalanish mumkin, izlash jarayonida esa muayyan hisoblashlarni bajarish zarur. Shuni qayd etib o‘tish kerakki, ketma-ket tartibga solingan ma’lumotlar izlash uchun qulay, yuritish uchun noqulay, chunki yozuvlarni qo‘shish yoki o‘chirishda har bir massivni qayta yozish talab etiladi. Ma’lumotlarning tuzilishi ikkilangan daraxt shaklida bo‘lgandagina ma’lumotlarni bog‘langan tarzda taqdim etishdan foydalanadigan massivlarda tezkor izlash olib borish mumkin. Bunday massivlarda tezkor izlashdan tashqari yozuvlarni kiritish va o‘chirish xam oson. Ikkilangan daraxt shaklidagi tuzilmada izlash ko‘rsatkichlar ko‘rsatib turadigan yo‘nalishda olib boriladi. Bo‘g‘inning o‘ng ko‘rsatkichi kaliti katta yozuvlarga, chap ko‘rsatkich esa kaliti kichik yozuvlarga olib boradi. Navbatdagi yozuv manzili va nomeri bunda talab etilmaydi. Birinchi murojaat daraxt ildiziga qaratiladi. Bunda keyingi har bir murojaat qilishda izlash argumenti joriy bo‘g‘inning yozuvi kaliti bilan solishtiriladi va keyingi murojaat yo‘nalishi aniqlanadi. Agar solishtirish natijasida izlash argumenti qiymati joriy bo‘g‘in yozuvi kalitidan katta bo‘lsa, keyingi murojaat aloqaning o‘ng manzili bo‘yicha qilinadi, aks xolda, o‘ng kichik daraxtdan chiqqan bo‘g‘inga murojaat qilinadi. Ikkilangan muvozanatlashtirilgan daraxt bo‘yicha izlashda solishtirishlar soni kam bo‘ladi va vaqt xam kam talab etiladi. Muvozanatlashtirilgan ikkilangan daraxtda izlashda solishtirishlarning o‘rtacha soni log2N ga mutanosib, bu erda N - daraxt bo‘g‘inlari soni. Yaxshi muvozanatlashgan daraxtda solishtirishlarning eng katta soni daraxt darajalari soniga teng bo‘ladi. Ikkilangan daraxt bo‘yicha izlash jarayonida yangi elementni qo‘yish mumkin bo‘ladi. Rasmda tasvirlangan daraxt tuzilishiga ega yozuvlar massiviga kalit 12 li yozuvni qo‘yish kerak bo‘lsin. Izlash jarayonida to‘rtta solishtirish operatsiyasidan keyin bunday kalitli yozuv massivda mavjud emasligi aniqlanadi. Agar yozuv joylashtirilgan xotira uyasiga kalit 11 li o‘ng ko‘rsatkich o‘rnatilsa, bu yozuv tuzilmaga kiritilgan bo‘ladi. Muvozanatlashtirilgan ikkilangan daraxt tuzilmasi ma’lumotlarning eng moslashuvchan tuzilmasi xisoblanadi. U massivni yuritish uchun eng yaxshi imkoniyatlarni (uning cheklanmagan o‘sishini, yozuvlarni tez qo‘yish va o‘chirish ), eng tez saralash va izlashni ta’minlab beradi. struct node { int data; struct node* left; struct node* right; } static int lookup(struct node* node, int tar get) { if (node == NULL) { return(false); }> else { // 2. see if found here if (target == node->data) return(true); else { if (target < node->data) return(lookup(node->left, target)); else return(lookup(node->right, target)); }}} 9-mustaqil ish Mavzu: Algoritmlashtirishda graflar nazariyasi, graflarni algoritmlashtirish Reja: 1.Graflar 2. Graflar nazariyasining asosiy tushunchalari 3 Grafni tasvirlash usullari . Graflarni o rganish bilan shug ullanadigan diskret matematikaning bo limi “Graflarʻ ʻ ʻ nazariyasi” deb ataladi. Graflar nazariyasida ushbu matematik obyektlarning asosiy tushunchalari, xususiyatlari, tasvirlash usullari va qo llanilish sohalari batafsil ko rib ʻ ʻ chiqilgan. Bizni faqat dasturlashda muhim bo lgan jihatlari qiziqtiradi. ʻ Graflar - bu chiziqlar bilan bog langan nuqtalar to plami. ʻ ʻ Nuqtalar uchlar (tugunlar) chiziqlar esa qirralar (yoylar) deb nomlanadi. Grafning ifodalanishi. Grafning to plam nazariya bo yicha ta’rifi ʻ ʻ . Bizga V - bo sh bo lmagan to plam berilgan, ʻ ʻ ʻ masalan {v1,v2,v3,v4,v5} . Uning barcha ikki elementli V(2) ichki to plamlari to plamini yozamiz. Bizning misolimiz ʻ ʻ uchun ushbu to plam quyidagicha bo ladi: ʻ ʻ Ixtiyor ravishda ba’zi bir E⊆V(2) ni olamiz, masalan: ⟨ V , E ⟩ juftligi yo naltirilmagan G grafi deb nomlanadi, unda ʻ V - uchlar to plami, ʻ E - qirralarning to plami, ʻ V(2) to plamining ichki to plami hisoblanadi. ʻ ʻ Yuqoridagilardan kelib chiqib, ushbu ta’rif odatda quyidagicha shakllantiriladi: ⟨ V , E ⟩ oriyentirlanmagan graflar juftligi deb ataladi, agar V uchlar deb ataladigan bo sh bo lmagan ʻ ʻ elementlar to plami bo lsa va ʻ ʻ E – V dagi qirralar deb ataluvchi turli elementlarning tartibsiz juftlari to plami bo lsa. ʻ ʻ Graflar nazariyasida turli xil munosabatlarni yozishda VG yoki V(G) yozuvlari, G graf qirralarining to plami uchun EG yoki E(G) yozuvlari ishlatiladi. ʻ Graf - bu abstrakt obyekt bo lib, uchlar to plami (tugunlar) va qirralarning to plami - uchlar ʻ ʻ ʻ juftliklari orasidagi bog lanishlardan tashkil topadi (ulanishlar). Graf mavzusi juda keng. ʻ Graflar diskret matematikaning o rganish mavzusidir (bu yerda graf tushunchasining aniqroq ʻ ta’rifi berilgan). Graf murakkab tuzilgan ma’lumotni tavsiflash uchun ishlatiladi va shuning uchun katta amaliy ahamiyatga ega. Matematikada graflar paydo bo lishiga Eyler asarlari ʻ yordam berdi. G graf - G: = (V, E) tartiblangan juftlik, bu yerda V - uchlarning (yoki tugunlarning) bo shʻ bo lmagan to plami, E esa qirralar deb nomlangan uchlarning juftlari to plamidir. Grafning ʻ ʻ ʻ uchlari va qirralari (ular graf elementlari deb ataladi), grafdagi uchlar soni | V | - graf tartibi, qirralarning soni | E | - graf hajmi deb ataladi. Graflar nazariyasining asosiy tushunchalari Grafdagi marshrut - bu har bir uch ( oxirgisidan tashqari ) ketma - ketlikdagi keyingi uchga qirra bilan bog ʻ langan uchlarning cheklangan ketma - ketligi . Yo ʻ l - bu qirralarning takrorlanmagan yo ʻ lidir . Oddiy zanjir - bu uchlarni takrorlamaydigan marshrut ( bu oddiy zanjirda takrorlanadigan qirralarning yo ʻ qligini anglatadi ) Orgrafdagi yo ʻ naltirilgan marshrut ( yoki yo ʻ l ) - bu har bir element oldingi va keyingi qismga tushadigan uchlar va yoylarning cheklangan ketma - ketligi . Birinchi va oxirgi uchlar bir - biriga to ʻ g ʻ ri keladigan zanjirlar sikl deb ataladi (1- rasmda ACD va ACDE sikllar ) Yo ʻ lning ( yoki siklning ) uzunligi uni tashkil etuvchi qirralarning soni deyiladi Agar uning qirralari takrorlanmasa , yo ʻ l ( yoki sikl ) oddiy deb nomlanadi ; agar u sodda bo ʻ lsa va undagi tepaliklar takrorlanmasa u elementar deb nomlanadi . Graf turlari . Yo ʻ naltirilgan graf - ( qisqacha orgraf ) - qirralari yo ʻ naltirilgan graf (4- rasm pastga qarang ). Yo ʻ naltirilmagan graf - uchlar juftligi tartiblanmagan graf (22- rasm ) Bog ʻ langan graf - bu har qanday uch juftligi o ʻ rtasida kamida bitta yo ʻ l mavjud bo ʻ lgan graf . Daraxt - bu bog ʻ langan asiklik grafik , ya ’ ni sikllar yo ʻ q va tepalik juftligi orasida bitta yo ʻ l bor (18- rasm ). Kirishning nol darajasiga ega bo ʻ lgan uch daraxtning ildizi , chiqish nol darajaga ega tugunlar esa barglar deb nomlanadi . Bog ʻ langan va bog ʻ lanmagan graflar . 16- rasmda ko ʻ rsatilganlar graflarni ikki guruhga bo ʻ lish mumkin ( kesilgan chiziq bilan ajratilgan ): bog ʻ lanmagan ( G1−G5 ) va bog ʻ langan ( G6−G11 ). Bog ʻ lanmagan graflarda qirralar bilan ulanmagan ikki yoki undan ortiq qismlar mavjud bo ʻ ladi . Ushbu qismlar bog ʻ lanish komponentlari deb ataladi . Yuqorida keltirilgan graflarda G 1 da to ʻ rtta komponent , G 2 da uchta komponent , G3,G4va G5 da 2 ta komponent mavjud , qolganlarida esa bittadan komponent mavjud . G6 va G11 graflari o ʻ rtasida G 11 grafini alohida ajratib ko ʻ rsatish mumkin , chunki to ʻ rtinchi darajali graf uchun maksimal sondagi qirralarga ega . Daraxtlar va zanjirlar . Bog ʻ langan graflarda minimal miqdordagi qirralar mavjud bo ʻ lsa , (| EG | = n − 1 ) ular daraxtlar sinfini tashkil etadi . Yuqorida rasmda bu G 6 va G7 daraxtga to ʻ g ʻ ri keladi . Daraxtlar haqida keyingi mavzuda batafsil to ʻ xtalamiz . Bu y erda biz 16-rasmda P 4 sifatida belgilangan G 7 grafini qayd etamiz , bu daraxtning alohida holati va oddiy zanjir deb ataladi . Grafni tasvirlash usullari Grafni tasvirlash uchun bir nechta usullardan foydalaniladi. Graflardan o tish uchun siz ʻ o zingizning muammoingizni eng samarali hal qiladiganlardan foydalanishingiz kerak. ʻ Ko pincha, tanlov qo shnilik matritsasi va qo shnilik ro yxati o rtasida bo ladi (quyidagi ʻ ʻ ʻ ʻ ʻ ʻ jadval ikkala yondashuvning samaradorligini taqqoslaydi). Shu bilan birga, o rnatilgan C- ʻ massivga tayanib, o zingizning ma’lumotlar tuzilmalaringizni modellashtirishingiz va STD- ʻ da mavjud bo lgan turli xil konteynerlardan foydalanishingiz mumkin. ʻ Qo shnilik matritsasi. ʻ Qo shnilik matritsasini n-tartibli ʻ A=[ai,aj] nosimmetrik kvadrat matritsa sifatida aniqlaymiz, unda a i , j elementlar 1 ga teng, agar grafda { vi,V j } qirrasi bo lsa, ʻ ya’ni vi va vj qo shni bo lsa, 0 ga teng, agar bunday qirra mavjud bo lmasa. ʻ ʻ ʻ Ta’rifdan kelib chiqadiki, har qanday i uchun ∑ j = 1n a i , j = d ( v i ) , har qanday j uchun ∑i=1 n ai,j=d(vj) va ∑ i = 1n ∑ j = 1n a i , j = 2 m , ya’ni qo shnilik matritsasining har qanday qatori yoki ʻ ustunidagi birlar soni grafning tegishli vertikal darajasiga teng va ularning umumiy soni uning qirralarining ikki baravariga teng. Misol sifatida –rasmda berilgan G grafning A qo shnilik matritsasini ʻ deg v i darajalar ketma-ketligini yozamiz. Yo naltirilmagan grafda qo shnilik matritsasi ʻ ʻ Yo naltirilgan grafda qo shnilik matritsasiʻ ʻ Qo shnilik matritsasini amalga oshirish uchun massivlar massivi qo llaniladi: vektorlar ʻ ʻ vektori (vector<vektor<bool>>) yoki kaliti uchlar soni, qiymati esa <bool> vektori. Agar grafni kengaytirish kerak bo lmasa, u holda vektorni ʻ array (massiv) bilan almashtirish kerak. 10-mustaqil ish Mavzu: Kombinatorika elementlarini dasturlash va algoritmlashtirish Reja: 1 Kirish 2. Kombinatorik masalalar va tartiblangan to‘plamlar 3. Kombinatorik masalalar va ularni yechishda qo‘llaniladigan qoidalar 4 Takrorsiz o‘rin almashtirishlar 5. Takrorsiz o‘rinlashtirishlar 6. Takrorlanuvchi o‘rinlashtirishlar Ehtimollar nazariyasi va matematik statistika – bir-birga uzviy bog‘liq matematik fanlar hisoblanadi. Hozirgi paytda bu sohalar bo‘yicha olingan bilimlar turli kasb mutaxassislariga juda ham ham zurur. O‘z faoliyatini maqsadini aniqlay olish va unga erishish uchun shaxdam qadamlar qo‘yish – kompetentli, raqobatbardosh qobiliyatli mutaxassisning xarakterli xususiyati, ehtimollar nazariyasi va matematik statistika esa har qanday fanga qaraganda ko‘proq shaxsning ijobiy o‘zgarishlari uchun yordam beradi. Ommaviy tasodifiy jarayonlar qonuniyatlarini (ehtimollar nazariyasi fani) va kuzatishlar natijalarini qayta ishlash muhim usul va yo‘llarini (matematik statistika o‘rganadigan) bilish har bir kasbdagi mutaxassis uchun amaliy masalalarni yechishda qo‘l keladi. Ehtimollar nazariyasi va matematik statistikani o‘rganishni esa avvalo kombinatorika asoslari bilan tanishmasdan mumkin bo‘lmaydi. «Kombinatorika» atamasi matematikaga Leybnits tomonidan kiritilgan bo‘lib, uni 1666 yilda chop etilgan «Kombinatorika san’ati to‘g‘risida mulohazalar» nomli kitobida birinchi marta qo‘llagan edi. Hozirgi vaqtda kombinatorik usullar informatsiya nazariyasi muammolarini, chiziqli dasturlash masalalarini yechishda, transport masalalarini yechish uchun va h.k.larni hal qilishda keng qo‘llanilmoqda. Kombinatorik masalalar nafaqat matematika go‘zalligini ko‘rsatishga, balki amaliy matematik masalarni yechishda yangi kompyuter texnoogiyalarining imkoniyatlarini ko‘rsatishga imkon beradi. Diskret matematikaning masalalaridan hisoblangan kombinatorik masalalar ko‘pincha ob’ektlarning turli kombinatorik konfiguratsiyalarini tanlashga va ular orasidan u yoki bu masala shartigav nuqtai nazaridan eng yaxshisini tanlashga olib kelinadi. Shuning uchun keng tarqalgan kombinatorik konfiguratsiyalarni hosil qilish algoritmlarini bilish masalani butunlay muvaffaqiyatli yechishning zarur sharti hisoblanadi. Uslubiy qo‘llanmada matematika o‘qitishda kombinatorika elementlarini o‘rganish samaradorligini oshirish maqsadida kombinatorika fanining asosiy 5 tushunchalari, kombinatorika elementlarini o‘rganish xususiyatlari, o‘qitish jarayonida kombinatorika elementlarini o‘rgatish bilan birga o‘quvchilarning ijodiy faolligini oshirish bo‘yicha uslubiy tavsiyalar bayon etilgan Kombinatorik masalalar va tartiblangan to‘plamlar. 1. Kombinatorika predmeti va paydo bo‘lish tarixi. Matematikaning kombinatorik tahlil, kombinatorik matematika, birlashmalar nazariyasi, qisqacha, kombinatorika deb ataluvchi bo‘limida chekli yoki muayyan ma‘noda cheklilik shartini qanoatlantiruvchi to‘plamni (bu to‘plamning elementlari qanday bo‘lishining ahamiyati yo‘q: harflar, sonlar, hodisalar, qandaydir predmetlar va boshqalar) qismlarga ajratish, ularni o‘rinlash va o‘zaro joylash ya‘ni, kombinatsiyalar, kombinatorik tuzilmalar bilan bog‘liq masalalar o‘rganiladi. Hozirgi davrda kombinatorikaga oid ma‘lumotlar inson faoliyatining turli sohalarida qo‘llanilmoqda. Jumladan, matematika, kimyo, fizika, biologiya, lingvistika, axborot texnologiyalari va boshqa sohalar bilan ish ko‘ruvchi mutaxassislar kombinatorikaning xilma-xil masalalariga duch keladilar. To‘plamlar nazariyasi iboralari bilan aytganda, kombinatorikada kortejlar va to‘plamlar, ularning birlashmalari va kesishmalari hamda kortejlar va qism to‘plamlarni turli usullar bilan tartiblash masalalari qaraladi. To‘plam yoki kortej elementlarining berilgan xossaga ega konfiguratsiyasi bor yoki yo‘qligini tekshirish, bor bo‘lsa, ularni tuzish va sonini topish usullarini o‘rganish hamda 7 bu usullarni biror parametr bo‘yicha takomillashtirish kombinatorikaning asosiy masalalari hisoblanadi. Kombinatorikaning ba’zi elementlari eramizdan oldingi II asrda hindistonliklarga ma‘lum edi. Ular hozirgi vaqtda gruppalashlar deb ataluvchi kombinatorik tushunchadan foydalanishgan. Eramizning XII asrida Bxaskara Acharya o‘zining ilmiy tadqiqotlarida gruppalash va o‘rin almashtirishlarni qo‘llagan. Tarixiy ma‘lumotlarga ko‘ra, hindistonlik olimlar kombinatorika elementlaridan, jumladan, birlashmalardan foydalanib, she‘riy asarlar tarkibiy tuzilishining mukammalligini tahlil qilishga uringanlar. Umuman olganda, kombinatorikaning dastlabki rivoji qimor o‘yinlarini tahlil qilish bilan bog‘liq. Ba‘zi atoqli matematiklar, masalan, fransuz matematigi B.Paskal (1623-1662), sveytasriyalik matematik Ya.Bernulli (1654- 1705), L.Eyler (1707-1783), rus matematigi P.L.Chebishev (1821-1894) turli o‘yinlarda (tanga tashlash, soqqa tashlash, qarta o‘yinlari va shu kabilarda) ilmiy jihatdan asoslangan qarorlar qabul qilishda kombinatorikani qo‘llashgan 2. Kombinatorik masalalar va ularni yechishda qo‘llaniladigan qoidalar . Ikkita chekli to‘plamning Dekart ko‘paytmasidagi juftliklarni hisoblash qoidasi va uni to‘plamlar n ta bo‘lgan hol uchun umumlashtirish kombinatorik masalalar deb ataluvchi masalalarni yechishda keng qo‘llaniladi. Kombinatorik masalalar – bu shunday masalalarki, ular chekli to‘plamlar elementlaridan turli-tuman kombinatsiya (birlashma) larning ba’zi qoidalari bo‘yicha tuziladi. Jumladan, “4, 5, 6 raqamlardan foydalanib, mumkin bo‘lgan barcha ikki xonali sonlarni shunday yozingki, sonning yozuvida ayni bir raqam takrorlanmasin” degan masalada 4, 5, 6 raqamlar bilan bajariladigan turli kombinatsiyalarni, bu kombinatsiyalarda raqamlar takrorlanmasligi shartida ko‘rib chiqish talab etiladi. Hayotda ham kombinatorik masalalar ko‘plab uchraydi, bunda ob’yektlarning biror to‘plamidan uning qism to‘plamlarini tanlash, to‘plam elementlarini biron bir tartibda joylashtirish va hokazolar qaraladi. Masalan, fermer o‘z ishchilariga turli ishlarni bo‘lib berishi, katta jamoa ichidan delegatlar tanlash, shaxmat o‘yinida turli yurishlar seriyasidan eng ma’qulini tanlash kombinatorik masalalardan iboratdir. Ko‘plab kombinatorik masalalarni yechishda qo‘shish va ko‘paytirish qoidalari qo‘l keladi: a) qo‘shish qoidasi: agar X to‘plam m elementli, Y to‘plam esa n elementli bo‘lsa va ular o‘zaro kesishmasa, X  Y to‘plamning elementlari soni n  m ga teng, ya’ni agar X  Y   bo‘lsa, n(X  Y)  n(X)  n(Y) bo‘ladi. Umuman ixtiyoriy ikki X va Y to‘plamlar uchun n(X  Y)  n(X)  n(Y)  n(X  Y) o‘rinli bo‘ladi. b) ko‘paytirish qoidasi: agar X to‘plam m elementga, Y to‘plam n elementga ega bo‘lsa, u holda X  Y to‘plam (Dekart ko‘paytma) m  n elementga ega bo‘ladi. Haqiqatdan, { , ,..., }, 1 2 m X  x x x { , ,..., } 1 2 n Y  y y y bo‘lsa, X  Y to‘plam ushbu mumkin bo‘lgan barcha juftliklardan tashkil topadi: ( , ), 1 1 x y ( , ),..., 1 2 x y ( , ) 1 n x y ( , ), 2 1 x y ( , ),..., 2 2 x y ( , ) 2 n x y …………………………. 10 ( , ), 1 x y m ( , ),..., 2 x y m ( , ) m n x y Ko‘rinib turibdiki, bu juftliklar soni m  n ga teng. Buni qisqacha n(X  Y)  n(X )  n(Y) ko‘rinishda ham yozish mumkin. Umuman, n ta n x , x ,...,x 1 2 to‘plamlar berilgan bo‘lsa, u holda ( .... ) ( ) ( ) .... ( ) 1 2 n 1 2 n n x  x   x  n x  n x   n x tenglik o‘rinli bo‘ladi 3. Takrorsiz o‘rin almashtirishlar . Agar chekli X to‘plamning elementlari qandaydir yo‘l bilan raqamlangan bo‘lsa, uni tartiblangan to‘plam deymiz: { , ,..., }. 1 2 n X  x x x Kortej tushunchasidan farqli o‘laroq tartiblangan to‘plam elemetlari orasida o‘zaro tenglari bo‘lmaydi. Masalan, (2,3,2,4,5) kortej tartiblangan to‘plam emas, (2,3,4,5) esa tartiblangan to‘plam bo‘ladi. Bitta to‘plamni turlicha tartiblash mumkin. m A B C a b 1 2 3 11 elementli X to‘plamni necha xil usul bilan tartiblash mumkin degan masalani qaraymiz. Har bir tartiblash quyidagicha amalga oshiriladi. To‘plamning qaysi bir elementini 1-nomer bilan, qaysi birini 2-nomer bilan va hokazo qaysi bir elementini m nomer bilan belgilaymiz. Agar birinchi element tanlangan bo‘lsa, ikkinchi elementni tanlash (m–1) ta elementning ichidan olinadi. Demak, birinchi element m usul bilan, ikkinchisi esa (m–1) usul bilan tanlanadi. Uchinchi element (m–2) usul bilan va hokazo oxirgi element m-o‘rinni egallaydi. Masalan, {5,6,7} elementli to‘plam quyidagicha tartiblanadi 567, 657, 756 – birinchi element 3 usul bilan olindi. 657, 756 – ikkinchi element 2 usul bilan tanlandi. Oxirgi tartiblash 765 bo‘ladi. Umumiy holda ko‘paytirish qoidasiga asosan tartiblash usulining umumiy soni P m(m 1)...1 m! m    ga teng bo‘ladi. Bunday tartiblash m elementdan takrorlanmaydigan o‘rin almashtirish deyiladi. Bunda har bir tartiblangan to‘plamning elementlari turlicha bo‘ladi. 4. Takrorsiz o‘rinlashtirishlar . Endi m elementli X to‘plam elementlaridan nechta k elementli tartiblangan to‘plamlar tuzish mumkin degan masalani qaraymiz. Bu masalaning yuqoridagi masaladan farqi shundaki, bu yerda k elementli tartiblangan to‘plamni tuzish k ta elementni olish bilan tugallanadi. Bunday tartiblangan to‘plamlarning sonini topish uchun k ta m, m–1, m–2, …, m–k+1 sonlarni ko‘paytirish yetarli (chunki {m, m–1, m–2,…,m–k+1} to‘plamda k ta element mavjud). Shunday qilib, X to‘plamdagi k elementli tartiblangan to‘plamlar soni A  m(m  1)(m  2)... (m  k  1) n m ga teng bo‘ladi. Bunday tartiblangan to‘plamlarni m elementdan k tadan takrorlanmaydigan o‘rinlashtirishlar deyiladi. n Am ning ifodasini 1  2...(m  k) ga ko‘paytirib va bo‘lib, uning ko‘rinishini o‘zgartirish mumkin: ( )! ! 1 2...( ) ( 1)( 2)...( 1)( )...2 1 m k m m k m m m m k m k A k m            12 Bunda A P m! m m m   bo‘ladi, bu yerda 0!=1 deb olinadi. 5. Takrorlanuvchi o‘rinlashtirishlar . Bu yerda quyidagi masala qaraladi: m elementli X to‘plamdan nechta uzunligi k ga teng bo‘lgan kortejlar tuzish mumkin. Bu masalani hal qilish uchun X  X  ...  X dan iborat k ta ko‘paytuvchiga ega bo‘lgan Dekart ko‘paytmadagi kortejlar sonini topish yetarli. Bunda k m k n(X  X  ...  X)  n(X)n(X)...n(X)  m  m....m  m  A Demak, m elementli X to‘plamdan tuzilgan uzunligi k ga teng bo‘lgan kortejlar soni k k Am  m ga teng. m elementli X to‘plam elementlaridan tuzilgan uzunligi k ga teng bo‘lgan kortej, m elementdan k tadan tuzilgan takrorlanadigan o‘rinlashtirish deyiladi.

ALGORITM VA MA’LUMOTLAR STRUKTURASI fanidan yozgan Tekshirdi:_____________________________ MUSTAQIL ISHI

1-mustaqil ish Mavzu: Ma’lumotlar tuzilmasi,tuzilmalar ustida bajariladigan amallar. Dasturlash texnologiyalari. Reja: 1.Ma’lumotlar tuzilmasi 2. Ma’lumotlar tuzilmalari ustida quyidagi amallarni bajarish mumkin: Ma’lumotlar tuzilmasi bu xotirada tashkil etiladigan elementlar yig’indisi bo’lib, ular ustida dastur yordamida amallar bajariladi. Ma’lumotlar tuzilmasi – bu bironta toifaga tegishli bo’lgan va o’zaro ma’lum munosabatga ega bo’lgan elementlar to’plamiga aytiladi. Ma’lumot – bironta qiymat yoki qiymatlar to’plami hisoblanadi.Misol uchun bu bironta eksperiment natijalari, yoki talabalarning imtixon ballari bo’lishi mumkin. Ma’lumotlar tuzilmasi elementi – bu qiymatlar to’plamining bir bo’lagi hisoblanadi. Tuzilma elementi – qiymatlar jamlanmasi bo’lib, misol uchun talabalarning ismi, sharifi, yoshi har bir fandan olgan bahosi va x.k. larni keltirish mumkin. Elementlar 2 taga bo’linishi mumkin:  Element sifatida ma’lumotlar guruhi olib qaraladi. Bunda e;lementlar yana qism bo’lak;arga bo’linishi mumkin. Masalan, ota-onalar maydoni talabalarning ota va onalari xaqida ma’lumot saqlaydigan alohida maydonlardan tashkil topadi.  Elementar, ya’ni bo’linmas, bunda element qism bo’laklarga ajratilmaydi. Ob’ekt – bu xususiyatlar va attributlariga ega bo’lgan va bu xususiyatlarga qiymat qabul qilishi mumkin bo’lgan tuzilma hisoblanadi. Masalan, talaba bu ob’ekt deb qaralishi mumkin tuzilma. Maydon – bu ob’ektlarning attributlari yoki xususiyatlarini ifodalovchi tushuncha bo’lib, sonli yoki son bo’lmagan qiymatlarni o’zlashtirishi mumkin. Yozuv – bu bironta ob’ektga tegishli turli toifadagi maydonlar to’plamidir. Fayl - bu bir-biriga bog’liq bo’lgan yozuvlar to’plamidir. Masalan, barcha talabalar xaqidagi yozuvlarni o’z ichiga olishi mumkin, Kalit – bu yozuvdagi maydon bo’lib, aynan shu yozuvni boshqa yozuvlardan ajratib turishga xizmat qiladi , uning qiymati boshqa yozuvlarda takrorlanmas hisoblanadi. Ba’zida bittadan ko’p maydonlar qiymatlari elementlararo betakror bo’lishi mumkin va bunga karrali kalit deyiladi. Ko’pincha asosiy kalit hisoblanadigan bitta maydon ma’lumoti ishlatiladi va u boshlang’ich kalit deyiladi, qolganlari esa alternativ kalit deyiladi. Ba’zida esa yozuvlaning yagona qiymatlatli kalit maydonni yo’qligi sababli kalit sifatida bir nechta maydonlar olinadi va ularga tarkibli kalit deyiladi. Eng yomon

holatda, ba’zan shunaqa bo’lishi mumkinki, bironta maydon kalit bo’la olmasa, xar bit elementga qo’shimcha, qiymati yagona bo’lgan kalit maydon kiritiladi. Ma’lumotlar tuzilmasi Ma’lumotlar turli yo’lar asosida tashkil etilishi mumkin, mantiqiy yoki matematik modelni tashkil etilishi ma’lumotlar tuzilmasi deyiladi. Konkret bir ma’lumotlar tuzilmasini tanlash quyidagilarga bog’liq:  Real voqe’likda elementlararo munosabatni yaqqol ifodalay olishi kerak;  U shunday soda tuzilishi kerakki, zarur bo’lganda ustida samarali amal bajarish mumkin bo’lsin. Ma’lumotlar tuzilmasini o’rganish quyidagilardan iborat:  Tuzilmani mantiqiy ifodalash;  Tuzilmani fiizik amalga oshirish ;  Tuzilmani sifatiy taxlili, ya’ni elementlarni saqlash uchun qancha xotira xajmi sarflanishini aniqlash (xotira sarfi) va qayta ishlashga ketadigan vaqtni (vaqt sarfi) xisoblash nazarda tutiladi. Ma’lumotlar tuzilmalari ustida quyidagi amallarni bajarish mumkin: 1. Ko’rikdan o’tkazish (traversing) - tuzilma elementlariga 1 martadan murojaat qilish amali. 2. Kiritish – tuzilmaga yangi element kiritish amali. 3. O’chirish – tuzlmadan bironta elementni o’chirish amali. Bunda element shunday o’chirilishi kerakki, qolgan elementlar stabil holatda bo’lishi kerak, ya’ni ayrim tuzilmalarda nosozlik sezilishi kerak emas. 4. Qidirish – tuzilmadan bironta elementni joylashgan o’rnini aniqlash amali. 5. Saralash – elementlarni ma’lum bir tartibda joylashtirish amali. 6. Birlashtirish (merging) – ikkita tuzilmani birlashtirish amali. Ma’lumotlar tuzilmasi (MT) – informatsion ob’ektning umumiy xossasi bo‘lib, mazkur xossa bilan biror bir dastur o‘zaro aloqador bo‘ladi. Ushbu umumiy xossa quyidagilar orqali tavsiflanadi: 1) mazkur tuzilmaning mumkin (qabul qilishi mumkin) bo‘lgan qiymatlari to‘plami; 2) mumkin bo‘lgan amallar (operatsiyalar) majmuasi; 3) tashkil etilganlik tasnifi.

2-mustaqil ish Mavzu: Algoritmlarni murakkablik darajalasining tahlili, murak-kablik darajasini baholash usullari. Reja: 1 Algoritmning asosiy xossalari 2 Algoritmlarning murakkabligi . 3 Murakkablikni baholash 4 Algoritmlar murakkabligining o sish tartibiʻ 1-ta’rif. Algoritm - bu ma’lum bir tilda berilgan, mumkin bo lgan dastlabki ʻ ma’lumotlar sinfi uchun masalani hal qilish uchun mumkin bo lgan elementar amallarning ʻ cheklangan ketma-ketligi. Algoritmning asosiy xossalari haqida quyidagilarni ta’kidlash mumkin: 1-xossa . Diskretlilik, ya’ni algoritmni chekli sondagi oddiy ko rsatmalar ketma- ʻ ketligi shaklida ifodalash mumkin. 2-xossa. Tushunarlilik, ya’ni ijrochiga tavsiya etilayotgan ko rsatmalar uning uchun ʻ tushunarli bo lishi shart, aks holda ijrochi oddiy amalni ham bajara olmay qolishi mumkin. ʻ Har bir ijrochining bajara olishi mumkin bo lgan ko rsatmalar tizimi mavjud. ʻ ʻ 3-xossa. Aniqlik, ya’ni ijrochiga berilayotgan ko rsatmalar aniq mazmunda bo lishi ʻ ʻ lozim hamda faqat algoritmda ko rsatilgan tartibda bajarilishi shart. ʻ 4-xossa . Ommaviylik, ya’ni har bir algoritm mazmuniga ko ra bir turdagi ʻ masalalarning barchasi uchun yaroqli bo lishi lozim ʻ . Masalan, ikki oddiy kasr umumiy maxrajini topish algoritmi har qanday kasrlar umumiy maxrajini topish uchun ishlatiladi. 5-xossa. Natijaviylik, ya’ni har bir algoritm chekli sondagi qadamlardan so ng ʻ albatta natija berishi lozim . Bu xossalar mohiyatini o rganish va konkret algoritmlar uchun qarab chiqish ʻ talabalarning xossalar mazmunini bilib olishlariga yordam beradi. Algoritmlar berilishi va ifodalanishiga qarab: chiziqli, tarmoqlanuvchi va takrorlanuvchi turlarga bo linadi. ʻ Algoritmlarning murakkabligi . Hisoblash muammolari cheklangan xotira resurslaridan foydalangan holda oqilona vaqt ichida yechilishi kerak. Bu algoritmning vaqt va fazoviy murakkabligi tushunchasiga olib keladi. Qoida tariqasida, algoritm turli vaqtlarni bajarishi mumkin bo lgan turli xil amallarni o z ichiga oladi. Algoritmlarni baholash uchun ʻ ʻ ko pgina mezonlar mavjud. Odatda kirituvchi berilganlarni ko payishida masalani yechish ʻ ʻ uchun kerak bo ladigan vaqt va xotira hajmlarini o sish tartibini aniqlash muammosi ʻ ʻ qo yiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini aniqlovchi ʻ qandaydir sonni bog lash zarur. Bunday son masalaning kattaligi deb qabul qilinadi. ʻ Masalan, ikkita matritsani ko paytirish masalasining o lchami bo lib, matritsalar kattaligig ʻ ʻ ʻ xizmat qilishi mumkin. Graflar haqidagi masalada o lcham sifatida graf ʻ uchlarining soni bo lishi mumkin. ʻ Algoritm sarflanayotgan vaqt masalaning o lchami funksiyasi sifatida ʻ algoritmni vaqt bo yicha qiyinligi deb nomlanadi. Bunday funksiyaga masalaning kattaligi ʻ oshganda limit ostidagi o zgarish asimptotik qiyinlik deb aytiladi. ʻ Murakkablikni baholash . Algoritmlarning murakkabligi odatda bajarilish vaqti yoki ishlatilgan xotira bo yicha baholanadi. Ikkala holatda ham, murakkablik kiritilgan ʻ ma’lumotlarning hajmiga bog liq: 100 ta elementdan iborat massivi xuddi shunga ʻ o xshash 1000 ta elementdan iborat massivga qaraganda tezroq qayta ishlanadi. Shu bilan ʻ birga, aniq vaqt bilan bir necha kishi qiziqadi: bu protsessorgabog liq, ma’lumotlar turi, ʻ

dasturlash tili va boshqa ko plab parametrlarga ham bog liq. Faqatgina ʻ ʻ asimptotik murakkablik muhim, ya’ni kirish ma’lumotlarining kattaligi cheksizlikka intilayotgandagi murakkablik. Masalan, ba’zi bir algoritmga kirish ma’lumotlarining n ta elementlarini qayta ishlash uchun 4n 3 + 7n ta shartli amallarni bajarish kerak. n ning ortishi bilan ishning umumiy davomiyligi n ning kubi uni 4 ga ko paytirgandan yoki 7n ni qo shgandan ko ra ʻ ʻ ʻ ko proq ta’sir qiladi. Ushbu algoritmning vaqt murakkabligi O(n ʻ 3 ), ya’ni u kubik bilan kiritilgan ma’lumotlarning hajmiga bog liq bo ladi. Bosh harf ʻ ʻ O dan foydalanish matematikadan kelib chiqadi, bu yerda ushbu belgi funksiyalarning asimptotik harakatlarini taqqoslash uchun ishlatiladi. Rasmiy ravishda O(f(n)) algoritmning ishlash vaqti (yoki egallagan xotira miqdori), kiritilgan ma’lumotlarning hajmiga qarab, f(n) ga ko paytiriladigan ba’zi konstantalardan tezroq emasligini anglatadi. ʻ O (n) - chiziqli murakkablik. Bunday murakkablik, masalan, saralanmagan massivdagi eng katta elementni topish algoritmiga ega. Qaysi biri maksimal ekanligini aniqlash uchun massivning barcha n elementlaridan o tishimiz kerak bo ladi. ʻ ʻ O (log n) - logaritmik murakkablik . Eng oddiy misol - ikkilik qidirish. Agar massiv saralangan bo lsa, uni ʻ yarmiga bo lish orqali ma’lum bir qiymatga ega ekanligini tekshirishimiz mumkin. O rta ʻ ʻ elementni tekshirib ko ramiz, agar u kattaroq bo lsa, unda massivning ikkinchi yarmini ʻ ʻ tashlab yuboramiz. Agar kichikroq bo lsa, unda aksincha - biz dastlabki yarmini ʻ tashlaymiz va shu tarzda ikkiga bo linishni davom ettiramiz, natijada (logn) elementlarini ʻ tekshiramiz. O (n 2 ) - kvadratik murakkablik. Bunday murakkablik, masalan, element qo shilishi natijasida yangi saralash algoritmiga ega. Kanonik dasturda ʻ bu ikkita ichki sikldan iborat: biri butun massivni bosib o tish, ikkinchisi esa allaqachon ʻ ajratilgan qismdan keyingi element uchun joy topish. Shunday qilib, amallar soni n*n, ya’ni n 2 kabi massiv o lchamiga bog liq bo ladi. ʻ ʻ ʻ Murakkablikning boshqa ko rinishlari ʻ ham mavjud, ammo ularning barchasi bir xil prinsipga asoslanadi. Algoritmning ishlash vaqti umuman kiritilgan ma’lumotlarning hajmiga bog liq emasligi ham sodir bo ladi. Bu ʻ ʻ holda murakkablik O(1) bilan belgilanadi. Masalan, massivning uchinchi elementi qiymatini aniqlash uchun elementlarni eslab qolishingiz yoki ular orqali bir necha bor o tishingiz shart emas. Siz har doimma’lumotlarni kiritish oqimidagi uchinchi elementni ʻ kutishingiz kerak va bu esa siz uchun natija bo ladi, bu har qanday ma’lumot uchun ʻ hisoblash uchun bir xil vaqtni oladi. Baholash muhim bo lgan taqdirda xotiradan xuddi ʻ shu tarzda amalga oshiriladi. Biroq, algoritmlar kirish ma’lumotlarining hajmi boshqalarga nisbatan kattalashganda sezilarli darajada ko proq xotiradan foydalanishi mumkin, ammo ʻ ular tezroq ishlaydi va aksincha. Bu hozirgi sharoit va talablar asosida muammolarni hal qilishning eng yaxshi usullarini tanlashga yordam beradi. Algoritmlar murakkabligining o sish tartibi ʻ Murakkablikning o sish tartibi ʻ (yoki aksiomatik murakkablik) katta kirish hajmi uchun algoritmning murakkablik funksiyasining taxminiy xatti-harakatini tavsiflaydi. Bundan kelib chiqadiki, vaqt murakkabligini baholashda elementar amallarni ko rib chiqishning ʻ hojati yo q, algoritm qadamlarini ko rib chiqish kifoya. ʻ ʻ Algoritm qadami – bu ketma-ket joylashtirilgan elementar amallar to plami, uning ʻ bajarilish vaqti kirish qadamiga bog liq emas, ya’ni yuqoridan qandaydir doimiy bilan ʻ chegaralangan.

O'xshashlar

DOIMIY MA’LUMOTLAR STRUKTURASI
Algoritm turlari
Django frameworkida ma’lumotlar bazasi hamda ilova strukturasi bilan ishlash,
Nazorat tizimining strukturasi va ijtimoiy regulyatorlar
Qattiq jismlarning kristall strukturasi