logo
  1. Bosh sahifa
  2. Referatlar
  3. Umumiy
  4. DINAMIK DASTURLASH METODLARINI

DINAMIK DASTURLASH METODLARINI

Yuklangan vaqt:

08.08.2023

Ko'chirishlar soni:

0

Hajmi:

2259 KB
Ko'chirib olish
“ DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI ” MAVZUSIDA TAYYORLAGAN 1KURS ISHI Mundarija I Kirish II Asosiy qism ……..………………………………………………..4 2.1. Dinamik dasturlash haqida umumiy tushunchalar……….…......4 2.2.Dinamik dasturlashda optimallik tamoyili……………………....8 2.3. C++ dasaturlash tilida dinamik ma’lumotlar tuzilmasi……..….24 III Xulosa………………………………………………...…………39 IV Foydalanilgan adabiyotlar………………………………….……40 2 3 Kirish Vatanimizda, erkin va farovon hayot barpo etish, rivojlangan mamlakatlar qatoridan o’rin olish, demokratik jamiyat qurish kabi ezgu maqsadlarni qo’yildi. Bu esa kelajagimizni yaqqol tasavvur etish, jamiyatimizning ijtimoiy-ma‘naviy poydevorini mustahkamlash ehtiyojini tug’diradi. Demak, galdagi eng asosiy vazifa: yosh avlodni vatan ravnaqi, yurt tinchligi, xalq farovonligi kabi olijanob tuyg’ular ruhida tarbiyalash, yuksak fazilatlarga ega, ezgu g’oyalar bilan qurollangan komil insonlarni voyaga etkazish, jahon andozalariga mos, kuchli bilimli, raqobatbardosh kadrlar tayyorlashdir. O’zbekistonning iqtisodiy va ijtimoiy sohalarda yuqori natijalarga erishishi, jahon iqtisodiy tizimida to’laqonli sheriklik o’rnini egallay borishi, inson faoliyatining barcha jabhalarida zamonaviy axborot texnologiyalaridan yuqori darajada foydalanishning ko’lamlari qanday bo’lishiga hamda bu texnologiyalar ijtimoiy mehnat samaradorligini oshishida qanday rol o’ynashiga bog’liq. Keyingi yillarda mamlakatimiz ilm-fani ham axborotlashtirishning nazariy asoslariga katta hissa qo’shib kelmoqda, shu bilan birgalikda, hodisalar, jarayonlarni yagona axborot asosida tadqiq etishning ilmiy yo’nalishlarini tahlil va sintez qilish natijasi bo’lgan fan-informatikaning vujudga kelishiga boshlang’ich poydevor qo’yildi. Axborot, energiya, vazn, bo’shliq va vaqtni bir butun holda batafsil o’rganish hozirgi vaqtda inson hayotining barcha jabhalarida muhim axamiyatga ega bo’lib qolmoqda. 4 Dinamik dasturlash haqida umumiy tushunchalar Dinamik dasturlash tushunchasi juda keng qamrovli tushuncha bolib,Bu tushunchao’z ichiga ko’plab yo’nalishlar va sohalarni qamrab oladi. Dasturchilar butunlay boshqacha vazifalarga ega bo'lishi mumkin. Bir holatda, biror narsani chizish uchun faqat belgilash tilidan foydalanishingiz kerak, ikkinchisida protsessor samarali ishlashi uchun assembler orqali ko'rsatmalar yozish kerak.Ammo bu assotsiatsiya barcha odamlar uchun ishlaydi - dasturchilar algoritmlarni ishlab chiqadilar. Tasavvur qilaylik, bizga yangi vazifa qo’yildi, uning maqsadi va cheklovlari bor. Har qanday vazifada bo'lgani kabi, u ham ma'lumotlar tuzilmalarini va tizimning boshqa qismlariga bog'liqlikni o'z ichiga oladi bir vaqtning o'zida siz ushbu vazifa uchun ishlash muhim. Bunidarhol tushunish mumkin. Masalan, avval muammoni hal qilgandan keyin yechim sekin ekanligini payqashimiz mumkin .Bunday holatda hisob-kitob natijalari kamroq vaqt ichida olinishi uchun muammoni qanday hal qilishni kerak.Dasturlash nuqtayi nazaridan dinamik dasturlash atamasi biz yaratayotgan dasturmizga ma’lumotlarni kirtganimizdak keyin vaqt o’tishi bilan avvalgi kiritgan ma’lumotlarimizning bizga keragi bo’lmasligi mumkin.Shunda bizga malumotlarni kiritish va chiqarish jarayonida eski ma’lumotlarni o’chirish kerak bo’ladi. Dinamik dasturga misol C++ dasturlash tilida #include<iostream> using namespace std; int main(){ int m; cout << "m="; cin >> m; //massiv elementlari soni; float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik massiv; 5 for (int j = 0; j < m; j++) cin >> b[j]; // bir o'lchamli Massivni to'ldirish cout<<" bir o'lchamli dinamik massiv"<<endl; for (int j = 0; j < m; j++) cout<<b[j]<<" "; delete [] b;//xotira bo'shatildi cout<<"\n xotira bo'shatildi"; return 0; } Dinamik dastur Java dasturlash tilida class Array { private int arr[]; private int count; public Array(int length) { arr = new int[length]; } public void printArray() { for (int i = 0; i < count; i++) System.out.print(arr[i] + " "); } } public void insert(int element) {if (arr.length == count) { int newArr[] = new int[2 * count]; for (int i = 0; i < count; i++) { newArr[i] = arr[i]; } arr = newArr; 6 } arr[count++] = element; } } public class GFG { public static void main(String[] args) {Array numbers = new Array(3); numbers.insert(10); numbers.insert(30); numbers.insert(40); numbers.insert(50); numbers.printArray(); }} Ammo kirish ma'lumotlarining soni va qiymatining oshishi bilan yechim vaqti sezilarli darajada oshib borishini tushunishimiz mukin.Bunda bizga Dinamik dasturlash haqida o’ylashimiz kerak bo’ladi. Algoritmni tavsiflashdan oldin ikkita tushunchani kiritamiz - xotira va jadval. 7 Dinamik dasturlashda optimallik tamoyili Dinamik dasturlash ham matematematik optimallashtrish usuli va kompyuter dasturlash usuli. Usul Richard Bellman tomonidan ishlab chiqilgan 1950 yillarda , aerokosmik muhandislik ga iqtisodiyot va ko'plab sohalarda dasturiy yechimlarni yaratdi. Ikkala kontekstda u murakkab muammoni oddiy kichik muammolarga ajratish orqali soddalashtirishga ishora qiladi rekursiv uslubi. Qaror bilan bog'liq ba'zi muammolarni shu tarzda ajratib bo'lmaydigan bo'lsa-da, bir necha vaqtni o'z ichiga olgan qarorlar ko'pincha rekursiv ravishda ajralib chiqadi. Xuddi shu tarzda, informatika fanida, agar muammoni kichik muammolarga ajratib, so'ngra kichik muammolarning optimal echimlarini rekursiv ravishda topish orqali optimal tarzda echimlarni olish mumkin bo’ladi. Agar kichik masalalarni rekursiv ravishda kattaroq masalalar ichiga joylashtirish mumkin bo'lsa, shuning uchun dinamik dasturlash usullari qo'llanilishi mumkin bo'lsa, unda kattaroq masalaning qiymati bilan kichik muammolarning qiymatlari o'rtasida bog'liqlik mavjud. Optimallashtirish bo'yicha adabiyotda bu munosabatlar Bellman tenglamalarida keltrilgan. Kompyuter dasturlash usuli Dinamik dasturlash uchun muammo yuzaga kelishi kerak bo'lgan ikkita asosiy xususiyat mavjud: maqbul tuzulish muammolar va bir birini qoplaydigan kichik jarayonlar. Agar muammoni optimal echimlarni birlashtirib hal qilish mumkin bo'lsa bir-birining ustiga chiqmaydigan kichik muammolar, strategiya "deb nomlangan “bo’lib tashla va hukumronlik qil”o'rniga.Shuning uchun birlashtrish va teskor tartiblash dinamik dasturlash muammolari deb tasniflanmagan. Optimal pastki tuzilish ma'lum bir optimallashtirish muammosining echimini uning quyi masalalariga optimal echimlarni birlashtirish orqali olish mumkinligini anglatadi. Bunday maqbul pastki tuzilmalar odatda rekursiya . Masalan, grafik berilgan G = (V, E) , eng qisqa yo'l p tepadan siz tepaga v maqbul pastki tuzilishni namoyish etadi: har qanday oraliq tepalikni oling w bu eng qisqa yo'lda p . 8 Agar p haqiqatan ham eng qisqa yo'l, keyin uni pastki yo'llarga bo'lish mumkin p 1 dan siz ga w va p 2 dan w ga v Shunday qilib, bular, albatta, mos keladigan tepalar orasidagi eng qisqa yo'llardir (tasvirlangan oddiy va kesilgan argument bo'yicha)Algoritmlarga kirish. Shunday qilib, rekursiv usulda eng qisqa yo'llarni topish uchun echimni osongina shakllantirish mumkin, bu esa Bellman- Ford algoritmi yoki Froyd-Uorshall algoritmi qiladi. Kichik masalalar kichik masalalar maydoni kichik bo'lishi kerakligini anglatadi, ya'ni har qanday rekursiv algoritm yangi kichik muammolarni yaratishdan ko'ra bir quyidagi ikki usuldan biri bilan erishish mumkin. Yuqoridan pastga yondashish. Bu har qanday muammoning rekursiv formulasidan to'g'ridan-to'g'ri tushish. Agar biron-bir muammoning echimi uning kichik muammolari echimi yordamida rekursiv tarzda tuzilishi mumkin bo'lsa va agar uning pastki muammolari bir-birining ustiga chiqsa, unda osonlikcha xotirada saqlab qolish yoki pastki muammolarning echimlarini jadvalda saqlash mumkin. Har doim yangi kichik masalani echishga urinayotganimizda, avval jadvalni allaqachon echilganligini tekshirib ko'ramiz. Agar echim yozib olingan bo'lsa, biz uni to'g'ridan-to'g'ri ishlatishimiz mumkin, aks holda kichik masalani echamiz va uning echimini jadvalga qo'shamiz. Pastdan yuqoriga qarab yondashuv. Agar muammoning echimini uning pastki muammolari nuqtai nazaridan retsursiv ravishda tuzgan bo'lsak, biz muammoni pastdan yuqoriga qarab qayta isloh qilishimiz mumkin: avval kichik muammolarni echishga urinib ko'ring va ularning echimlaridan foydalanish uchun kattaroq kichik muammolarni hal qilish. Bu, odatda, jadval shaklida, kichik kichik muammolarga echimlardan foydalangan holda, katta va kattaroq kichik muammolarga echimlarni yaratish orqali amalga oshiriladi. Masalan, F 41 va F 40 , ning qiymatlarini allaqachon bilsak biz F 42 ning qiymatini to'g'ridan-to'g'ri qiymatini hisoblashimiz mumkin . Dinamik dasturlashda optimal quyi tuzilma asl masalani yechish uchun kichikroq kichik muammolarning optimal yechimidan foydalanish mumkinligini bildiradi. Masalan, grafikdagi eng qisqa yo‘lni bir cho‘qqidan (s ni belgilang) ikkinchi cho‘qqiga (tni belgilang) quyidagicha topish mumkin: avval s ga tutashgan barcha 9 cho‘qqilardan t gacha bo‘lgan eng qisqa yo‘lni hisoblaymiz, so‘ngra ni hisobga olgan holda eng qisqa yo‘lni hisoblaymiz. s ni qo'shni cho'qqilar bilan bog'laydigan qirralarning og'irliklari, t ga eng yaxshi yo'lni tanlang (qaysi cho'qqidan o'tish yaxshiroq). Umuman olganda, biz quyidagi uchta qadamni bajarib, optimal quyi tuzilma bilan muammoni hal qilishimiz mumkin. Vazifani kichikroq kichik vazifalarga bo'lish.Xuddi shu uch bosqichli algoritmga amal qilgan holda rekursiv usulda kichik muammolarning optimal yechimini topish.Olingan kichik masalalar yechimidan foydalanib, dastlabki masala yechimini qurish. Voqealarning bunday rivojiga yo'l qo'ymaslik uchun biz allaqachon hal qilgan kichik muammolarning echimlarini saqlab qo'yamiz va bizga yana kichik muammoning echimi kerak bo'lganda, uni qayta hisoblash o'rniga, biz uni shunchaki xotiradan olib tashlaymiz. Bunday yondashuv memoizatsiya deb ataladi. Qo'shimcha optimallashtirishlar amalga oshirilishi mumkin - masalan, agar biz quyi vazifaga yechim kerak emasligiga ishonchimiz komil bo'lsa, biz uni xotiradan chiqarib tashlashimiz, boshqa ehtiyojlar uchun bo'shatishimiz yoki protsessor ishlamayotgan bo'lsa va biz bu yechimni bilamiz. Ba'zi hali hisoblanmagan kichik vazifalardan keyin bizga kerak bo'ladi, biz ularni oldindan hal qilishimiz mumkin. Yuqoridagilarni umumlashtirib, shuni aytishimiz mumkinki, dinamik dasturlash muammoning quyidagi xususiyatlaridan foydalanadi:bir-biriga moskeladigan kichik vazifalar;optimal quyi tuzilma;tez-tez duch keladigan kichik vazifalarning echimlarini yodlash qobiliyati. Dinamik dasturlash odatda muammolarni hal qilishda ikkita yondashuvni qo'llaydi:Yuqoridan pastga dinamik dasturlash: muammo kichikroq kichik muammolarga bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi. Yodlash allaqachon hal qilingan kichik vazifalarni hal qilish uchun ishlatiladi. Pastdan yuqoriga dinamik dasturlash: asl muammoni hal qilish uchun keyinchalik zarur bo'lgan barcha kichik vazifalar oldindan hisoblab chiqiladi va keyin asl muammoning echimini yaratish uchun ishlatiladi. Bu usul kerakli 10 stekning o'lchami va funksiya chaqiruvlari soni bo'yicha yuqoridan pastga dasturlashdan ko'ra yaxshiroqdir, lekin ba'zida kelajakda qaysi kichik muammolarni hal qilishimiz kerakligini oldindan aniqlash oson emas. Dinamik dasturlash muammolari uchun bosqichma-bosqich algoritm Bizda Z funksiyaning natijasidir.Jami Z (x) = y, bu erda x - kirish parametrlari, y - kirish parametrlari x bo'yicha masala yechimi.X ning kichik va izchil qiymatlari uchun muammoning yechimi qanday ishlashini ko'ring. Ya'ni, hisoblash miqdori kichik bo'lgan hollarda. "Qarang" deganda men tom ma'noda aytmoqchiman - barcha natijalarni (va ular qanday paydo bo'lganligini) yozing va barcha echimlarni o'z ko'zingiz bilan ko'rib chiqing. Misol uchun, agar siz x ning natural sonlarning qiymatlarini olishi mumkinligini bilsangiz, funktsiya natijalarini olamiz: Z (1) = y_1 Z (2) = y_2 Z (3) = y_3 Z (4) = y_4 Z (5) = y_5 Agar x qandaydir massiv bo'lsa, u holda Z funksiyasi turli xil kichik massivlar bilan orasidagi bog’liqlikni tekshiramiz: Z ([1, 2, 3]) = y1 Z ([4, 5]) = y2 Z ([1, 5, 4]) = y3 Bu yerda massiv elementlari talablarga javob berishi kerak (masalan, tabiiy yoki ijobiy va oqilona sizning aniq vazifangizga bog'liq).Va bu juda muhim, hisoblash natijalarida bog’liqlik mavjudligini tekshiramiz. Ya'ni, y_5 y_4 yoki y_2 ga bog'liq bo'lishi mumkin. Yoki y_3 ni hisoblashda olingan ma'lumotlardan y_5 ni hisoblashda foydalanish mumkin. Masalan, Fibonachchi raqamlarida F (5) F (3) 11 va F (4) ga bog'liq.Turli xil hisob-kitoblarning natijalari o'rtasida to'g'ridan-to'g'ri bog'liqlik bo'lmagan holatlar mavjud. Agar biz Fibonachchi raqamlari bilan misol olsak, bu ba'zi qiymatlarni echish jarayonida xotirada saqlash osonroq bo'ladi va har safar qayta hisoblanmaydi. Va bu shunchaki xotira bo'ladi. N + 1 uchun muammoning yechimini N uchun yechimdan olish mumkin bo'lgan misollarda, echimni olish paytida o'zgaruvchilarning holati (indekslar, ko'rsatkichlar) xotirada saqlanishi kerak bo'ladi. N.Oddiy misol qatorni Fibonachchi raqamlari bilan tsikl orqali to'ldirishdir.(arr [i] = arr [[i-1] + arr [i-2]. arr [i] ni hisoblash vaqtida bizda arr [i-1] va arr [i-2] uchun to'g'ri echimlar mavjud edi. ].) Bir o'lchovli muammo uchun u quyidagicha ko'rinishi mumkin: 2-rasm Bir o'lchovli massivning saqlangan holatini tasvirlash Dinamik dasturlash asosan oddiy rekursiya bilan solishtirganda optimallashtirishdir. Asosiy g'oya - asl savolni takrorlanadigan naqshlarga bo'lish va keyin natijalarni ko'p sub-javoblarni saqlash . Shuning uchun, kerak bo'lganda , biz bosqichdan oldingi javoblarni keyinroq qayta hisoblashimiz shart emas . Katta O nuqtai nazaridan, ushbu optimallashtirish usuli odatda vaqt murakkabligini eksponensialdan polinomga qisqartiradi. 1. Rekursiya ham, dinamik dasturlash ham boshlang'ichni ishga tushiradigan asosiy holatdan boshlanadi. 12 2. Asosiy holatni yozganimizdan so'ng, muammoning mantiqiy oqimidan keyin har qanday naqshlarni topishga harakat qilamiz. Uni topganimizdan so'ng, biz asosan tugatdik. 3. Asosiy farq shundaki, rekursiya uchun biz hech qanday oraliq qiymatlarni saqlamaymiz , dinamik dasturlash esa undan foydalanadi. Fibonachchi raqami python dasturlash tilida ko’rib chiqaylik 3-rasm. Fibonachchi sonlarining dynamik dasturlashdagi rekursiv algoritmi Rekursiya uchun vaqt murakkabligi O(2 n ) bo'ladi, chunki har bir tugun ikkita kichik tarmoqqa bo'linadi va fazoning murakkabligi O (N) bo'ladi, chunki daraxtning chuqurligi n o'lchamiga mutanosib bo'ladi.Dinamik dasturlash uchun vaqt murakkabligi O(n) bo'ladi, chunki biz uni faqat bir marta aylantiramiz. Dinamik dasturlash protsedurasi diagrammasida ko'rib turganingizdek, u chiziqli.va kosmik murakkablik O(N) bo'ladi, chunki biz barcha 13 oraliq qiymatlarni dp_listimizga saqlashimiz kerak. Shunday qilib, bizga kerak bo'lgan joy n berilgan bilan bir xil. Dinamik dasturlash yondashuvi Rekursiya kodi class Solution(object): def fib(self, n): #int parameter sifatida qabul qiladi va int qaytarishi kerak ""“ :type n: int :rtype: int ""“ if n == 0: return(0) if n == 1: return(1) dp = [0] * (n + 1) dp[0] = 0 dp[1] = 1 print("oldindan yaratilgan dinamik massiv= ", dp) for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print("to’ldrilgandan keyin dinamk massiv yaratiladi= ", dp) return(dp[n]) 14 Rekursiya bilan alohida dinamik dasturlashning asosiy farqidir.   Rekursiyada biz dinamik dasturlashda oraliq natijalarni saqlamaymiz, biz barcha oraliq bosqichlarni saqlaymiz.F[4] ni hisoblash uchun biz avval F[2], F[3] ni hisoblab chiqamiz va   ularning qiymatin i   oldindan tuzilgan   DP ro'yxatiga joylashtiramiz . 15 Dinamik ma’lumotlar tuzilmasi Statik ma’lumotlar tuzilmasi vaqt o’tishi bilan o’z o’lchamini o’zgartirmaydi. Biz har doim dastur kodidagi statik ma’lumotlar tuzilmasiga qarab ularning olchamini bilishimiz mumkin. Bunday ma’lumotlarga teskari ravishda dinamik ma’lumotlar tuzilmasi mavjud bo’lib, bunda dastur bajarilishi davomida dinamik ma’lumotlar tuzilmasi o’lchamini o’zgartirishi mumkin. Dinamik ma’lumotlar tuzilmasi – bu qandaydir bir qonuniyatga asoslanib shakllangan, lekin elementlari soni, o’zaro joylashuvi va o’zaro aloqasi dastur bajarilishi davomida shu qonuniyat asosida dinamik o’zgaruvchan bo’lgan ma’lumotlar tuzilmasidir.Malumotlar tuzilmasi dasturlarda ma’lumotlar ajratish usuli bo’yicha staticdinamikaga bo’linadi.Statik ma’lumotlar tuzilmasi-bu kompyuterning xotirasida joylashishi va elementlarning o’zaro aloqalari ular tomondan amalga oshiriladigan soha dasturini bajarish paytida o’zgarishsiz qoladigan ma’lumotlardir.Statik strukturaning ma’lumotlariga dasturda elon qilingan asosiyva mahalliy hamda global darajadagi o’zgaruvchilar kiradi.Dinamik ma’lumotlar tuzilmasi-bu kompyuterning xotirasiga joylashtrilishi va NEW va DELETE kabi tizm protseduralari yordamida dasturni bajarishda xotiradan o’chirilishi mumkinbo’lgan ma’lumotlar. Dinamik ma’lumotlar tuzilmasi o’zichiga malumotlar strukturasini hosil qilishda kerak bo’ladigan barcha tuzilma va texnologiyalarni qamrab oladi. Bularga C++ dasturlash tilidagi STL(Standart template library),classlar,structuralar Emun xizmachi so’zi bilan hosil qilingan malumot tuzilmalari,union( birlashmalar) Ko’rsatkichlar va boshqalarni o’z ichiga oladi. Dinamik ma’lumotlar tuzilmasi quyidagicha klassifikatsiyalanadi.(3.1-rasm) 16 Dasturlarda dinamik ma’lumotlar tuzilmasidan kopincha chiziqli royhatlar, steklar, navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning bog’lanish usuli va ular ustida bajarilishi mumkin bo’lgan amallari bilan farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ xotirada ketma-ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2 ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo’layotgan informatsion maydon va elementlarning o’zaro aloqasini ta’minlovchi ko‘rsatkichli maydon. Chiziqli ro’yhatlarda har bir element o’zidan keyingisi yoki oldingisi bilan ham bog’langan bo’lishi mumkin. Birinchi holatda, ya’ni elementlar o’zidan 17 keyingi element bilan bog’langan bo’lsa, bunday ro’yhatga bir bog‘lamli ro‘yhat deyiladi. Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan bog’langan bo’lsa, u holda bunday ro’yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi. Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday ro’yhatga halqasimon ro‘yhat deyiladi. Ro’yhatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo’ladi. Kalit odatda butun son yoki satr ko’rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo’ladi. Ro’yhatlar ustida quyidagi amallarni bajarish mumkin. - ro’yhatni shakllantirish (birinchi elementini yaratish); - ro’yhat oxiriga yangi element qo’shish; - berilgan kalitga mos elementni o’qish; - ro’yhatning ko’rsatilgan joyiga element qo’shish (berilgan kalitga mos elementdan oldin yoki keyin) - berilgan kalitga mos elementni o’chirish; - kalit bo’yicha ro’yhat elementlarini tartibga keltirish. Ro’yhatlar bilan ishlashda dasturda boshlang’ich elementni ko’rsatuvchi ko’rsatkich talab etiladi. Chiziqli bir bog’lamli ro’yhatlar ustida turli amallar bajarish algoritmlari va dasturlarini ko’rib chiqamiz. Chiziqli bir tomonlama bog’langan ro’yhatlar 3.2-rasm. Chiziqli bir bog’lamli ro’yhatlar Bir bog’lamli ro’yhat deb elementlarning shunday tartiblangan ketma- ketligiga aytiladiki, har bir element 2 ta maydonga: informatsion maydon info va ko’rsatkich maydoni ptr ga ega bo’ladi (3.2-rasm). Mazkur ko’rinishdagi ro’yhat elementi ko’rsatkichining o’ziga xosligi shundan iboratki, u faqatgina ro’yhatning 18 navbatdagi (o’zidan keyin keluvchi) elementi adresini ko’rsatadi. Bir tomonlama yo’naltirilgan ro’yhatda eng so’ngi element ko’rsatkichi bo’sh, ya’ni NULL bo’ladi. Lst – ro’yhat boshi ko’rsatkichi. U ro’yhatni yagona bir butun sifatida ifodalaydi. Ba’zan ro’yhat bo’sh bo’lishi ham mumkin, ya’ni ro’yhatda bitta ham element bo’lmasligi mumkin. Bu holda lst = NULL bo’ladi. Hozir chiziqli bir bog’lamli ro’yhat hosil qilish dasturini ko’rib chiqsak. Buning uchun biz foydalanuvchi tomonidan yaratiladigan nostandart toifa yaratib olishimiz kerak. Buning bir qancha usullari mavjud, ya’ni klasslar yoki strukturalar bilan amalga oshirish mumkin. Masalan: class Node{ public://klass ma’lumotlariga tashqaridan bo‘ladigan murojaatga ruxsat berish int info; // informatsion maydon Node* next;// ko‘rsatkichli maydon }; Bu yerda biz Node nomli toifa yaratdik va ro’yhatimiz butun sonlardan iborat. Endi ro’yhat elementlarini shu toifa orqali e’lon qilsak bo’ladi, ya’ni Node *lst = NULL;// ro‘yhat boshi ko‘rsatkichi Node *last = NULL;// ro‘yhatga oxirgi kelib tushgan elementning ko‘rsatkichi Endi shu belgilashlar orqali ro„yhat hosil qilamiz. Node * p = new Node; int numb = -1; cout<<"son kiriting: "; cin>>numb p->info = numb; p->next = NULL; 19 if (lst == NULL) { lst = p; last = p; } else{ last->next = p; last = p; } Bu dasturda yangi element ro’yhat oxiridan kelib qo’shiladi. Bir bog’lamli ro’yhatlar ustida amallar bajarish algoritmlari 1. Bir bog’lamli ro’yhat boshiga element qo’yish 3.3-rasm. Bir bog’lamli chiziqli ro’yhat tuzilishi 3.3-rasmdagi ro’yhat boshiga informatsion maydoni D o’zgaruvchi bolgan element qo’yamiz. Ushbu ishni amalga oshirish uchun quyidagi amallarni bajarish lozim bo’ladi: a) p ko’rsatkich murojaat qiladigan, bo’sh element yaratish (3.4-rasm). b) Yaratilgan element informatsion maydoniga D o’zgaruvchi qiymatini o’zlashtirish (3.5-rasm) 20 c) Yangi elementni ro’yhat bilan bog’lash: p->ptr=lst; (shu holatda yangi element va lst – ro’yhat boshini ko’rsatyapti) d) lst ko’rsatkichni ro’yhat boshiga ko’chirish (3.6-rasm). lst=p; Va nihoyat: Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqamiz. Node * p = new Node; int numb = -1; cout<<"son kiriting: "; cin>>numb; p->info = numb; if (lst ==NULL){ p->next = NULL; lst = p; } else{ p->next = lst; lst = p; } 2. Bir bog’lamli ro’yhat boshidan elementni o’chirish Ro’yhatda birinchi element info informatsion maydonidagi ma’lumotni esda saqlab qolib uni ro’yhatdan o’chiramiz (3.7-rasm) 21 Yuqorida aytilganlarni amalga oshirish uchun quyidagi ishlarni bajarish lozim: a) o’chirilayotgan elementni ko’rsatuvchi p ko’rsatkich kiritish: p=lst; b) p ko’rsatkich ko’rsatayotgan element info maydonini qandaydir x o’zgaruvchida saqlash: x=p->info; c) lst ko’rsatkichni yangi ro’yhat boshiga ko„chirish: lst=p->ptr; d) p ko’rsatkich ko’rsatayotgan elementni o’chirish: delete(p); Natijada 3.8-rasmdagi ko’rinishga ega bo’lamiz. Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqsak. Node* p = new Node; if (lst == NULL){ cout<<"ro'yhat bo'sh"; system("pause"); system("CLS"); } else { p = lst; lst = p->next ; delete(p); } 22 3. Elementni ro’yhatga qo’shish Berilgan ro’yhatda p ko’rsatkich ko’rsatayotgan elementdan keyin informatsion maydoni x bo’lgan elementni qo’yamiz (3.9-rasm). Aytilganlarni amalga oshirish uchun quyidagi amallarni bajarish lozim: a) q ko’rsatkich ko’rsatuvchi bo’sh elementni yaratish: Node *q=new Node; b) Yaratilgan element informatsion maydoniga x ni kiritish: q->info=x; c) q elementni p elementdan keyingi element bilan bog’lash. q->ptr=p->ptr – yaratilgan element ko’rsatkichiga p element ko’rsatkichini o’zlashtirish. d) p element bilan q elementni bog„lash. p->ptr=q – bu amal p elementdan keyingi element q ko’rsatkich murojaat qilgan element bo’lishini anglatadi. Natijada quyidagi rasmdagidek ko’rinishga ega bo’lamiz. Endi shu algoritmni C++ tilidagi realizatsiyasini ko’rib chiqsak. Node * p = lst; Node * q = new Node; 23 int numb = -1; cout<<"son kiriting: "; cin>>numb; q->number = numb; int k; cout<<"nechta elementdan keyin kiritasiz k=";cin>>k; for(int i=0;i<k-1;i++) p=p->next; q->next=p->next; p->next=q; 4. Bir bog’lamli ro’yhatdan elementni o’chirish Ro’yhatda p ko’rsatkich ko’rsatayotgan elementdan keyingi elementni o’chiramiz (3.11-rasm). Buni bajarish uchun quyidagi ishlarni amalga oshirish lozim: a) O’chirilayotgan elementni ko’rsatuvchi q ko’rsatkichni kiritish. q=p->ptr; b) p elementni q elementdan keyingi element bilan bog’lash. p->ptr=q->ptr; c) O’chirilayotgan element info maydonidagi informatsiyani yodda saqlash (agar zarur bo’lsa) k=q->info; d) q ko’rsatkich ko’rsatayotgan elementni o’chirish. delete(q) Natijada ro’yhat quyidagi ko’rinishga ega bo’ladi: 24 Shu algoritm dasturi Node* p = lst; Node* q = new Node; int k; cout<<"k=";cin>>k; for(int i=0;i<k-1;i++) p=p->next;q = p->next; p->next = q->next; delete(q); Dastur quyidagicha ishlaydi 1. Ekranga menyu chiqaramiz: 1 - element qo’shish; 2 - ro’yhatni ko’rish; 3 - ro’yhat maksimalini topish; 0 - chiqish; tanlash uchun tanla o’zgaruvchisiga qiymat so’raymiz. 2-qadamga o’tish. 2. Agar tanlang=1 bo’lsa, 3-qadamga, 2 ga teng bo’lsa, 4-qadamga, 3 tanlansa, 6-qadamga o’tish, 0 tanlansa dasturni yakunlash. 3. Navbatdagi elementni yaratish p; (p ning info maydoniga qiymat so’rab olib yozishh va ptr maydoniga NULL yozishh) Agar ro’yhat boshi 25 ko’rsatkichi lst=NULL bo lsa, lst=p va last=p; aks holda last – ro’yhat ‟ oxirgi elementi ptr maydoniga p ni yozib, p elementni last qilib belgilaymiz. 1-qadamga o’tamiz. Agar lst NULL ga teng bo’lsa, ro’yhat bo’shligini ekranga chiqarib, 1-qadamga o’tish. Aks holda, p=lst va 5-qadamga o’tish. Agar p ning ptr maydoni NULL bo’lmasa, p ning info maydonini ekranga chiqaramiz va keyingi elementga o’tamiz, ya’ni p=p->ptr, 5-qadamga o’tamiz, aks holda, 1-qadamga o’tamiz. 5. max=lst->info, ya’ni max o zgaruvchisiga ro’yhat 1-elementi info maydoni ‟ qiymatini o’zlashtiramiz. p=lst va 7-qadamga o’tish. 6. Agar p NULL ga teng bo’lmasa, 8-qadamga o’tamiz, aks holda max ni ekranga chiqaramiz va 1-qadamga o’tamiz. 8. Agar max< p->info bo’lsa, max=p->info. Keyingi elementga o’tamiz, ya’ni p=p->ptr. 7-qadamga o’tamiz. Dasturning umumiy ko’rinishi #include <iostream> using namespace std; class Node{ public: int number; Node* next; }; int main() { Node* head = NULL; Node* lastPtr = NULL; 26 short action = -1; cout<<" Dinamik ro'yhat ustida bajariladigan amallar"<<endl; while (1) { cout<<"1. ruyhatga element qo'shish\n"; cout<<"2. ro'yhatni ko'rish\n"; cout<<"3. royhatdan maksimalini topish\n"; cout<<"0. chiqish\n\n"; cout<<"tanlang: "; cin>>action; if (action == 0) { system("CLS"); break;} if (action == 1) { system("CLS"); Node* ptr = new Node; int numb = -1; cout<<"son kiriting: "; cin>>numb; ptr->number = numb; ptr->next = NULL; if (head == 0) 27 { head = ptr; lastPtr = ptr; system("CLS"); continue; } lastPtr->next = ptr; lastPtr = ptr; system("CLS"); continue; } if (action == 2){ Node* ptr = NULL; system("CLS"); if (head == 0) { cout<<"\t!!! ro’yhat bo’sh !!!\n\n"; system("PAUSE"); system("CLS"); continue; } cout<<"* * * * * ruyhat * * * * *\n\n"; ptr = head; while (1) { 28 cout<<ptr->number<<" "; if (ptr->next == 0) break; ptr = ptr->next; } cout<<"\n\n"; system("PAUSE"); system("CLS"); continue; } if (action == 3) { system("CLS"); Node* p = head; Node* q = new Node; Node* last = new Node; int max=p->number; q=head; while(p){ if(max<p->number){ max=p->number;} p=p->next; } system("CLS"); 29 cout<<"max="<<max<<endl; system("pause"); continue; } }} Dastur bosh oynasi 1-menuni 6 marta tanlab qiymatlarni kiritib quyidagi natijalarni olamiz 2.Ro’yhatni ko’rish bo’limi 3.maksimal elementini topish 30 Xulosa Dinamik dasturlash ikkala kontekstda u murakkab muammoni oddiy kichik muammolarga ajratish orqali soddalashtirishga ishora qiladi rekursiv uslubi. Qaror bilan bog'liq ba'zi muammolarni shu tarzda ajratib bo'lmaydigan bo'lsa-da, bir necha vaqtni o'z ichiga olgan qarorlar ko'pincha rekursiv ravishda ajralib chiqadi. Xuddi shu tarzda, informatika fanida, agar muammoni kichik muammolarga ajratib, so'ngra kichik muammolarning optimal echimlarini rekursiv ravishda topish orqali optimal tarzda echimlarni olish mumkin bo’ladi. Agar kichik masalalarni rekursiv ravishda kattaroq masalalar ichiga joylashtirish mumkin bo'lsa, shuning uchun dinamik dasturlash usullari qo'llanilishi mumkin bo'lsa, unda kattaroq masalaning qiymati bilan kichik muammolarning qiymatlari o'rtasida bog'liqlik mavjud. Optimallashtirish bo ' yicha adabiyotda bu munosabatlar muhim o ’ rin tutadi . Dinamik dasturlasning ahamiyati shundan iboratki biz faqat bir xil ma ’ lumotlar bilan emas balki vaqt o ’ tishi bilan yangilanib turadigan ma ’ lumotlar bilan ishlashda kata ahamiyatga egadi . Ushbu kurs ishimda dinamik dasturlashning umumiy tushunchalari , dinamik dasturlashning tamoyillar , dinamik dasturlashning ma ’ lumotlar tuzilmasdagi o ’ rni , C ++ dasturlash tilida dinamik dasturlashning qo ’ llanilishi haqida ma ’ lumotlar keltirganman . Bu kurs ishidan akademik litseylarda,kollejlarda,oliy ta’lim muassasalarida alogritmlar va ma’lumotlar strukturasi fanidan qo’llanma sifatida foydalansa bo’ladi. 31 Foydalanilgan adabiyolar 1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV, “ALGORITMLAR” , «Fan va texnologiya» nashriyoti, 2018. 2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009, 3. Akbaraliyev B.B., Yusupova Z.Dj. , “MA LUMOTLAR TUZILMASI VA ‟ ALGORITMLAR”, Toshkent 2013 4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA KIRISH” fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”, Samarqand 2015, 5. Xayitmatov O’.T., Inogomjonov E.E., Sharipov B.A., Ro’zmetova N., Rahimboboeva D,” MA'LUMOTLAR TUZILMASI VA ALGORITMLARI”, Toshkent – 2011 6. Л.И.Домнин, “ЭЛИМЕНТЫ ТЕОРИИ ГРАФОВ” , “ Пенза Издательство Пензенского государственного университета“ ,2007 7. Никлаус Вирт ,”Алгоритмы и структуры данных Новая версия для Оберона + CD “, Москва, 2010. Foydalanilgan internet saytlar: 1) https://kursovik.com/programming/320372.html 2) http://aliev.me/runestone/Graphs/PrimsSpanningTreeAlgorithm.html 3) http://www.hpcc.unn.ru/?dir=836 4) https://brestprog.by/topics/mst/ 5) wikipedia 6) https://evileg.com/ru/post/524/ 7) http://www.mkurnosov.net/ 8) www.fayllar .org 32 33

“ DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI ” MAVZUSIDA TAYYORLAGAN 1KURS ISHI

Mundarija I Kirish II Asosiy qism ……..………………………………………………..4 2.1. Dinamik dasturlash haqida umumiy tushunchalar……….…......4 2.2.Dinamik dasturlashda optimallik tamoyili……………………....8 2.3. C++ dasaturlash tilida dinamik ma’lumotlar tuzilmasi……..….24 III Xulosa………………………………………………...…………39 IV Foydalanilgan adabiyotlar………………………………….……40 2

3

Kirish Vatanimizda, erkin va farovon hayot barpo etish, rivojlangan mamlakatlar qatoridan o’rin olish, demokratik jamiyat qurish kabi ezgu maqsadlarni qo’yildi. Bu esa kelajagimizni yaqqol tasavvur etish, jamiyatimizning ijtimoiy-ma‘naviy poydevorini mustahkamlash ehtiyojini tug’diradi. Demak, galdagi eng asosiy vazifa: yosh avlodni vatan ravnaqi, yurt tinchligi, xalq farovonligi kabi olijanob tuyg’ular ruhida tarbiyalash, yuksak fazilatlarga ega, ezgu g’oyalar bilan qurollangan komil insonlarni voyaga etkazish, jahon andozalariga mos, kuchli bilimli, raqobatbardosh kadrlar tayyorlashdir. O’zbekistonning iqtisodiy va ijtimoiy sohalarda yuqori natijalarga erishishi, jahon iqtisodiy tizimida to’laqonli sheriklik o’rnini egallay borishi, inson faoliyatining barcha jabhalarida zamonaviy axborot texnologiyalaridan yuqori darajada foydalanishning ko’lamlari qanday bo’lishiga hamda bu texnologiyalar ijtimoiy mehnat samaradorligini oshishida qanday rol o’ynashiga bog’liq. Keyingi yillarda mamlakatimiz ilm-fani ham axborotlashtirishning nazariy asoslariga katta hissa qo’shib kelmoqda, shu bilan birgalikda, hodisalar, jarayonlarni yagona axborot asosida tadqiq etishning ilmiy yo’nalishlarini tahlil va sintez qilish natijasi bo’lgan fan-informatikaning vujudga kelishiga boshlang’ich poydevor qo’yildi. Axborot, energiya, vazn, bo’shliq va vaqtni bir butun holda batafsil o’rganish hozirgi vaqtda inson hayotining barcha jabhalarida muhim axamiyatga ega bo’lib qolmoqda. 4

Dinamik dasturlash haqida umumiy tushunchalar Dinamik dasturlash tushunchasi juda keng qamrovli tushuncha bolib,Bu tushunchao’z ichiga ko’plab yo’nalishlar va sohalarni qamrab oladi. Dasturchilar butunlay boshqacha vazifalarga ega bo'lishi mumkin. Bir holatda, biror narsani chizish uchun faqat belgilash tilidan foydalanishingiz kerak, ikkinchisida protsessor samarali ishlashi uchun assembler orqali ko'rsatmalar yozish kerak.Ammo bu assotsiatsiya barcha odamlar uchun ishlaydi - dasturchilar algoritmlarni ishlab chiqadilar. Tasavvur qilaylik, bizga yangi vazifa qo’yildi, uning maqsadi va cheklovlari bor. Har qanday vazifada bo'lgani kabi, u ham ma'lumotlar tuzilmalarini va tizimning boshqa qismlariga bog'liqlikni o'z ichiga oladi bir vaqtning o'zida siz ushbu vazifa uchun ishlash muhim. Bunidarhol tushunish mumkin. Masalan, avval muammoni hal qilgandan keyin yechim sekin ekanligini payqashimiz mumkin .Bunday holatda hisob-kitob natijalari kamroq vaqt ichida olinishi uchun muammoni qanday hal qilishni kerak.Dasturlash nuqtayi nazaridan dinamik dasturlash atamasi biz yaratayotgan dasturmizga ma’lumotlarni kirtganimizdak keyin vaqt o’tishi bilan avvalgi kiritgan ma’lumotlarimizning bizga keragi bo’lmasligi mumkin.Shunda bizga malumotlarni kiritish va chiqarish jarayonida eski ma’lumotlarni o’chirish kerak bo’ladi. Dinamik dasturga misol C++ dasturlash tilida #include<iostream> using namespace std; int main(){ int m; cout << "m="; cin >> m; //massiv elementlari soni; float *b = new float[m]; //Element haqiqiy sonlar bo'lgan m ta elementli dinamik massiv; 5

O'xshashlar

DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI
Dinamik tizimlar
DINAMIK XOTIRA
Dinamik xotiradan foydalanish, dinamik xotirani ishlatishda ko’rsatkich turlari
DINAMIK XOTIRA 19v